发表更新算法 / LeetCode3 分钟读完 (大约447个字)

第 112 场力扣夜喵双周赛

判断通过操作能否让字符串相等 I

同下。

判断通过操作能否让字符串相等 II

模拟。也可以手动比较，就是适用性不好。（PS：想出一个写法，结果被自己 Hack 掉了~）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean checkStrings(String s1, String s2) {
        int n = s1.length();
        int[][] c1 = new int[2][26], c2 = new int[2][26];
        for (int i = 0; i < n; i++) {
            c1[i & 1][s1.charAt(i) - 'a']++;
            c2[i & 1][s2.charAt(i) - 'a']++;
        }
        return Arrays.deepEquals(c1, c2);
    }
}

几乎唯一子数组的最大和

滑动窗口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public long maxSum(List<Integer> nums, int m, int k) {
        int n = nums.size();
        long sum = 0L, ans = 0L;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.merge(nums.get(i), 1, Integer::sum);
            sum += nums.get(i);
            if (i >= k - 1) {
                if (map.size() >= m) ans = Math.max(ans, sum);
                if (map.merge(nums.get(i - k + 1), -1, Integer::sum) == 0) {
                    map.remove(nums.get(i - k + 1));
                }
                sum -= nums.get(i - k + 1);
            }
        }
        return ans;
    }
}

统计一个字符串的 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
40
41
42
43
class Solution {
    private static final long MOD = (long) 1e9 + 7;

    public int countKSubsequencesWithMaxBeauty(String s, int k) {
        char[] ss = s.toCharArray();
        int[] cnt = new int[26];
        for (char c : ss) {
            cnt[c - 'a']++;
        }
        TreeMap<Integer, Integer> map = new TreeMap<>((a, b) -> b - a);
        for (int i = 0; i < 26; i++) {
            map.merge(cnt[i], 1, Integer::sum);
        }
        long ans = 1L;
        for (var e : map.entrySet()) {
            int key = e.getKey(), val = e.getValue();
            if (val >= k) {
                return (int) (ans * comb(val, k) % MOD * pow(key, k) % MOD);
            }
            k -= val;
            ans = (ans * pow(key, val)) % MOD;
        }
        return 0;
    }
    
    private long pow(long x, int n) {
        long res = 1L;
        while (n != 0) {
            if ((n & 1) == 1) res = (res * x) % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }

    private long comb(long n, int k) {
        long res = n;
        for (int i = 2; i <= k; i++) {
            res = res * --n / i;
        }
        return res % MOD;
    }
}
发表更新算法 / LeetCode8 分钟读完 (大约1134个字)

第 360 场力扣周赛

距离原点最远的点

核心：要距离原点最远，那么可选的位置肯定是向同一个方向移动。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int furthestDistanceFromOrigin(String moves) {
        int n = moves.length(), dis = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            char c = moves.charAt(i);
            if (c == 'L') dis--;
            else if (c == 'R') dis++;
            else cnt++;
        }
        return Math.max(cnt - dis, cnt + dis);
    }
}

找出美丽数组的最小和

和上周一样的题目。

1
2
3
4
5
6
class Solution {
    public long minimumPossibleSum(int n, int target) {
        long m = Math.min(target / 2, n);
        return (m * (m + 1) + (target * 2 + n - m - 1) * (n - m)) / 2;
    }
}

使子序列的和等于目标的最少操作次数

比赛时思路满天飞，各种乱写。其实最后的思路是对的，但是基于之前的代码改写，导致有很多 Bug。赛后 15 分钟 AC。从低位到高位枚举 \(target\) 中的 \(1\)，假设当前 \(1\) 对应的值为 \(x\)，那么 \(nums\) 中所有小于等于 \(x\) 的值都可以用来填补 \(x\)，如果不够那么肯定需要将下一个大于 \(x\) 的值分解为 \(x\)。（更优的做法）

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 minOperations(List<Integer> nums, int target) {
        Collections.sort(nums);
        int n = nums.size();
        int idx = 0, sum = 0, ans = 0;
        for (int i = target; i != 0; ) {
            int x = i & -i;
            i -= x;
            while (idx < n && nums.get(idx) <= x) {
                sum += nums.get(idx++);
            }
            sum -= x;
            if (sum < 0) {
                if (idx == n) return -1;
                ans += Integer.numberOfTrailingZeros(nums.get(idx) / x);
                sum += nums.get(idx++);
            }
        }
        return ans;
    }
}

在传球游戏中最大化函数值

参考大佬的题解。

方法一：倍增 DP

因为 CPU 缓存的原因，数组开成 new int[35][n] 会更快。因为这样转移的时候只从上一行转移，具有空间局部性；而下面的代码是从左边一列转移，不具有空间局部性。

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 Solution {
    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        int n = receiver.size();
        int[][] f = new int[n][35];
        long[][] w = new long[n][35];
        for (int i = 0; i < n; i++) {
            f[i][0] = receiver.get(i);
            w[i][0] = i;
        }
        for (int j = 1; j < 35; j++) {
            for (int i = 0; i < n; i++) {
                f[i][j] = f[f[i][j - 1]][j - 1];
                w[i][j] = w[i][j - 1] + w[f[i][j - 1]][j - 1];
            }
        }
        long ans = 0L;
        for (int i = 0; i < n; i++) {
            long cur = 0L;
            int pos = i;
            for (int j = 0; j < 35; j++) {
                if ((k >> j & 1) == 0) continue;
                cur += w[pos][j];
                pos = f[pos][j];
            }
            ans = Math.max(ans, cur + pos);
        }
        return ans;
    }
}

方法二：内向基环树

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
class Solution {
    public long getMaxFunctionValue(List<Integer> receiver, long k) {
        int n = receiver.size();
        // 建立环外节点的反向边
        int[] in = new int[n];
        List<Integer>[] reverse = new List[n];
        Arrays.setAll(reverse, r -> new ArrayList<>());
        for (int i = 0; i < n; i++) {
            in[receiver.get(i)]++;
            reverse[receiver.get(i)].add(i);
        }
        // 拓扑序去除环外节点
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) q.add(i);
        }
        while (!q.isEmpty()) {
            int x = q.poll();
            if (--in[receiver.get(x)] == 0) {
                q.offer(receiver.get(x));
            }
        }
        // 计算每个环的前缀和，并记录每个节点在哪个环的哪个位置
        int[] cirNum = new int[n];
        int[] cirPos = new int[n];
        boolean[] vis = new boolean[n];
        List<List<Long>> circles = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (!vis[i] && in[i] != 0) {
                List<Long> cir = new ArrayList<>();
                cir.add(0L); // 前缀和的冗余节点
                // 存储环的节点，并记录每个节点在哪个环的哪个位置
                for (int cur = i; !vis[cur]; cur = receiver.get(cur)) {
                    vis[cur] = true;
                    cirNum[cur] = circles.size();
                    cirPos[cur] = cir.size();
                    cir.add((long) cur);
                }
                // 重复存储环的节点，方便计算从任意节点开始和结束的价值和
                for (int t = cir.size() - 1, j = 1; t > 0; t--, j++) {
                    cir.add(cir.get(j));
                }
                // 计算前缀和
                for (int j = 1; j < cir.size(); j++) {
                    cir.set(j, cir.get(j) + cir.get(j - 1));
                }
                circles.add(cir);
            }
        }
        // 对环内的每个节点向环外进行 dfs，从而计算出以每个节点作为起点的价值和
        long ans = 0L;
        // 存储环外节点的前缀和
        List<Long> outSum = new ArrayList<>();
        outSum.add(0L);
        for (int i = 0; i < n; i++) {
            // 注意传递 k + 1，表示总节点数量
            if (in[i] != 0) ans = Math.max(ans, dfs(i, circles.get(cirNum[i]), cirPos[i], reverse, in, outSum, k + 1));
        }
        return ans;
    }

    private long dfs(int x, List<Long> cir, int pos, List<Integer>[] reverse, int[] in, List<Long> outSum, long k) {
        long res = 0L;
        int outLen = outSum.size() - 1;
        if (outLen < k) {
            int n = cir.size() / 2; // 因为 cir 多存储了 n - 1 个环内节点，以及一个冗余节点，所以 cir.size() / 2 就是环的长度
            res = (k - outLen) / n * cir.get(n) + cir.get(pos + (int) ((k - outLen) % n) - 1) - cir.get(pos - 1);
        }
        res += outSum.get(outLen) - outSum.get((int) Math.max(0L, outLen - k));
        for (int y : reverse[x]) {
            if (in[y] != 0) continue;
            outSum.add(outSum.get(outLen) + y);
            res = Math.max(res, dfs(y, cir, pos, reverse, in, outSum, k));
            outSum.remove(outLen + 1);
        }
        return res;
    }
}
发表更新算法 / LeetCode5 分钟读完 (大约797个字)

第 359 场力扣周赛

判别首字母缩略词

Java

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean isAcronym(List<String> words, String s) {
        int n = words.size(), m = s.length();
        if (n != m) return false;
        for (int i = 0; i < n; i++) {
            if (words.get(i).charAt(0) != s.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isAcronym(vector<string>& words, string s) {
        int m = words.size(), n = s.size();
        if (m != n) return false;
        for (int i = 0; i < n; i++) {
            if (words[i][0] != s[i]) {
                return false;
            }
        }
        return true;
    }
};

k-avoiding 数组的最小总和

贪心。

Java

1
2
3
4
5
6
class Solution {
    public int minimumSum(int n, int k) {
        int m = Math.min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
}

C++

1
2
3
4
5
6
7
class Solution {
public:
    int minimumSum(int n, int k) {
        int m = min(k / 2, n);
        return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
    }
};

销售利润最大化

不从动态规划的角度思考，我首先用的是对左端点排序。如果用动态规划，那么根据转移方程就会对右端点排序，处理方式也比对左端点排序简单一些。还可以不排序做，使用桶存储相同 \(end\) 的 \(offer\)，分别处理每个桶。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maximizeTheProfit(int n, List<List<Integer>> offers) {
        Collections.sort(offers, (a, b) -> a.get(1) - b.get(1));
        offers.add(List.of(n - 1, n - 1, 0));
        int m = offers.size(), i = 0;
        int[] leftMax = new int[n + 1];
        for (var offer : offers) {
            int s = offer.get(0), e = offer.get(1), g = offer.get(2);
            for (; i <= e; i++) leftMax[i + 1] = leftMax[i];
            leftMax[e + 1] = Math.max(leftMax[e + 1], leftMax[s] + g);
        }
        return leftMax[n];
    }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        vector<vector<pair<int, int>>> groups(n);
        for (auto &offer : offers) {
            groups[offer[1]].emplace_back(offer[0], offer[2]);
        }
        vector<int> f(n + 1);
        for (int end = 0; end < n; end++) {
            f[end + 1] = f[end];
            for (auto &[start, gold] : groups[end]) {
                f[end + 1] = max(f[end + 1], f[start] + gold);
            }
        }
        return f[n];
    }
};

找出最长等值子数组

Java

滑动窗口：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size();
        Map<Integer, Integer> map = new HashMap<>();
        int lo = 0, hi = 0, ans = 0;
        while (hi < n) {
            map.merge(nums.get(hi++), 1, Integer::sum);
            if (hi - lo - map.get(nums.get(lo)) > k) {
                map.merge(nums.get(lo++), -1, Integer::sum);
            }
            ans = Math.max(ans, map.get(nums.get(lo)));
        }
        while (lo + 1 < n) {
            map.merge(nums.get(lo++), -1, Integer::sum);
            ans = Math.max(ans, map.get(nums.get(lo)));
        }
        return ans;
    }
}

滑动窗口（优化）：

  • 优化一：观察到 \(1\leq nums[i]\leq nums.lenth\)，所以可以用数组模拟哈希表。
  • 优化二：滑动窗口直接枚举右端点，这样可以枚举到所有情况。但是如何保证删除的元素数量小于等于 \(k\) 呢？当左端点的值 \(nums[i]\) 不能构成等值数组，则将左端点右移。为什么这样可以保证？当 \(nums[i]\neq nums[j]\) 时，移动左端点不影响答案；当 \(nums[i]=nums[j]\) 时，移动左端点可以保证删除的元素数量小于等于 \(k\)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int longestEqualSubarray(List<Integer> nums, int k) {
        int n = nums.size(), ans = 0;
        int[] map = new int[n + 1];
        for (int i = 0, j = 0; j < n; j++) {
            map[nums.get(j)]++;
            if (j - i + 1 - map[nums.get(i)] > k) {
                map[nums.get(i++)]--;
            }
            ans = Math.max(ans, map[nums.get(j)]);
        }
        return ans;
    }
}

C++

分组 + 双指针：

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 longestEqualSubarray(vector<int>& nums, int k) {
        int n = nums.size(), ans = 0;
        vector<vector<int>> pos(n + 1);
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        for (auto &ps : pos) {
            int left = 0;
            for (int right = 0; right < ps.size(); right++) {
                while (ps[right] - ps[left] - right + left > k) {
                    left++;
                }
                ans = max(ans, right - left + 1);
            }
        }
        return ans;
    }
};

关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×