Morii

Appearance

算法模板 ​

基础算法 ​

gcd / lcm ​

java
public static int gcd(int a, int b){
    return b == 0 ? a : gcd(b, a % b);
}

public static int lcm(int a, int b){
    return a * b / gcd(a, b);
}

质数 ​

  • p 和 q 为两个正整数且互质，那么 px + qy 不能表示的最大正整数为 (p - 1) * (q - 1) -1
  • 任何一个正整数都可以分解为有穷个质数幂之积，如 6936 = 2^3^ * 3 * 17^2^
java
// 试除法
boolean isPrime(long x){
　　if (x < 2) return false;
　　for (long i = 2; i * i <= x; i++){
　　　　if (x % i == 0) return false;
　　}
　　return true;
}

// 分解质因数

二分 ​

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

public int leftBinarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid - 1;   // 锁定左侧边界，收缩右侧边界
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (left < 0 || left >= nums.length)
        return -1;
    return nums[left] == target ? left : -1;
}

public int rightBinarySearch(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) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        }
    }
    if (right < 0 || right >= nums.length) {
        return -1;
    }
    return nums[right] == target ? right : -1;
}


public static void main(String[] args) {
    int[] nums = new int[]{1, 2, 2, 2, 3};
    System.out.println(new TEMP().binarySearch(nums, 2));       // 2
    System.out.println(new TEMP().leftBinarySearch(nums, 2));   // 1
    System.out.println(new TEMP().rightBinarySearch(nums, 2));  // 3
}

位运算 ​

txt
求n的第k位数字: n >> k & 1
返回n的最后一位1：lowbit(n) = n & -n

双指针 ​

数据结构 ​

并查集 ​

java
class UF {
    // 连通分量个数
    private int count;
    // 存储一棵树
    private int[] parent;
    // 记录树的「重量」
    private int[] size;

    // n 为图中节点的个数
    public UF(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    // 将节点 p 和节点 q 连通
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;

        // 小树接到大树下面，较平衡
        if (size[rootP] > size[rootQ]) {
            parent[rootQ] = rootP;
            size[rootP] += size[rootQ];
        } else {
            parent[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        // 两个连通分量合并成一个连通分量
        count--;
    }

    // 判断节点 p 和节点 q 是否连通
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }

    // 返回节点 x 的连通分量根节点
    private int find(int x) {
        while (parent[x] != x) {
            // 进行路径压缩
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    // 返回图中的连通分量个数
    public int count() {
        return count;
    }
}

图 ​

DFS & BFS ​

java
int ans = 0;
boolean[][] visited;
int[][] dir = {
        {0, 1}, //right
        {1, 0}, //down
        {-1, 0}, //up
        {0, -1} //left
};

public void dfs(char[][] grid, int x, int y) {
    if (visited[x][y] || grid[x][y] == '0') {
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nextX = x + dir[i][0];
        int nextY = y + dir[i][1];
        if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length && !visited[nextX][nextY] && grid[nextX][nextY] == '1') {
            dfs(grid, nextX, nextY);
        }
    }
}

public void bfs(char[][] grid, int x, int y) {
    visited[x][y] = true;
    LinkedList<int[]> queue = new LinkedList<>();
    queue.addLast(new int[]{x, y});
    while (!queue.isEmpty()) {
        int[] pop = queue.pop();
        for (int i = 0; i < 4; i++) {
            int nextX = pop[0] + dir[i][0];
            int nextY = pop[1] + dir[i][1];
            if (nextX >= 0 && nextX < grid.length && nextY >= 0 && nextY < grid[0].length && !visited[nextX][nextY] && grid[nextX][nextY] == '1') {
                queue.addLast(new int[]{nextX, nextY});
                visited[nextX][nextY] = true;
            }
        }
    }
}

public int numIslands(char[][] grid) {
    visited = new boolean[grid.length][grid[0].length];

    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (!visited[i][j] && grid[i][j] == '1') {
                ans++;
//                        dfs(grid, i, j);
                bfs(grid, i, j);
            }
        }
    }
    return ans;
}

拓扑排序 ​

java
public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[] in = new int[numCourses];
    List<List<Integer>> map = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
        map.add(new ArrayList<>());
    }
    for (int[] prerequisite : prerequisites) {
        int v = prerequisite[0];
        int u = prerequisite[1];
        map.get(u).add(v);
        in[v]++;
    }
    int num = 0;
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < numCourses; i++) {
        if (in[i] == 0) {
            stack.push(i);
            num++;
        }
    }
    while (!stack.isEmpty()) {
        int u = stack.pop();
        for (Integer v : map.get(u)) {
            in[v]--;
            if (in[v] == 0) {
                num++;
                stack.push(v);
            }
        }
    }
    return num == numCourses;
}

Kruskal 最短路径算法 ​

所谓最小生成树，就是图中若干边的集合（我们后文称这个集合为 mst，最小生成树的英文缩写），你要保证这些边：

1、包含图中的所有节点。

2、形成的结构是树结构（即不存在环）。

3、权重和最小。

有之前题目的铺垫，前两条其实可以很容易地利用 Union-Find 算法做到，关键在于第 3 点，如何保证得到的这棵生成树是权重和最小的。

这里就用到了贪心思路：

将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和 mst 中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入 mst 集合；否则，这条边不是最小生成树的一部分，不要把它加入 mst 集合。

java
class Solution {
    int[] father;
    // 连通分量个数
    int count;

    int find(int u) {
        while (father[u] != u) {
            father[u] = father[father[u]];
            u = father[u];
        }
        return u;
    }

    void union(int u1, int u2) {
        u1 = find(u1);
        u2 = find(u2);
        if (u1 == u2) return;
        father[u1] = u2;
        count--;
    }

    boolean connected(int u1, int u2) {
        return father[u1] == u2;
    }

    public int minimumCost(int n, int[][] connections) {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        count = n;

        Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));
        int mst = 0;
        for (int[] connection : connections) {
            int u = connection[0] - 1;
            int v = connection[1] - 1;
            if (connected(u, v)) continue;
            union(u, v);
            mst += connection[2];
        }
        return count == 1 ? mst : -1;
    }
}

Dijkstra 算法 ​

计算 start 到其他节点的最短距离

java
class State {
    // 图节点的 id
    int id;
    // 从 start 节点到当前节点的距离
    int distFromStart;

    State(int id, int distFromStart) {
        this.id = id;
        this.distFromStart = distFromStart;
    }
}

// 返回节点 from 到节点 to 之间的边的权重
int weight(int from, int to);

// 输入节点 s 返回 s 的相邻节点
List<Integer> adj(int s);

// 输入一幅图和一个起点 start，计算 start 到其他节点的最短距离
int[] dijkstra(int start, List<Integer>[] graph) {
    // 图中节点的个数
    int V = graph.length;
    // 记录最短路径的权重，你可以理解为 dp table
    // 定义：distTo[i] 的值就是节点 start 到达节点 i 的最短路径权重
    int[] distTo = new int[V];
    // 求最小值，所以 dp table 初始化为正无穷
    Arrays.fill(distTo, Integer.MAX_VALUE);
    // base case，start 到 start 的最短距离就是 0
    distTo[start] = 0;

    // 优先级队列，distFromStart 较小的排在前面
    Queue<State> pq = new PriorityQueue<>((a, b) -> {
        return a.distFromStart - b.distFromStart;
    });

    // 从起点 start 开始进行 BFS
    pq.offer(new State(start, 0));

    while (!pq.isEmpty()) {
        State curState = pq.poll();
        int curNodeID = curState.id;
        int curDistFromStart = curState.distFromStart;

        if (curDistFromStart > distTo[curNodeID]) {
            // 已经有一条更短的路径到达 curNode 节点了
            continue;
        }
        // 将 curNode 的相邻节点装入队列
        for (int nextNodeID : adj(curNodeID)) {
            // 看看从 curNode 达到 nextNode 的距离是否会更短
            int distToNextNode = distTo[curNodeID] + weight(curNodeID, nextNodeID);
            if (distTo[nextNodeID] > distToNextNode) {
                // 更新 dp table
                distTo[nextNodeID] = distToNextNode;
                // 将这个节点以及距离放入队列
                pq.offer(new State(nextNodeID, distToNextNode));
            }
        }
    }
    return distTo;
}

floyd 算法 ​

java
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    // 初始化
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
   			else d[i][j] = INF;
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

最小栈 ​

java
class MinStack {
    private final Stack<Integer> stack;

    private final Stack<Integer> minStack;

    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }

    public void pop() {
        if (stack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}