Ruoke Zhang

31. Next Permutation

Consider the last permutation: 5-4-3-2-1, all in descending order.

1. From right to left, find the first ascending pair nums[i] and nums[i+1], e.g., 12947653, found nums[4]=4.
2. From right to left, find the first number nums[j] greater than nums[i], which is 5.
3. Swap nums[i] and nums[j], resulting in 12957643. At this point, all numbers after nums[i] are in descending order.
4. Sort the numbers after nums[i] in ascending order, resulting in 12953467.

128. Longest Consecutive Sequence

[100,4,200,1,3,2]

LC 188 Rotate Array

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4]

Method 1: Slicing operation; take last k elements: nums[-k%n:]

Method 2: Reverse entire array first, then reverse parts. Implement reversal separately without slicing to avoid extra space.

Two Pointers

Opposite Direction Two Pointers

LC 75: Sort Colors

Use pointer i to traverse array, left and right pointers point to next position to fill 0 or 2. First continuously fill 2s, then fill 0s when encountered. Loop condition: i<=r. When i>r, nums[i] must be 2.

Reference: JavaGuide

Concurrency Issues

CPU Cache

The value of a variable in the Cache may be inconsistent with the value in Main Memory, leading to calculation errors.

Instruction-Level Reordering

Compiler Optimization Reordering

JVM and JIT do this. For Java programs, instruction reordering is performed during compilation without changing its semantics, similar to g1, g2 optimization reordering.

Solution: Prohibit compiler reordering

Instruction Parallel Reordering

CPU does this, related to CPU pipeline. It means a thread can run in parallel on different CPU hardware.

Merge Sort

LC 148: Sort a Linked List

Use fast and slow pointers to divide into two halves, break in the middle, recursively sort each half, and finally merge the two sorted linked lists in ascending order. Boundary conditions: head==None or head.next==None.

LC 23. Merge k Sorted Lists

Pay attention to edge cases.

Quick Sort

Using an element of the array (usually the first element) as the pivot, move all elements smaller than the pivot to its left, and all elements larger than the pivot to its right. Python Template

intervals.sort(key=lambda p: p[0])

LC 189 [:] slicing operation

dict

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# Dictionary with initial key-value pairs
filled_dict = {'key1': 'value1', 'key2': 'value2'}

# Using dict() constructor
constructed_dict = dict(key1='value1', key2='value2')

valueList=list(filled_dict.values())

my_dict = {'apple': 1, 'banana': 2, 'cherry': 3}
for key in my_dict.keys():
    print(f"Key: {key}")

LC 49

Reference: JavaGuide

Threads

Thread Implementation

A Java program runs as a process and is actually multi-threaded concurrently; the main function is the main thread. Each instance of java.lang.Thread that has called start() and not yet finished is a thread. Java threads are the concurrent execution units of Java programs.

One-to-One Thread Model✨

Each Java thread corresponds to a kernel thread in the operating system, fully utilizing multi-core processors. (Now Windows and Linux use this.)

Prefix Sum Problem List

One-dimensional Prefix Sum

LC 1749

Maximum absolute sum of any subarray: Find the minimum and maximum values in the prefix sum array, and the absolute difference between them is the answer.

1
2
3

def maxAbsoluteSum(self, nums: List[int]) -> int:
    s = list(accumulate(nums, initial=0))  # prefix sum of nums
    return max(s) - min(s)

2055. Plates Between Candles

1. Find the first candle at or to the right of a
2. Find the first candle at or to the left of b
3. Use prefix sum to count the number of plates between them

Steps 1 and 2 can use binary search, but it will time out. It’s best to pre-process and record the position of the first candle to the left/right of each position.

reference: Lingchashan Aifu

Fixed-size Sliding Window

Entry: The element at index i enters the window, update relevant statistics. If i<k-1, repeat the first step.

Update: Update the answer. Generally, update the maximum/minimum value.

Exit: The element at index i-k+1 leaves the window, update relevant statistics.

LC 1456 LC 1052 Grumpy Bookstore Owner: Answer = number of customers during all non-grumpy times + number of grumpy customers within the window.

1297. Maximum Number of Occurrences of a Substring ✨

High-frequency problem, greedy approach.

References: Understanding the JVM (3rd Edition, Chinese) , G1 & ZGC deep dive (Chinese)

Is an Object Dead?

Reference Counting

Drawback: they reference each other, so neither count goes to 0; they won’t be collected.

Reachability Analysis

Start from GC Roots and traverse references downward, marking all reachable objects. The traversal paths are “reference chains.”

Ling Shen Problem List

Linear DP

10. Regular Expression Matching

dp[i][j] indicates if s(0,i-1) matches p(0,j-1)

Base case: s empty, p empty → True; s empty, p xx type → True Compare s[i], p[j]: if not match and p[j] is *, and s[i] matches p[j-1], three possibilities: match one letter, zero letters, multiple letters. If not match and p[j] is *, and s[i] doesn’t match p[j-1], check zero letter option.