冲刺大厂基础

1.给定一个有序数组，找出（>=value）的最左位置

思路：采用二分法，用一个index变量，每次记录(>=value)的位置，最后返回。

public class Code05_BSNearLeft {    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;    }}

2.给定一个有序数组，找出（<=value）的最右位置

思路：采用二分法，用一个index变量，每次记录(<=value)的位置，最后返回。

public class Code06_BSNearRight {    public static int nearestRight(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;  L = mid + 1;     }else{  R = mid - 1;     } } return index;    }}

3.给定一个数组，其中只有一个数出现奇数次，其他的数都出现偶数次。打印这个出现奇数次的数。

思路：可以采用容器的方法记录每一个数出现的次数，这个不是最优解。

最优解：采用异或方法，（0^N = N）（N ^ N = 0）,并且异或运算满足交换律与分配律

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

4. 求指定数二进制中最右侧的1

思路：无论正数负数，执行N&(-N)即可拿出N最右侧的1，也等同于N&(~N + 1)。

public static int bit1Right(int N){return N & (-N);//return N & (~N + 1);}

5.给定一个数组，其中只有两个不同的数出现奇数次，剩下的数出现偶数次

思路：可以采用容器的方法记录每一个数出现的次数，这个不是最优解。

最优解：首先将数组中的每一个数进行异或操作，结果是这两个出现奇数次的数异或的结果（eor），取出结果的二进制中最右侧的1（onlyOne）。将数组中的数与onlyOne进行&操作，(数组中的元素)&(onlyOne)不等于0的数进行异或操作。onlyOne最后为出现奇数次的两个数中一个，然后（eor）^（onlyOne）得出另一个出现奇数次的数。

public static void printOddTimesNum2(int[] arr){ int eor = 0; for (int num : arr) {     eor ^= num; } int rightOne = eor & (-eor); int onlyOne = 0; for (int num : arr) {     if((num & rightOne) != 0){  onlyOne ^= num;     } } System.out.println(onlyOne + " " + (eor ^ onlyOne));    }

开发者涨薪指南 48位大咖的思考法则、工作方式、逻辑体系唱吧