Atopos's Blog

One step at a time!

0%

LeetCode 每日一题

发表于 更新于 分类于
本文字数： 20k 阅读时长 ≈ 18 分钟
LeetCode 每日一题

0306：使字符串平衡的最少删除次数

使字符串平衡的最少删除次数

标签

栈、字符串、动态规划

思路

枚举

通过删除字符，是字符串达到平衡状态，主要有以下三种情况：

  • 字符串里全是a
  • 字符串里全是b
  • 字符串里既有a又有b，且a全在b的左侧

首先定义两个变量righta和leftb，其中righta用来记录划分为两个部分中在右边的a的字符的数量，leftb用来保存两个部分中在左边的b的字符的数量。

动态规划

状态表示：f[i]表示前i个字符平衡需要最少的删除次数

状态方程：需要注意前i个字符，中最后一个字符的下标为i - 1

  • 如果s[i - 1] == 'b'，则f[i] = f[i - 1]
  • 如果s[i - 1] == 'a'，则需要在f[i - 1] + 1（表示删除a）和countb选择较小的值。其中countb表示直到第i - 1个时字符b的个数。状态方程表示为：f[i] = min(f[i - 1] + 1, countb)

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minimumDeletions(String s) {
        int righta = 0, leftb = 0; // 分别记录划分后在右边的a的个数，和在左边的b的个数
        for(int i = 0; i < s.length(); i ++) {
            char ch = s.charAt(i);
            if(ch == 'a') righta ++;
        }
        int res = righta;
        for(int i = 0; i < s.length(); i ++) {  // 以第i个字符位分界线，[0, i]是左边，[i + 1, n - 1] 是右边
            char ch = s.charAt(i);
            if(ch == 'a') righta --;
            else leftb ++;
            res = Math.min(res, righta + leftb);
        } 
        return res;
    }
}
  • 时间复杂度：$O(n)$，其中n是字符串s的长度。
  • 空间复杂度：$O(1)$

执行用时：54 ms, 在所有 Java 提交中击败了13.19%的用户

内存消耗：42.4 MB, 在所有 Java 提交中击败了32,41%的用户

通过测试用例：157 / 157个通过测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        int f[n + 1];  // f[i] 表示前i个字符是平衡的所需要的最少删除次数
        f[0] = 0;
        int countb = 0;
        for(int i = 1; i <= s.size(); i ++) {
            if(s[i - 1] == 'b') {
                f[i] = f[i - 1];
                countb ++;
            }
            else {
                f[i] = min(f[i - 1] + 1, countb);  // 删除a或者删除b
            } 
        }
        return f[n];
    }
};
  • 时间复杂度：$O(n)$，其中n是字符串s的长度。
  • 空间复杂度：$O(1)$

执行用时：72 ms, 在所有 C++ 提交中击败了77.94%的用户

内存消耗：22 MB, 在所有 C++ 提交中击败了57.84%的用户

通过测试用例：157 / 157个通过测试用例

0307：花括号展开 II❗

花括号展开 II

标签

栈、广度优先搜索、字符串、回溯

题解

1

  • 时间复杂度：$O(n)$，其中n是字符串s的长度。
  • 空间复杂度：$O(1)$

执行用时：54 ms, 在所有 Java 提交中击败了13.19%的用户

内存消耗：42.4 MB, 在所有 Java 提交中击败了32,41%的用户

通过测试用例：157 / 157个通过测试用例

0308：礼物的最大价值

礼物的最大价值

标签

数组、动态规划、矩阵

思路

使用动态规划

状态表示：dp[i][j] 表示从左上角走到[i,j]能拿的最大价值。

状态转移：

  • 从当前位置上面拿：dp[i][j] = dp[i - 1][j] + grid[i][j]
  • 从当前位置左边拿：dp[i][j] = dp[i][j - 1] + grid[i][j]
  • 最后取最大值即可：dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

注意：需要考虑出界的问题。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[][] dp = new int[m][n];

        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j ++) {
                if(i > 0) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                if(j > 0) dp[i][j] = Math.max(dp[i][j], dp[i][j - 1]);
                dp[i][j] += grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }
}
  • 时间复杂度：$O(m n)$，其中n*是矩阵grid的行数，m是矩阵grid的列数。
  • 空间复杂度：$O(m n)$，其中n*是矩阵grid的行数，m是矩阵grid的列数。

执行用时：4 ms, 在所有 Java 提交中击败了3.89%的用户

内存消耗：43.8 MB, 在所有 Java 提交中击败了79.16%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        int dp[m][n];
        memset(dp, 0, sizeof(dp));  // 将数组初始化为0

        for(int i = 0; i < m; i ++) {
            for(int j = 0; j < n; j ++) {
                if(i > 0) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
                if(j > 0) dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                dp[i][j] += grid[i][j];
            }
        }

        return dp[m - 1][n - 1];
    }
};
  • 时间复杂度：$O(m n)$，其中n*是矩阵grid的行数，m是矩阵grid的列数。
  • 空间复杂度：$O(m n)$，其中n*是矩阵grid的行数，m是矩阵grid的列数。

执行用时：0 ms, 在所有 Java 提交中击败了100%的用户

内存消耗：9 MB, 在所有 Java 提交中击败了53.92%的用户

知识点

C++将数组初始化为0或任意值：memset(需要初始化的数组, 需要初始化的值, sizeof(数组名));

1
2
int arr[10][10];
memset(arr, 0, sizeof(arr));

0309：得到 K 个黑块的最少涂色次数

得到 K 个黑块的最少涂色次数

标签

字符串、滑动窗口

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minimumRecolors(String blocks, int k) {
        int count = 0;
        int res = 500;
        for(int l = 0, r = 0; r < blocks.length(); r ++){
            if(r >= k - 1) {  // k个元素已经满了
                if(blocks.charAt(r) == 'W') count ++;  // 先将最新的元素入栈
                res = Math.min(count, res);   // 已经满足k个元素，求res
                if(blocks.charAt(l ++) == 'W') count --;  // 遍历下一元素时，需要将左侧元素出队
            } else {  // 不到k个元素时，一直入队
                if(blocks.charAt(r) == 'W') count ++; 
            }
        }
        return res;
    }
}
  • 时间复杂度：$O(n)$，其中n是字符串block的长度。
  • 空间复杂度：$O(1)$

执行用时：1 ms, 在所有 Java 提交中击败了58.27%的用户

内存消耗：39.7 MB, 在所有 Java 提交中击败了39.37%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int count = 0;
        int res = 500;
        for(int l = 0, r = 0; r < blocks.size(); r ++) {
            if(r >= k - 1) {
                if(blocks[r] == 'W') count ++;
                res = min(res, count);
                if(blocks[l ++] == 'W') count --;
            } else {
                if(blocks[r] == 'W') count ++;
            }
        }
        return res;
    }
};
  • 时间复杂度：$O(n)$，其中n是字符串block的长度。
  • 空间复杂度：$O(1)$

执行用时：8 ms, 在所有 Java 提交中击败了2.87%的用户

内存消耗：6.1 MB, 在所有 Java 提交中击败了15.16%的用户

知识点

判断某个字符是否存在于字符串String中，可以使用函数contains()，需要将字符转为字符串。

1
2
String str = "abgsdfkjdg"；
str.contains('a' + "");

0309：递增子序列

递增子序列

标签

位运算、数组、哈希表、回溯

题解

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
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> arr = new ArrayList<>();

    // nums 数组，npc：本次低轨开始的下标，pre：前一个加入arr集合中的数
    void dfs(int[] nums, int npc, int pre) {
        if(npc >= nums.length) return; // 低轨出口
        Set<Integer> hset = new HashSet<>();  // hashset 用来保存本层低轨中所有使用过的数
        for(int i = npc; i < nums.length; i ++) {
            if(i == 0 || (!hset.contains(nums[i]) && nums[i] >= pre)) {  // 如果是第一个数 或者 当前数大于前一个数并且不存在于hashset中，则可以加入arr
                arr.add(nums[i]);
                hset.add(nums[i]);
                if(arr.size() >= 2) {  // 如果list里已经存了大于等于两个的数，则直接加入res
                    res.add(new ArrayList<Integer>(arr));
                }
                dfs(nums, i + 1, nums[i]);
                arr.remove(arr.size() - 1);  // 恢复现场
            }
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(nums, 0, -101);
        return res;
    }
}
  • 时间复杂度：$O(n)$，其中n是字符串block的长度。
  • 空间复杂度：$O(1)$

执行用时：1 ms, 在所有 Java 提交中击败了58.27%的用户

内存消耗：39.7 MB, 在所有 Java 提交中击败了39.37%的用户

0310：使数组和能被P整除❗

使数组和能被P整除

标签

数组、哈希表、前缀和

思路

首先需要了解两个定理：

定理一：给定整数x、y、z、p，如果$y\ mod\ p = x$，那么$(y - z)\ mod\ p = 0$ 等价于$z\ mod\ p = x$

定理二：给定正整数x、y、z、p，那么$(y - z)\ mod\ p = x$ 等价于 $z\ mod\ p = (y - x)\ mod\ p$

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minSubarray(int[] nums, int p) {
        int x = 0;
        for (int num : nums) {
            x = (x + num) % p;
        }
        if (x == 0) {
            return 0;
        }
        Map<Integer, Integer> index = new HashMap<Integer, Integer>();
        int y = 0, res = nums.length;
        for (int i = 0; i < nums.length; i++) {
            index.put(y, i); // f[i] mod p = y，因此哈希表记录 y 对应的下标为 i
            y = (y + nums[i]) % p;
            if (index.containsKey((y - x + p) % p)) {
                res = Math.min(res, i - index.get((y - x + p) % p) + 1);
            }
        }
        return res == nums.length ? -1 : res;
    }
}
  • 时间复杂度：$O(n)$，其中n是数组nums的长度。
  • 空间复杂度：$O(n)$，哈希表的空间复杂度

执行用时：28 ms, 在所有 Java 提交中击败了33.58%的用户

内存消耗：56.1 MB, 在所有 Java 提交中击败了96.27%的用户

0311：字母与数字💡

字母与数字

标签

数组、哈希表、前缀和

思路

主要使用到前缀和和哈希表，哈希表的部分类似（题目 两数之和 ）

定义前缀和数组为sum，sum[0] = 0 遍历一遍数组，如果是字母，则sum[i + 1] = sum[i] - 1，否则是数字：sum[i + 1] = sum[i] + 1

使用哈希表遍历前缀和数组，如果存在sum[i] == sum[j]则说明在i~j之间的字母和数字数量相等。然后找出满足条件的最大同时也是最左侧的子数组。

题解

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
class Solution {
    public String[] findLongestSubarray(String[] array) {
        int n = array.length;
        int[] sum = new int[n + 1];  // 数字 -1， 字母 +1
        sum[0] = 0;
        Map<Integer, Integer> hsp = new HashMap<>();
        int count = 0;
        int l = 0;
        for(int i = 0; i < array.length; i ++) {
            if(array[i].charAt(0) >= 'A' && array[i].charAt(0) <= 'Z' || array[i].charAt(0) >= 'a' && array[i].charAt(0) <= 'z')
                sum[i + 1] = sum[i] - 1;
            else if(array[i].charAt(0) >= '0' && array[i].charAt(0) <= '9')
                sum[i + 1] = sum[i] + 1;
        }

        for(int i = 0; i <= n; i ++) {
            if(!hsp.containsKey(sum[i])) 
                hsp.put(sum[i], i); // 将 sum[i] : i 加入哈希表
            else {
                int x = hsp.get(sum[i]); // 获得当前值的左边界的下标 [x, i]之间的数字和字母数量相等。
                int ans = i - x; // 中间字符的总数
                if(count < ans) {  // 当前记录的数量小于此刻的数量
                    count = ans;
                    l = x;
                }
            }
        }
        // [l, l + count - 1]
        System.out.println(l + " " + count);
        
        if(count == 0) return new String[]{};
        return Arrays.copyOfRange(array, l, l + count);
    }
}
  • 时间复杂度：$O(n)$，其中n是数组array的长度。
  • 空间复杂度：$O(n)$，哈希表的空间复杂度和前缀和数组

执行用时：31 ms, 在所有 Java 提交中击败了8.49%的用户

内存消耗：60.9 MB, 在所有 Java 提交中击败了44.81%的用户

知识点

java中将一个数组中的部分元素复制到另一个数组中方法：使用Arrays.copyOfRange(orginalArray, startIndex, endIndex)函数

1
2
int[] data = {1,2,3,4,5,6,7,8};
int[] newData = Arrays.copyOfRange(data, 2, 7);

0312：统计子树中城市之间最大距离

统计子树中城市之间最大距离

标签

位运算、树、动态规划、状态压缩、枚举

题解

1

  • 时间复杂度：$O(n)$，其中n是数组array的长度。
  • 空间复杂度：$O(n)$，哈希表的空间复杂度和前缀和数组

执行用时：31 ms, 在所有 Java 提交中击败了8.49%的用户

内存消耗：60.9 MB, 在所有 Java 提交中击败了44.81%的用户

0313：赢得比赛需要的最少训练时长

赢得比赛需要的最少训练时长

标签

贪心、数组

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
        int res = 0;
        for(int x : energy) {
            if(initialEnergy <= x) {
                res += (x - initialEnergy + 1);
                initialEnergy += (x - initialEnergy + 1);
            }
            initialEnergy -= x;
        }
        for(int x : experience) {
            if(initialExperience <= x) {
                res += (x - initialExperience + 1);
                initialExperience += (x - initialExperience + 1);
            }
            initialExperience += x;
        }
        return res;

    }
}
  • 时间复杂度：$O(n)$，其中n是数组energy的长度。
  • 空间复杂度：$O(1)$

执行用时：0 ms, 在所有 Java 提交中击败了100%的用户

内存消耗：40.5 MB, 在所有 Java 提交中击败了94.61%的用户

0314：给定行和列的和求可行矩阵

给定行和列的和求可行矩阵

标签

数组、矩阵、贪心

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[][] restoreMatrix(int[] rowSum, int[] colSum) {
        int m = rowSum.length;
        int n = colSum.length;
        int[][] res = new int[m][n];
        for(int i = 0; i < m; i ++ ){
            int row = rowSum[i];
            for(int j = 0; j < n; j ++) {
                int col = colSum[j];
                int cnt = Math.min(row, col);  // 这个位置需要填写的值
                res[i][j] = cnt;
                row -= cnt;
                colSum[j] -= cnt;
            } 
        }
        return res;
    }
}
  • 时间复杂度：$O(mn)$，其中m是数组rowSum的长度，n是数组colSum的长度。
  • 空间复杂度：$O(mn)$，结果数组res的大小。

执行用时：4 ms, 在所有 Java 提交中击败了67.94%的用户

内存消耗：49.5 MB, 在所有 Java 提交中击败了35.11%的用户

0315：最大网络秩

最大网络秩

标签

图、哈希表

思路

哈希表：

将所有节点及其对应的边保存在哈希表中，对哈希表按照value进行排序，然后取出边数是前两大的所有节点，对这些节点进行遍历，判断是否两个节点有相连。并求res

题解

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
class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        Map<Integer, Integer> hsp = new HashMap<>();
        for(int i = 0; i < roads.length; i ++) {
            if(!hsp.containsKey(roads[i][0])) hsp.put(roads[i][0], 1);
            else {
                hsp.put(roads[i][0], hsp.get(roads[i][0]) + 1);
            }
            if(!hsp.containsKey(roads[i][1])) hsp.put(roads[i][1], 1);
            else {
                hsp.put(roads[i][1], hsp.get(roads[i][1]) + 1);
            }
        }
        
        List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(hsp.entrySet());
        Collections.sort(list, (o1, o2) -> {
            if(o1.getValue() != null && o2.getValue() != null && o2.getValue().compareTo(o1.getValue()) > 0) {
                return 1;
            } else if(o2.getValue().compareTo(o1.getValue()) == 0){  // 键相等
                if(o1.getKey() != null && o2.getKey() != null && o2.getKey().compareTo(o1.getKey()) < 0) {
                    return 1;
                } else {
                    return -1;
                }
            } else {
                return -1;
            }
        });
        for(Map.Entry<Integer, Integer> entry : list) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
        
        List<Integer> arr = new ArrayList<>();
        int num = 0, pre = -1;  // num 表示加了几次节点对应的边数
        for(Map.Entry<Integer, Integer> entry : list) {
            if(num == 0 || num == 1) {
                // res += entry.getValue();
                arr.add(entry.getKey());
                pre = entry.getValue();
                num ++;
            } 
            else if(entry.getValue() == pre) {  // 后面还有和前一节点边数相等的节点
                arr.add(entry.getKey());
            } else {
                break;
            }
        }
        int res = 0;
        for(int i = 0; i < arr.size() - 1; i ++) {
            for(int j = i + 1; j < arr.size(); j ++) {
                int sum = 0;
                int start = arr.get(i), end = arr.get(j);
                sum += (hsp.get(start) + hsp.get(end));
                for(int k = 0; k < roads.length; k ++) {
                    if(roads[k][0] == start && roads[k][1] == end || roads[k][1] == start && roads[k][0] == end) {
                        sum --;
                        break;
                    }
                }
                res = Math.max(res, sum);
            }
        }

        return res;
    }
}
  • 时间复杂度：$O(nnn)$，其中n是节点的个数。
  • 空间复杂度：$O(n)$，哈希表。

执行用时：52 ms, 在所有 Java 提交中击败了5.65%的用户

内存消耗：43.7 MB, 在所有 Java 提交中击败了5.21%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        boolean[][] st = new boolean[n][n];
        int[] node = new int[n];
        for(int[] v : roads) {
            st[v[0]][v[1]] = true;
            st[v[1]][v[0]] = true;
            node[v[0]] ++;
            node[v[1]] ++;
        }
        int res = 0;
        for(int i = 0; i < n - 1; i ++) {
            for(int j = i + 1; j < n; j ++) {
                res = Math.max(res, node[i] + node[j] - (st[i][j] ? 1 : 0));
            }
        }
        return res;
    }
}
  • 时间复杂度：$O(n)$，其中n是节点的个数。
  • 空间复杂度：$O(n*n)$，哈希表。

执行用时：4 ms, 在所有 Java 提交中击败了34.78%的用户

内存消耗：41.7 MB, 在所有 Java 提交中击败了88.25%的用户

知识点

HashMap按照value进行排序，实际上用的是ArrayList排序的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Map<Integer, Integer> hsp = new HashMap<>();
// 进行排序
List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(hsp.entrySet());
Collections.sort(list, (o1, o2) -> {
    if(o1.getValue() != null && o2.getValue() != null && o2.getValue().compareTo(o1.getValue()) > 0) {
        return 1;
    } else if(o2.getValue().compareTo(o1.getValue()) == 0){  // 键相等
        if(o1.getKey() != null && o2.getKey() != null && o2.getKey().compareTo(o1.getKey()) < 0) {
            return 1;
        } else {
            return -1;
        }
    } else {
        return -1;
    }
});
// 输出
for(Map.Entry<Integer, Integer> entry : list) {
    System.out.println(entry.getKey() + " " + entry.getValue());
}

哈希表遍历⭐

1
2
3
4
5
6
7
Map<Integer, Integer> hsp = new HashMap<>();
Interator<Map.Entry<Integer, Integer>> iterator = hsp.entrySet().iterator();
while(iterator.hasNext()) {
    Map.Entry<Integer, Integer> entry = iterator.next();
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}
1
2
3
4
5
6
7
Map<Integer, Integer> hsp = new HashMap<>();
Iterator<Integer> iterator = hsp.keySet().iterator();
while (iterator.hasNext()) {
    Integer key = iterator.next();
    System.out.println(key);
    System.out.println(map.get(key));
}
1
2
3
4
5
Map<Integer, Integer> hsp = new HashMap<>();
for (Map.Entry<Integer, String> entry : hsp.entrySet()) {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
}
1
2
3
4
5
Map<Integer, Integer> hsp = new HashMap<>();
for (Integer key : hsp.keySet()) {
    System.out.println(key);
    System.out.println(map.get(key));
}
1
2
3
4
5
Map<Integer, Integer> hsp = new HashMap<>();
hsp.forEach((key, value) -> {
    System.out.println(key);
    System.out.println(value);
});
1
2
3
4
5
Map<Integer, Integer> hsp = new HashMap<>();
hsp.entrySet().stream().forEach((entry) -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});
1
2
3
4
5
Map<Integer, Integer> hsp = new HashMap<>();
map.entrySet().parallelStream().forEach((entry) -> {
    System.out.println(entry.getKey());
    System.out.println(entry.getValue());
});

0316：统计中位数为K的子数组

统计中位数为K的子数组

标签

数组、哈希表、前缀和

思路

更新nums数组：

  • 当nums[i] > k时，则nums[i] = 1;
  • 当nums[i] < k时，则nums[i] = -1;
  • 当nums[i] == k时，则nums[i] = 0;

计算前缀和sum，如果[i ~ j-1]的和为0，则是奇数个中位数为k，和为1，则是偶数个中位数为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
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int countSubarrays(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        sum[0] = 0;
        int npc = -1; // 记录k在nums中的位置
        for(int i = 0; i < n; i ++) {
            if(nums[i] < k) nums[i] = -1;
            else if(nums[i] > k) nums[i] = 1;
            else {
                npc = i;
                nums[i] = 0;
            }
            sum[i + 1] = sum[i] + nums[i];
        }

        Map<Integer, Integer> hsp = new HashMap<>();
        int res = 0;
        // 如果是奇数个的话,则有sum[j, i-1] = 0, 偶数个 sum[j, i - 1] = 1;
        for(int i = 0; i <= n; i ++) {
            if(!hsp.containsKey(sum[i]) && i <= npc) hsp.put(sum[i], 1);
            else if(hsp.containsKey(sum[i])) {
                int x = hsp.get(sum[i]);
                if(npc < i)
                    res += x;
                if(i <= npc)
                    hsp.put(sum[i], x + 1);
            }
            if(!hsp.containsKey(sum[i] + 1) && i <= npc) hsp.put(sum[i] + 1, 1);
            else if(hsp.containsKey(sum[i] + 1)) {
                int x = hsp.get(sum[i] + 1);
                if(i <= npc)
                    hsp.put(sum[i] + 1, x + 1);
            }
        }
        return res;
        
    }
}
  • 时间复杂度：$O(n)$，其中n是数组nums的大小。
  • 空间复杂度：$O(n)$，前缀和数组sum的大小

执行用时：33 ms, 在所有 Java 提交中击败了5.71%的用户

内存消耗：57.6 MB, 在所有 Java 提交中击败了5%的用户

0317：和有限的最长子序列

和有限的最长子序列

标签

贪心、数组、二分查找、前缀和、排序

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] answerQueries(int[] nums, int[] queries) {
        Arrays.sort(nums);
        int[] res = new int[queries.length];
        for(int i = 0; i < queries.length; i ++) {
            int tar = queries[i];
            int sum = 0;
            for(int j = 0; j < nums.length; j ++) {
                sum += nums[j];
                if(sum > tar) {
                    res[i] = j;
                    break;
                }
            }
            if(sum <= tar) res[i] = nums.length;
        }
        return res;
    }
}
  • 时间复杂度：$O(nm)$，其中n是数组nums的大小，m是数组queries的大小。
  • 空间复杂度：$O(n)$，结果数组res的大小。

执行用时：6 ms, 在所有 Java 提交中击败了58.97%的用户

内存消耗：42.1 MB, 在所有 Java 提交中击败了49.85%的用户

0318：分割两个字符串得到回文串💡

分割两个字符串得到回文串

标签

双指针、字符串

题解

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
class Solution {
    public boolean checkPalindromeFormation(String a, String b) {
        return checkConcatenation(a, b) || checkConcatenation(b, a);
    }

    public boolean checkConcatenation(String a, String b) {
        int n = a.length();
        int left = 0, right = n - 1;
        while (left < right && a.charAt(left) == b.charAt(right)) {
            left++;
            right--;
        }
        if (left >= right) {
            return true;
        }
        return checkSelfPalindrome(a, left, right) || checkSelfPalindrome(b, left, right);
    }

    public boolean checkSelfPalindrome(String a, int left, int right) {
        while (left < right && a.charAt(left) == a.charAt(right)) {
            left++;
            right--;
        }
        return left >= right;
    }
}
  • 时间复杂度：$O(n)$，其中n是输入字符串的长度。每个字符串最多遍历两边。
  • 空间复杂度：$O(1)$，仅使用常数空间。

执行用时：3 ms, 在所有 Java 提交中击败了96.41%的用户

内存消耗：42.2 MB, 在所有 Java 提交中击败了45.2%的用户

0319：执行操作后字典序最小的字符串

执行操作后字典序最小的字符串

标签

广度优先搜索、字符串

思路

使用栈 + 广度优先搜索，每次先将当前元素出栈，然后和当前记录的最小字符串比较，然后如果更小，则进行更新。然后分别进行两种操作，如果操作过后没有遇到过，则将其入栈，然后用哈希表记录。一直循环直到栈为空。

题解

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
class Solution {
    Map<String, Boolean> hsp = new HashMap<>();
    Stack<String> stk = new Stack<>();
    String res;

    void bfs(String s, int a, int b) {
        stk.push(s);
        hsp.put(s, true);
        while(!stk.empty()) {
            String str = stk.pop();  // 弹出栈顶元素
            int n = str.length();

            if(str.compareTo(res) < 0) {
                res = str;
            }

            StringBuilder strs = new StringBuilder();  // 用来保存奇数位置加a
            for(int i = 0; i < str.length(); i ++) {
                if(i % 2 == 0) strs.append(str.charAt(i)); // 偶数位置
                else {  // 奇数位置
                    char ch = str.charAt(i);
                    int c = ((ch - '0') + a) % 10;
                    strs.append(String.valueOf(c));
                }
            }
            if(!hsp.containsKey(strs.toString())){
                stk.push(strs.toString());
                hsp.put(strs.toString(), true);
            }
            String second = str.substring(n - b) + str.substring(0, n - b);  // 轮转b位
            if(!hsp.containsKey(second)) {
                stk.push(second);
                hsp.put(second, true);
            }
        }
    }

    public String findLexSmallestString(String s, int a, int b) {
        res = s;
        bfs(s, a, b);
        return res;
    }
}
  • 时间复杂度：$O(n^2)$，其中n是字符串s的长度。
  • 空间复杂度：$O(2n)$，栈的大小。

执行用时：256 ms, 在所有 Java 提交中击败了5.66%的用户

内存消耗：49.3 MB, 在所有 Java 提交中击败了16.98%的用户

0320：最少有1位重复数字❗【未作】

最少有1位重复数字

标签

数学、动态规划

题解

1

  • 时间复杂度：$O(n^2)$，其中n是字符串s的长度。
  • 空间复杂度：$O(2n)$，栈的大小。

执行用时：256 ms, 在所有 Java 提交中击败了5.66%的用户

内存消耗：49.3 MB, 在所有 Java 提交中击败了16.98%的用户

0321：温度转换

温度转换

标签

数学

题解

1
2
3
4
5
6
7
8
class Solution {
    public double[] convertTemperature(double celsius) {
        double[] res = new double[2];
        res[0] = celsius + 273.15;
        res[1] = celsius * 1.8 + 32;
        return res;
    }
}
  • 时间复杂度：$O(1)$，只需要常数级的时间复杂度。
  • 空间复杂度：$O(1)$，只需要常数级的空间。

执行用时：0 ms, 在所有 Java 提交中击败了100%的用户

内存消耗：40 MB, 在所有 Java 提交中击败了33.61%的用户

0322：无矛盾的最佳球队❗【未做】

无矛盾的最佳球队

标签

数组、动态规划、排序

题解

1

  • 时间复杂度：$O(1)$，只需要常数级的时间复杂度。
  • 空间复杂度：$O(1)$，只需要常数级的空间。

执行用时：0 ms, 在所有 Java 提交中击败了100%的用户

内存消耗：40 MB, 在所有 Java 提交中击败了33.61%的用户

0323：等差子数组

等差子数组

标签

数组、排序

题解

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
class Solution {
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {
        List<Boolean> lists = new ArrayList<>();
        int n = l.length;
        for(int i = 0; i < n; i ++) {
            int[] arr;
            arr = Arrays.copyOfRange(nums, l[i], r[i] + 1);
            Arrays.sort(arr);
            int len = arr.length;
            if(len == 1) {
                lists.add(true);
                continue;
            }
            int npc = arr[1] - arr[0];
            boolean flag = true;
            for(int j = 2; j < len; j ++) {
                if(arr[j] - arr[j - 1] != npc) {
                    flag = false;
                    break;
                } 
            }
            lists.add(flag);
        }
        return lists;
    }
}
  • 时间复杂度：$O(n * m)$，其中n是指数组l的长度，m是数组nums的长度。
  • 空间复杂度：$O(n)$，只需要常数级的空间。

执行用时：18 ms, 在所有 Java 提交中击败了64.68%的用户

内存消耗：42.2 MB, 在所有 Java 提交中击败了30.16%的用户

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
class Solution {
public:
    vector<bool> checkArithmeticSubarrays(vector<int>& nums, vector<int>& l, vector<int>& r) {

        vector<bool> res;
        for(int i = 0; i < l.size(); i ++) {
            vector<int> arr(nums.begin() + l[i], nums.begin() + r[i] + 1);
            sort(arr.begin(), arr.end());
            if(arr.size() == 1 || arr.size() == 2) res.push_back(true);
            else {
                int x = arr[1] - arr[0];
                bool flag = true;
                for(int i = 2; i < arr.size(); i ++) {
                    if(arr[i] - arr[i - 1] != x) {
                        flag = false;
                        break;
                    }
                }
                res.push_back(flag);
            }
        
        }
        return res;
    }
};
  • 时间复杂度：$O(n * m)$，其中n是指数组l的长度，m是数组nums的长度。
  • 空间复杂度：$O(n)$，只需要常数级的空间。

执行用时：44 ms, 在所有 Java 提交中击败了76.3%的用户

内存消耗：25.2 MB, 在所有 Java 提交中击败了38.58%的用户

0329：统计字典序元音字符串的数目

统计字典序元音字符串的数目

标签

数学、动态规划、组合数学

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    char[] ch = {'a', 'e', 'i', 'o', 'u'};
    int res = 0;
    void dfs(int n, StringBuilder str, int npc) {
        if(str.length() == n) {
            res ++;
            return ;
        }
        for(int i = npc; i < 5; i ++) {
            str.append(ch[i]);
            dfs(n, str, i);
            str.deleteCharAt(str.length() - 1);
        }
    }
    public int countVowelStrings(int n) {
        StringBuilder str = new StringBuilder();
        dfs(n, str, 0);
        return res;
    }
}
  • 时间复杂度：$O(n * n)$。
  • 空间复杂度：$O(1)$，只需要常数级的空间。

执行用时：404 ms, 在所有 Java 提交中击败了5.58%的用户

内存消耗：38 MB, 在所有 Java 提交中击败了91.88%的用户

正在加载今日诗词....