leetcode and key points

link to leetcode company repo: https://github.com/youhusky/Leetcode_Company ref to detail solution in chinese: https://leetcode.wang/leetCode-30-Substring-with-Concatenation-of-All-Words.html !!!with time complexity for each problem

记住：

如果把这道题放到真实工程场景里，我会优先考虑数据规模、请求模式、并发情况和可维护性。
在这样的前提下，我选择的解法不仅满足复杂度最优，还能很好地扩展到高并发系统，并支持缓存/分布式等工程优化。

把 LeetCode 题抽象成真实业务：

• 这题像日志流分析？
• 某字段要去重？
• 找最大窗口代表限流？
• DP 表示预算规划？
• BFS 代表任务调度？

不仅说时间复杂度，还说：

• 是否能并行化
• 是否适用于大数据 / 流式处理 / 分布式
• 是否可以“增量计算”：仅重新计算那些依赖于已更改数据的新计算结果，从而在部分数据发生变化时显著节省计算时间。增量计算的常见示例包括电子表格中单元格的自动重算功能，只有直接或间接受影响的单元格才会被更新
• 是否会占用大量内存
• 代码可维护性高不高

你要明确：不是最优算法复杂度，是最优工程实现（可维护、可扩展、可 debug）

• 用缓存？
• 用索引？
• 用 bitset？
• 用分布式？

展示“算法 → 真正工程架构”的迁移能力。

1. 业务场景映射

   类似于电商系统：用户购物车中有 N 个商品和它们的价格，想知道是否有两个商品加起来恰好等于预算值。

2. 分析不同方案的工程代价

   解法 A：双指针（排序）

   会改变输入，破坏业务数据顺序。不能用在“流式数据”或变化中的列表，❌ 工程成本太高

   解法 B：Hash 映射（O(n)）

   只需要一遍扫描，空间换时间，易 debug，可以增量更新 ✔ 工程最佳实践

3. 为什么哈希表是工程上最优？

• 多线程下可以用 ConcurrentHashMap
• 大数据场景可以做分片哈希
• 流式数据中可以渐进构建 hash
• 数据更新时不需要重排数组

4. 真实系统优化

• 大量查询情况下可以加 缓存（LRU）
• 超大规模数据可以用 分布哈希 + 一致性哈希
• 若要控制内存，可用 BitMap + BloomFilter 做存在性快速过滤（亿级数据）

1. 业务映射

   缓存系统的基本模型（Redis、操作系统 Page Cache）。

2. 工程代价

   • 用 LinkedHashMap — 可维护性最强
   • 双向链表 + HashMap — 允许细粒度控制
   • 如果高并发 → 用 CAS + SegmentLock

3. 为什么选择双向链表 + HashMap？

   • O(1) 操作， 高性能， 可扩展到分布式缓存（多层缓存架构）

4. 真系统延伸

• 多线程必须考虑锁
• 分布式场景要解决缓存不一致，可引出：Redis + 本地缓存 、 Guava Cache 、 异步刷新

1. 业务映射

   • 类似 APM（性能监控）中：统计系统中某个时间窗口的最大性能波动值。

2. 工程代价

   • DP O(n) 是最优，不适合 MapReduce（因为子数组不能任意拆分）

3. 为什么选择 Kadane？

• 一遍扫描

• 常数内存

• 易扩展到 streaming

• 可以用于实时监控

4. 系统级优化

• 对多节点数据可用 中间结果：prefixMax, suffixMax, totalSum

• 可分治、可分片，支持离线大数据计算（Hadoop/Spark）

Note:

1. always start with:

        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        dummy.next = head;

        use curr to go through list and perform actions

        return dummy.next;

2. to delete a node: 不要跳过所求的node，停在那个node之前，才能skip desired node
3. when change order, always set tempNode = x.next, then change the node before x
4. always check, head != null
5. 虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，⽽递归解法需要堆栈，空间复杂度是 O(N),所以平时更推荐用迭代解法

note:

5. Two pointers:

    while(leftPointer< RightPointer) 
   

6. Peak and valley:

• when there are a simultaneously increasing or decreasing array
• ex. lc 135-Candy
• can use Stack

1. 框架：

    public int fn(int[] arr) {
        int left = 0, ans = 0, curr = 0;

        for (int right = 0; right < arr.length; right++) {
            // do logic here to add arr[right] to curr

            while (WINDOW_CONDITION_BROKEN) {
                // remove arr[left] from curr
                left++;
            }

            // update ans
        }

        return ans;
    }

problem: [lc3 - Longest Substring Without Repeating Characters](problems/lc3_longest_substring_without_repeating_char.java)
		 [lc 76 - Minimum Window Substring](problems/lc76-min-window-substr.java)
		 lc 239
		 lc 1040
		 lc 424
		 lc 567 !!! interesting sliding window
         lc 713 - subarray product less than k
         lc 992 - subarrays with k different integers
         google - block-with-min-distance
         lc 1074 - # of submatricies that sum to target
         lc 727 - interesting 2points
         lc 1423 - take first k or mid k or last k --> make it a circular array and do sliding window
         lc 1031 - max sum of 2 non-overlapping subarrays, prefix sum + sliding window

array-problem summary

array-key points

1. Arrays.toString(another_array[]);

2. Sort: Arrays.sort(nums);

    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
   

3. if have result = List<List>, then add to the result by: result.add(Arrays.asList(x,y, z......));

4. check array is empty: if (array.length == 0 || array == null)

5. Array length: int[] a --> a.length ArrayList b --> b.size() // because arraylist is a collection element

6. if need to return int[][] result, but don't know the size of result yet:

    List<int[]> res = new ArrayList<>();
    return res.toArray(new int[res.size()][]);
   

// length can be used for int[], double[], String[] // to know the length of the arrays.

// length() can be used for String, StringBuilder, etc // String class related Objects to know the length of the String

7. type --> Given an unsorted integer array, find the smallest missing positive integer in this range

   lc41, 442, 136

8. change from Arraylist to Array

    arrayListVar.stream().mapToInt(i -> i).toArray();
   

1. iterative method:

• same as swapping A and B

public ListNode reverseList(ListNode head) {
    
    //  1. Initialize 3 pointers: prev as NULL, curr as head, next as NULL.
    ListNode prev = null;
    ListNode next = null;
    ListNode curr = head;

    while (curr != null) {
        next = curr.next;               Before changing next of current, store next node
        curr.next = prev;               change next of current, this is where actual reversing happens
        prev = curr;                    Move prev and curr one step forward
        curr = next;
    }
    return prev;                        In last step, cur = null, and prev stores the last real node
}

2.Recursive Method:

1. Divide the list in two parts - first node and rest of the linked list.
2. Call reverse for the rest of the linked list.
3. Link rest to first.
4. Fix head pointer

  
public ListNode reverseList(ListNode head) {
    return reverseListInt(head, null);
}

private ListNode reverseListInt(ListNode head, ListNode prev) {
    if (head == null)
        return prev;
    ListNode next = head.next;
    head.next = prev;
    return reverseListInt(next, head);          !!! be careful with the order
}


---------
Node reverseUtil(Node curr, Node prev) 
    { 
  
        /* If last node mark it head*/
        if (curr.next == null) { 
            head = curr; 
  
            /* Update next to prev node */
            curr.next = prev; 
  
            return head; 
        } 
  
        /* Save curr->next node for recursive call */
        Node next1 = curr.next; 
  
        /* and update next ..*/
        curr.next = prev; 
  
        reverseUtil(next1, curr); 
        return head; 
    } 

Redo:

lc 430: flatten multilevel double linked list
lc 234: palindrome linked list

prev.next = current.next;

1. Always check if node == null
2. use 1 at the begining for any recursive/traversal problems

(刷到 835)

dp-problem summary

Notes:

1. when want to optimize space --> from m * n reduce to O(m), declare 2 rows only, prev & current, then use i % 2 to determine which row it is current

    boolean[][] dp = new boolean[2][pattern.length() + 1];
    dp[text.length() % 2][pattern.length()] = true;
    dp[i % 2][j] = dp[i % 2][j + 1] || first_match && dp[(i + 1) % 2][j];
   

2. good practise/optimize question

3. whenever we do sum, subtract, multiply or divide of integers, check overflow!

4. How to find loop:

   1. if dp[i][j] depends on dp[i-1][j-1] --> 需要知道比他小的dp for(i = 0, ....) for (j = 0, ....)

5. use bit mask to represent state --> more see Math section

我们只要在递归之前做出选择，在递归之后撤销刚才的选择

框架：

result = []
def backtrack(路路径, 选择列列表):
    if 满⾜足结束条件: 
        result.add(路路径)
    return

    for 选择 in 选择列列表: 
        做选择
        backtrack(路路径, 选择列列表) 
        撤销选择

如果有list all permutations的情况，比如 17. Letter Combinations of a Phone Number， 则不撤销选择，一直往前走

class Solution {
  Map<String, String> phone = new HashMap<String, String>() {{
    put("2", "abc");
    put("3", "def");
    put("4", "ghi");
    put("5", "jkl");
    put("6", "mno");
    put("7", "pqrs");
    put("8", "tuv");
    put("9", "wxyz");
  }};

  List<String> output = new ArrayList<String>();

  // main method
  public List<String> letterCombinations(String digits) {
    if (digits.length() != 0)
        backtrack("", digits);

    return output;
  }

  public void backtrack(String combination, String next_digits) {
    // if there is no more digits to check
    if (next_digits.length() == 0) {
      output.add(combination);
    }
    else {
      // iterate over all letters which map the next available digit
      String digit = next_digits.substring(0, 1);
      String letters = phone.get(digit);
      
      for (int i = 0; i < letters.length(); i++) {
        String letter = phone.get(digit).substring(i, i + 1);

        // append the current letter to the combination
        // and proceed to the next digits, substirng(1) means delete the first char in string
        backtrack(combination + letter, next_digits.substring(1));
      }
    }
  }

其实特别简单，只要稍微修改⼀一下回溯算法的代码即可:

// 函数找到⼀一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
    // 触发结束条件
    if (row == board.size()) {
            res.push_back(board);
            return true;
        }
        ...
        for (int col = 0; col < n; col++) {
            ...
            board[row][col] = 'Q';
            if (backtrack(board, row + 1))
                return true;
            board[row][col] = '.';
        }
    return false;
}

!! try RECURSION first tree-problem summary

tree-key points

Tree problems and tricks

• Trie：

  • please see tree problems note pad.
  • can also be solved by hashmap??
  • problem list: lc 421: use search to do XOR lc 208: implement trie lc 336: palindrome lc 1065: lc 720: lc 211: lc 648 lc 677: lc 642: auto-complete system 472. Concatenated Words 1268. Search Suggestions System 1032. stream of characters: store the search words in reverse per question's request

• Binary search tree: 257: Binary Tree Paths 450: Delete Node in a BST 1373 Maximum Sum BST in Binary Tree 98: BST, in order traversal !!!!!!!!

• Huffman algorithm --> greedy: 1199 min time to build blocks

(刷到1130)

1. Island problems:

   • use dfs / bfs / union find
   • when reach a '1', go to dfs function
     • in dfs: 1) check for validility, 2) mark current position to a 0, 3) call dfs on neigbors
   • water flood fill lc 1254: num of closed islands lc 695: max area of island

2. Double end bfs: lc 752: open the lock

   have 2 hashSet: begin, end The whole process is like: Running BFS in 'begin' set -----> Create a new set 'temp' to store the value -----> begin = temp -----> 'begin'(is 'temp' now) and 'end' exchange value ------> (next loop) Running BFS in 'end'(is now 'begin')

   Caution: for 2 end bfs, need to maintain a global set visited in order to not let 2 ends into looping

3. represent visited/unvisited node state: use int mask

    for (int next : graph[node.id])
        Node nextNode = new Node(next, node.mask | (1 << next));
   

question summary

Interesting binary search problems:

lc 1011
lc 875
lc 774
lc 410 --> value 
lc 74
lc 1231
lc 162 - Find Peak Element - Medium

Tricks:

1. Sorting Algorithm:

   Arrays.sort() used to sort elements of a array. Collections.sort() used to sort elements of a collection.

For primitives, Arrays.sort() uses dual pivot quicksort algorithms.

2. Searching Algorithm:

   Arrays.binarySearch(array,key)) used to apply binary search on an sorted array. Collections.binarySearch() used to apply binary search on a collection based on comparators.

            int i = Arrays.binarySearch(dp, 0, len, num);   // search in entire array
            int i = Arrays.binarySearch(int[] arr, int fromIndex, int toIndex, int key) // in subarray

            if (i < 0) {
                i = -(i + 1);
            }

注意：

1. ”maximize the minimum" or "minimize the maximum“ 就是binary search解法！

2. 三种情况不同的只需要改两行：

• 1. 找到target的时候，左侧边界right = mid - 1;右侧边界left = mid + 1
• 2. 最后的返回条件，左侧边界检查左侧越界情况

    左侧
        if (left >= nums.length || nums[left] != target) return -1， 

    右侧
        if (right < 0 || nums[right] != target) return -1;

if you use while (lo <= hi) you use lo=mid+1 and hi=mid-1

if you use while (lo < hi) you use lo = mid+1 and hi=mid

3. 最后 return left 还是 right，取决于：循环结束时，哪一个指针“一定满足你要找的条件”

• 二分不是在找“位置”，而是在找 第一个 / 最后一个满足某个 predicate 的点。
• 第一个满足条件的, return left
• 最后一个满足条件的, return right

🟢 例 1：LeetCode 704（标准找值

• 在一个已排序（升序）的整数数组 nums 中搜索一个目标值 target，如果找到，返回其索引；如果没找到，返回 -1

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) 
            l = mid + 1;
        else 
            r = mid - 1;
    }
    return -1;

👉 这是“精确命中”，找不到就 -1，不涉及 return left/right

🟡 例 2：第一个 ≥ target（Lower Bound） nums = [1,2,4,4,5],target = 4,答案是 index = 2

    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] >= target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return l;

循环结束时,l 指向第一个满足条件的：

         r | l
           ↓
[ < target ][ >= target ]

🟡 例 3：最后一个 ≤ target（Upper Bound）

• return r？

结束状态：

[ <= target ][ > target ]
           ↑
           r

👉 r 是 最后一个合法的

🔴 例 4：二分答案（最重要的面试场景）

典型题：

• Capacity To Ship Packages

• Koko Eating Bananas

• Minimum Speed / Maximum Value

LeetCode 875 — Koko Eating Bananas

问题：

• piles = [3, 6, 7, 11]， h = 8 小时，每小时吃 k 根香蕉，问：最小的 k 是多少？

🔍 我们二分的不是数组，而是「答案空间」

k = 1  → 吃得太慢 ❌
k = 2  → ❌
k = 3  → ❌
k = 4  → ✅
k = 5  → ✅
k = 6  → ✅

👉 明显单调，所以可以二分：

false false false true true true

1️⃣ 搜索区间

• left = 1
• right = max(piles) = 11

2️⃣ 判定函数

    boolean canEat(int k) {
        int hours = 0;
        for (int p : piles) {
            hours += (p + k - 1) / k; // 向上取整
        }
        return hours <= h;
    }

完整二分过程（逐步动画）

🟢 Step 1

• l = 1, r = 11
• mid = 6
• 算 canEat(6)：总 = 6 ≤ 8 ✅

👉 mid 可行 → 向左找更小的： r = mid - 1 = 5

🟢 Step 2

• l = 1, r = 5
• mid = 3

3/3=1 6/3=2 7/3=3 11/3=4 总 = 10 > 8 ❌

👉 不可行 → 速度太慢 → 向右： l = mid + 1 = 4

🟢 Step 3

• l = 4, r = 5
• mid = 4

3/4=1 6/4=2 7/4=2 11/4=3 总 = 8 ≤ 8 ✅

👉 可行 → 再试更小

r = mid - 1 = 3

🛑 结束条件 l = 4, r = 3 l > r → loop ends

为什么最后 return left？

    k: 1  2  3  4  5  6 ...
       ❌ ❌ ❌ ✅ ✅ ✅
               ↑
             left


    right = 3 → 最后一个 ❌

    left = 4 → 第一个 ✅

👉 题目要的是：最小可行解, 所以 return left; // 4

1. 最基本的二分查找算法

因为我们只需找到⼀个 target 的索引即可 所以当 nums[mid] == target 时可以立即返回

    int binary_search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;

        while(left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } 
            else if (nums[mid] > target) {
                right = mid - 1;
            } 
            else if(nums[mid] == target) { // 直接返回
                return mid; 
            }
        }
    // 直接返回
    return -1; 
    }

2. 寻找左侧边界的二分搜索

   因为我们需找到 target 的最右侧索引 所以当 nums[mid] == target 时不要立即返回 ⽽要收紧左侧边界 以锁定右侧边界

    int left_bound(int[] nums, int target) { 
        int left = 0, 
            right = nums.length - 1; 
        
        while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] < target) {
                // 搜索区间变为 [mid+1, right]
                    left = mid + 1;
                } 
                else if (nums[mid] > target) {
                // 搜索区间变为 [left, mid-1]
                    right = mid - 1;
                } 
                else if (nums[mid] == target) {
                // 收缩右侧边界，找到 target 时不要⽴即返回，⽽是缩小「搜索区间」的上界 right ，在区间 [left, mid) 中 继续搜索，即不断向左收缩，达到锁定左侧边界的目的
                    right = mid - 1;
                }
        }
        // 检查出界情况
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }

3. 寻找右侧边界的二分查找

    int right_bound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } 
            
            else if (nums[mid] > target) {
                right = mid - 1;
            } 

            else if (nums[mid] == target) { // 这⾥改成收缩左侧边界即可
                left = mid + 1;
            } 
        }
        // 这⾥改为检查 right 越界的情况，⻅见下图
        if (right < 0 || nums[right] != target)
            return -1;
        
        return right;
    }

凡是符合单调性的，都可以用binary search

left & right为weight，比如left = array里最大的重量，right = 总重，binary search一个合适的重量mid such that满足某个条件，比如五天内运完所有货物

1011. Capacity To Ship Packages Within D Days - Medium
1012. Minimum Number of Days to Make m Bouquets
1013. Divide Chocolate

🟢 关键观察

容量越大，越容易在 D 天内运完；容量越小，越难。 👉 符合 单调性，所以可以用 二分搜索。

在算法题里，单调性通常指：

当某个参数 变大/变小 时，问题的可行性结果不会“跳来跳去”，而是保持 单调变化。

也就是说：如果参数满足某个条件，那么更大的参数（或更小的参数）也一定满足（或一定不满足）。

🟢 二分范围

最小容量 = max(weights)（至少能运得动最重的包裹）。

最大容量 = sum(weights)（一次性运完所有包裹）。

🟢 检查函数（贪心模拟）

给一个候选容量 cap，模拟装货过程：

从第一个包裹开始，依次累加重量；

如果加上下一个包裹超出 cap，则开新的一天（day++）；

最后检查天数是否 <= D。

如果 day <= D，说明容量够大，可以尝试减小； 否则说明容量太小，需要增加。

public int shipWithinDays(int[] weights, int D) {
        int beg=0;
        int end=0;

        for(int w:weights){
            beg = Math.max(beg,w);
            end +=w;
        }

        int ans = 0;
        while(beg <= end){
            int mid = beg + (end-beg)/2;
            int days = findDays(weights,mid);

            // with current mid, use less days then required, can further reduce capacity
            if(days <= D){
                end=mid-1;
                ans = mid;
            }
            else{
                beg=mid+1;
            }
        }
        return ans;
    }
 
    public int findDays(int a[],int capacity){
        int days=1;
        int sum=0;
        for(int x:a){
            sum=sum+x;
            //一天之内装不完，days++ 作为新的单独一天
            if(sum > capacity){
                days++;
                sum=x;
            }
        }
        return days;
    }

similar question: 410. Split Array Largest Sum - Hard

Note: binary search can be optimized by setting a close bound for left and right

        //最少一小时吃了1个香蕉，最后+1是margin of error
        int low = (int)((totalBanana-1)/hours) + 1;

        //如果length中每一个pile用一个小时吃，也要用这么多
        int high = (int)((totalBanana-length)/(hours-length+1)) + 1;

math summary

Tricks:

1. Calculating the most significant digit of number N:

   double K = Math.log10(N); K = K - Math.floor(K); int X = (int)Math.pow(10, K); X will be the most significant digit.

2. Calculating the # of digits directly:

   No. of digits in N = Math.floor(Math.log10(N)) + 1;

3. checking for a prime number: returns true if this BigInteger is probably prime(with some certainty), false if it’s definitely composite.

   BigInteger.valueOf(1235).isProbablePrime(1)

4. XOR:

    If we take XOR of zero and some bit, it will return that bit
        a⊕0=a
    If we take XOR of two same bits, it will return 0
        a⊕a=0
    
    a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
   

   public int singleNumber(int[] nums) { int a = 0; for (int i : nums) { a ^= i; } return a; }

5. bit mask (lc 1349)

• 0. use (1 << x) to set the x-th bit to one, ex. 1<< 2 = 2^2 = 4, 1<<3 = 2^3 = 8, ...

     Thus, we can use an int variable int mask to show the status of x workers

     1. check if the j-th worker is already being processed: if (mask & (1<<j)) == 0)

     2）set the j-th worker as 'already processed': mask | (1 << j)

     3）unset j-th bit
     used &= ~(1 << j) // (1<<3) = 100, ~(1 << 3) = 011, used = used & 011 // ex. used = 1100 now, 1100 & 011 = 1000, now we unset the 3rd bit to 0

• 1. We can use (x >> i) & 1 to get i-th bit in state x, where >> is the right shift operation. If we are doing this in an if statement (i.e. to check whether the i-th bit is 1), we can also use x & (1 << i), where the << is the left shift operation.
• 2. We can use (x & y) == x to check if x is a subset of y. The subset means every state in x could be 1 only if the corresponding state in y is 1.
• 3. We can use (x & (x >> 1)) == 0 to check if there are no adjancent valid states in x.

• 4. store pre-compute count in an array

     for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) validRows[i] = (validRows[i] << 1) + (seats[i][j] == '.' ? 1 : 0);

6. bit problem (lots of time only care about last digit, don't store entire number to avoid overflow): lc 190 --> reverse unsigned bits lc 1349 --> use bit and mask to check for upper left position, upper right position lc 868 --> binary gap

7. Bitwise operator:

Bitwise operator works on bits and performs bit-by-bit operation.

Assume if a = 60 and b = 13; now in binary format they will be as follows −

a = 0011 1100

b = 0000 1101

a&b = 0000 1100

a|b = 0011 1101

a^b = 0011 0001

~a = 1100 0011

• & (bitwise and) Binary AND Operator copies a bit to the result if it exists in both operands.
  (A & B) will give 12 which is 0000 1100

• | (bitwise or)
  Binary OR Operator copies a bit if it exists in either operand. (A | B) will give 61 which is 0011 1101

• ^ (bitwise XOR) Binary XOR Operator copies the bit if it is set in one operand but not both.
  (A ^ B) will give 49 which is 0011 0001

• ~ (bitwise compliment)
  Binary Ones Complement Operator is unary and has the effect of 'flipping' bits. (~A ) will give -61 which is 1100 0011 in 2's complement form due to a signed binary number.

• << (left shift) Binary Left Shift Operator. The left operands value is moved left by the number of bits specified by the right operand. A << 2 will give 240 which is 1111 0000

• (right shift)
  Binary Right Shift Operator. The left operands value is moved right by the number of bits specified by the right operand.
  A >> 2 will give 15 which is 1111

• (zero fill right shift) Shift right zero fill operator. The left operands value is moved right by the number of bits specified by the right operand and shifted values are filled up with zeros.
  A >>>2 will give 15 which is 0000 1111

• ex. flip 0 to 1, and 1 to 0 int x ^ 1 a = 0011 1100 --> a^1 = 1100 0011

V put(K key, V value)：插入键值对。如果 Key 已存在，覆盖旧值并返回旧值。

V get(Object key)：获取 Key 对应的值，不存在则返回 null。

V remove(Object key)：根据 Key 删除键值对。

boolean containsKey(Object key)：判断是否包含某个 Key。

int size()：返回当前键值对的数量。

void clear()：清空 Map。

• 用法：map.getOrDefault("ID_123", 0);

• 价值：避免了 null 指针检查，直接提供备选方案。

computeIfAbsent(K key, Function mappingFunction)

• 核心作用是：“如果指定的键（Key）不存在或值为 null，则通过给定的映射函数计算一个值，并将其放入 Map 中，最后返回这个值。”

• 场景：初始化集合。例如 map.computeIfAbsent("list", k -> new ArrayList<>()).add(item);

V value = map.computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction);

场景 A：初始化集合（构建多值 Map）

这是最常见的用法。例如，将学生按班级分组：

    Map<String, List<String>> classMap = new HashMap<>();

    // 逻辑：如果班级不存在，新建一个 ArrayList；然后把学生加进去
    classMap.computeIfAbsent("一班", k -> new ArrayList<>()).add("张三");
    classMap.computeIfAbsent("一班", k -> new ArrayList<>()).add("李四");

    // 结果：一班 -> [张三, 李四]

如果value是一个priority queue：

    HashMap<String, PriorityQueue<Food>>cuisineMap = new HashMap<>();
    
    cuisineMap.computeIfAbsent(cuisines[i], k ->
                new PriorityQueue<>((a, b) -> {
                    if (a.rating != b.rating) return b.rating - a.rating; // higher rating first
                    return a.name.compareTo(b.name);                     // lexicographically smaller first
                })
            ).add(food);

场景 B：本地缓存（Cache） 作为简单的内存缓存，避免重复计算：

Map<Integer, Integer> fibCache = new ConcurrentHashMap<>();

public int fibonacci(int n) {
    if (n <= 1) return n;
    return fibCache.computeIfAbsent(n, k -> fibonacci(k - 1) + fibonacci(k - 2));
}

如果 Value 是简单的常量，使用 putIfAbsent 更直观。

     HashMap<String, Integer> map = new HashMap<>(); 
     map.put("key5", 10000); 
     map.computeIfAbsent("key5", k -> 2000 + 3000); 

     不会放入(key5, 5000)因为 key1 已经有了

putIfAbsent(K key, V value)

• 场景：仅在 Key 不存在时插入，防止覆盖已有数据。

merge(K key, V value, BiFunction remappingFunction)

• 场景：计数器或合并逻辑。例如 map.merge(key, 1, Integer::sum);（如果不存在设为 1，存在则加 1）。

    for (Map.Entry<String, Integer> entry : map.entrySet()) {
        System.out.println(entry.getKey() + ": " + entry.getValue());
    }

Lambda 表达式（最简洁）：

• map.forEach((k, v) -> System.out.println(k + ": " + v));

仅遍历 Key 或 Value：

• map.keySet() 或 map.values()。

Notes:

	if (hashMap.getOrDefault(c, 0) != 0) {
	    return false;
	} else 
	    hashMap.put(c, 1);
	            

	!!getOrDefault(key, defaultValue): 当Map集合中有这个key时，就使用这个key值，如果没有就使用默认值defaultValue

if (!singleSet.add(board[i][j])) return false;

void putIfAbsence(path, value)

	Map<String, List<String>> map = new HashMap<String, List<String>>();
	Arrays.sort(strs);
	for (String s : strs) {
		char[] ca = s.toCharArray();
		Arrays.sort(ca);
		String keyStr = String.valueOf(ca);
		if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<String>());
			map.get(keyStr).add(s);
	}

3.create array with each hash map's value:

new ArrayList<List<String>>(hashmap.values())

4.store letter in hashmap:

	1. Map<Character, Integer> dictT = new HashMap<Character, Integer>();
        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }

!! another possibility --> if only characters or integers, use array as the hashmap !!

    2. int[] map = new int[256];
       for(char c: t.toCharArray()){
         map[c - 'A']++;
       }

2. Treemap.floorEntry(int key): return a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

Treemap.ceilingEntry(int key):return a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

Complexity: treemap guaranteed log(n) time cost for the containsKey, get, put and remove operations, and the implementation of floorEntry() is similar to the implementation of get() in terms of complexity.

Hashmap-problem summary https://note.youdao.com/web/#/file/WEB8268b1d897cef35a3e813ddfb5809e69/note/WEBe30238f51ab83c604d162dfa8a53492b/

1. length: string.length();

2. substring: string.substring(int startIndex, int endIndex) --> 不包含endindex，只到endIndex - 1 string.substring(int index): 保留这个index及其之后的所有letter ex. "abcde".substring(2) = "cde"

3. find the index within this string of the first occurrence of the specified character or -1, if the character does not occur.

   string.indexOf(String sub)

4. str.indexOf(char ch, int strt ): returns the index within this string of the first occurrence of the specified character, starting the search at the specified index or -1, if the character does not occur.

str.indexOf(String str, int strt) : This method returns the index within this string of the first occurrence of the specified substring, starting at the specified index. If it does not occur, -1 is returned.

str.indexOf(String str)

5. instead of using +: s.concat(String b)

6. split: String[] arrOfStr = str.split(":");

7. change from char[] to string

   // Method 1: Using String object char[] ch = {'g', 'o', 'o', 'd', ' ', 'm', 'o', 'r', 'n', 'i', 'n', 'g'}; String str = new String(ch);

   // Method 2: Using valueOf method String str2 = String.valueOf(ch);

8. regex:

   string.split("\(") --> \ means 'abc((((d' --> [abc,d] string.split("\.")

9. remove all special character:

   String text = "This - text ! has \ /allot # of % special % characters"; text = text.replaceAll("[^a-zA-Z0-9]", ""); System.out.println(text);

   String html = "This is bold"; html = html.replaceAll("[^a-zA-Z0-9\\s+]", ""); System.out.println(html);

Output Thistexthasallotofspecialcharacters b This is bold b

10. Palindrome

• 1. check if palindrome:

     String rev = new StringBuffer(actual).reverse().toString(); return actual.equals(rev);

• 2. create a palindrome given the first half (lc 564) ex. orig = 12345, wants its closest palindrome --> left = 123 (depend on length of orig is even or odd), then call getPalindrome(123, len(12345)%2 == 0)

    private long getPalindrome(long left, boolean even) {
        long res = left;

        // 123 --> 12, so only add '21' to left = 12321
        if (!even) 
            left = left / 10;
        while (left > 0) {
            res = res * 10 + left % 10;
            left /= 10;
        }
        return res;
    }

11. KMP algo: leetcode 214

12. check if the char is a letter: if (Character.isLetter(S.charAt(i)))

13. reverse a string:

1. reverse & string builder

    String input = "Geeks for Geeks"; 
    StringBuilder input1 = new StringBuilder(); 
    input1.append(input); 
    output = input1.reverse(); 
   

2. swap in string array

    String input = "Geeks For Geeks"; 
    char[] arr = input.toCharArray(); 
    int left = 0, 
        right= arr.length-1; 
    for (left=0; left < right ; left++ ,right--) { 
        // Swap values of left and right 
        char temp = arr[left]; 
        arr[left] = arr[right]; 
        arr[right]=temp; 
    } 
   

14. From string to integer:

    Integer.parseInt(str.substring(0,2) --> ex. str = 11:25, and get the integer 11

(刷tag 到 1221)

notes on minimax: notes/minimax.md