leetcode刷题前置知识总结，2021年Java开发进阶

leetcode刷题前置知识总结，2021年Java开发进阶

public class Code04_BSExist {

public static void main(String[] args) {

int[] arr = {1, 2, 4, 6, 10, 20, 21, 33, 43, 54};

System.out.println(exist(arr, 55));

}

public static boolean exist(int[] arr, int num) {

if (arr == null || arr.length == 0) {

return false;

}

int l = 0;

int r = arr.length - 1;

int mid = 0;

while (l < r) {

mid = l + ((r - l) >> 1);

if (arr[mid] == num) {

return true;

} else if (arr[mid] > num) {

r = mid - 1;

} else {

l = mid + 1;

}

}

return arr[l] == num;

}

}

知识扩展：

2*n         可以表示为     n<<1

2*n + 1   可以表示为    (n<<1) | 1

在一个有序数组中，找>=某个数最左侧的位置

package com.zy.class001;

public class Code05_BSNearLeft {

public static void main(String[] args) {

int[] arr = {1, 2, 2, 3, 3, 3, 3, 3, 4 ,4 ,4};

System.out.println(nearestIndex(arr, 3));

}

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;

}

}

局部最小值：

package com.zy.class001;

public class Code06_BSAwesome {

public static int getLessIndex(int[] arr) {

if (arr == null || arr.length == 0) {

return -1;

}

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;

while (left < right) {

int 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;

}

}

认识异或运算

======

相同为0   不同为1

异或运算的性质：

1)0^N == N    N^N == 0

2)异或运算满足交换律和结合律

题目一：如何不用额外变量交换两个数

---

a = a ^ b;

b = a ^ b;

a = a ^ b;

解释：

首先a = a ^ b;

然后b = a ^ b = a ^ b ^ b = a;

最后a = a ^ b = a ^ b ^ a = b;

结果就是b = a; a = b;

package com.zy.class001;

public class Test {

public static void mai

《一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》

【docs.qq.com/doc/DSmxTbFJ1cmN1R2dB】 完整内容开源分享

n(String[] args) {

int a = 6;

int b = -1000;

a = a ^ b;

b = a ^ b;

a = a ^ b;

System.out.println(a);

System.out.println(b);

}

}

这样搞的前提：a和b指向的内存地址不是同一块区域，不然就是0了

题目二

---

一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数。

package com.zy.class001;

public class Code07_EvenTimesOddTimes {

public static void main(String[] args) {

int[] arr = {1, 2, 3, 2, 3, 1, 4};

printOddTimesNum1(arr);

}

// arr中，只有一种数，出现奇数次

public static void printOddTimesNum1(int[] arr) {

int eor = 0;

for (int i = 0; i < arr.length; i++) {

eor ^= arr[i];

}

System.out.println(eor);

}

}

题目三：

---

怎么把一个int类型的数，提取出最右侧的1来

例如：11001100-》00000100

答案:N & ((~N) + 1)

题目四：

====

一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数？