没有特殊说明，题目均来自牛客面试必刷101

链表

反转链表

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 Node {
  int val;
  Node nxt;
  public Node(int val) {
    this.val = val;
  }
}
public class Solution {
  public static void main(String[] args) {
    Node dummy = new Node(-1), pre = dummy;
    for (int i = 0; i < 10; i++) {
      Node cur = new Node(i);
      pre.nxt = cur;
      pre = cur;
    }
    pre = null;
    Node cur = dummy.nxt;
    while (cur != null) {
      Node nxt = cur.nxt;
      cur.nxt = pre;
      pre = cur;
      cur = nxt;
    }
    while (pre != null) {
      System.out.println(pre.val);
      pre = pre.nxt;
    }
  }
}

链表内指定区间反转

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
public ListNode Merge (ListNode pHead1, ListNode pHead2) {
    // write code here
    ListNode dummy = new ListNode(0), cur = dummy;;
    while (pHead1 != null && pHead2 != null) {
        if (pHead1.val < pHead2.val) {
            cur.next = pHead1;
            pHead1 = pHead1.next;
        }
        else {
            cur.next = pHead2;
            pHead2 = pHead2.next;
        }
        cur = cur.next;
    }
    while (pHead1 != null) {
        cur.next = pHead1;
        pHead1 = pHead1.next;
        cur = cur.next;
    }
    while (pHead2 != null) {
        cur.next = pHead2;
        pHead2 = pHead2.next;
        cur = cur.next;
    }
    return dummy.next;
}

合并k个已排序的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public ListNode mergeKLists (ArrayList<ListNode> lists) {
    // write code here
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    ListNode dummy = new ListNode(0), cur = dummy;
    for (ListNode list : lists) {
        if (list != null) pq.offer(list);
    }
    while (!pq.isEmpty()) {
        ListNode p = pq.poll();
        cur.next = p;
        p = p.next;
        if (p != null) pq.offer(p);
        cur = cur.next;
    }
    return dummy.next;
}

链表中环的入口结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public ListNode EntryNodeOfLoop(ListNode pHead) {
    ListNode slow = pHead, fast = pHead;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) break;
    }
    if (fast == null || fast.next == null) return null;
    ListNode head = pHead;
    while (head != slow) {
        head = head.next;
        slow = slow.next;
    }
    return head;
}

dfs

岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int res = 0;
public int solve (char[][] grid) {
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '1') {
                dfs(i, j, grid);
                res++;
            }
        }
    }
    return res;
}
private void dfs(int x, int y, char grid[][]) {
    int dirs[] = new int[]{1, 0, -1, 0, 1};
    grid[x][y] = '0';
    int m = grid.length, n = grid[0].length;
    for (int i = 0; i < 4; i++) {
        int nx = x + dirs[i], ny = y + dirs[i+1];
        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
        if (grid[nx][ny] == '0') continue;
        dfs(nx, ny, grid);
    }
}

dp

编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int editDistance (String str1, String str2) {
    // write code here
    int m = str1.length(), n = str2.length();
    int f[][] = new int[m+1][n+1];
    for (int i = 0; i <= m; i++) f[i][0] = (int)1e9;
    for (int i = 0; i <= n; i++) f[0][i] = (int)1e9;
    f[0][0] = 0;
    for (int i = 0; i < m; i++) {
        char c1 = str1.charAt(i);
        for (int j = 0; j < n; j++) {
            char c2 = str2.charAt(j);
            int add = c1 == c2 ? 0 : 1;
            f[i+1][j+1] = Math.min(f[i][j] + add, Math.min(f[i+1][j] + 1, f[i][j+1] + 1));
        }
    }
    return f[m][n];
}

堆/栈/队列

寻找第k大的数

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 int findKth (int[] a, int n, int K) {
    // return quickSort(a, 0, n-1, K-1);  // 寻找第k小的数
    return quickSort(a, 0, n-1, n-K);
}
private void swap(int nums[], int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
}
private int partition(int nums[], int l, int r) {
    int pivot = nums[l];
    int i = l, j = r;
    while (i < j) {
        while (i < j && nums[j] >= pivot) j--;
        while (i < j && nums[i] <= pivot) i++;
        swap(nums, i, j);
        if (i == j) swap(nums, l, j);
    }
    return j;
}
private int quickSort(int nums[], int l, int r, int K) {
    int p = partition(nums, l, r);
    if (K < p) return quickSort(nums, l, p-1, K);
    else if (K > p) return quickSort(nums, p+1, r, K);
    else return nums[p];
}

旋转数组（右移m位）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] solve (int n, int m, int[] a) {
    m %= n;
    reverse(a, 0, n-1);  // 反转整个数组
    reverse(a, 0, m-1);  // 反转数组前m个数
    reverse(a, m, n-1);  // 反转数组剩余的n-m个数
    return a;
}
public void reverse(int a[], int left, int right) {
    while (left < right) {
        int t = a[left];
        a[left] = a[right];
        a[right] = t;
        left++;
        right--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int[] solve (int n, int m, int[] a) {
    m = m % n;  // 左移m位
    int start = 0, cnt = 0;
    while (cnt < n) {
        int cur = start;
        while (cnt < n) {  // 迭代左移这个环
            int nxt = (cur + n - m) % n;
            // int nxt = (cur + m) % n;  // 右移
            cnt++;
            if (nxt == start) break;
            swap(a, cur, nxt);
            cur = nxt;
        }
        start++;  // 处理下一个环
    }
    return a;
}
private void swap(int a[], int i, int j) {
    int t = a[i];
    a[i] = a[j];
    a[j] = t;
}

结构

LRU

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
class Node {
    int key, val;
    Node pre, nxt;
}
int capacity;
Node head = new Node(), tail = new Node();  // 虚拟dummy头尾Node
HashMap<Integer, Node> map = new HashMap<>();
public Solution(int capacity) {
    this.capacity = capacity;
    head.nxt = tail;
    tail.pre = head;
}
private void addFirst(Node cur) {
    cur.pre = head;
    cur.nxt = head.nxt;
    head.nxt.pre = cur;
    head.nxt = cur;
}
private void delete(Node cur) {
    cur.pre.nxt = cur.nxt;
    cur.nxt.pre = cur.pre;
}
private void moveToHead(Node cur) {
    delete(cur);
    addFirst(cur);
}
public int get(int key) {
    Node cur = map.get(key);
    if (cur == null) return -1;
    moveToHead(cur);
    return cur.val;
}
public void set(int key, int value) {
    Node cur = map.get(key);
    if (cur == null) {
        cur = new Node();
        cur.key = key;
        cur.val = value;
        addFirst(cur);
        map.put(key, cur);
        if (map.size() > capacity) {
            map.remove(tail.pre.key);
            delete(tail.pre);
        }
    }
    else {
        cur.val = value;
        moveToHead(cur);
    }
}

LFU

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
class Node {
    int key, val, freq;
    Node pre, nxt;
}
class NodeList {
    Node head = new Node(), tail = new Node();
    public NodeList() {
        head.nxt = tail;
        tail.pre = head;
    }
    private void addFrist(Node cur) {
        cur.pre = head;
        cur.nxt = head.nxt;
        head.nxt.pre = cur;
        head.nxt = cur;
    }
    private void delete(Node cur) {
        cur.pre.nxt = cur.nxt;
        cur.nxt.pre = cur.pre;
    }
    private void moveToHead(Node cur) {
        delete(cur);
        addFrist(cur);
    }
}
int minFreq = 0, capacity;
HashMap<Integer, Node> map = new HashMap<>();  // 存储key和对应的Node
HashMap<Integer, NodeList> freqMap = new HashMap<>();  // 存储频率和对应Node组成的NodeList
public int get(int key) {
    Node cur = map.get(key);
    if (cur == null) return -1;
    incrFreq(cur);
    return cur.val;
}
public void set(int key, int val) {
    Node cur = map.get(key);
    if (cur == null) {
        if (map.size() == capacity) {
            NodeList list = freqMap.get(minFreq);
            map.remove(list.tail.pre.key);
            list.delete(list.tail.pre);
        }
        cur = new Node();
        cur.key = key; cur.val = val; cur.freq = 1;
        minFreq = 1;
        map.put(key, cur);
        addNode(cur);
    }
    else {
        incrFreq(cur);
        cur.val = val;
    }
}
public void incrFreq(Node cur) {
    NodeList list = freqMap.get(cur.freq);
    list.delete(cur);
    if (list.head.nxt == list.tail) {
        if (cur.freq == minFreq) {
            minFreq++;
        }
    }
    cur.freq++;
    addNode(cur);
}
public void addNode(Node cur) {
    NodeList list = freqMap.getOrDefault(cur.freq, new NodeList());
    list.addFrist(cur);
    freqMap.put(cur.freq, list);
}
public int[] LFU (int[][] operators, int k) {
    // 若opt=1，接下来两个整数x, y，表示set(x, y)
    // 若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
    capacity = k;
    ArrayList<Integer> res = new ArrayList<>();
    for (int operator[] : operators) {
        if (operator[0] == 1) {
            int key = operator[1], val = operator[2];
            set(key, val);
        }
        else {
            int key = operator[1];
            res.add(get(key));
        }
    }
    return res.stream().mapToInt(i -> i).toArray();
}

矩阵

搜索二维矩阵 leetcode 74

每行中的整数从左到右按非严格递增顺序排列，每行的第一个整数大于前一行的最后一个整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int l = 0, r = m-1;
        while (l < r) {  // 找到第一列中，第一个小于等于target的值（行索引）
            int mid = l + (r-l+1)/2;
            if (matrix[mid][0] <= target) l = mid;
            else r = mid - 1;
        }
        int x = l;
        l = 0; r = n-1;
        while (l < r) {  // 在这个行中，二分查找target（大于等于和小于等于都可以）
            int mid = l + (r-l)/2;
            if (matrix[x][mid] >= target) r = mid;
            else l = mid + 1;
        }
        int y = l;
        System.out.println(matrix[x][y]);
        return matrix[x][y] == target;
    }
}

搜索二维矩阵 II leetcode 240

每行的元素从左到右升序排列，每列的元素从上到下升序排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length, n = matrix[0].length;
        int x = 0, y = n-1;  // 从右上角出发
        while (x <= m-1 && y >= 0) {
            if (matrix[x][y] > target) {  // 舍弃这一列
                y--;
            }
            else if (matrix[x][y] < target) {  // 舍弃这一行
                x++;
            }
            else return true;
        }
        return false;
    }
}