当前位置：网站首页>today‘s task
today‘s task
2022-08-02 21:50:00 【漫漫行程路】
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);
}
}
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);
}
}
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);
}
}
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;
}
}
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;
}
}
6
package class01;
public class Code06_BSAwesome {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
}
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);
}
}
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);
}
}
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]);
}
}
边栏推荐
- 源码构建LAMP环境-3
- 面试官居然问我：删库后，除了跑路还能干什么？
- I interviewed a 985 graduate, and I will never forget the expression when answering the "performance tuning" question
- 快速学会ansible的安装
- How to seize the new trend of NFT, yuan|universe|universe?
- H5网页播放器EasyPlayer.js播放器界面的加载效果无法消失是什么原因？
- Summary of @Transactional transaction invocation and effective scenarios
- win10安全中心设置不扫描某个文件夹的方法
- 如何通过 IDEA 数据库管理工具连接 TDengine？
- ＃ 医院管理系统完整项目代码以及数据库建表语句分享
猜你喜欢
了解 NFT 质押：Web3 中赚取被动收益的另一种方式
I interviewed a 985 graduate, and I will never forget the expression when answering the "performance tuning" question
![[TypeScript] Deep Learning of TypeScript Classes (Part 1)](/img/47/34954f1e01b844816d74f3ac556f9b.png)
[TypeScript] Deep Learning of TypeScript Classes (Part 1)
总数据量超万亿行，玉溪卷烟厂通过正确选择时序数据库轻松应对
Jmeter二次开发实现rsa加密
word操作：单独调整英文字体
「X」to「Earn」：赛道现状与破局思路
matplotlib绘图的核心原理讲解(超详细)
抽象工厂模式
Shunted Self-Attention via Multi-Scale Token Aggregation
随机推荐
The only way to go from a monthly salary of 10k to 30k: automated testing
软件测试到底自学还是报班？
Software testing pen questions 1 (with answers)
kubernetes pod podsecurityPolicies（PSP）
Zabbix 5.0 Monitoring Tutorial (2)
搭建直播平台，使用node生成验证码图片，并进行验证
双轴晶体中锥形折射的建模与应用
命令行启动常见问题及解决方案
如何通过开源数据库管理工具 DBeaver 连接 TDengine
创建型模式 - 抽象工厂模式AbstractFactory
Ansible安装与配置
You and I will meet the needs of: how to export the data in a MySQL simple ~!Practical!
谷粒商城-day13-es和商品上架
圆锥折射作为偏振计量工具的模拟
How does Redis easily achieve system instant kill?
MDL 内存描述符链表
SSM integration steps (emphasis)
js函数防抖和函数节流及其他使用场景
博客主题美化第二弹
How many ways do you know the singleton pattern?