LeetCodeHot100刷题笔记

1for i in range(len(nums)):
2    for j in range(i+1, len(nums)):
3        if ... 
4# O(n^2)

1hashtable = dict()
2for i in range(len(nums)):
3    if nums[i] in hashtable:
4        return [i, hashtable[nums[i]]]
5    else:
6        hashtable[nums[i]] = i
7# 保存遍历过的元素，参考过去

 1HashMap<String, List<String>> hashTable = new HashMap<>();
 2for(String str : strs){
 3    char[] charArray = str.toCharArray(); // 将字符串转换为字符数组
 4    Arrays.sort(charArray); // 对字符数组进行排序
 5    String orderStr = new String(charArray);
 6    if (hashTable.containsKey(orderStr)) {
 7        hashTable.get(orderStr).add(str);
 8    }else {
 9        hashTable.put(orderStr, new ArrayList<>());
10        hashTable.get(orderStr).add(str);
11    }
12}
13
14List<List<String>> res = new ArrayList<>();
15
16for (Map.Entry<String, List<String>> entry : hashTable.entrySet()) {
17    res.add(entry.getValue());
18}
19return res;

 1HashSet<Integer> hashSet = new HashSet<>();
 2// 去重复，并且查询O(1)
 3for (int num : nums) {
 4    hashSet.add(num);
 5}
 6
 7List<Integer> start_nums = new ArrayList<>();
 8
 9// 找所有为起点的数
10for (Iterator<Integer> it = hashSet.iterator(); it.hasNext(); ) {
11    int num = it.next();
12    if (!hashSet.contains(num-1)){
13        start_nums.add(num);
14    }
15}
16
17// 遍历起点x, 遍历 x+1, x+2, ...
18int longest_length = 0;
19for(int start : start_nums){
20    int current_length = 1;
21    int start_i = start;
22    while (hashSet.contains(start_i+1)) {
23        current_length += 1;
24        start_i += 1;
25    }
26    if (current_length > longest_length){
27        longest_length = current_length;
28    }
29}
30return longest_length;
31}

 1if (nums.length == 1){
 2    return;
 3}
 4int i = 0;
 5int j = 1;
 6for (;j<nums.length;j++) {
 7    if (nums[i] == 0 && nums[j] != 0){
 8        nums[i] = nums[j];
 9        nums[j] = 0;
10    }
11    while (i<=j) {
12        if (nums[i] != 0) {
13            i+=1;
14        } else {
15            break;
16        }
17    }
18}
19for (;i<nums.length;i++) {
20    nums[i] = 0;
21}

 1// 左右双指针，area = h * w, h限制于最矮的边 <= 漏水
 2int i = 0;
 3int j = height.length - 1;
 4int max = 0;
 5while (i < j) {
 6    int h = 0;
 7    if (height[i] < height[j]) {
 8        h = height[i];
 9    } else {
10        h = height[j];
11    }
12    int area = h * (j - i);
13    if (area > max) {
14        max = area;
15    }
16    if (height[i] < height[j]) {
17        i += 1;
18    } else {
19        j -= 1;
20    }
21}
22return max;

 1// 固定a, b => c !!! 由于 nums[b]<=nums[c] 并且nums递增 c不比每次从末尾开始，因为b向右，则c向左。
 2Arrays.sort(nums);
 3ArrayList<List<Integer>> res = new ArrayList<>();
 4for (int a=0; a<nums.length-2; a++) {
 5    if (a-1>=0 && nums[a-1] == nums[a]) {
 6        continue;
 7    }
 8    if (nums[a] > 0){
 9        break;
10    }
11    // 最右侧
12    int c = nums.length-1;
13    for (int b=a+1; b<nums.length-1; b++) {
14        if (b-1>a && nums[b] == nums[b-1]) {
15            // b+=1;
16            continue;
17        }
18        int target = -nums[a] - nums[b];
19
20        while (b < c && target <= nums[c]) {
21            if (nums[a] + nums[b] + nums[c] == 0) {
22                List<Integer> temp = new ArrayList<>();
23                temp.add(nums[a]);
24                temp.add(nums[b]);
25                temp.add(nums[c]);
26                res.add(temp);
27                break;
28            }
29            c -= 1;
30        }
31    }
32}
33return res;

11. 先排个序 ⭐预处理
2for num : nums:
3   if num > 0: 后面不可能组合出负数来抵消
4   if 后面的数和当前值一样，且大于0：  3 3 3 ；跳过这部分
5   // 双指针
6   // num [num+1, ..., -1]
7   // 找符合的三元组
8   // 注意left|right可能跳过重复的数值(去重复)

 1// 暴力 => 分解为局部某小块[单位长度]聚水量
 2if (height.length < 3)
 3    return 0;
 4int ans = 0;
 5for (int i=1; i<height.length-1; i++) {
 6    int max_left = 0;
 7    // 左侧最大值
 8    for (int left=0; left<i; left++) {
 9        if (max_left < height[left])
10            max_left = height[left];
11    }
12    if (max_left < height[i]) {
13        continue;
14    }
15    int max_right = 0;
16    // 右侧最大值
17    for (int right=height.length-1; right>i; right--) {
18        if (max_right < height[right])
19            max_right = height[right];
20    }
21    if (max_left>height[i] && max_right>height[i]){
22        ans += Math.min(max_left, max_right) - height[i];
23    }
24}
25return ans;

 1if (height.length < 3)
 2            return 0;
 3// 预先存储每个位置的左右最大高，判断该位置是否能蓄水
 4int[] per_pos_left_max = new int[height.length];
 5per_pos_left_max[0] = 0;
 6int[] per_pos_right_max = new int[height.length];
 7per_pos_right_max[height.length-1] = 0;
 8
 9for (int i=1; i<height.length; i++) {
10    per_pos_left_max[i] = Math.max(per_pos_left_max[i-1], height[i-1]);
11}
12for (int i=height.length-2; i >= 0; i--) {
13    per_pos_right_max[i] = Math.max(per_pos_right_max[i+1], height[i+1]);
14}
15int ans = 0;
16for (int i=0; i<height.length; i++) {
17    int min = Math.min(per_pos_left_max[i], per_pos_right_max[i]);
18    if (min > height[i])
19        ans += min - height[i];
20}
21
22return ans;

 1char[] chars = s.toCharArray();
 2HashSet<Character> hashSet = new HashSet<>();
 3int res = 0;
 4for(int left=0, right=0; right<s.length(); right++) {
 5    char ch = chars[right];
 6
 7    while(hashSet.contains(ch)) {
 8        hashSet.remove(chars[left]);
 9        left+=1;
10    }
11
12    hashSet.add(ch);
13    res = Math.max(res, right - left + 1);
14}
15
16return res;

 1List<Integer> ans = new ArrayList<>();
 2
 3// 意外情况
 4if (s.length() < p.length()) {
 5    return ans;
 6}
 7
 8// 词频表 index-value == alpha-count
 9int[] sCount = new int[26];
10int[] pCount = new int[26];
11for (int i = 0; i < p.length(); i++) {
12    sCount[s.charAt(i) - 'a'] += 1;
13    pCount[p.charAt(i) - 'a'] += 1;
14}
15// 首个异构词
16if (Arrays.equals(sCount, pCount)) {
17    ans.add(0);
18}
19
20int left = 0;
21int right = p.length()-1;
22for(int i=0; i<s.length()-p.length(); i++) {
23    // 左侧出界
24    sCount[s.charAt(left) - 'a'] -= 1;
25    left += 1;
26    // 右边界添加新元素
27    right += 1;
28    sCount[s.charAt(right) - 'a'] += 1;
29
30    if (Arrays.equals(sCount, pCount)) {
31        ans.add(left);
32    }
33}
34
35return ans;

 1public static int subarraySum(int[] nums, int k) {
 2    int count = 0;
 3    // preSum -> count
 4    HashMap<Integer, Integer> preSum = new HashMap<>();
 5    preSum.put(0, 1);
 6    int sum = 0;
 7    for (int i = 0; i < nums.length; i++) {
 8        sum += nums[i];
 9        if (preSum.containsKey(sum - k)) {
10            count += preSum.get(sum - k);
11        }
12        preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
13    }
14
15    return count;
16}

 1int n = nums.length;
 2int ans_idx = 0;
 3int[] ans = new int[n-k+1];
 4
 5Deque<Integer> deque = new LinkedList<>(); // 存储下标就行
 6// 第一个窗口
 7for (int i = 0; i < k; i++) {
 8    while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
 9        deque.removeLast();
10    }
11    deque.offerLast(i);
12}
13
14ans[ans_idx++] = nums[deque.peekFirst()];
15// 开始移动
16for (int i = k; i < n; i++) {
17    while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
18        deque.removeLast();
19    }
20    deque.offerLast(i);
21
22    while (deque.peekFirst() < i-k+1) {
23        deque.removeFirst();
24    }
25    ans[ans_idx++] = nums[deque.peekFirst()];
26}
27return ans;

 1public boolean isCovered(Map<Character, Integer> targetMap, Map<Character, Integer> curMap) {
 2    Set<Character> keySet = targetMap.keySet();
 3    for (Character key : keySet) {
 4        Integer tgt = targetMap.getOrDefault(key, 0);
 5        Integer crt = curMap.getOrDefault(key, 0);
 6        if (tgt > crt)
 7            return false;
 8    }
 9    return true;
10}
11
12public String minWindow(String s, String t) {
13    Map<Character, Integer> targetMap = new HashMap<>();
14    Map<Character, Integer> curMap = new HashMap<>();
15
16    for (int i = 0; i < t.length(); i++) {
17        char c = t.charAt(i);
18        targetMap.put(c, targetMap.getOrDefault(c, 0)+1);
19    }
20    int minLen = Integer.MAX_VALUE; int startLoc = 0;
21    int left = 0, right = 0;
22    for (right = 0; right < s.length(); right++) {
23        char c = s.charAt(right);
24        curMap.put(c, curMap.getOrDefault(c, 0)+1);
25        while (isCovered(targetMap, curMap)) {
26            if (minLen > (right - left)){
27                minLen = right - left;
28                startLoc = left;
29            }
30            char ch = s.charAt(left);
31            curMap.put(ch, curMap.get(ch)-1);
32            left += 1;
33        }
34    }
35
36    if (minLen < Integer.MAX_VALUE) return s.substring(startLoc, startLoc+minLen+1);
37    else return "";
38}

 1public String minWindow(String s, String t) {
 2    Map<Character, Integer> targetMap = new HashMap<>();
 3    Map<Character, Integer> curMap = new HashMap<>();
 4
 5    for (int i = 0; i < t.length(); i++) {
 6        char c = t.charAt(i);
 7        targetMap.put(c, targetMap.getOrDefault(c, 0) + 1);
 8    }
 9    int minLen = Integer.MAX_VALUE; int startLoc = 0;
10    int curLen = 0; int tgtLen = targetMap.keySet().size();
11    int left = 0, right;
12
13    for (right = 0; right < s.length(); right++) {
14        char c = s.charAt(right);
15        if (targetMap.containsKey(c)) {
16            curMap.put(c, curMap.getOrDefault(c, 0)+1);
17            if (targetMap.get(c).equals(curMap.get(c))) {
18                curLen += 1;
19            }
20        }
21        while (curLen == tgtLen) {
22            if (minLen > (right-left)){
23                minLen = right-left;
24                startLoc = left;
25            }
26            char ch = s.charAt(left);
27            if (curMap.containsKey(ch)) {
28                curMap.put(ch, curMap.get(ch)-1);
29                if (curMap.get(ch) < targetMap.get(ch))
30                    curLen -=1;
31            }
32            left += 1;
33        }
34    }
35
36    if (minLen < Integer.MAX_VALUE) return s.substring(startLoc, startLoc+minLen+1);
37    else return "";
38}

 1// 例 [-2,4,5,-1][-1,2,3,-4]
 2// l:{
 3//	iSum=6,lSum=7,rSum=8,mSum=9
 4// }
 5// r:{
 6//	iSum=0,lSum=4,rSum=1,mSum=5
 7// }
 8public class Status {
 9    public int iSum, lSum, rSum, mSum;
10
11    public Status(int iSum, int lSum, int rSum, int mSum) {
12        this.iSum = iSum;  // 区间总和
13        this.lSum = lSum;  // 区间从左边界开始最大和
14        this.rSum = rSum;  // 区间从右边界开始最大和
15        this.mSum = mSum;  // 区间最大和
16    }
17}
18
19public Status getMaxSum(int[] nums, int start, int end) {
20    if (start == end) {
21        return new Status(nums[start], nums[start], nums[start], nums[start]);
22    }
23    int mid = (start + end) >> 1;
24    Status l = getMaxSum(nums, start, mid);
25    Status r = getMaxSum(nums, mid+1, end);
26    return popPush(l, r);
27}
28
29// 
30public Status pushUp(Status l, Status r) {
31    int iSum = l.iSum + r.iSum;  // 区间总和
32    // 1. [x?][??] or [xx][x?]
33    int lSum = Math.max(l.lSum, l.iSum+r.lSum);  
34    // 2. [??][?x] or [?x][xx] 
35    int rSum = Math.max(r.rSum, l.rSum+r.iSum);  
36    // 1. [?xx?][???] 2. [???][?xx?] 3. [?xx][xx?]
37    int mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum+r.lSum); 
38    return new Status(iSum,lSum,rSum,mSum);
39}
40
41public int maxSubArray(int[] nums) {
42    return getMaxSum(nums, 0, nums.length-1).mSum;
43}

 1// 传递给方法的是引用的拷贝，而不是引用本身
 2public void rotate(int[] nums, int k) {
 3	int n = nums.length;
 4    int[] ans = new int[n];
 5    // ...
 6    nums = ans; //❌❌❌ nums的引用是原数组引用的拷贝
 7}
 8
 9例：  a -> [???] 
10    rotate(a) => rotate(nums) {
11    // nums->[???]<-a
12}
13// nums != a

 1使用额外标记数组 col,row 标识某列\行是否存在0，刷新为0的col或row
 2		   col: 0,1,0   row    判断 mark col[0][j]==0 || row[i][0]==0
 3输入：matrix = [[1,1,1],  0
 4               [1,0,1],  1
 5               [1,1,1]]  0
 6额外空间=> O(M+N)
 7输出：[[1,0,1],
 8      [0,0,0],
 9      [1,0,1]]
10    
11利用第一行和第一列充当标记数组，并且使用两个变量标识第一列行是否刷为0 空间复杂度O(1)
12                1 1 1
13 输入：matrix =  1[0,1]
14                1[1,1]

1思路： 定义四个边界 top,bottm,left,right
2while() {
3    1.for ➡️ 并且更新边界 + 判断是否退出
4    2.for ⬇️
5    3.for ⬅️
6    4.for ⬆️
7}

11 2 3 4     
22 y z 5
33 x k 6
45 6 7 8    
5    
6分步 先旋转外围 再逐层往内进行旋转
7x ➡️ x    
8⬆️  ⬇️
9x ⬅️ x    

 1int len = matrix.length;
 2int count = len - 2 > 0?len - 2:1;
 3for (int i = 0; i < count; i++) {
 4    int left=i, top=i, right=len-1-i, bottom=len-1-i;
 5    for (int j = i; j < len-i-1; j++) {
 6        int temp1, temp2;
 7        // 1. matrix[top][left]
 8        temp1 = matrix[top][len-1-i];
 9        matrix[top][len-1-i] = matrix[i][left];
10
11        // 2. matrix[top][right]
12        temp2 = matrix[len-1-i][right];
13        matrix[len-1-i][right] = temp1;
14
15        // 3. matrix[bottom][right]
16        temp1 = matrix[bottom][i];
17        matrix[bottom][i] = temp2;
18
19        // 4. matrix[bottom][left]
20        matrix[i][left] = temp1;
21
22        // move
23        left += 1;
24        top += 1;
25        right -= 1;
26        bottom -= 1;
27    }
28}

1// small<-medium->large
2[1,4,7,11,{15⭐}]                 small<- medium
3[2,5,8,12,19]                               ⬇
4[3,6,9,16,22]                              large

 1head => 环入口       记为x
 2第一次相遇点 => 环入口 记为z
 3环入口 => 第一次相遇点 记为y
 4
 5快慢指针 
 6slow(单步)： x+y
 7fast(双步)： x+y + n(y+z)  // 多绕了n圈
 8
 9通过步数建立等式
10
112(x+y) = x+y + n(y+z)
12x+y = n(y+z)
13x = n(y+z) - y
14x = (n-1)(y+z) + z  # 当只绕一圈相遇时 n=1
15x = z
16
17第一次相遇点到入口的距离 == 起点到入口的距离 ⭐⭐⭐

 1public ListNode detectCycle(ListNode head) {
 2    ListNode fast = head;
 3    ListNode slow = head;
 4    while (fast != null && fast.next != null) {
 5        fast = fast.next.next;
 6        slow = slow.next;
 7
 8        if (fast == slow) {
 9            ListNode index1 = head;
10            ListNode index2 = fast;
11            while (index1 != index2) {
12                index1 = index1.next;
13                index2 = index2.next;
14            }
15
16            return index1;
17        }
18    }
19    return null;
20}

1// 暴力
2// for(nodeA: A)
3//   for(nodeB: B)  => nodeA?nodeB
4// 利用空间替换时间 => 查找时间利用hashSet O(1)
5// All nodeA => hashSet
6// for(nodeB:B) nodeB?hashSet

1X-?-?-√-√-√
2?-?-?-√-√-√
3同时遍历
4or
5从尾部开始？ 知道第一个不相等的Node？   

1-lenA-
2       -lenC-
3-lenB-
4// A+C+B => 循环后 可视为 B+A+C
5// B+C+A                A+B+C

 1// 快慢指针：快一次走一步；慢一次走两步
 2head: 1-2-3-[3-2-1]-null 偶数
 3          p      q   
 4head: 1-2-3-4-[3-2-1]-null  奇数
 5            p          q
 6
 7head    - [1-2-3]    
 8newHead - [1-2-3] // 头插，逆序
 9判断完
10头插回去，进行复原

 1class LRUCache {
 2    class BiLinkedList {
 3        int key,val;
 4        BiLinkedList prev,next;
 5
 6        public BiLinkedList() {
 7        }
 8
 9        public BiLinkedList(int key, int val) {
10            this.key = key;
11            this.val = val;
12        }
13    }
14
15    private Map<Integer, BiLinkedList> map =  new HashMap<>();
16    private int capacity; // total
17    private int size; // current
18    private BiLinkedList head, tail;
19
20    public LRUCache(int capacity) {
21        this.capacity = capacity;
22        this.size = 0;
23        head = new BiLinkedList();
24        tail = new BiLinkedList();
25        head.next = tail;
26        tail.prev = head;
27    }
28
29    public int get(int key) {
30        // 访问 => 放表头
31        if (map.containsKey(key)) {
32            BiLinkedList node = map.get(key);
33            move2Head(node);
34            return node.val;
35        } else {
36            return -1;
37        }
38    }
39
40    public void put(int key, int value) {
41        // 修改 => 放表头
42        if (map.containsKey(key)) {
43            map.get(key).val = value;
44            move2Head(map.get(key));
45        }else {
46            // 新增
47            if (size >= capacity) {
48                BiLinkedList node = deleteTail();// map 也需要删除啊
49                map.remove(node.key);
50                size -= 1;
51            }
52            // 插入到表头
53            BiLinkedList node = insert2Head(key, value);
54            map.put(key, node);
55            size += 1;
56        }
57    }
58
59    public void move2Head(BiLinkedList node) {
60        node.prev.next = node.next;
61        node.next.prev = node.prev;
62
63        node.next = head.next;
64        node.prev = head;
65        head.next.prev = node;
66        head.next = node;
67    }
68
69    public BiLinkedList deleteTail() {
70        BiLinkedList node = tail.prev;
71        tail.prev.prev.next = tail;
72        tail.prev = tail.prev.prev;
73        return node;
74    }
75
76    public BiLinkedList insert2Head(int key, int value) {
77        BiLinkedList node = new BiLinkedList(key, value);
78        node.next = head.next;
79        node.prev = head;
80        head.next.prev = node;
81        head.next = node;
82        return node;
83    }
84}