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]

1. First, add all numbers to a set, so checking if a number exists takes O(1) time.
2. Iterate through each number x in the set, and see who can be the starting point of a sequence. If x-1 is also in the set, then x cannot be the starting point, continue.
3. If x can be the starting point, continuously check if x+1 is in the set.

169. Majority Element

Moore’s Voting Algorithm can only find the majority element that appears more than half the time.

For example, 1,1,1,2,3,9,9 will not work.

48. Rotate Image

First flip horizontally, then flip along the main diagonal.

41. First Missing Positive

In-place hash, put the element with value i+1 at index i in the array.

Iterate through the array’s index, check if nums[i] is equal to nums[nums[i]+1]. If not, use a loop to swap.

75. Sort Colors

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def sortColors(self, nums: List[int]) -> None:
    n=len(nums)
    p0,p2=0,n-1
    i=0
    while i<=p2: # Note the loop condition here
        while i<=p2 and nums[i]==2:
            nums[i], nums[p2]=nums[p2], nums[i]
            p2-=1
        if nums[i]==0:
            nums[i],nums[p0]=nums[p0], nums[i]
            p0+=1
        i+=1

136

x^x=0 0^x=x Can continuously XOR to eliminate all numbers that appear twice.

287. Find Duplicate

Similar to fast and slow pointers, check if there is a cycle in a linked list. [1,3,4,2,2] can be seen as: From index 0, nums[0]=1; To index=1, nums[1]=3; To index=3, nums[3]=2; To index=2, nums[2]=4; To index=4, nums[4]=2

Then there is a cycle from node 4 to node 2, and 2 is indeed the duplicate.

394. Decode String

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def decodeString(self, s: str) -> str:
    stack=[]
    res=""
    multi=0
    for x in s:
        if x=='[':
            stack.append([res, multi])
            res=""
            multi=0
        elif x==']':
            preFix, m=stack.pop()
            res=preFix+m*res
        elif '0'<=x<='9':
            multi=int(x)+multi*10
        else:
            res+=x
    return res

79. Word Search

Backtracking. dfs(i, j, k) means starting from board[i][j], it can match word[k:], and no duplicate elements are used. Remember to restore the array after dfs!

88. Merge Sorted Array

Reverse two pointers

32. Longest Valid Parentheses

Mark valid matching parenthesis positions as 1, find the length of the longest continuous 1s.

Median

Number of elements smaller than it = number of elements larger than it OR Number of elements smaller than it = number of elements larger than it - 1