leetcode算法

leetcode算法练习。

1135最低成本联通所有城市

最小生成树 图的生成树是一棵含有其所有的顶点的无环联通子图，一幅加权图的最小生成树（ MST ） 是它的一颗权值（树中所有边的权值之和）最小的生成树。

并查集 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。

方法一：Kruskal 算法

思路

根据题意，我们可以把 n 座城市看成 n 个顶点，连接两个城市的成本 cost 就是对应的权重，需要返回连接所有城市的最小成本。很显然，这是一个标准的最小生成树，首先我们介绍第一种经典算法： Kruskal 算法。

既然我们需要求最小成本，那么可以肯定的是这个图没有环（如果有环的话无论如何都可以删掉一条边使得成本更小）。该算法就是基于这个特性： 按照边的权重顺序（从小到大）处理所有的边，将边加入到最小生成树中，加入的边不会与已经加入的边构成环，直到树中含有 n - 1 条边为止。这些边会由一片森林变成一个树，这个树就是图的最小生成树

算法

1. 将所有的边按照权重从小到大排序。
2. 取一条权重最小的边。
3. 使用并查集（union-find）数据结构来判断加入这条边后是否会形成环。若不会构成环，则将这条边加入最小生成树中。
4. 检查所有的结点是否已经全部联通，这一点可以通过目前已经加入的边的数量来判断。若全部联通，则结束算法；否则返回步骤 2.

class Solution {
    public int minimumCost(int n, int[][] connections) {
        int[] id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        // 将所有边按照权重从小到大排序
        Arrays.sort(connections,(a, b)->(a[2] != b[2] ? a[2]-b[2] : a[0] - b[0]));
        int count = 0, cost = 0;
        for (int[] c : connections) {
            if (count == n - 1) {
                break;
            }
            if (find(c[0] - 1, id) == find(c[1] - 1, id)) {
                continue;
            }
            union(c[0] - 1, c[1] - 1, id);
            count++;
            cost += c[2];
        }
        if (count != n - 1) {
            return -1;
        }
        return cost;

    }
    private void union (int i, int j, int[] id) {
        int x = find(i, id);
        int y = find(j, id);
        if (x == y) {
            return;
        }
        id[x] = y;
    }

    private int find(int x, int[] id) {
        if (x == id[x]) {
            return x;
        }
        return find(id[x], id);
    }
}

复杂度分析

• 时间复杂度：O(elog⁡e+e∗n)，其中 e 为边的数量，n 为城市的数量。排序的时间复杂度为 O(elog⁡e)，我们需要遍历 e条边。对于每条边，查找两个端点的根结点最多需要经过 2n个结点。所以时间复杂度最坏为 O(e∗n)。

• 空间复杂度：O(n)，需要大小为 n 的并查集结构存储点的关系，其中 n 为城市的个数。

方法二：Kruskal 算法 + 加权 Union 算法
思路

方法一我们检查环的过程中，最坏的情况下每次需要遍历所有的边，形成一个永远只有左子节点的树。为了避免形成这样的结构，我们可以记录每一颗树的大小并且总是将较小的树连接到较大的树上，这个算法就叫加权 Union 算法。该算法需要添加一个数组记录树中的节点数，并且在联通的时候比较节点个数，将较小的树连接到较大的树上。

public int minimumCost(int n, int[][] connections) {
        int[] id = new int[n];
        int[] sz = new int[n]; // 记录树的大小
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        // 将所有边按照权重从小到大排序
        Arrays.sort(connections,(a, b)->(a[2] != b[2] ? a[2]-b[2] : a[0] - b[0]));
        int count = 0, cost = 0;
        for (int[] c : connections) {
            if (count == n - 1) {
                break;
            }
            if (find(c[0] - 1, id) == find(c[1] - 1, id)) {
                continue;
            }
            union2(c[0] - 1, c[1] - 1, sz, id);
            count++;
            cost += c[2];
        }
        if (count != n - 1) {
            return -1;
        }
        return cost;

    }

    // 将较小的树连接到较大的树上
    private void union2 (int i, int j, int[] sz, int[] id) {
        int x = find(i, id);
        int y = find(j, id);
        if (x == y) {
            return;
        }
        if (sz[x] < sz[y]) {
            id[x] = y;
            sz[y] += sz[x];
        } else {
            id[y] = x;
            sz[x] += sz[y];
        }
    }


    private int find(int x, int[] id) {
        if (x == id[x]) {
            return x;
        }
        return find(id[x], id);
    }
}

复杂度分析**

• 时间复杂度：O(e(log⁡e+log⁡n))，使用加权 Union 算法后，find 操作的时间复杂度为 O(log⁡n)。另外此时的时间复杂度还受排序操作制约，排序操作复杂度为 O(elog⁡e)，综合起来时间复杂度为 O(e(log⁡e+log⁡n))

• 空间复杂度：O(n)，需要大小为 n 的并查集结构存储点的关系，其中 n 为城市的个数。

方法三：Kruskal 算法 + 加权 Union 算法 + 路径压缩
思路

考虑在方法一和方法二中我们使用的 find 函数，可以发现，一些路径是被重复寻找了的。

举个例子，假设在并查集中有四个结点，其中 1 的父亲是 2，2 的父亲是 3，3 的父亲是 4。那么我们在以后每次寻找 1 所在的集合时，都需要经过 1-2-3 这条路径；查找 2 所在的集合时，都需要经过 2-3-4 这条路径。可以想到，在一个大型图中，查找根结点的路径中会存在大量与此类似的重复查询。

而事实上，我们通过一个简单的操作来避免这样的重复查询：我们可以在 find 函数结束的时候，将路径上所有的结点，修改为根结点的直接子结点。这样，我们下次查询时，就可以直接找到刚才找到的根结点，不需要再查询一次相同的路径了。

public int minimumCost(int n, int[][] connections) {
        int[] id = new int[n];
        int[] sz = new int[n]; // 记录树的大小
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        // 将所有边按照权重从小到大排序
        Arrays.sort(connections,(a, b)->(a[2] != b[2] ? a[2]-b[2] : a[0] - b[0]));
        int count = 0, cost = 0;
        for (int[] c : connections) {
            if (count == n - 1) {
                break;
            }
            if (find(c[0] - 1, id) == find(c[1] - 1, id)) {
                continue;
            }
            union(c[0] - 1, c[1] - 1, sz, id);
            count++;
            cost += c[2];
        }
        if (count != n - 1) {
            return -1;
        }
        return cost;

    }

    // 将较小的树连接到较大的树上
    private void union (int i, int j, int[] sz, int[] id) {
        int x = find(i, id);
        int y = find(j, id);
        if (x == y) {
            return;
        }
        if (sz[x] < sz[y]) {
            id[x] = y;
            sz[y] += sz[x];
        } else {
            id[y] = x;
            sz[x] += sz[y];
        }
    }


    private int find(int x, int[] id) {
        while (x != id[x]) {
            id[x] = id[id[x]];
            x = id[x];
        }
        return id[x];
    }
}

复杂度分析

• 时间复杂度：O(e∗(log⁡e+α(n)))，其中 e 为边的数量，n为城市的数量。经过优化后，find 操作的时间复杂度为 O(α(n)) ，其中 α为反阿克曼函数，其增长极其缓慢，也就是说其单次操作的平均运行时间可以认为是一个很小的常数。具体的证明过于复杂，了解结论即可。此时算法的总体时间复杂度仍然受排序操作制约，为 O(elog⁡e)，综合可得时间复杂度为 O(e∗(log⁡e+α(n)))。

• 空间复杂度：O(n)，需要大小为 n 的并查集结构存储点的关系，其中 n 为城市的个数。

方法四：Prim 算法
思路

Kruskal 算法的核心思想是每次把权重最小的边加入到树中，Prim 算法则是依据顶点来生成的，它的每一步都会为一颗生长中的树添加一条边，一开始这棵树只有一个顶点，然后会添加 n - 1 条边，每次都是将下一条连接树中的顶点与不在树中的顶点且权重最小的边加入到树中。

算法

1. 根据 connections 记录每个顶点到其他顶点的权重，记为 edges 。
2. 使用 visited 记录所有被访问过的点。
3. 使用堆来根据权重比较所有的边。
4. 将任意一个点记为已访问，并将其所有连接的边放入堆中。
5. 从堆中拿出权重最小的边。
6. 如果已经访问过，直接丢弃。
7. 如果未访问过，标记为已访问，并且将其所有连接的边放入堆中，检查是否有 n 个点。
   重复操作 5。

class Solution {
        public class Edge{
            int from;
            int to;
            int weight;
            public Edge(int f, int t, int w) {
                from = f;
                to = t;
                weight = w;
            }
        }
        public int minimumCost(int n, int[][] connections) {
            Map<Integer, List<Edge>> graph = new HashMap<>();
            for (int[] arr : connections) {
                int from = arr[0];
                int to = arr[1];
                int weight = arr[2];
                // 无向图转换成双向图
                Edge e1 = new Edge(from, to, weight);
                Edge e2 = new Edge(to, from, weight);
                if (graph.get(from) == null) {
                    List<Edge> list1 = new ArrayList<>();
                    list1.add(e1);
                    graph.put(from, list1);
                } else {
                    graph.get(from).add(e1);
                }
                if (graph.get(to) == null) {
                    List<Edge> list1 = new ArrayList<>();
                    list1.add(e2);
                    graph.put(to, list1);
                } else {
                    graph.get(to).add(e2);
                }
            }
            // 优先级队列 核心
            Queue<Edge> queue = new PriorityQueue<>((Edge a, Edge b) -> (a.weight - b.weight));
            Set<Integer> set = new HashSet<>();
            int ans = 0;
            // 随机选一个点加进去，就选第一个点
            for (Edge edge : graph.get(connections[0][0])) {
                queue.offer(edge);
            }
            set.add(connections[0][0]);
            while (!queue.isEmpty()) {
                // 边解锁点，点解锁边
                Edge edge = queue.poll();
                int from = edge.from;
                int to = edge.to;
                int weight = edge.weight;
                if (!set.contains(to)) {
                    set.add(to);
                    ans += weight;
                    for (Edge e : graph.get(to)) {
                        queue.offer(e);
                    }
                }
            }
            // set的大小和n不一致就返回-1
            if (set.size() == n) {
                return ans;
            } else {
                return -1;
            }

        }
    }

2022. 将一维数组转变成二维数组

三种方法

遍历赋值

class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        int len = original.length;
        if(len != m * n) return new int[0][0];
        int[][] ans = new int[m][n];
        for(int i = 0;i < len;i++){
            ans[i / n][i % n] = original[i];
        }
        return ans;
    }
}

Arrays.copyOfRange

• original：第一个参数为要拷贝的数组对象
• from：第二个参数为拷贝的开始位置（包含）
• to：第三个参数为拷贝的结束位置（不包含）

class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        int len = original.length;
        if(len != m * n) return new int[0][0];
        int[][] ans = new int[m][];
        for(int i = 0;i < m;i++){
            ans[i] = Arrays.copyOfRange(original,i * n,(i + 1) * n);
        }
        return ans;
    }
}

System.arraycopy

• 第一个参数默认是src 来源数组 类型为数组
• 第二个参数默认是srcPos 从来源数组开始复制的位置 类型为整行（其实就是下标）
• 第三个参数默认是dest 目标数组 类型为数组
• 第四个参数默认是destPos 目标数组起始下标
• 第五个参数默认是length 复制的长度

class Solution {
    public int[][] construct2DArray(int[] original, int m, int n) {
        int len = original.length;
        if(len != m * n) return new int[0][0];
        int[][] ans = new int[m][n];
        for(int i = 0;i < m;i++){
            System.arraycopy(original,i * n,ans[i],0,n);
        }
        return ans;
    }
}

1185. 一周中的第几天

method1:

class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        String[] week ={"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        // 1970的最后一天是星期四
        int ans = day + 4;
        for (int i = 1971; i < year; i++) {
            if ((i % 4 == 0 && i % 100 !=0) || (i % 400 == 0)) {
                ans += 366;
            }else {
                ans += 365;
            }
        }
        int[] day4month = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        for (int i = 0; i < month - 1; i++) {
            ans += day4month[i];
        }

        if (((year % 4 == 0 && year % 100 !=0) || (year % 400 == 0)) && month > 2) {
            ans += 1;
        }

        return week[ans % 7];
 	}
}

method2:

class Solution {
    public String dayOfTheWeek(int day, int month, int year) {
        String[] week ={"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
        // 1970的最后一天是星期四
        int ans = day + 4;
        // 1970前一个闰年是1968年， -1是因为从上一年开始才算整年
        ans += 365 * (year - 1971) + ((year - 1) - 1968) / 4;
        int[] day4month = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        for (int i = 0; i < month - 1; i++) {
            ans += day4month[i];
        }

        if (((year % 4 == 0 && year % 100 !=0) || (year % 400 == 0)) && month > 2) {
            ans += 1;
        }

        return week[ans % 7];
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = {-1,-1};
        ans[0] = binarySearch(nums,target,true);
        ans[1] = binarySearch(nums,target,false);
        return ans;
    }

    public int binarySearch(int[] nums, int target, boolean isLeft){
        int left = 0;
        int right = nums.length - 1;
        int ans = -1;
        while(left <= right){
            int mid = (left + right) / 2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                ans = mid;
                if(isLeft){
                    //如果要找的是最左边的，让右区间往左移一位
                    right = mid - 1;
                }else{
                    //如果要找的是最右边的，让左区间往右移一位
                    left = mid + 1;
                }
            }
        }
        return ans;
    }
}

1576. 替换所有的问号

class Solution {
    public String modifyString(String s) {
        int n = s.length();
        char[] ss = s.toCharArray();
        for(int i = 0;i < n;i++){
            if(ss[i] == '?'){
                for(int j = 0;j < 26;j++){
                    char c = (char)('a' + j);
                    if((i - 1 < 0 || ss[i - 1] != c) && (i + 1 >= n || ss[i + 1] != c)){
                        ss[i] = c;
                    }
                }
            }
        }
        return String.valueOf(ss);
    }
}

71. 简化路径

class Solution {
    public String simplifyPath(String path) {
        String[] paths = path.split("/");
        Deque<String> stack = new LinkedList<>();
        for(String p : paths){
            if(".".equals(p)){
                continue;
            }else if("..".equals(p)){
                if(!stack.isEmpty()){
                    stack.pollLast();
                }
            }else if(!"".equals(p)){
                stack.offerLast(p);
            }
        }
        StringBuilder sb = new StringBuilder();
        if(stack.isEmpty()){
            sb.append("/");
        }
        while(!stack.isEmpty()){
            sb.append("/").append(stack.pollFirst());
        }
        return sb.toString();
    }
}

1614. 括号的最大嵌套深度

class Solution {
    public int maxDepth(String s) {
        //并不需要真的创建一个栈，只需要记录栈的大小即可
        int size = 0;
        int ans = 0;
        for(int i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if('(' == c){
                size++;
                ans = Math.max(size,ans);
            }else if(')' == c){
                size--;
            }
        }
        return ans;
    }
}

89. 格雷编码

class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < 1 << n /*Math.pow(2,n)*/; i++) {
            //格雷码的公式
            ans.add((i >> 1) ^ i);
        }
        return ans;
    }
}

1629. 按键持续时间最长的键

class Solution {
    public char slowestKey(int[] releaseTimes, String keysPressed) {
        int n = keysPressed.length();
        char[] chars = keysPressed.toCharArray();
        //持续时间最长的键的index
        int maxIndex = 0;
        //持续时间最长的时间
        int maxTimes = -1;
        //上一个键的时间
        int lastTimes = 0;
        for(int i = 0;i < n;i++){
            int curTimes = releaseTimes[i] - lastTimes;
            lastTimes = releaseTimes[i];
            if(maxTimes < curTimes){
                maxTimes = curTimes;
                maxIndex = i;
            }else if(maxTimes == curTimes){
                maxIndex = chars[i] > chars[maxIndex] ? i : maxIndex;
            }
        }
        return chars[maxIndex];
    }
}

306. 累加数

class Solution {
    int len;
    char[] nums;

    public boolean isAdditiveNumber(String num) {
        len = num.length();
        if(len < 3) return false;
        nums = num.toCharArray();
        long num1 = 0;
        //len / 2: 第一个数如果超过一半的长度，后面的数就已经无法相等了
        for(int i = 0;i < len / 2;i++){
            num1 = num1 * 10 + nums[i] - '0';
            long num2 = 0;
            for(int j = i + 1;j < len - 1;j++){
                num2 = num2 * 10 + nums[j] - '0';
                if(num2 == 0){
                    if(judge(num1, num2, j + 1)){
                        return true;
                    }
                    //num2 == 0,如果不能一通到底，则在第一轮遍历直接跳出
                    break;
                }
                if(judge(num1, num2, j + 1)){
                    return true;
                }
            }
            if(num1 == 0){
                //num1 == 0,如果不能一通到底，则在第一轮遍历直接跳出
                break;
            }
        }
        return false;
    }

    private boolean judge(long num1, long num2, int num3Index){
        //累加序列里的数 不会 以 0 开头，但这个数本身可以是0
        if(nums[num3Index] == '0'){
            if(num1 + num2 == 0){
                //递归出口
                if(num3Index == len - 1){
                    return true;
                }
                //进入递归，判断下一个累加序列
                else if(judge(num2, 0, num3Index + 1)){
                    return true;
                }
            }
            //因为 累加序列里的数 不会 以 0 开头，所以当这个数是 0 时，第一轮判断不符合就可以跳出了
            return false;
        }
        long num3 = 0;
        for(int i = num3Index;i < len;i++){
            num3 = num3 * 10 + nums[i] - '0';
            if(num1 + num2 == num3){
                //递归出口
                if(i == len - 1){
                    return true;
                }
                //进入递归
                if(judge(num2, num3, i + 1)){
                    return true;
                }
            }else if(num1 + num2 < num3){
                //剪枝
                return false;
            }
        }
        return false;
    }
}

1036. 逃离大迷宫

class Solution {
       int N = (int) 1e6;
       int[][] direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
       Set<String> blockSet = new HashSet<>();

       public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
           int fromX = source[0], fromY = source[1];
           for (int[] b : blocked) {
               blockSet.add(b[0] + "," + b[1]);
           }

           return dfs(source[0], source[1], source[0], source[1], target[0], target[1], new HashSet<>())
            && dfs(target[0], target[1], target[0], target[1], source[0], source[1], new HashSet<>());

       }

       private boolean dfs(int x, int y, int fromX, int fromY, int toX, int toY, Set<String> visitedSet) {
           if (x == toX && y == toY) {
               return true;
           }
           if (Math.abs(x - fromX) + Math.abs(y - fromY) > 200) {
               return true;
           }

           visitedSet.add(x + "," + y);
           for (int[] d : direction) {
               int tx = x + d[0];
               int ty = y + d[1];
               if (!hasBlocked(tx, ty, blockSet, visitedSet) && dfs(tx, ty, fromX, fromY, toX, toY, visitedSet)) {
                   return true;
               }
           }
           return false;
       }

       private boolean hasBlocked(int x, int y, Set<String> blockSet, Set<String> visitedSet) {
           if (x >= N || y >= N || x < 0 || y < 0) {
               return true;
           }
           String s = x + "," + y;
           if (blockSet.contains(s) || visitedSet.contains(s)) {
               return true;
           }
           return false;
       }

   }

不同于普通的 DFS、BFS，因为数据范围太大，如果直接开二维数组来存matrix或是visited，会超出内存限制，而应该保存对应位置到Set中。同样的，为了不超时，应该在搜索一定的范围后剪枝，因为0 <= blocked.length <= 200，如果能搜出曼哈顿距离大于 200 的范围，则能保证出发点没有被 block 住，一定能到达。

334. 递增的三元子序列

class Solution {
    public boolean increasingTriplet(int[] nums) {
        if(nums.length < 3)return false;
        int small = Integer.MAX_VALUE;
        int mid = Integer.MAX_VALUE;
        for(int n : nums){
            if(n <= small){
                small = n;
            }else if(n <= mid){
                mid = n;
            }else{
                return true;
            }
        }
        return false;
    }
}

747. 至少是其他数字两倍的最大数

class Solution {
    public int dominantIndex(int[] nums) {
        int max = -1;
        int max2 = -1;
        int maxIndex = -1;
        for(int i = 0;i < nums.length;i++){
            if(nums[i] > max){
                maxIndex = i;
                max2 = max;
                max = nums[i];
            }else if(nums[i] > max2){
                max2 = nums[i];
            }
        }
        return max >= max2 * 2 ? maxIndex : -1;
    }
}

373. 查找和最小的 K 对数字

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>(k);
        PriorityQueue<int[]> heap = new PriorityQueue<>((a,b)->(nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]]));
        for(int i = 0;i < Math.min(k,nums1.length);i++){
            heap.offer(new int[]{i,0});
        }
        while(k-- > 0 && !heap.isEmpty()){
            int[] cur = heap.poll();
            ans.add(Arrays.asList(nums1[cur[0]],nums2[cur[1]]));
            if(++cur[1] < nums2.length){
                heap.offer(cur);
            }
        }
        return ans;
    }
}

1716. 计算力扣银行的钱

class Solution {
    public int totalMoney(int n) {
        // method1 等差数列求和进行优化,每周七天存的钱之和比上一周多 7 块，因此每周存的钱之和的序列是一个等差数列，可以用等差数列求和公式来求出所有完整的周存的钱总和。 剩下的天数里，每天存的钱也是一个等差数列，可以用相同的公式进行求和。最后把两者相加即可。
        int weekNum = n / 7;
        int firstWeekMoney = (1 + 7) * 7 / 2;
        int lastWeekMoney = 7 * (weekNum - 1) + firstWeekMoney;
        int weekMoney = (firstWeekMoney + lastWeekMoney) * weekNum / 2;

        int dayNum = n % 7;
        int firstDayMoney = 1 + weekNum;
        int lastDayMoney = firstDayMoney + dayNum - 1;
        int dayMoney = (firstDayMoney + lastDayMoney) * dayNum / 2;
        return weekMoney + dayMoney;
        
         // method2,计算合并，简化空间。节约空间
        int week = n / 7;
        int mod = n % 7;
        return 28 * week + 7 * week * (week - 1) / 2 + (week + 1) * mod + mod * (mod - 1) / 2;
    }
}

382. 链表随机节点

class Solution {
    List<Integer> list = new ArrayList<>();
    Random random = new Random();
    public Solution(ListNode head) {
        while(head != null){
            list.add(head.val);
            head = head.next;
        }
    }
    
    public int getRandom() {
        return list.get(random.nextInt(list.size()));
    }
}

1220. 统计元音字母序列的数目

题目中给定的字符的下一个字符的规则如下：

• 字符串中的每个字符都应当是小写元音字母 （‘a’,‘e’,‘i’,‘o’,‘u’）
• 每个元音‘a’ 后面都只能跟着 ‘e’；
• 每个元音 ‘e’后面只能跟着 ‘a’ 或者是 ‘i’；
• 每个元音 ‘i’ 后面不能再跟着另一个 ‘i’；
• 每个元音 ‘o’后面只能跟着 ‘i’ 或者是 ‘u’；
• 每个元音 ‘u’ 后面只能跟着 ‘a’；

以上等价于每个字符的前一个字符的规则如下：

• 元音字母 ‘a’ 前面只能跟着 ‘e’,‘i’,‘u’
• 元音字母 ‘e’前面只能跟着 ‘a’,‘i’；
• 每个元音 ‘i’ 前面只能跟着 ‘e’,‘o’
• 每个元音 ‘o’ 前面只能跟着 ‘i’
• 每个元音 ‘u’ 后面只能跟着 ‘o’,‘i’；

我们设dp[i][j]代表当前长度为i且以字符j为结尾的字符串的数目，其中j=0,1,2,3,4分别代表元音字母‘a’,‘e’,‘i’,‘o’,‘u’，通过以上的字符规则，我们可以得到动态规划递推公式如下：

统计元音字母序列的数目

• 实际计算过程中只需要保留前一个状态即可推导出后一个状态，计算长度为 i 的状态只需要长度为 i−1的中间变量即可，i−1 之前的状态全部都可以丢弃掉。计算过程中，答案需要取模 1e9+7。

class Solution {
    //long mod = (int) 1e9 + 7;
    public int countVowelPermutation(int n) {
        long mod = 1000000007;
        long[] dp = new long[5];
        long[] ndp = new long[5];
        for (int i = 0; i < 5; ++i) {
            dp[i] = 1;
        }
        for (int i = 2; i <= n; ++i) {
            /* a前面可以为e,u,i */
            ndp[0] = (dp[1] + dp[2] + dp[4]) % mod;
            /* e前面可以为a,i */
            ndp[1] = (dp[0] + dp[2]) % mod;
            /* i前面可以为e,o */
            ndp[2] = (dp[1] + dp[3]) % mod;
            /* o前面可以为i */
            ndp[3] = dp[2];
            /* u前面可以为i,o */
            ndp[4] = (dp[2] + dp[3]) % mod;
            System.arraycopy(ndp, 0, dp, 0, 5);
        }
        long ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans = (ans + dp[i]) % mod;
        }
        return (int)ans;
    }
}

539. 最小时间差

方法一：排序

将 timePoints排序后，最小时间差必然出现在 timePoints 的两个相邻时间，或者 timePoints的两个首尾时间中。因此排序后遍历一遍timePoints 即可得到最小时间差。

class Solution {
    public int findMinDifference(List<String> timePoints) {
        Collections.sort(timePoints);
        int ans = Integer.MAX_VALUE;
        int t0Minutes = getMinutes(timePoints.get(0));
        int preMinutes = t0Minutes;
        for (int i = 1; i < timePoints.size(); ++i) {
            int minutes = getMinutes(timePoints.get(i));
            ans = Math.min(ans, minutes - preMinutes); // 相邻时间的时间差
            preMinutes = minutes;
        }
        ans = Math.min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
        return ans;
    }

    public int getMinutes(String t) {
        return ((t.charAt(0) - '0') * 10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
    }
}

方法二：鸽巢原理

根据题意，一共有 24×60=1440种不同的时间。由鸽巢原理可知，如果 timePoints 的长度超过 1440，那么必然会有两个相同的时间，此时可以直接返回 0。

class Solution {
    public int findMinDifference(List<String> timePoints) {
        int n = timePoints.size();
        if (n > 1440) {
            return 0;
        }
        Collections.sort(timePoints);
        int ans = Integer.MAX_VALUE;
        int t0Minutes = getMinutes(timePoints.get(0));
        int preMinutes = t0Minutes;
        for (int i = 1; i < n; ++i) {
            int minutes = getMinutes(timePoints.get(i));
            ans = Math.min(ans, minutes - preMinutes); // 相邻时间的时间差
            preMinutes = minutes;
        }
        ans = Math.min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
        return ans;
    }

    public int getMinutes(String t) {
        return ((t.charAt(0) - '0') * 10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
    }
}

方法三

class Solution {
    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() >= 1440) {
            return 0;
        }

        int[] n = new int[1440 * 2];
        for (String t : timePoints) {
            int tMinute = getMinutes(t);
            n[tMinute]++;
            n[1440 + tMinute]++;
            if (n[tMinute] > 1) {
                return 0;
            }
        }

        int ans = 1440;
        int last = -1;
        // 比较到1440 * 1.5即可，差值都在其范围内，不用到1440 * 2
        for (int i = 0; i <= 1440 * 1.5; i++) {
           if (n[i] == 0) {
               continue;
           }
           if (last != -1) {
               ans = Math.min(i - last, ans);
           }
           last = i;
        }

        return ans;
    }

    public int getMinutes(String t) {
        return ((t.charAt(0) - '0') * 10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
    }
}

219. 存在重复元素 II

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            if(map.get(nums[i]) != null && Math.abs(map.get(nums[i]) - i) <= k){
                return true;
            }
            map.put(nums[i],i);
        }
        return false;
    }
}

1492. n 的第 k 个因子

class Solution {
    public int kthFactor(int n, int k) {
        int cnt = 0;
        for(int i = 1;i <= n;i++){
            if(n % i == 0){
                cnt++;
                if(cnt == k) return i;
            }
        }
        return -1;
    }
}

1345. 跳跃游戏 IV

class Solution {
    public int minJumps(int[] arr) {
        int n = arr.length;
        //构建一个arr[i]可以「等值跳」的map，可以跳的下标可能有多个，so value=List
        Map<Integer,List<Integer>> map = new HashMap<>();
        //从后往前添加，让后面的优先跳
        for(int i = n - 1;i >= 0;i--){
            List<Integer> list = map.getOrDefault(arr[i],new ArrayList<>());
            list.add(i);
            map.put(arr[i],list);
        }
        int[] dist = new int[n];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);
        dist[0] = 0;
        while(!q.isEmpty()){
            int cur = q.poll();
            int step = dist[cur];
            if(cur == n - 1) return step;
            if(cur + 1 < n && dist[cur + 1] == -1){
                q.offer(cur + 1);
                dist[cur + 1] = step + 1;
            }
            if(cur - 1 >= 0 && dist[cur - 1] == -1){
                q.offer(cur - 1);
                dist[cur - 1] = step + 1;
            }
            List<Integer> list = map.get(arr[cur]);
            if(list != null){
                for(Integer i : list){
                    if(dist[i] == -1){
                        q.offer(i);
                        dist[i] = step + 1;
                    }
                }
            }
            map.remove(arr[cur]);
        }
        return 0;
    }
}

1332. 删除回文子序列

class Solution {
    public int removePalindromeSub(String s) {
        for(int i = 0;i < s.length() / 2;i++){
            if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
                //不是回文串，删两次
                return 2;
            }
        }
        return 1;
    }
}

2034. 股票价格波动

class StockPrice {
    int curTime;
    //{时间戳:价格}
    Map<Integer,Integer> map;
    //treeMap{价格:该价格出现的次数}
    //利用TreeMap有序特性，首尾Key便是最低最高价格
    TreeMap<Integer,Integer> treeMap;

    public StockPrice() {
        curTime = 0;
        map = new HashMap<>();
        treeMap = new TreeMap<>();
    }
    
    public void update(int timestamp, int price) {
        curTime = Math.max(curTime,timestamp);
        if(map.containsKey(timestamp)){
            //存在该时间戳，维护treeMap
            //旧价格
            int old = map.get(timestamp);
            int cnt = treeMap.get(old);
            if(cnt == 1){
                treeMap.remove(old);
            }else{
                treeMap.put(old,cnt - 1);
            }
        }
        map.put(timestamp,price);
        treeMap.put(price,treeMap.getOrDefault(price,0) + 1);
    }
    
    public int current() {
        return map.get(curTime);
    }
    
    public int maximum() {
        return treeMap.lastKey();
    }
    
    public int minimum() {
        return treeMap.firstKey();
    }
}

1688. 比赛中的配对次数

method1:数学推理：最终冠军只剩一个队伍，因此有n - 1个无法晋级的队伍，也就会有n - 1场比赛

class Solution {
    public int numberOfMatches(int n) {
        return n - 1;
    }
}

method2:直接计算

class Solution {
    public int numberOfMatches(int n) {
      int ans = 0;
        while (n > 1) {
            if (n % 2 == 1) {
                ans += (n - 1) / 2;
                n = (n - 1) / 2 + 1;
            } else {
                ans += n / 2;
                n /= 2;
            }
        }
        return ans;
    }
}

2013. 检测正方形

class DetectSquares {
    Map<Integer, Map<Integer, Integer>> row2Col = new HashMap<>();
    
    public void add(int[] point) {
        int x = point[0], y = point[1];
        Map<Integer, Integer> col2Cnt = row2Col.getOrDefault(x, new HashMap<>());
        col2Cnt.put(y, col2Cnt.getOrDefault(y, 0) + 1);
        row2Col.put(x, col2Cnt);
    }
    
    public int count(int[] point) {
        int x = point[0], y = point[1];
        int ans = 0;
        Map<Integer, Integer> col2Cnt = row2Col.getOrDefault(x, new HashMap<>());
        for (int ny : col2Cnt.keySet()) {
            if (ny == y) continue;
            int c1 = col2Cnt.get(ny);
            int len = y - ny;
            int[] nums = new int[]{x + len, x - len};
            for (int nx : nums) {
                Map<Integer, Integer> temp = row2Col.getOrDefault(nx, new HashMap<>());
                int c2 = temp.getOrDefault(y, 0), c3 = temp.getOrDefault(ny, 0);
                ans += c1 * c2 * c3;
            }
        }
        return ans;
    }
}

2047. 句子中的有效单词数

class Solution {
    public int countValidWords(String sentence) {
        int ans = 0;
        String[] split = sentence.split(" ");
        for(String s : split){
            if(judge(s))ans++;
        }
        return ans;
    }

    private boolean judge(String s){
        if(s.length() == 0)return false;
        if((s.charAt(0) == '!' || s.charAt(0) == '.' || s.charAt(0) == ',') && s.length() == 1)return true;
        if(s.charAt(0) < 'a' || s.charAt(0) > 'z')return false;
        int cnt = 0;
        for(int i = 0;i < s.length();i++){
            char a = s.charAt(i);
            if(a >= '0' && a <= '9')return false;
            if(a == '-'){
                cnt++;
                if(cnt > 1)return false;
                if(i == s.length() - 1)return false;
                if(s.charAt(i + 1) < 'a' || s.charAt(i + 1) > 'z')return false;
            }
            if((a == '!' || a == '.' || a == ',') && i != s.length() - 1)return false;
        }
        return true;
    }
}

1996. 游戏中弱角色的数量

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties,(a,b)->{
            return a[0] != b[0] ? b[0] - a[0] : a[1] - b[1];
        });
        int ans = 0;
        int max = 0;
        for(int[] p : properties){
            if(p[1] < max){
                ans++;
            }else{
                max = p[1];
            }
        }
        return ans;
    }
}

1765. 地图中的最高点

class Solution {
    int[][] direction = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
    
        public int[][] highestPeak(int[][] isWater) {
            int m = isWater.length;
            int n = isWater[0].length;
            int[][] ans = new int[m][n];
            Deque<int[]> deque = new ArrayDeque<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isWater[i][j] == 1) {
                        ans[i][j] = 0;
                        deque.addLast(new int[]{i, j});
                    } else {
                        ans[i][j] = -1;
                    }
                }
            }

            while (!deque.isEmpty()) {
                int[] t = deque.pollFirst();
                int x = t[0], y = t[1];
                for (int[] d : direction) {
                    int nx = x + d[0];
                    int ny = y + d[1];
                    if (judge(nx, ny, ans)) {
                        ans[nx][ny] = ans[x][y] + 1;
                        deque.addLast(new int[]{nx, ny});
                    }
                }
            }
            return ans;
        }

        private boolean judge(int nx, int ny, int[][] ans) {
            if (nx < 0 || nx >= ans.length || ny < 0 || ny >= ans[0].length || ans[nx][ny] != -1) {
                return false;
            }
            return true;
        }
}

884. 两句话中的不常见单词

class Solution {
    public String[] uncommonFromSentences(String s1, String s2) {
        Map<String,Integer> map = new HashMap<>();
        List<String> ans = new ArrayList<>();

        String[] split1 = s1.split(" ");
        for(String s : split1){
            map.merge(s,1,Integer::sum);
        }
        String[] split2 = s2.split(" ");
        for(String s : split2){
            map.merge(s,1,Integer::sum);
        }
        map.forEach((k,v)->{
            if(v == 1){
                ans.add(k);
            }
        });

        String[] a = new String[ans.size()];
        return ans.toArray(a);
    }
}

1342. 将数字变成 0 的操作次数

class Solution {
    public int numberOfSteps(int num) {
        int ans = 0;
        while(num > 0){
            num = num % 2 == 0 ? num / 2 : num - 1;
            ans++;
        }
        return ans;
    }
}

680. 回文字符串

public boolean validPalindrome(String s) {
    for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
        if (s.charAt(i) != s.charAt(j)) {
            return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
        }
    }
    return true;
}

private boolean isPalindrome(String s, int i, int j) {
    while (i < j) {
        if (s.charAt(i++) != s.charAt(j--)) {
            return false;
        }
    }
    return true;
}

88. 归并两个有序数组

需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int index1 = m - 1, index2 = n - 1;
    int indexMerge = m + n - 1;
    while (index2 >= 0) {
        if (index1 < 0) {
            nums1[indexMerge--] = nums2[index2--];
        } else if (index2 < 0) {
            nums1[indexMerge--] = nums1[index1--];
        } else if (nums1[index1] > nums2[index2]) {
            nums1[indexMerge--] = nums1[index1--];
        } else {
            nums1[indexMerge--] = nums2[index2--];
        }
    }
}

630. 课程表 III

方法一：优先队列 + 贪心

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);

        PriorityQueue<Integer> q = new PriorityQueue<Integer>((a, b) -> b - a);
        // 优先队列中所有课程的总时间
        int total = 0;

        for (int[] course : courses) {
            int ti = course[0], di = course[1];
            if (total + ti <= di) {
                total += ti;
                q.offer(ti);
            } else if (!q.isEmpty() && q.peek() > ti) {
                total -= q.poll() - ti;
                q.offer(ti);
            }
        }

        return q.size();
    }
}

1462. 课程表 IV

方法一：广度优先搜索 + 拓扑排序

思路与算法

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<Integer>[] g = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<Integer>();
        }
        int[] indgree = new int[numCourses];
        boolean[][] isPre = new boolean[numCourses][numCourses];
        for (int[] p : prerequisites) {
            ++indgree[p[1]];
            g[p[0]].add(p[1]);
        }
        Queue<Integer> queue = new ArrayDeque<Integer>();
        for (int i = 0; i < numCourses; ++i) {
            if (indgree[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int ne : g[cur]) {
                isPre[cur][ne] = true;
                for (int i = 0; i < numCourses; ++i) {
                    isPre[i][ne] = isPre[i][ne] | isPre[i][cur];
                }
                --indgree[ne];
                if (indgree[ne] == 0) {
                    queue.offer(ne);
                }
            }
        }
        List<Boolean> res = new ArrayList<Boolean>();
        for (int[] query : queries) {
            res.add(isPre[query[0]][query[1]]);
        }
        return res;
    }
}

方法二：深度优先搜索 + 拓扑排序

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        List<Integer>[] g = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            g[i] = new ArrayList<Integer>();
        }
        boolean[] vi = new boolean[numCourses];
        boolean[][] isPre = new boolean[numCourses][numCourses];
        for (int[] p : prerequisites) {
            g[p[0]].add(p[1]);
        }
        for (int i = 0; i < numCourses; ++i) {
            dfs(g, isPre, vi, i);
        }
        List<Boolean> res = new ArrayList<Boolean>();
        for (int[] query : queries) {
            res.add(isPre[query[0]][query[1]]);
        }
        return res;
    }

    public void dfs(List<Integer>[] g, boolean[][] isPre, boolean[] vi, int cur) {
        if (vi[cur]) {
            return;
        }
        vi[cur] = true;
        for (int ne : g[cur]) {
            dfs(g, isPre, vi, ne);
            isPre[cur][ne] = true;
            for (int i = 0; i < isPre.length; ++i) {
                isPre[cur][i] = isPre[cur][i] | isPre[ne][i];
            }
        }
    }
}

486.预测赢家

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        return total(nums, 0, nums.length - 1, 1) >= 0;
    }

    public int total(int[] nums, int start, int end, int turn) {
        if (start == end) {
            return nums[start] * turn;
        }
        int scoreStart = nums[start] * turn + total(nums, start + 1, end, -turn);
        int scoreEnd = nums[end] * turn + total(nums, start, end - 1, -turn);
        return Math.max(scoreStart * turn, scoreEnd * turn) * turn;
    }
}

上述最后一行代码可改成：

if(turn == 1){
    return Math.max(scoreStart ,scoreEnd );
}else{
    return Math.min(scoreStart ,scoreEnd );
}

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[][] dp = new int[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][length - 1] >= 0;
    }
}

class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        for (int i = 0; i < length; i++) {
            dp[i] = nums[i];
        }
        for (int i = length - 2; i >= 0; i--) {
            for (int j = i + 1; j < length; j++) {
                dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
            }
        }
        return dp[length - 1] >= 0;
    }
}