• today‘s task

    1

    package class01;

    import java.util.Arrays;

    public class Code01_SelectionSort {

    public static void selectionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 0; i < arr.length - 1; i++) {
		int minIndex = i;
		for (int j = i + 1; j < arr.length; j++) {
			minIndex = arr[j] < arr[minIndex] ? j : minIndex;
		}
		swap(arr, i, minIndex);
	}
}

public static void swap(int[] arr, int i, int j) {
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}

// for test
public static void comparator(int[] arr) {
	Arrays.sort(arr);
}

// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
	int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
	for (int i = 0; i < arr.length; i++) {
		arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
	}
	return arr;
}

// for test
public static int[] copyArray(int[] arr) {
	if (arr == null) {
		return null;
	}
	int[] res = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		res[i] = arr[i];
	}
	return res;
}

// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
	if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
		return false;
	}
	if (arr1 == null && arr2 == null) {
		return true;
	}
	if (arr1.length != arr2.length) {
		return false;
	}
	for (int i = 0; i < arr1.length; i++) {
		if (arr1[i] != arr2[i]) {
			return false;
		}
	}
	return true;
}

// for test
public static void printArray(int[] arr) {
	if (arr == null) {
		return;
	}
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}

// for test
public static void main(String[] args) {
	int testTime = 500000;
	int maxSize = 100;
	int maxValue = 100;
	boolean succeed = true;
	for (int i = 0; i < testTime; i++) {
		int[] arr1 = generateRandomArray(maxSize, maxValue);
		int[] arr2 = copyArray(arr1);
		selectionSort(arr1);
		comparator(arr2);
		if (!isEqual(arr1, arr2)) {
			succeed = false;
			printArray(arr1);
			printArray(arr2);
			break;
		}
	}
	System.out.println(succeed ? "Nice!" : "Fucking fucked!");

	int[] arr = generateRandomArray(maxSize, maxValue);
	printArray(arr);
	selectionSort(arr);
	printArray(arr);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100

    }

    2

    package class01;

    import java.util.Arrays;

    public class Code02_BubbleSort {

    public static void bubbleSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int e = arr.length - 1; e > 0; e--) {
		for (int i = 0; i < e; i++) {
			if (arr[i] > arr[i + 1]) {
				swap(arr, i, i + 1);
			}
		}
	}
}

public static void swap(int[] arr, int i, int j) {
	arr[i] = arr[i] ^ arr[j];
	arr[j] = arr[i] ^ arr[j];
	arr[i] = arr[i] ^ arr[j];
}

// for test
public static void comparator(int[] arr) {
	Arrays.sort(arr);
}

// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
	int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
	for (int i = 0; i < arr.length; i++) {
		arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
	}
	return arr;
}

// for test
public static int[] copyArray(int[] arr) {
	if (arr == null) {
		return null;
	}
	int[] res = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		res[i] = arr[i];
	}
	return res;
}

// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
	if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
		return false;
	}
	if (arr1 == null && arr2 == null) {
		return true;
	}
	if (arr1.length != arr2.length) {
		return false;
	}
	for (int i = 0; i < arr1.length; i++) {
		if (arr1[i] != arr2[i]) {
			return false;
		}
	}
	return true;
}

// for test
public static void printArray(int[] arr) {
	if (arr == null) {
		return;
	}
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}

// for test
public static void main(String[] args) {
	int testTime = 500000;
	int maxSize = 100;
	int maxValue = 100;
	boolean succeed = true;
	for (int i = 0; i < testTime; i++) {
		int[] arr1 = generateRandomArray(maxSize, maxValue);
		int[] arr2 = copyArray(arr1);
		bubbleSort(arr1);
		comparator(arr2);
		if (!isEqual(arr1, arr2)) {
			succeed = false;
			break;
		}
	}
	System.out.println(succeed ? "Nice!" : "Fucking fucked!");

	int[] arr = generateRandomArray(maxSize, maxValue);
	printArray(arr);
	bubbleSort(arr);
	printArray(arr);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98

    }

    3

    package class01;

    import java.util.Arrays;

    public class Code03_InsertionSort {

    public static void insertionSort(int[] arr) {
	if (arr == null || arr.length < 2) {
		return;
	}
	for (int i = 1; i < arr.length; i++) {
		for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
			swap(arr, j, j + 1);
		}
	}
}

public static void swap(int[] arr, int i, int j) {
	arr[i] = arr[i] ^ arr[j];
	arr[j] = arr[i] ^ arr[j];
	arr[i] = arr[i] ^ arr[j];
}

// for test
public static void comparator(int[] arr) {
	Arrays.sort(arr);
}

// for test
public static int[] generateRandomArray(int maxSize, int maxValue) {
	int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
	for (int i = 0; i < arr.length; i++) {
		arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
	}
	return arr;
}

// for test
public static int[] copyArray(int[] arr) {
	if (arr == null) {
		return null;
	}
	int[] res = new int[arr.length];
	for (int i = 0; i < arr.length; i++) {
		res[i] = arr[i];
	}
	return res;
}

// for test
public static boolean isEqual(int[] arr1, int[] arr2) {
	if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
		return false;
	}
	if (arr1 == null && arr2 == null) {
		return true;
	}
	if (arr1.length != arr2.length) {
		return false;
	}
	for (int i = 0; i < arr1.length; i++) {
		if (arr1[i] != arr2[i]) {
			return false;
		}
	}
	return true;
}

// for test
public static void printArray(int[] arr) {
	if (arr == null) {
		return;
	}
	for (int i = 0; i < arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}

// for test
public static void main(String[] args) {
	int testTime = 500000;
	int maxSize = 100;
	int maxValue = 100;
	boolean succeed = true;
	for (int i = 0; i < testTime; i++) {
		int[] arr1 = generateRandomArray(maxSize, maxValue);
		int[] arr2 = copyArray(arr1);
		insertionSort(arr1);
		comparator(arr2);
		if (!isEqual(arr1, arr2)) {
			succeed = false;
			break;
		}
	}
	System.out.println(succeed ? "Nice!" : "Fucking fucked!");

	int[] arr = generateRandomArray(maxSize, maxValue);
	printArray(arr);
	insertionSort(arr);
	printArray(arr);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96

    }

    4

    package class01;

    public class Code04_BSExist {

    public static boolean exist(int[] sortedArr, int num) {
	if (sortedArr == null || sortedArr.length == 0) {
		return false;
	}
	int L = 0;
	int R = sortedArr.length - 1;
	int mid = 0;
	while (L < R) {
		mid = L + ((R - L) >> 1);
		if (sortedArr[mid] == num) {
			return true;
		} else if (sortedArr[mid] > num) {
			R = mid - 1;
		} else {
			L = mid + 1;
		}
	}
	return sortedArr[L] == num;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    }

    5

    package class01;

    public class Code05_BSNearLeft {

    // 在arr上，找满足>=value的最左位置
public static int nearestIndex(int[] arr, int value) {
	int L = 0;
	int R = arr.length - 1;
	int index = -1;
	while (L < R) {
		int mid = L + ((R - L) >> 1);
		if (arr[mid] >= value) {
			index = mid;
			R = mid - 1;
		} else {
			L = mid + 1;
		}
	}
	return index;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    }

    6

    package class01;

    public class Code06_BSAwesome {

    public static void main(String[] args) {
	// TODO Auto-generated method stub

}

    • 1
    • 2
    • 3
    • 4

    }

    7

    package class01;

    public class Code07_EvenTimesOddTimes {

    public static void printOddTimesNum1(int[] arr) {
	int eO = 0;
	for (int cur : arr) {
		eO ^= cur;
	}
	System.out.println(eO);
}

public static void printOddTimesNum2(int[] arr) {
	int eO = 0, eOhasOne = 0;
	for (int curNum : arr) {
		eO ^= curNum;
	}
	int rightOne = eO & (~eO + 1);
	for (int cur : arr) {
		if ((cur & rightOne) != 0) {
			eOhasOne ^= cur;
		}
	}
	System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
}

public static void main(String[] args) {
	int a = 5;
	int b = 7;

	a = a ^ b;
	b = a ^ b;
	a = a ^ b;

	System.out.println(a);
	System.out.println(b);

	int[] arr1 = { 3, 3, 2, 3, 1, 1, 1, 3, 1, 1, 1 };
	printOddTimesNum1(arr1);

	int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
	printOddTimesNum2(arr2);

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    }

    8

    package class01;

    public class Code08_GetMax {

    public static int getMax(int[] arr) {
	return process(arr, 0, arr.length - 1);
}

public static int process(int[] arr, int L, int R) {
	if (L == R) {
		return arr[L];
	}
	int mid = L + ((R - L) >> 1);
	int leftMax = process(arr, L, mid);
	int rightMax = process(arr, mid + 1, R);
	return Math.max(leftMax, rightMax);
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    }

    9

    package class01;

    public class Code09_FindOneLessValueIndex {

    public static int getLessIndex(int[] arr) {
	if (arr == null || arr.length == 0) {
		return -1; // no exist
	}
	if (arr.length == 1 || arr[0] < arr[1]) {
		return 0;
	}
	if (arr[arr.length - 1] < arr[arr.length - 2]) {
		return arr.length - 1;
	}
	int left = 1;
	int right = arr.length - 2;
	int mid = 0;
	while (left < right) {
		mid = (left + right) / 2;
		if (arr[mid] > arr[mid - 1]) {
			right = mid - 1;
		} else if (arr[mid] > arr[mid + 1]) {
			left = mid + 1;
		} else {
			return mid;
		}
	}
	return left;
}

public static void printArray(int[] arr) {
	for (int i = 0; i != arr.length; i++) {
		System.out.print(arr[i] + " ");
	}
	System.out.println();
}

public static void main(String[] args) {
	int[] arr = { 6, 5, 3, 4, 6, 7, 8 };
	printArray(arr);
	int index = getLessIndex(arr);
	System.out.println("index: " + index + ", value: " + arr[index]);

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40

    }

  • 相关阅读:
    华为OD机试真题-分积木-2023年OD统一考试（B卷）
    c#中字段和属性的区别，委托和事件的区别
    ModelSim相关实用设置
    bp神经网络遗传算法举例,bp神经网络 遗传算法
    ComplexHeatmap | 你的热图注释还挤在一起看不清吗！？
    【Java基础】变量、标识符及类型转换
    JavaScript基础
    CP-CNN 实验
    termux安装docker
    吃透Java线程安全问题
  • 原文地址：https://blog.csdn.net/ycfxxr/article/details/126114477