位运算

^运算符理解

• ^ 可理解为不进位相加
• a^a=0
• a^0=a

public static void sway(int[] arr,int i,int j){if(i!=j){//不能两个值指向同一地址arr[i]=arr[i]^arr[j];arr[j]=arr[i]^arr[j];//就是arr[i]^arr[j]^arr[j]就表示aarr[i]=arr[i]^arr[j];//表示arr[i]^arr[j]^arr[i]^arr[j]^arr[j]就是b}
}

寻找出现双中的单数

题目：一组数只有一个数出现一次，其他出现两次，找出这个出现一次的数

public class Main {private static int process(int[] arr) {int res = 0;for (int i : arr) {res ^= i;}return res;}
}

取出一个数最右边1的位置

int mostRightOne = pos & (~pos + 1); 
// mostRightOne值在二进制位上的位次就是pos得最右第一个1的位置

找所有双出现中的两个单数

题目：一组数只有两个数出现一次，其他出现两次，找出这两个数：

• 因为两个值不同，所以两个值定存在二进制某一位定不同，用这两个值的异或结果二进制中的1，从而将数字分成两组，该位为1和不为1

public class Main {private static void process(int[] arr) {int med = 0;for (int a : arr) {med ^= a;// 两个不同的单数^最后得到med}int rightOne = med & (~med + 1);// 取出med中二进制为1的位值（必存在，因为不同值）int med1 = 0;for (int a : arr) {// 对应位为1的值取出进行^最后的到两个单数对应位为1的// (a&rightOne)== 0得到对应位为0if ((a & rightOne) == rightOne) {med1 ^= a;}}System.out.println(med1);// 两个单数其中一个值System.out.println(med ^ med1);// 两个单数令一个值}
}

整数二进制奇数位偶数位交换

题目 : 例如：010110—>101001

public class Main {private static int process(int pos) {int pre = 0xAAAAAAAA; // 1010 1010 1010 1010 1010 1010 1010 1010 int post = 0x55555555; // 0101 0101 0101 0101 0101 0101 0101 0101 pre &= pos;post &= pos;pre >>= 1;post <<= 1;return pos + post;}
}

数组中全部出现k次返回出现一次的数

题目：给定一个整数数组，只有一个数出现了一次，其他数字均出现了三次，输出这一个只出现一次的数。

• 只看出现三次到数字，那么对于这些值的二进制位的累加和定能被3整除。
• 现在出现了一个只出现一次的数，由于该数的存在，所有二进制位累加和除以3的余数就是该值的对应二进制位数。
• 除了3，主要是大于等于2都可以这样做。

public class Main {public static int twoSingleNum(int[] arr) {int[] bit = new int[32];// 每一位求和for (int a : arr) {int b = 1;for (int i = 31; i >= 0; --i) {if ((a & b) != 0) {// 为1就累加++bit[i];}b <<= 1;// 换位}}int res = 0;for (int i = 0; i < 32; ++i) {res = res << 1;res += (bit[i] % 3);// 取余数}return res;}
}

链表

判读链表元素是否回文

利用栈结构

• 先遍历后全部入栈，然后再遍历和栈中元素依次比较。

public class Main {public static boolean process(Node header) {if (header == null) {return false;}Stack<Node> stack = new Stack<>();Node tail = header;while (tail != null) {stack.push(tail);tail = tail.next;}tail = header;while (tail != null) {if (stack.pop().value != tail.value) {return false;}}return true;}public static class Node {int value;Node next;}
}

利用栈结构和快慢指针

• 先用快慢指针定位中间位置，然后继续运动慢指针依次和栈中元素进行比较。需要注意链表整体的个数是双是单。

public class Main {public static boolean process(Node header) {if (header == null) {return false;}Node slow = header;Node quick = header;Stack<Node> stack = new Stack<>();while (quick.next != null && quick.next.next != null) {stack.push(slow);slow = slow.next;quick = quick.next.next;}// 此时若整个链表为双数，slow指向上一半的最后一个，需要入栈slow// 若为单数，指向中间元素，不需要入栈slow// 单双数的判断由quick的终止条件确定if (quick.next!=null) {stack.push(slow);}slow = slow.next;while (!stack.isEmpty()) {if (slow.value != stack.pop().value) {return false;}}return true;}public static class Node {int value;Node next;}
}

快慢指针和链表反向

public class Main {public static boolean process(Node header) {if (header == null) {return false;}Node slow = header;Node quick = header;while (quick.next != null && quick.next.next != null) {slow = slow.next;quick = quick.next.next;}slow=slow.next;Node preNode=null;Node postNode=null;// 后半段反转while (slow!=null) {preNode=slow.next;slow.next=postNode;postNode=slow;slow=preNode;}Node tailLeft=header;Node tailRight=postNode;boolean flag=true;// 两边向中间判断while (tailRight!=null) {if (tailLeft.value!=tailRight.value) {flag=false;break;}tailLeft=tailLeft.next;tailRight=tailRight.next;}Node tailNode=null;// 后半段链表恢复while (postNode!=null) {preNode=postNode.next;postNode.next=tailNode;tailNode=postNode;postNode=preNode;}return flag;}public static class Node {int value;Node next;}
}

三分链表

给定一个值，将比该值小的节点放左边，大的放右边

• 该题并不是思维上难点，主要是注意边界条件

class SEL{public static Node sEL(Node header,int pivot){Node head_1=null;Node tail_1=null;Node head_2=null;Node tail_2=null;Node head_3=null;Node tail_3=null;Node nextNode=null;while (header!=null){nextNode=header.next;header.next=null;if (header.num<pivot){if (head_1==null){head_1=header;tail_1=header;}else { tail_1.next=header;tail_1=tail_1.next;}}else if (header.num==pivot){if (head_2==null){head_2=header;tail_2=header;}else {tail_2.next=header;tail_2=tail_2.next;}}else {if (head_3==null){head_3=header;tail_3=header;}else {tail_3.next=header;tail_3=tail_3.next;}}header=nextNode;}if (tail_1==null){if (tail_2==null){return head_3;}else {tail_2.next=head_3;return head_2;}}else {if (tail_2==null){tail_1.next=head_3;}else {tail_1.next=head_2;tail_2.next=head_3;}return head_1;}}public static class Node {int value;Node next;}
}

链表环问题

判断链表是否有环，若有返回第一个入环节点
慢:1 快:2
若慢:1快3：
都入环时相差奇数步，且环节点数量为偶数则永不相交

都入环时相差奇数步说明每次差值减少2步，定在第一轮反超，此时差 环节点个数-1，若该值仍为奇数，那么第二轮也反超，故永不相遇

class List{/*有环：1.同环：- 入环节点相同  返回相交节点- 入环节点不同  返回其中一个入环节点2.不同环：- 返回null无环：1.相交：- 返回相交节点2.不相交：- 返回null*/public static Node getIntersectNode(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node loop1 = hasCircle(head1);Node loop2 = hasCircle(head2);if (loop1 == null && loop2 == null) {return noLoop(head1, head2);//无环，判断是否为链式相交或不相交}if (loop1 != null && loop2 != null) {return bothLoop(head1, loop1, head2, loop2);//有环，返回相交节点}return null;//一有环，一无环必定不相交}private static Node hasCircle(Node header){if (header==null)return null;boolean flag=false;Node slow=header;Node quick=header;while (quick.next!=null&&quick.next.next!=null){slow=slow.next;quick=quick.next.next;if (slow==quick){//判断是否却有环flag=true;break;}}if (!flag)return null;quick=header;while (quick!=slow){//相遇时将其中一个指针指向header走相同的步数定在入环节点相遇quick=quick.next;slow=slow.next;}return quick;}private static Node noLoop(Node head1, Node head2) {if (head1 == null || head2 == null) {return null;}Node cur1 = head1;Node cur2 = head2;int n = 0;//计算链表差值while (cur1.next != null) {n++;cur1 = cur1.next;}while (cur2.next != null) {n--;cur2 = cur2.next;}if (cur1 != cur2) {return null;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);//长的走到和短的长度同位置while (n != 0) {n--;cur1 = cur1.next;}//判断是否有相同节点，若无就会走到最后返回nullwhile (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;}private static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {Node cur1 = null;Node cur2 = null;if (loop1 == loop2) {cur1 = head1;cur2 = head2;int n = 0;while (cur1 != loop1) {n++;cur1 = cur1.next;}while (cur2 != loop2) {n--;cur2 = cur2.next;}cur1 = n > 0 ? head1 : head2;cur2 = cur1 == head1 ? head2 : head1;n = Math.abs(n);while (n != 0) {n--;cur1 = cur1.next;}while (cur1 != cur2) {cur1 = cur1.next;cur2 = cur2.next;}return cur1;} else {cur1 = loop1.next;while (cur1 != loop1) {if (cur1 == loop2) {return loop1;//环内相交}cur1 = cur1.next;}return null;//两个有环链表环不是同一个}}public class Node{int value;Node next;}
}

分治策略

数组中的逆序对

题目：数组中的两个数，若前面的一个数大于后面的一个数，那么这两个数组成一个逆序对。输入一个数组，返回逆序对的个数。

• 归并排序过程，和求小数和相似。
• 关于为什么归并排序过程中能实现单方向的大小判断？实际上是因为归并排序在排序过程中保持了数据的局部有序性，当合并时，在两个子数组整体之间存在相对位置关系。这也是为什么只有在合并的时候才能进行单方向上的大小判断。

public class Main {public static int process(int[] arr) {if (arr == null || arr.length == 0) {return 0;}return divideTest(arr, 0, arr.length - 1, new int[arr.length]);}private static int divideTest(int[] arr, int left, int right, int[] temp) {if (left < right) {int m = (left + right) / 2;return divideTest(arr, left, m, temp) // 左侧的总和+ divideTest(arr, m + 1, right, temp)// 右侧的总和+ mergeTest(arr, left, m, right, temp);// 左侧右侧组合过程中形成总和}return 0;}private static int mergeTest(int[] arr, int left, int m, int right, int[] temp) {int i = left;int j = m + 1;int tempIndex = 0;int res = 0;while (i <= m && j <= right) {// 和小数和就相差在大于小于符号和这里没有乘以arr[i]res += arr[i] > arr[j] ? (right - j + 1) : 0;temp[tempIndex++] = arr[i] < arr[j] ? arr[i++] : arr[j++];}while (i <= m)temp[tempIndex++] = arr[i++];while (j <= right)temp[tempIndex++] = arr[j++];System.arraycopy(temp, 0, arr, left, tempIndex);return res;}
}

基于归并排序的小数和🔐

题目：小和问题和逆序对问题 小和问题 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组 的小和。求一个数组 的小和。 例子:[1,3,4,2,5] 1左边比1小的数，没有; 3左边比3小的数，1; 4左 边比4小的数，1、3; 2左边比2小的数，1; 5左边比5小的数，1、3、4、 2; 所以小和为1+1+3+1+1+3+4+2=16

public class Main {public static int process(int[] arr) {if (arr == null || arr.length == 0) {return 0;}return divideTest(arr, 0, arr.length - 1, new int[arr.length]);}private static int divideTest(int[] arr, int left, int right, int[] temp) {if (left < right) {int m = (left + right) / 2;return divideTest(arr, left, m, temp) // 左侧小数和的总和+ divideTest(arr, m + 1, right, temp)// 右侧小数和的总和+ mergeTest(arr, left, m, right, temp);// 左侧右侧组合过程中形成的小数和总和}return 0;}private static int mergeTest(int[] arr, int left, int m, int right, int[] temp) {int i = left;int j = m + 1;int tempIndex = 0;int res = 0;while (i <= m && j <= right) {// 若左小，就是会出现小数的位置。个数由右侧确定。res += arr[i] < arr[j] ? arr[i] * (right - j + 1) : 0;temp[tempIndex++] = arr[i] < arr[j] ? arr[i++] : arr[j++];}while (i <= m)temp[tempIndex++] = arr[i++];while (j <= right)temp[tempIndex++] = arr[j++];System.arraycopy(temp, 0, arr, left, tempIndex);return res;}
}

查找

深度探索二分查找

经典二分查找

查找大于该值的最小值

查找小于该值的最大值

查找极小值

题目：
极值定义该值比左右的值都小，如果是在数组两侧则只比较一点即可。
在无序数组中找到该极小值。

public class Main {private static Integer process(int[] arr) {if (arr == null || arr.length == 0) {return null;}int N = arr.length;if (N == 1) {return arr[0];}// 最左侧if (arr[0] < arr[1]) {return arr[0];}// 最右侧if (arr[N - 1] < arr[N - 2]) {return arr[N - 1];}int left = 1;int right = N - 2;while (left < right) {int med = ((right - left) >> 1) + left;// right=med+1和left=med这种情况是在判断条件为arr[med]>arr[med-1]时if (arr[med] < arr[med + 1]) {right = med;} else {left = med + 1;}}return arr[left];}
}

贪心算法

子数组累计和最大值

• 我们利用假设检验的思想，先假设子数组为最大值，来推充要条件：
• 若满足最大累加和就要考虑前面连续子数组的累计和定小于0，否则会将前面的子数组加上。
• 对于每个值进行遍历索引时，若出现了累加为负数，那么就意味着此时就是我们重新向后累计的重要标志。

public class Test {public static int maxLenNum(int[] arr){int max=Integer.MIN_VALUE;int cur=0;for (int i : arr) {cur+=i;max=Math.max(max,cur);cur=Math.max(cur, 0);}return max;}
}

子矩阵累计和最大值

• 子矩阵往往考虑是否可以转换成字数组的问题，就是将多行转化成一行或者多列转化成多列
• 转化之后思考一维情况下的解决思路，看看是否能应用到矩阵中

public class Test {public static int maxAreaNum(int[][] arr) {if (arr == null || arr.length == 0 || arr[0].length == 0) return 0;int max = Integer.MIN_VALUE;int cur;int[] sumArr;for (int i = 0; i != arr.length; i++) {sumArr = new int[arr[0].length];for (int j = i; j != arr.length; j++) {cur = 0;for (int k = 0; k != sumArr.length; k++) {sumArr[k] += arr[j][k];cur += sumArr[k];max = Math.max(max, cur);cur = Math.max(cur, 0);}}}return max;}
}

打表法

• 出现和倍数相关的问题时，可以考虑通过一般方法解题后的结果是否存在某种特殊的规律，通过直观的答案直接进行代码的书写，不需要关注本质含义。

整体装袋

一般思路

public class Main {public static int num(int apple) {if (apple % 8 == 0)return apple / 8;int n8 = apple / 8;int m = apple % 8;while (m < 24 && n8 >= 0) {if (m % 6 == 0)return n8 + m / 6;--n8;m += 8;}return -1;}
}

打表代码

18前无规律，18后单为-1，双为一个值，每增加8个就增加1

public class Main {public static int daBiao(int apple) {if (apple < 18)return apple == 0 ? 0: (apple == 6 || apple == 8) ? 1 : (apple == 12 || apple == 14 || apple == 16) ? 2 : -1;if (apple % 2 == 1)return -1;return (apple - 18) / 8 + 3;}
}

幂次方吃草

一般思路

public class Main {public static String winner(int N) {if (N <= 4)return N == 0 || N == 2 ? "羊羊" : "牛牛";int eatTest = 1;while (eatTest <= N) {if (winner(N - eatTest).equals("羊羊"))return "牛牛";eatTest *= 4;}return "羊羊";}
}

打表代码

public static String win(int N){return (N)%5==0||(N)%5==2?"羊羊":"牛牛";
}

经典数据结构类

栈

用栈将栈元素排序

public class Main {public static void sortStackByStack(Stack<Integer> stack) {Stack<Integer> help = new Stack<Integer>();while (!stack.isEmpty()) {int cur = stack.pop();while (!help.isEmpty() && help.peek() < cur) {stack.push(help.pop());}help.push(cur);}while (!help.isEmpty()) {stack.push(help.pop());}}
}

单调栈

• 当遇见向左右边进行大于该值或小于该值的最近值的寻找时就是单调栈

经典单调栈模型

求没有重复值的数组中每个元素的左右两个方向离该值最近的且比该值大的元素的索引，没有记录-1

public class Main {public static int[][] process(int[] arr) {if (arr == null || arr.length == 0) {return null;}int[][] res = new int[arr.length][2];// 一直保持栈中索引对应的元素维持降序原则Stack<Integer> singleStack = new Stack<>();for (int i = 0; i < arr.length; i++) {// 若果直接插入打破了降序原则，那么就要将栈中元素进行删除// 在删除的同时,每个删除元素的最左大的值是栈中上一个值，右边最近的大值就是将要入栈的值while (!singleStack.isEmpty() && arr[singleStack.peek()] < arr[i]) {int popIndex = singleStack.pop();res[popIndex][0] = singleStack.isEmpty() ? -1 : singleStack.peek();res[popIndex][1] = i;}singleStack.push(i);}// 将栈中剩余元素进行确定，此时栈中元素右侧没有大值while (!singleStack.isEmpty()) {int popIndex = singleStack.pop();res[popIndex][0] = singleStack.isEmpty() ? -1 : singleStack.peek();res[popIndex][1] = -1;}return res;}
}

单调栈题

• 贪心算法做基础：将每个值作为该累计数组中的最小值，最佳范围就是向两边寻找比该值小的值作为累计数组的分界点。
• 数据预处理：优先计算累计和，根据贪心定范围
• 升序单调栈定分界点

class T {public static int m(int[] arr) {int size = arr.length;int[] sums = new int[size];sums[0] = arr[0];//我们使用单调栈时是获取左右的最近的较小的两个值之间的元素（不包括两个较小值）//元素累计和，这样根据两个值相减就会得到中间元素的值for (int i = 1; i < size; i++) {sums[i] = sums[i - 1] + arr[i];}int max = Integer.MIN_VALUE;Stack<Integer> stack = new Stack<>();for (int i = 0; i < size; i++) {while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {//保持降序int j = stack.pop();//通过左右两边累计和的差值求出对应值j的指标max = Math.max(max, (stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()])) * arr[j]);}stack.push(i);}//处理右无较小值的数据while (!stack.isEmpty()) {int j = stack.pop();max = Math.max(max, (stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()])) * arr[j]);}return max;}
}

堆

输出出现次数最多的

大根堆实现

public class Test {public static List maxK(int[] arr, int k) {HashMap<Integer, Integer> map = new HashMap<>();for (int i:arr){map.merge(i,1, Integer::sum);}PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.getValue(),o1.getValue()));Set<Map.Entry<Integer, Integer>> entries = map.entrySet();queue.addAll(entries);ArrayList<Integer> list = new ArrayList<>();for (int i=0;i<k;i++){list.add(Objects.requireNonNull(queue.poll()).getKey());}return list;}
}

小根堆实现

public class Test {public static void main(String[] args) {System.out.println(maxK(new int[]{1, 2, 3, 2, 3, 2, 2, 2, 2, 25, 5, 6, 6, 6}, 2));}public static List maxK(int[] arr, int k) {HashMap<Integer, Integer> map = new HashMap<>();for (int i : arr) {map.merge(i, 1, Integer::sum);}PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();for (int i = 0; entries.hasNext(); i++) {Map.Entry<Integer, Integer> next = entries.next();if (i<k){queue.add(next);}else {if (queue.peek().getValue()<next.getValue()){queue.poll();queue.add(next);}}}ArrayList<Integer> list = new ArrayList<>();for (Map.Entry<Integer, Integer> entry : queue) {list.add(entry.getKey());}return list;}
}