记录我刷题的笔记，从2022年11月29日开始，到2023年5月12日，第一阶段。

日期 hpy 我 差值
2022年11月29日 591 348 243
2022年12月11日 618 388 230
2022年12月26日 639 430 209
2023年1月6日 652 453 199
2023年1月10日 666 475 191
2023年1月16日 677 510 167
2023年1月17日 678 518 160
2023年1月22日 693 535 158
2023年1月25日 700 550 150
2023年1月29日 707 563 144
2023年1月30日 708 568 140
2023年1月31日 709 571 138
2023年2月2日 715 580 135
2023年2月16日 750 622 128
2023年3月5日 774 646 128
2023年3月12日 779 656 123
2023年4月6日 812 680 132
2023年4月15日 817 696 121
2023年5月12日 835 769 66
2023年5月28日 842 812 30
2023年7月4日 872

每日一题

2022年11月21日

\808. 分汤

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
 class Solution {
    private static Map<Integer, int[]> map = new HashMap<>(){{
        put(1,  new int[]{100, 0});
        put(2,  new int[]{75, 25});
        put(3,  new int[]{50, 50});
        put(4,  new int[]{25, 75});
    }};

    public double soupServings(int n) {
        if(n >= 4451)return 1;

        double dp[][] = new double[n+1][n+1];
        dp[0][0] = 0.5;
        for(int i = 1; i <= n; i++){
            dp[0][i] = 1;
            dp[i][0] = 0;
        }
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                for(int i = 1; i <= 4; i++){
                    int[] choice = map.get(i);
                    int a = Math.max(j - choice[0], 0);
                    int b = Math.max(k - choice[1], 0);
                    dp[j][k] += 0.25 * dp[a][b];
                }
            }
        }
        return dp[n][n];
    }
}

\878. 第 N 个神奇数字

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
class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long MOD = (long)1e9 + 7;
        long left = 0,right = (long)Math.min(a,b)*n;
        // System.out.println(right);
        long lc = lcm(a,b);
        // System.out.println(lc);
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (mid / a + mid / b - mid / lc >= n) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return (int)(left%MOD);
    }
    // 求最小公倍数
    private int lcm(int a,int b) {
        return a / gcd(a,b) * b;
    }
    // 辗转相除法 求a b最大公因数
    private int gcd(int a,int b) {
        return b > 0 ? gcd(b,a % b):a;
    }
}

\795. 区间子数组个数

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
class Solution {
    public int numSubarrayBoundedMax(int[] nums, int a, int b) {
        int n = nums.length, ans = 0;
        int[] l = new int[n + 10], r = new int[n + 10];
        Arrays.fill(l, -1); Arrays.fill(r, n);
        Deque<Integer> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            // 
            while (!d.isEmpty() && nums[d.peekLast()] < nums[i]) r[d.pollLast()] = i;
            d.addLast(i);
        }
        d.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!d.isEmpty() && nums[d.peekLast()] <= nums[i]) l[d.pollLast()] = i;
            d.addLast(i);
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] < a || nums[i] > b) continue;
            ans += (i - l[i]) * (r[i] - i);
        }
        return ans;
    }
}

作者：宫水三叶
链接：https://leetcode.cn/problems/number-of-subarrays-with-bounded-maximum/solutions/1988320/by-ac_oier-gmpt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

6.Z字形变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String convert(String s, int numRows) {
        if (numRows<2) return s;
        List<StringBuilder> res = new ArrayList<>();
        for (int i=0;i<numRows;i++) {
            // 这样写 才对 这个是要学习的
            res.add(new StringBuilder());
        }
        int flag = -1;
        int i=0;
        for (int j=0;j<s.length();j++) {
            res.get(i).append(s.charAt(j));
            if (i==0||i==numRows-1) flag = -flag;
            i+=flag;
        }
        StringBuilder sb = new StringBuilder();
        for (int j=0;j<res.size();j++) sb.append(res.get(j).toString());
        return sb.toString();
    }
}

最大波动的字符

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
class Solution {
    public int largestVariance(String s) {
        int res = 0;
        int n =  s.length();
        for (char i='a';i<='z';i++) {
            for (char j='a';j<='z';j++) {
                if (i==j) continue;
                int diff = 0;
                int diffWithJ = -n;
                for (int k=0;k<n;k++) {
                    char c = s.charAt(k);
                    if (c==i) {
                        diff++;
                        diffWithJ++;
                    }   else if (c==j) {
                        diffWithJ = --diff;
                        diff = Math.max(0,diff);
                    }
                    res = Math.max(res,diffWithJ);
                }
            }
        }
        return res;
    }
}

基础

O(n)代表最差的情况是n次常数项的操作

字符串

\71. 简化路径

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
class Solution {
    public String simplifyPath(String path) {
        LinkedList<String> stack = new LinkedList<>();
        int n = path.length();
        for (int i=0;i<n;i++) {
            while(i<n&&path.charAt(i)=='/') i++;
            int j = i + 1;
            while(j<n&&path.charAt(j)!='/') j++;
            // System.out.println(path+" "+i+" "+j);
            if (i==n) break;
            String str = path.substring(i,j);
            // System.out.println(str);
            if (str.equals("..")) {
                if (!stack.isEmpty()) stack.removeLast();
            } else if (!str.equals(".")) {
                stack.add(str);
            }
            i = j;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append("/"+stack.poll());
        }
        return sb.length()==0?"/":sb.toString();
    }
}

双指针

面试题 01.05. 一次编辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean oneEditAway(String a, String b) {
        int n = a.length(), m = b.length();
        if (Math.abs(n - m) > 1) return false;
        // 这里写的是真的精彩
        if (n > m) return oneEditAway(b, a);
        int i = 0, j = 0, cnt = 0;
        // 几种情况都概括了
        while (i < n && j < m && cnt <= 1) {
            char c1 = a.charAt(i), c2 = b.charAt(j);
            if (c1 == c2) {
                i++; j++;
            } else {
                if (n == m) {
                    i++; j++; cnt++;
                } else {
                    j++; cnt++;
                }
            }
        }
        return cnt <= 1;
    }
}

\1574. 删除最短的子数组使剩余数组有序

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
class Solution {
    public int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int left = 0;
        while (left + 1 < n && arr[left] <= arr[left+1]) {
            left++;
        }
        // [0...left]有序
        if (left == n - 1) {
            return 0;
        }
        // [right...n-1]有序
        int right = n - 1;
        while (right > 0 && arr[right - 1] <= arr[right]) {
            right--;
        }
        // 完全删除一边[left+1, n-1], 或者[0...right - 1]
        int result = Math.min(n - left - 1, right);

        // 左边和右边各保留一部分
        int i = 0, j = right;
        
        while (i <= left && j <= n - 1) {
            if (arr[i] <= arr[j]) {
                // [0...i] 和 [j...n-1] 有序, 删除 [i+1...j-1]
                result = Math.min(result, j - i - 1);
                i++;
            } else {
                // 小的+1
                j++;
            }
        }
        return result;
    }
}

位运算

int 无符号整型有32位

1.a^b表示a和b异或，可以理解为无进位相加，

满足以下的三个定律 交换律 结合律 还有本身异或等于0 这三个定律

1
2
3
4
5
6
private void swap(int a,int b) {
   	// 如果 a 和 b相等的话 int a = 0;b = b;
	int a = a^b;
	int b = a^b;
	int a = a^b;
}

2272 但是在数组进行交换的时候 ，如果i和j的下标一样的话 就会出现

1
2
3
4
5
6
7
8
9
10
11
12
public int[] twoSum(int[] nums, int target) {
        int[] arr = new int[]{1,1};
        swap(arr,0,0);
        Arrays.stream(arr).forEach(System.out::println);
        return arr;
    }
	// 最后的交换的会成为0
    private 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];
    }

2.**b&(~b+1)**表示的是取出最右边的二进制为1的数 **b&-b ** b&-b=b判断是不是二的幂

面试题 05.01. 插入

1
2
3
4
5
6
7
8
public int insertBits(int N, int M, int i, int j) {
        //left in (,j+1];middle in [i,j];right in [i-1,0];
        int left = N>>j>>1; //把最左边的部分调整好了，即抛弃了替换部分和低位部分
        left = left<<j<<1;  //因此最后要进行或运算，所以把他再移到原来的高位上。
        int middle = M<<i;  //替换N的j<-----i位，那么只需要将M左移i位即可
        int right = N&((1<<i)-1);//只需要N的低位，将高位置零,(1<<2)-1 = (11)2
        return left | middle | right;
    }

最低位的0变成1是nums|(nums+1)

最低位的1变成0是nums&(nums-1)

Integer.bitCount()是计算位数的

num&-num是lowbit

题目：给定两个有符号32位整数，返回比较大的数字（不允许使用判断）

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
private static int flip(int n) {
        return n^1;
    }
    // n是非负数返回1
    // n是负数返回0
    private static int sigh(int n) {
        return flip((n>>31)&1);
    }
    private static int getMax(int a,int b) {
        int c = a-b;
        // a 大 scA=1 else scB = 1
        int scA =sign(c);
        int scB = flip(scA);
        return a*scA+b*scB;
    }
// 可能会发生溢出的情况 所以还需要 优化
	private static int getMax2(int a,int b) {
        int c = a-b;
        // a和b符号相同 a-b 就不会溢出
        int sa = sign(a);
        int sb = sign(b);
        int sc = sign(c);
        int difSab = sa^sb;
        int sameSab = flip(difSab);
        int returnA = difSab*sa + sameSab*sc;
        int returnB = flip(returnA);
        return a*returnA + b*returnB
    }

5.判断32位整型数是否二进制和四进制

1
2
3
4
5
// 二进制
n&(n-1)==0//打散之后 判断某位是不是只有1 是的话就是二进制
// 四进制
偶数位是1
(n&(n-1)==0)&&(n&0x55555555)!=0

排序算法

O（n^2）

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private void selection_sort(int[] arr) {
	int n = arr.lenghth;
	for (int i=n-1;i>=0;i--) {
        int max = Integer.MIN_VALUE;
        int max_index = i;
        for (int j=0;j<=i;j++) {
            if (arr[j]>max) {
                max = arr[j];
                max_index = j;
            }
            swap(arr,i,max_index);
}
    }
}

冒泡排序bubble_sort

1
2
3
4
5
6
7
8
9
10
private void bubble_sort(int[] arr) {
	int n = arr.length;
	for (int i=n-1;i>0;i--) {
		for (int j=0;j<i;j++) {
            if(arr[j]>arr[j+1]) {
                swap(arr,j,j+1);
            }
        }
	}
}

插入排序insertion_sort 插入排序是不稳定的 一直保证前i个是有序的

1
2
3
4
5
6
7
8
private void insertion_sort(int[] arr) {
	int n = arr.length;
	for (int i=0;i<arr.length;i++) {
	for (int j=i-1;j>=0&&arr[j]>arr[j+1];j--) {
		swap(arr,i,j);
}
}
}

O(n*logn)

排序的信息没有浪费所以成了 （n*logN）

归并排序-merge_sort->拓展（小和 逆序对）

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
private static void merge_sort(int[] arr,int left,int right) {
        if (left==right) return;
        // 这样比除2要快一些 以后都用这个
        int mid = left + (right-left)>>1;
        merge_sort(arr,left,mid);
        merge_sort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }
    private void merge(int[] arr,int left,int mid,int right) {
        if (left==right) return;
        int[] helper = new int[right-left+1];
        int p1 = left;
        int p2 = mid+1;
        int i=0;
        while (p1<=mid&&p2<=right) {
            helper[i++] = arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while (p1<=mid) {
            helper[i++] = arr[p1++];
        }
        while (p2<=right) {
            helper[i++] = arr[p2++];
        }
        for (int i=0;i<helper.length;i++) {
            arr[left+i] = helper[i];
        }
    }

快速排序

O(n^2)最坏的情况

1.0

总拿最后一个数字做划分 然后再进行递归

2.0

一次搞定一批数 （划分点打到中点 是最好的情况）

快排3.0

随机打乱 每种情况占比1/N 最后的算法复杂度求数学期望是O(N*logN)

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
private static void quick_sort(int[] arr,int left,int right) {
        if (left<right) {
            // 介绍:Math.random()是令系统随机选取大于等于 0.0 且小于 1.0 
            // 这样可以让时间复杂度的期望成为O(N*logN)
            swap(arr,left+(int)Math.random()*(right-left+1),right);
            int[] p = patition(arr,left,right);
            quick_sort(arr,left,p[0]-1);
            quick_sort(arr,p[1]+1,right);
        }
    }
    // 三色荷兰国旗问题 patition是分开的意思 
    private static int[] patition(int[] arr,int left,int right) {
        int less = left - 1;
        int more = right;
        while (left<more) {
            if (arr[left]<arr[right]) {
                // 这个数遇到了 在left之前的less 可能和target相等也可能小于 所以是可以直接去走的
                swap(arr,++less,left++);
            } else if (arr[left]>arr[right]) {
                // 这个数没有遇到过 所以说不会left++
                swap(arr,--more,left);
            } else{
                left++;
            }
        }
        swap(arr,more,right);
        return new int[]{less+1,more};
    }
    private static void swap(int[] arr,int i,int j) {
        if (i==j) return;
        arr[i] = arr[i]^arr[j];
        arr[j] = arr[i]^arr[j];
        arr[i] = arr[i]^arr[j];
    }

堆排序heap_sort

时间复杂度O(n*logn) 空间复杂度O(1);

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
private static void heap_sort(int[] arr,int left,int right) {
        if(arr==null||arr.length<2) return;
        for (int i=0;i<arr.length;i++) heapInsert(arr,i);
        int heapSize = arr.length;
        swap(arr,0,--heapSize);
        while (heapSize>0) {
            heapify(arr,0,heapSize);
            swap(arr,0,--heapSize);
        }
    }
    private static void heapInsert(int[] arr,int index) {
        while (arr[index]>arr[(index-1)/2]) {
            swap(arr,index,(index-1)/2);
            index = (index-1)/2;
        }
    }
    private static void heapify(int[] arr,int index,int heapSize) {
        int left = 2*index+1;
        while(left<heapSize) {
            // 两个孩子中谁的数值大 谁赋值给largest
            int largest = left+1<heapSize&&arr[left+1]>arr[left]?left+1:left;
            largest = arr[largest] > arr[index] ? largest : index;
            if (largest==index) break;
            swap(arr,largest,index);
            index = largest;
            left = 2* index + 1;
        }
    }

基数排序-桶排序

桶可以是队列可以是栈 桶是容器

比较器

返回负数的时候，第一个参数排在前面

返回正数的时候，第二个参数排在前面

返回0的时候，无所谓

链表

技巧：快慢指针和哈希表

两个链表找公共节点 一起走统计个数 然后去掉差（快的先走差值） 在一起走

找环的节点入口-》先快指针再快指针归位，一起走指针到达的就是入口；

1
2
// 快指针这么写更好
	while (fast.next!=null&&fast.next!=null) {}

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode reverseList(ListNode head) {
    // 1. 递归终止条件
    if (head == null || head.next == null) {
        return head;
    }
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

作者：老汤
链接：https://leetcode.cn/problems/UHnkqh/solutions/941827/jian-dan-yi-dong-javac-pythonjs-dong-hua-gy6w/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

二分查找

二分查找不一定要保持有序，局部最小值也是可以使用二分的。

解题思路：二分查找low_bound 【时间复杂度O(lgn),n是数组长度】

峰值和mid的下一个比较

最小值和最后一个元素比较

- 核心要素
- 注意区间开闭，三种都可以
- 循环结束条件：当前区间内没有元素
- 下一次二分查找区间：不能再查找(区间不包含)mid，防止死循环
- 返回值：大于等于target的第一个下标（注意循环不变量）

- 有序数组中二分查找的四种类型（下面的转换仅适用于数组中都是整数）
\1. 第一个大于等于x的下标： low_bound(x)
\2. 第一个大于x的下标：可以转换为第一个大于等于 x+1 的下标 ，low_bound(x+1)
\3. 最后一个一个小于x的下标：可以转换为第一个大于等于 x 的下标 的左边位置, low_bound(x) - 1;
\4. 最后一个小于等于x的下标：可以转换为第一个大于等于 x+1 的下标 的 左边位置, low_bound(x+1) - 1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private int lowerBound(int[] arr,int target) {
      // 主要看的是不变的量 不变的量就是区间外面的量
      int left = 0;
      int right = arr.length;
      while (left < right) {
          int mid = left + (right-mid)/2;
          // 这里的小于就是保证 left左边的数都比他要小
          if (arr[mid] < left) {
              left = mid + 1;
              // 保证right右边的数都比他要大
          } else {
              right = mid;
          }
      }
      return left;
  }

递归

递归求数组的最大值

1
2
3
4
5
6
7
8
9
10
11
public static getMax(int[] arr) {
        return dfs(arr,0,arr.length-1);
    }
    private static int dfs(int[] arr,int left,int right) {
        if (left==right) return arr[left];
        // 这样比除2要快一些 以后都用这个
        int mid = left + (right-left)>>1;
        int leftMax = dfs(arr,left,mid);
        int rightMax = dfs(arr,mid+1,right);
        return Math.max(leftMax,rightMax);
    }

二叉树

必须利用第三次到达节点做强整合的，递归套路是最优解

没有必要第三次到达节点的，Morris遍历是优解

二叉树的迭代遍历和递归遍历

前序遍历-》压栈先右后左

1
2
3
4
5
6
7
8
9
10
11
12
public static void preOrderUnRecur(Node head) {
    if (head==null) return;
    Stack<Node> stack = new Stack<Node>();
    stack.add(head);
    while (!stack.isEmpty()) {
        Node poll = stack.poll();
        System,out.print(poll.value+" ");
        if (head.right!=null) stack.push(head.right);
        if (head.left!=null) stack.push(head.left);
    }
    System.out.println();
}

中序遍历-》一路左子树-》然后左子树为空-》右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//判断的条件写的特别有意思
public void inOrderUnRecur(Node head) {
	if (head!=null) {
        Stack<Node> srack = new Stack<Node>();
        while (stack!=null||head!=null) {
            if (head!=null) {
                stack.push(head);
                head = head.left;
            }else {
                head = stack.pop();
                System.out.println(head.value+" ");
                // 一到右边就开始往左
                // 一层一层左边的
                head = head.right;
            }
        }
    }
}

后序遍历-》压栈先左后右 使用一个栈倒序就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public void postOrderUnRecur(Node head) {
    if (head==null) return;
    Stack<Node> s1 = new Stack<>();
    Stack<Node> s2 = new Stack<>();
    s1.push(head);
    while (!s1.isEmpty()) {
        head = s1.pop();
        s2.push(head);
        if (head.left!=null) s1.push(head.left);
        if (head.right!=null) s1.push(head.right);
    }
    while(!s2.isEmpty()) {
        Sout(s2.pop().value+" ");
    }
}

层序遍历

层序遍历 统计每层的个数

Morris遍历-》O(N)时间复杂度 O(1)空间复杂度

Morris遍历 有的节点会被遍历两次 有的节点会被遍历一次 打印遍历的第一次

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
public static void morris(TreeNode root) {
        if (root==null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur!=null) {
            mostRight = cur.left;
            // 没有左子树也是直接往右走
            if (mostRight!=null) {
                // 1.第一次遍历到空节点 2.第二次遍历到head节点
                while(mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight = mostRight.right;
                } 
                // mos
                // 如果是第一次遍历到 往左边走
                if (mostRight.right==null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            }
            // 第二次遍历就走右边
            cur = cur.right;
        }
    }

Morris的前序遍历的代码：

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
public static void morris(TreeNode root) {
        if (root==null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur!=null) {
            mostRight = cur.left;
            // 没有左子树也是直接往右走
            if (mostRight!=null) {
                // 1.第一次遍历到空节点 2.第二次遍历到head节点
                while(mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight = mostRight.right;
                } 
                // mos
                // 如果是第一次遍历到 往左边走
                if (mostRight.right==null) {
                    System.out.println(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;
                }
            } else{
                System.out.println(cur.val);
            }
            // 第二次遍历就走右边
            cur = cur.right;
        }
    }

Morris遍历的中序遍历：（只遍历一次的节点 直接打印 遍历两次的节点 第二次打印）

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
public static void morris(TreeNode root) {
        if (root==null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur!=null) {
            mostRight = cur.left;
            // 没有左子树也是直接往右走
            if (mostRight!=null) {
                // 1.第一次遍历到空节点 2.第二次遍历到head节点
                while(mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight = mostRight.right;
                } 
                // mos
                // 如果是第一次遍历到 往左边走
                if (mostRight.right==null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // System.out.println(cur.val);
                    mostRight.right = null;
                }
            } 
            // 如果没有左树，continue 跳不过去这边的打印 所以在下面直接打印即可
            System.out.println(cur.val);
            // 第二次遍历就走右边
            cur = cur.right;
        }
    }

morris遍历的后序遍历-》(第二次回到节点 逆序打印左子树的右边界-最后结束的时候逆序打印整棵树的右边界)

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
public static void morris(TreeNode root) {
        if (root==null) return;
        TreeNode cur = root;
        TreeNode mostRight = null;
        while (cur!=null) {
            mostRight = cur.left;
            // 没有左子树也是直接往右走
            if (mostRight!=null) {
                // 1.第一次遍历到空节点 2.第二次遍历到head节点
                while(mostRight.right!=null&&mostRight.right!=cur) {
                    mostRight = mostRight.right;
                } 
                // mos
                // 如果是第一次遍历到 往左边走
                if (mostRight.right==null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // System.out.println(cur.val);
                    printReverse(cur.left);
                    mostRight.right = null;
                }
            } 
            // 最后继续逆序打印整棵树的右边界
            printReverse(head);
            // 第二次遍历就走右边
            cur = cur.right;
        }
    }

二叉搜索树的中继遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if(p==null||root==null){
        return null;
    }
    if(root.val<=p.val){//当前和左边都不可能>p
        return inorderSuccessor(root.right,p);
    }
    //root>p
    TreeNode res1=inorderSuccessor(root.left,p);
    if(res1!=null){
        return res1;
    }else{
        return root;
    }
}
}

二叉搜索树的中继遍历2

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
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node inorderSuccessor(Node node) {
        if (node==null) return null;
        if (node.right!=null) {
            return getLeftMost(node.right);
        }else {
            Node parent = node.parent;
            while(parent!=null&&parent.left!=node) {
                node = parent;
                parent = node.parent;
            } 
            return parent;
        }
    }
    private Node getLeftMost(Node node) {
        while (node.left!=null) {
            node = node.left;
        }
        return node;
    }
}

二叉树的序列化和反序列化：

树转化为字符串叫序列化，字符串转化为树叫做反序列化。

完全二叉树的节点个数

时间复杂度O(lognlogn)

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {//计算某个点的子总数
        return count(root);
    }

    public int count(TreeNode root){
        int left = 0,right = 0;
        // 主要注意一下是从这里开始的
        TreeNode leftNode = root,rightNode = root;
        while (leftNode != null) {
            left++;
            leftNode = leftNode.left;
        }
        while (rightNode != null) {
            right++;
            rightNode = rightNode.right;
        }
        if (left==right) return (int)Math.pow(2,left) - 1;
        return count(root.left)+count(root.right)+1;
        
    }
}

树形DP

向左树要信息和向右树要信息

题目： 判断树是否是二叉搜索树 中序遍历来判断 

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
// int min = Integer.MAX_VALUE;
// int max = Integer.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
    //左子树的最大值小于中间节点 右子树的最小值大于中间节点 左子树和右子树是二叉搜索树
    return dfs(root).isBST;
}
public Info dfs(TreeNode root) {

    if (root==null) return null;
    Info LeftInfo = dfs(root.left);
    Info RightInfo = dfs(root.right);
    /// 左边最大的
    int max = root.val;
    int min = root.val;
    if (LeftInfo!=null) {
        max = Math.max(max,LeftInfo.max);
        min = Math.min(min,LeftInfo.min);
    }
    if (RightInfo!=null) {
        max = Math.max(max,RightInfo.max);
        min = Math.min(min,RightInfo.min);
    }
    boolean isBST = true;
    if (LeftInfo!=null&&(!LeftInfo.isBST||LeftInfo.max>=root.val)) {
        isBST = false;
    }
    if (RightInfo!=null&&(!RightInfo.isBST||root.val>=RightInfo.min)) {
        isBST = false;
    }
    // System.out.println("max=="+max+"min=="+min+"isBst=="+isBST);
    return new Info(max,min,isBST);
}
public class Info{
    int max;
    int min;
    boolean isBST;
    public Info(int max,int min,boolean isBST) {
        this.max = max;
        this.min = min;
        this.isBST = isBST;
    }
}

平衡树 左子树平衡 右子树平衡 并且高度差不为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isBalanced(TreeNode root) {
       return dfs(root).isBalance;
   }
   private Info dfs(TreeNode root) {
       if (root==null) return new Info(0,true);
       Info leftInfo = dfs(root.left);
       Info RightInfo = dfs(root.right);
       int height = Math.max(leftInfo.height,RightInfo.height)+1;
       boolean isBalance = leftInfo.isBalance&&RightInfo.isBalance&&Math.abs(leftInfo.height-RightInfo.height)<2;
       return new Info(height,isBalance);
   }
   public static class Info{
       int height;
       boolean isBalance;
       public Info(int height,boolean isBalance) {
           this.height = height;
           this.isBalance = isBalance;
       }
   }

完全树：遇到左节点为存在右节点不存在的情况下其他的节点都应该是叶子节点

dfs->记忆化搜索->dp动态规划

例题

贪心

比较字典序：给一个字符串数组 返回最小的字典序 比较（a+b）和（b+a）的字典序 不是去比较a和b的字典序

会议安排：结束时间先结束的优先安排

贪心策略最常用的就是 堆和排序 哈夫曼编码问题

花费项目-》大小根堆

大根堆：每一棵树最大的值都是头节点的数值，

小根堆：每一棵树最小的值都是根节点的数值

自顶向下：直接return 函数调用自身下一级实现，比如 return Fibonacci(n-1) + Fibonacci(n-2);
自底向上：先递归到最小单位(叶子节点)，再从最小单位往上抛结果，传递结果

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
/**
 * 两种遍历方向，计算最大深度
 * 自顶向下
 * 自底向上
 *
 */
public class _11_10_Top_Down {

    //自顶向下
    private int answer;
    private void maximum_depth(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            answer = Math.max(answer, depth);
        }
        maximum_depth(root.left, depth + 1);
        maximum_depth(root.right, depth + 1);
    }

    //自底向上
    public int maximum_depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //感受一下这里是将最底层的结果往上抛
        //，因为这里的递归边界条件是叶子节点
        int left_depth = maximum_depth(root.left);
        int right_depth = maximum_depth(root.right);
        return Math.max(left_depth, right_depth) + 1;
    }
}


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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * LettCode中的题：
 * 235. 二叉搜索树的最近公共祖先
 * 236. 二叉树的最近公共祖先
 */

class Solution {

	//搜索二叉树直接可以分为比大小，定位
    //分为都在左子树、都在右子树、两边(root)
    public TreeNode lowestCommonAncestor235(TreeNode root, TreeNode p, TreeNode q) {
        if(p.val<root.val && q.val<root.val){
        	//这里就是自顶向下
            return lowestCommonAncestor235(root.left,p,q);
        }
        if(p.val>root.val && q.val>root.val){
            return lowestCommonAncestor235(root.right,p,q);
        }
        return root;
    }


    //递归自底向上，讨论子树中是否含有某个节点
    // 如果分别在左右子树，则返回跟节点
    // 如果在同一个子树继续往下递归
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null ||root==p || root==q){
            return root;
        }else{
        //着也是自底向上的思想
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(left==null && right==null){
                return null;
            }

            if(left==null){
                return right;
            }

            if(right==null){
                return left;
            }

            return root;

        }
    }
}

今天又忘记了 求最大公因数应该是gcd(b,a % b):a，有一点要注意的是**(long)Math.min(a,b)n*;

复习了一下二分法 ，求左侧边界。

二分查找又死循环了？一个视频讲透二分本质！【基础算法精讲 04】循环不变量 在排序数组中查找元素的第一个和最后一个位置 | 力扣 LeetCode 高频面试题_哔哩哔哩_bilibili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int left_bound(int[] nums, int target) {
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

求右侧边界：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

：首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。

至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在锁定右边界时的这个条件判断：

1
2
3
4
// 增大 left，锁定右侧边界
if (nums[mid] == target) {
    left = mid + 1;
    // 这样想: mid = left - 1

\809. 情感丰富的文字

双指针 不要想得很复杂 直接带进去开始比较

return i==str1.length()&&j==str2.length()?1:0; 是证明遍历完成最好的写法 

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
class Solution {
    public int expressiveWords(String s, String[] words) {
        int res = 0;
        for (int i=0;i<words.length;i++) {
            res+=fun(s,words[i]);
        }
        return res;
    }
    private int fun(String str1,String str2) {
        int i=0,j=0;
        while (i<str1.length()&&j<str2.length()) {
            if (str1.charAt(i)!=str2.charAt(j)) return 0;
            char ch1 = str1.charAt(i);
            int sum1 = 0, sum2 = 0;
            while (i<str1.length()&&str1.charAt(i)==ch1) {
                ++sum1;
                ++i;
            }
            char ch2 = str2.charAt(j);
            while (j<str2.length()&&str2.charAt(j)==ch2) {
                ++sum2;
                ++j;
            }
            if (sum1<sum2) {return 0;}
            if (sum1>sum2&&sum1<3) {return 0;}
        }
        return i==str1.length()&&j==str2.length()?1:0;
    }
}

\6248. 统计中位数为 K 的子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int countSubarrays(int[] nums, int k) {

        int pos = 0, n = nums.length;
        while (nums[pos] != k) ++pos;
        var cnt = new HashMap<Integer, Integer>();
        // cnt里面放的是出现的次数
        cnt.put(0, 1); // i=pos 的时候 c 是 0，直接记到 cnt 中，这样下面不是大于就是小于
        for (int i = pos + 1, c = 0; i < n; ++i) {
            c += nums[i] > k ? 1 : -1;
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
        }
        int ans = cnt.get(0) + cnt.getOrDefault(1, 0); 
        // i=pos 的时候 c 是 0，直接加到答案中，这样下面不是大于就是小于
        for (int i = pos - 1, c = 0; i >= 0; --i) {
            c += nums[i] < k ? 1 : -1;
            ans += cnt.getOrDefault(c, 0) + cnt.getOrDefault(c + 1, 0);
        }
        return ans;
    }
}

\1796. 字符串中第二大的数字

set排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    // List<Integer> list = new ArrayList<>();
    Set<Integer> set = new HashSet<>();
    public int secondHighest(String s) {
        for (int i = 0;i < s.length();i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
               set.add(c-'0');
            }
        }
        // 复习一下java8的collect(Collectors.toList())
        int[] arr = set.stream().sorted(Comparator.naturalOrder()).mapToInt(Integer::valueOf).toArray();
        return arr.length<2?-1:arr[arr.length-2];
    }
}

Hash

一致性哈希

虚拟节点 顺时针 环 数据迁移

https://mp.weixin.qq.com/s/zL-n7zq0Zyhf-l_GQil2dg

布隆过滤器

位图：

布隆过滤器不可remove 允许一定的错误律

m 是位数 k 是哈希函数的个数 如果面试官可以扩大到32G之后还可以重新进行校订

算出来的是bit int是4个byte 32个bit 所以 可以表示很多 如果开四个int 最后可以表示很多数字

Manacher算法

KMP算法

常数级别的字符串匹配

两个字符串S1和S2 对于S2先搞到一个getIndexOf()统计最大的前缀相同的字符长度 next[0] = -1 next[1] = 0 这个数组表示的是之前的不包括当前字符的前缀后缀相同的个数

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
public int strStr(String haystack, String needle) {
        int n = haystack.length();
        int m = needle.length();
        int i = 0,j = 0;
        int[] next = getIndex(needle);
        // Arrays.stream(next).forEach(System.out::println);
        while (i<n&&j<m) {
            if (haystack.charAt(i)==needle.charAt(j)) {
                i++;
                j++;
            } 
            else if (next[j]==-1) i++;
            else {
                j = next[j];
            }
        }
        // System.out.println(i+"---"+j);
         return j==m?i-j:-1;
    }
    // 返回前缀数组
    private int[] getIndex(String m) {
        if (m.length()==1) return new int[]{-1};
        int[] next = new int[m.length()];
        char[] chars = m.toCharArray();
        next[0] = -1;
        next[1] = 0;
        // 指向的位置
        int cnt = 0;
        // i-1比较的是
        for (int i=2;i<m.length();) {
            if(chars[i-1]==chars[cnt]) next[i++] = ++cnt;
            else if (cnt>0) cnt = next[cnt];
            else next[i++] = 0;
        }
        return next;
    }

单调栈

用栈来储存元素index index可以储存的元素要更多一点

下一个最大的元素 栈底到栈顶是从大到小的 遇到比当前的元素小的直接添加进来就可以 遇到比当前元素大的 进行比较移除栈当中的元素 而要移除的元素下面压得就是左边比他大的的元素

下一个最小的元素 栈底到栈顶是从小到大的 遇到比他大的就添加进来 遇到比他小的就移除栈当中的元素 移除的元素下面压得就是比他小的元素

(82条消息) 算法与数据结构——单调栈（Java）（b站左程云课程笔记总结）-CSDN博客

图（后续再补充）

邻接表用的多 

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
// 主函数
public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 建图，有向边代表「被依赖」关系
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    // 构建入度数组
    int[] indegree = new int[numCourses];
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 节点 to 的入度加一
        indegree[to]++;
    }

    // 根据入度初始化队列中的节点
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.offer(i);
        }
    }

    // 记录遍历的节点个数
    int count = 0;
    // 开始执行 BFS 循环
    while (!q.isEmpty()) {
        // 弹出节点 cur，并将它指向的节点的入度减一
        int cur = q.poll();
        count++;
        for (int next : graph[cur]) {
            indegree[next]--;
            if (indegree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.offer(next);
            }
        }
    }

    // 如果所有节点都被遍历过，说明不成环
    return count == numCourses;
}


// 建图函数
List<Integer>[] buildGraph(int n, int[][] edges) {
    // 见前文
}

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
// 记录后序遍历结果
List<Integer> postorder = new ArrayList<>();
// 记录是否存在环
boolean hasCycle = false;
boolean[] visited, onPath;

// 主函数
public int[] findOrder(int numCourses, int[][] prerequisites) {
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    visited = new boolean[numCourses];
    onPath = new boolean[numCourses];
    // 遍历图
    for (int i = 0; i < numCourses; i++) {
        traverse(graph, i);
    }
    // 有环图无法进行拓扑排序
    if (hasCycle) {
        return new int[]{};
    }
    // 逆后序遍历结果即为拓扑排序结果
    Collections.reverse(postorder);
    int[] res = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        res[i] = postorder.get(i);
    }
    return res;
}

// 图遍历函数
void traverse(List<Integer>[] graph, int s) {
    if (onPath[s]) {
        // 发现环
        hasCycle = true;
    }
    if (visited[s] || hasCycle) {
        return;
    }
    // 前序遍历位置
    onPath[s] = true;
    visited[s] = true;
    for (int t : graph[s]) {
        traverse(graph, t);
    }
    // 后序遍历位置
    postorder.add(s);
    onPath[s] = false;
}
// 建图函数
List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
    // 图中共有 numCourses 个节点
    List<Integer>[] graph = new LinkedList[numCourses];
    for (int i = 0; i < numCourses; i++) {
        graph[i] = new LinkedList<>();
    }
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 添加一条从 from 指向 to 的有向边
        // 边的方向是「被依赖」关系，即修完课程 from 才能修课程 to
        graph[from].add(to);
    }
    return graph;
}


大数据问题

给3KB的空间只找到一个没出现过的数

进阶

预处理技巧

求2^31次方之上可能会在计算机的时候超时并且越界 所以提前进行预处理

\1498. 满足条件的子序列数目

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
class Solution {
    public int numSubseq(int[] nums, int target) {
        int MOD = (int)1e9 + 7;
        int res = 0;
        Arrays.sort(nums);
        // 预处理2的n次方
        int n = nums.length;
        int[] pow2arr = new int[n];
        pow2arr[0] = 1;
        for (int i = 1; i < n; i++) {
            pow2arr[i] = (pow2arr[i - 1] << 1) % MOD;
        }
        
        // System.out.println(nums.length);
        for (int i=0;i<nums.length;i++) {
            if (nums[i] > target - nums[i]) break;
            int left = binarySearch(nums,target - nums[i]);
            res = (res+pow2arr[left-i-1])%MOD;
        }
        return res;
    }
    private int binarySearch(int[] nums,int target) {
        int left = 0,right = nums.length;
        while (left<right) {
            int mid = left + (right - left) / 2;
            if (nums[mid]<=target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

二维前缀和

\1292. 元素和小于等于阈值的正方形的最大边长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxSideLength(int[][] mat, int threshold) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] pre = new int[m+1][n+1];
        for (int i=1;i<=m;i++) {
            for (int j=1;j<=n;j++) {
                pre[i][j] = mat[i-1][j-1] + pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1];
            }
        }
        int ans = 0;
        out : for (int k=1;k<=Math.min(m,n);k++) {
            for (int i=1;i<=m;i++) {
                for (int j=1;j<=n;j++) {
                    if (i<k||j<k) continue;
                    int tmp = pre[i][j] - pre[i-k][j] - pre[i][j-k] + pre[i-k][j-k];
                    if (tmp<=threshold) {ans = k; continue out;}
                }
            }
        }
        return ans;
    }
}

图论搜索专题

图的构造结构

\127. 单词接龙

1

拓扑排序

【数据结构】07拓扑排序_哔哩哔哩_bilibili

1.找到没有入度的点

2.任选其中一点写入排序队列

\2192. 有向无环图中一个节点的所有祖先

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
class Solution {
    public List<List<Integer>> getAncestors(int n, int[][] edges) {
        List<List<Integer>> ans = new ArrayList<>();
        // 自动排序
        List<Set<Integer>> sets = new ArrayList<>();
        // Map<Integer,List<Integer>> map = new HashMap<>();
        Map<Integer,List<Integer>> map = new HashMap<>();
        int[] in = new int[n];
        Queue<Integer> queue = new LinkedList<>();
        for (var edge:edges) {
            var from = edge[0];
            var to = edge[1];
            in[to]++;
            if (!map.containsKey(from)) map.put(from,new ArrayList());
            map.get(from).add(to);
        }
        for (int i=0;i<n;i++) {
            if (in[i]==0) {
                queue.add(i);
                // 小细节
                in[i]--;
            }
            
            ans.add(new ArrayList());
            sets.add(new TreeSet());
        }
        while (!queue.isEmpty()) {
            var poll = queue.poll();
            if (map.containsKey(poll)) {
                for (var i:map.get(poll)) {
                    in[i]--;
                    sets.get(i).add(poll);
                    sets.get(i).addAll(sets.get(poll));
                    if (in[i]==0) {
                        // 细节
                        queue.add(i);
                        in[i]--;
                    }
                }
            }
        }
        for (int i=0;i<n;i++) {
            ans.get(i).addAll(sets.get(i));
        }
        return ans;
    }
}

DP

状态机DP

\1186. 删除一次得到子数组最大和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maximumSum(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][2];
        int max = arr[0];
        // 0代表不删除
        // 1代表删除
        dp[0][0] = arr[0];
        dp[0][1] = 0;
        // max = 
        for (int i=1;i<n;i++) {
            if (arr[i]>0) {
                dp[i][0] = Math.max(dp[i-1][0] + arr[i],arr[i]);
                dp[i][1] = dp[i-1][1] + arr[i];
            } else {
                dp[i][0] = Math.max(dp[i-1][0] + arr[i],arr[i]); 
                dp[i][1] = Math.max(dp[i-1][0],dp[i-1][1] + arr[i]);
            }
            max = Math.max(max,Math.max(dp[i][0],dp[i][1]));
        }
        return max;
    }
}

\1143. 最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        text1 = " " + text1;
        text2 = " " + text2;
        int m = text1.length(),n = text2.length();
        int[][] dp = new int[m][n];
        for (int i=1;i<m;i++) {
            for (int j=1;j<n;j++) {
                if (text1.charAt(i)==text2.charAt(j)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[m-1][n-1];
    }
}

数学

快速幂

1
2
3
4
5
6
7
8
9
10
11
12
public long quickMul(int x, int n){
    long res = 1, cur = x;
    while(n > 0){
        // n 不为偶数
        if((n & 1) != 0){
            res = (res * cur) % MOD;
        }
        cur = (cur * cur) % MOD;
        n /= 2;
    }
    return res;
}

二分进阶

最大化最小值 和 最小化最大值

刷题积累

数据范围

1000的数据量可以O(n^2)

100000的数据量可以是O(n*log(n))

分治算法 :分而治之

\241. 为运算表达式设计优先级

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
class Solution {
    List<Integer> diffWaysToCompute(String input) {
    List<Integer> res = new LinkedList<>();
    
    for (int i = 0; i < input.length(); i++) {
        char c = input.charAt(i);
        // 扫描算式 input 中的运算符
        if (c == '-' || c == '*' || c == '+') {
            /****** 分 ******/
            // 以运算符为中心，分割成两个字符串，分别递归计算
            List<Integer> 
                left = diffWaysToCompute(input.substring(0, i));
            List<Integer> 
                right = diffWaysToCompute(input.substring(i + 1));
            /****** 治 ******/
            // 通过子问题的结果，合成原问题的结果
            for (int a : left)
                for (int b : right)
                    if (c == '+')
                        res.add(a + b);
                    else if (c == '-')
                        res.add(a - b);
                    else if (c == '*')
                        res.add(a * b);
        }
    }
    // base case
    // 如果 res 为空，说明算式是一个数字，没有运算符
    if (res.isEmpty()) {
        res.add(Integer.parseInt(input));
    }
    return res;
}

}

剑指 Offer 51. 数组中的逆序对

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
class Solution {
    //利用归并排序解答，在合并的时候，当左边的大于右边，就计算逆序数。
    //计算公式； mid-left+1
    //定义一个全局的计数器变量
    int count = 0;
    public int reversePairs(int[] nums) {
        this.count = 0;
        mergeSort(nums, 0, nums.length-1);
        return count;
    }
    public void mergeSort(int[] nums,int left,int right){
        //当只有一个节点的时候，直接返回，退出递归
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;
        //左拆分
        mergeSort(nums,left,mid);
        //右拆分
        mergeSort(nums,mid+1,right);
        //合并
        merge(nums,left,mid,right);
    }
    public void merge(int[] nums,int left,int mid,int right){
        //定义一个临时数组
        int[] temp = new int[right-left+1];
        //定义一个指针，指向第一个数组的第一个元素
        int i = left;
        //定义一个指针，指向第二个数组的第一个元素
        int j = mid+1;
        //定义一个指针，指向临时数组的第一个元素
        int t = 0;
        //当两个数组都有元素的时候，遍历比较每个元素大小
        while(i <= mid && j <= right){
            //比较两个数组的元素，取较小的元素加入到，临时数组中
            //并将两个指针指向下一个元素
            if(nums[i] <= nums[j]){
                temp[t++] = nums[i++];
            }else{
                //当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
                //此时这个数就是，逆序数
                //定义一个计数器，记下每次合并中存在的逆序数。
                count += mid-i+1;
                temp[t++] = nums[j++];
            }
        }
        //当左边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
        while(i <= mid){
            temp[t++] = nums[i++];
        }
        //当右边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
        while(j <= right){
            temp[t++] =nums[j++];
        }
        //将新数组中的元素，覆盖nums旧数组中的元素。
        //此时数组的元素已经是有序的
        for(int k =0; k< temp.length;k++){
            nums[left+k] = temp[k];
        }
    }
}

链表

\725. 分隔链表

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode[] splitListToParts(ListNode head, int k) {
        ListNode[] nodes = new ListNode[k];
        if (head==null) return nodes;
        int num = 0;
        ListNode tmp = head;
        while (tmp!=null) {
            tmp = tmp.next;
            ++num;
        }
        int cs = num/k,ys=num%k;
        int i = 0;
        ListNode cur = head;
        while (i<k&&cur!=null) {
            int size = cs + (i<ys?1:0);
            nodes[i] = cur;
            for (int j=1;j<size;j++) {
                cur = cur.next;
            }
            ListNode next = cur.next;
            cur.next = null;
            cur = next;
            i++;
        }
        return nodes;
    }
}

滑动窗口

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
/* 滑动窗口算法框架 */
void slidingWindow(string s) {
    unordered_map<char, int> window;
    
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

/76.最小覆盖子串

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
class Solution {
    Map<Character,Integer> need = new HashMap<>();
    Map<Character,Integer> tmp = new HashMap<>();
    public String minWindow(String s, String t) {
        for (char c : t.toCharArray()) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left=0,right=0;
        int start=0,len=Integer.MAX_VALUE;
        int cns = 0;
        String ans = "";
        while (right<s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                tmp.put(c,tmp.getOrDefault(c,0)+1);
                if (need.get(c)>=tmp.get(c)) {
                    cns++;
                }
            }
            // System.out.println(cns);
            // System.out.println("left"+left+"--"+"right"+right);
            while (cns==t.length()) {
                if (right-left<len-start) {
                    start = left;
                    len = right;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    // 注意判断字符串相等的时候 这里是equals
                    if (need.get(d).equals(tmp.get(d))){cns--;}
                    tmp.put(d,tmp.get(d)-1);
                }
            }
        }
        // System.out.print(start+"-"+len);
        return len-start==Integer.MAX_VALUE?"":s.substring(start,len);
    }
}

（灵神模板）

周赛失利就是忘掉 tmp这个周转元素了

把right 先丢到下面写吧

前缀和 和 差分技巧

前缀和 多次离线query 快速求一个区间的元素 和快速 求[i,j]的元素和 prefix[j] - prefix[i-1] i!=0

差分 多次离线query 操作一个数组加数或者减数 让[i,j]区间＋1 diff[i]++;diff[j+1]–;

class PrefixSum {
// 前缀和数组
private int[] prefix;

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 输入一个数组，构造前缀和 */
public PrefixSum(int[] nums) {
    prefix = new int[nums.length + 1];
    // 计算 nums 的累加和
    for (int i = 1; i < prefix.length; i++) {
        prefix[i] = prefix[i - 1] + nums[i - 1];
    }
}

/* 查询闭区间 [i, j] 的累加和 */
public int query(int i, int j) {
    return prefix[j + 1] - prefix[i];
}
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
// 差分数组工具类
class Difference {
    // 差分数组
    private int[] diff;

/* 输入一个初始数组，区间操作将在这个数组上进行 */
public Difference(int[] nums) {
    assert nums.length > 0;
    diff = new int[nums.length];
    // 根据初始数组构造差分数组
    diff[0] = nums[0];
    for (int i = 1; i < nums.length; i++) {
        diff[i] = nums[i] - nums[i - 1];
    }
}

/* 给闭区间 [i, j] 增加 val（可以是负数）*/
public void increment(int i, int j, int val) {
    diff[i] += val;
    if (j + 1 < diff.length) {
        diff[j + 1] -= val;
    }
}

/* 返回结果数组 */
public int[] result() {
    int[] res = new int[diff.length];
    // 根据差分数组构造结果数组
    res[0] = diff[0];
    for (int i = 1; i < diff.length; i++) {
        res[i] = res[i - 1] + diff[i];
    }
    return res;
}
}

1094 拼车 差分 再 前缀和 就会得到 原数组 （差分要注意越界）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] ans = new int[n];
        for (int i=0;i<bookings.length;i++) {
            int first = bookings[i][0]-1;
            int last = bookings[i][1]-1;
            int seat = bookings[i][2];
            ans[first] += seat;
            if (last+1<n) {
                ans[last+1]-= seat;
            }
        }
        int sum = 0;
        for (int i=0;i<ans.length;i++) {
            sum+=ans[i];
            ans[i] = sum;
        }
        return ans;
    }
}

排序

桶排序

位运算

\1356. 根据数字二进制下 1 的数目排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] sortByBits(int[] arr) {
        int[] map = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            map[i] = Integer.bitCount(arr[i]) * 10000000 + arr[i];
        }
        Arrays.sort(map);
        for (int i = 0; i < map.length; i++) {
            map[i] = map[i] % 10000000;
        }
        return map;
    }
    // a&(a-1)完成功能:去掉a右边1 例:a=110，则： a&(a-1) = 100
    private int getCount(int a) {
        int t = 0;
        while (a != 0) {
            a &= a-1;
            t++;
        }
        return t;
    }
}

第二种解决办法

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
class Solution {
    public int[] sortByBits(int[] arr) {
        List<Integer> list = new ArrayList<Integer>();
        for (int x : arr) {
            list.add(x);
        }
        int[] bit = new int[10001];
        for (int i = 1; i <= 10000; ++i) {
            bit[i] = bit[i >> 1] + (i & 1);
        }
        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer x, Integer y) {
                if (bit[x] != bit[y]) {
                    return bit[x] - bit[y];
                } else {
                    return x - y;
                }
            }
        });
        for (int i = 0; i < arr.length; ++i) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int totalFruit(int[] fruits) {
        int left = 0,right = 0 ,ans = 0;
        int length = fruits.length;
        Map<Integer,Integer> map = new HashMap<>();
        for (right = 0;right < length;right++) {
            map.put(fruits[right],map.getOrDefault(fruits[right],0)+1);
            while (map.size()>2) {
                map.put(fruits[left],map.get(fruits[left])-1);
                if (map.get(fruits[left])==0) {
                    map.remove(fruits[left]);
                }
                left++;
            }
            ans = Math.max(right-left+1,ans);
        }
        return ans;
    }
}

Trie树

\208. 实现 Trie (前缀树)

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
class Trie {
    class TrieNode {
        boolean isEnd;
        TrieNode[] next;
        public TrieNode() {
            isEnd = false;
            next = new TrieNode[26];
        }
    }
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            if (node.next[c-'a']==null) {
                node.next[c-'a'] = new TrieNode();
            }
            node = node.next[c-'a'];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            node = node.next[c-'a'];
            if (node==null) {
                return false;
            }
        }
        return node.isEnd;

    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char c : prefix.toCharArray()) {
            if (node.next[c-'a']==null) {
                return false;
            }
            node = node.next[c-'a'];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

排序

桶排序

剑指 Offer II 057. 值和下标之差都在给定的范围内

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
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int n = nums.length;

        //桶的大小为t+1，允许最大元素和最小元素之差为t
        long w = (long) t + 1;

        //因为一个桶有两个元素就会返回true，因此一个桶只有一个元素，可以用哈希表的一条key-value表示桶
        Map<Long, Long> map = new HashMap<Long, Long>();

        for (int i = 0; i < n; i++) {
            long id = getID(nums[i], w);

            //桶里已有元素x，nums[i]和x同属一个桶，值符合范围
            //只保留下标 i 之前的 k 个元素，因此下标也符合范围
            //桶有两个元素就会返回，因此一个桶只有一个元素
            if (map.containsKey(id)) {
                return true;
            }

            //前一个桶有一个元素，并且值的范围符合要求
            if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
                return true;
            }

            //后一个桶有一个元素，并且值的范围符合要求
            if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                return true;
            }

            //没有和nums[i]匹配的元素，把nums[i]加入自己的桶里
            map.put(id, (long) nums[i]);

            //下标范围[i-k+1, i]，从nums[i-k]所在桶移除元素
            if (i >= k) {
                map.remove(getID(nums[i - k], w));
            }
        }
        return false;
    }

    public long getID(long x, long w) {
        //非负数区间，如[0, t] 会被归到 id=0
        //其余的区间，如[(n-1)t+1, nt+1]，每t+1个元素会被归到 id = n-1
        if (x >= 0) {
            return x / w;
        }

        //负数区间，如[-t, -1] 会被归到 id=-1
        //其余的区间，如[-(n+1)t-1, -nt-1]，每t+1个元素会被归到 id = -(n+1)
        return (x + 1) / w - 1;
    }
}

动态规划

\931. 下降路径最小和

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
class Solution {
    int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int res = Integer.MAX_VALUE;
    // 备忘录里的值初始化为 66666
    memo = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(memo[i], 66666);
    }
    // 终点可能在 matrix[n-1] 的任意一列
    for (int j = 0; j < n; j++) {
        res = Math.min(res, dp(matrix, n - 1, j));
    }
    return res;
}

// 备忘录
int[][] memo;

int dp(int[][] matrix, int i, int j) {
    // 1、索引合法性检查
    if (i < 0 || j < 0 ||
        i >= matrix.length ||
        j >= matrix[0].length) {
        
        return 99999;
    }
    // 2、base case
    if (i == 0) {
        return matrix[0][j];
    }
    // 3、查找备忘录，防止重复计算
    if (memo[i][j] != 66666) {
        return memo[i][j];
    }
    // 进行状态转移
    memo[i][j] = matrix[i][j] + min(
            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        );
    return memo[i][j];
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}
}

\813. 最大平均值和的分组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        // dp[i][j] 将i个元素分为j个组的最大值
        int n = nums.length;
        double [][] dp = new double[n+10][k+10];
        double [] sum = new double[n+10];
        for (int i=1;i<=n;i++) sum[i] = sum[i-1] + nums[i-1];
        for (int i=1;i <= n;i++) {
            for (int j=1;j<=Math.min(i,k);j++) {
                if (j==1) {dp[i][1] = sum[i]/i;}
                else{
                for (int m = 2;m<=i;m++) {
                    dp[i][j] = Math.max(dp[i][j],dp[m-1][j-1]+(sum[i]-sum[m-1])/(i-m+1));
                }
            }
            } 
        }
        return dp[n][k];
    }
}

路径问题

\64. 最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        for (int i=0;i<m;i++) {
            for (int j=0;j<n;j++) {
                if (i==0&&j==0) dp[i][j] = grid[i][j];
                else if (i==0) dp[i][j] = dp[i][j-1] + grid[i][j];
                else if (j==0) dp[i][j] = dp[i-1][j] + grid[i][j];
                else dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
}

\120. 三角形最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(m-1).size();
        int[][] dp = new int[m][n];
        for (int i=0;i<m;i++) {
            Arrays.fill(dp[i],100001);
        }
        dp[0][0] = triangle.get(0).get(0);
        for (int i=1;i<m;i++) {
            for (int j=0;j<i+1;j++) {
                if (j-1<0) dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
                else dp[i][j] = Math.min(dp[i-1][j],dp[i-1][j-1]) + triangle.get(i).get(j);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i=0;i<n;i++) {
            min = Math.min(min,dp[m-1][i]);
        }
        return min;
    }
}

空间压缩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        int n = triangle.get(m-1).size();
        int[][] dp = new int[2][n];
        for (int i=0;i<2;i++) {
            Arrays.fill(dp[i],100001);
        }
        dp[0][0] = triangle.get(0).get(0);
        for (int i=1;i<m;i++) {
            for (int j=0;j<i+1;j++) {
                if (j-1<0) dp[i&1][j] = dp[(i-1)&1][j] + triangle.get(i).get(j);
                else dp[i&1][j] = Math.min(dp[(i-1)&1][j],dp[(i-1)&1][j-1]) + triangle.get(i).get(j);
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i=0;i<n;i++) {
            min = Math.min(min,dp[(m-1)&1][i]);
        }
        return min;
    }
}

有序表

红黑树 SB树(叔侄Size) AVL树（平衡） 跳表（概率）

左旋 右旋 LL，RR（一次）LR，RL(两次 按着字母顺序 )

[(68条消息) 有序表TreeMap/TreeSet底层实现：AVL树、傻逼树SBT、红黑树RBT、跳表SkipMap失衡类型_冰露可乐的博客-CSDN博客](https://blog.csdn.net/weixin_46838716/article/details/125019440?ops_request_misc=%7B%22request%5Fid%22%3A%22167367213716800215071854%22%2C%22scm%22%3A%2220140713.130102334.pc%5Fall.%22%7D&request_id=167367213716800215071854&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-1-125019440-null-null.142^v71^wechat_v2,201^v4^add_ask&utm_term=红黑树 SB树(叔侄Size) AVL树（平衡） 跳表)

17.基础提升 暴力递归（下）等_哔哩哔哩_bilibili

习题1 剑指 Offer II 058. 日程表

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
class MyCalendar {
    TreeMap<Integer,Integer> tmap;
    public MyCalendar() {
        tmap = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        Map.Entry<Integer,Integer> floorEntry = tmap.floorEntry(start);
        Map.Entry<Integer,Integer> ceilingEntry = tmap.ceilingEntry(start);
        if (floorEntry!=null) {
            if (floorEntry.getValue()>start) {
                return false;
            }
        }
        if (ceilingEntry!=null) {
            if (ceilingEntry.getKey() < end) {
                return false;
            }
        }
        tmap.put(start,end);
        return true;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

\1146. 快照数组

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
class SnapshotArray {
    List<TreeMap<Integer,Integer>> res;
    int snap;
    public SnapshotArray(int length) {
        snap = 0;
        res = new ArrayList<>();
        for (int i=0;i<length;i++) {
            // 次数 + val
            res.add(new TreeMap<>());
        }
    }
    public void set(int index, int val) {
        res.get(index).put(snap,val);
    }
    public int snap() {
        return snap++;
    }
    public int get(int index, int snap_id) {
        return res.get(index).floorKey(snap_id)==null?0:res.get(index).get(res.get(index).floorKey(snap_id));
    }
}

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray obj = new SnapshotArray(length);
 * obj.set(index,val);
 * int param_2 = obj.snap();
 * int param_3 = obj.get(index,snap_id);
 */

差分-二维-一维

API

lamada表达式

1
2
3
4
5
6
7
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>(){
            @Override
            public int compare(int[] a,int[] b) {
                if (a[2]==b[2]) return a[0] - b[0];
                else return a[2] - b[2];
            }
        });

简化

1
2
3
4
5
PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });

Stream

boxed 将基本类型转为包装类

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
class Solution {
    private int cntInt(int val){
        int count = 0;
        while(val > 0) {
            val = val & (val - 1);
            count ++;
        }
        return count;
    }
    public int[] sortByBits(int[] arr) {
        // boxed用法
      return Arrays.stream(arr).boxed()
            .sorted(new Comparator<Integer>(){
                @Override
                public int compare(Integer o1, Integer o2) {
                    int cnt1 = cntInt(o1);
                    int cnt2 = cntInt(o2);
                    // 写的不错 Integer.compare(a,b)
                    return (cnt1 == cnt2) ? Integer.compare(o1, o2) : Integer.compare(cnt1, cnt2);
                }
            })

            .mapToInt(Integer::valueOf)
            .toArray();
    }
    }


数组

1
System.arraycopy(srcArr,startIndex,baseArr,startIndex,length);

gcd

1
2
3
private int gcd (int a,int b) {
    return b==0?a:gcd(b,a%b);
}
1
2
3
4
5
6
7
private int gcd(int a, int b) {
        if (a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }

自己和自己的最大公因数就是自己本身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int subarrayGCD(int[] nums, int k) {
        int res = 0,n = nums.length;
        for (int i=0;i<n;i++) {
            int gcd = nums[i];
            for (int j=i;j<n;j++) {
                gcd = gcd(gcd,nums[j]);
                if (gcd==k) res++;
                else if (gcd==1) break;
            }
        }
        return res;
    }
    
    private int gcd(int a,int b) {
        return b==0?a:gcd(b,a%b);
    }
}

Arrays.sort()

1.对数组进行分类的时候，没有办法去降序排列

对于Integer 等非基本类型可以使用下面的接口来进行降序排列

1
Arrays.sort(arr,Collections.reverseOrder());

2.一个数组根据另一个数组排序的方法

1
Arrays.sort(qid, (i, j) -> queries[i][2] - queries[j][2]);

队列和栈

官方推荐使用Deque stack = new ArrayDeque<>();来实现栈

推荐使用Queue queue = new LinkedList<>();来实现队列

推荐使用Queue queue = new PriorityQueue<>();来实现优先队列

推荐使用Deque deque = new LinkedList<>();来实现双端队列

技巧使用Last模拟的是栈，使用First和Last搭配模拟的是队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//默认为小顶堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, (a,b)->a-b);
 
PriorityQueue<Integer> minHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
           @Override
           public int compare(Integer a, Integer b) {
               return a - b;
           }
 });
 
//大顶堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, (a,b)->b-a);
 
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>() {
           @Override
           public int compare(Integer a, Integer b) {
               return b - a;
           }
 });

向上取整和向下取整

1
(x + y - 1) / y

将连续多个字符二进制转化为十进制的方法

1
x = x<<1 | (s[r] & 1)

将n进制转化为十进制

1
2
public static int parseInt(String s,int radix)
Integer.parseInt(num,2);

十进制转化为二进制

1
Integer.toBinarySearch(num);