leetcode biweekly contest 509

leetcode contest 509

本周的题目还算是比较经典的题目，T3 是个好题目，T4 反而是个非常板的题目

Q1. Sum of Integers with Maximum Digit Range

You are given an integer array nums.

The digit range of an integer is defined as the difference between its largest digit and smallest digit.

For example, the digit range of 5724 is 7 - 2 = 5.

Return the sum of all integers in nums whose digit range is equal to the maximum digit range among all integers in the array.

Example 1:

Input: nums = [5724,111,350]

Output: 6074

Explanation:

`i`	`nums[i]`	Largest	Smallest	Digit Range
0	5724	7	2	5
1	111	1	1	0
2	350	5	0	5

The maximum digit range is 5. The integers with this digit range are 5724 and 350, so the answer is 5724 + 350 = 6074.

Example 2:

Input: nums = [90,900]

Output: 990

Explanation:

`i`	`nums[i]`	Largest	Smallest	Digit Range
0	90	9	0	9
1	900	9	0	9

The maximum digit range is 9. Both integers have this digit range, so the answer is 90 + 900 = 990.

Constraints:

1 <= nums.length <= 100
10 <= nums[i] <= 105

地址

https://leetcode.com/contest/weekly-contest-509/problems/sum-of-integers-with-maximum-digit-range/description/

题意

模拟

思路

直接找到每个与元素的最大插值，并按照最大差值进行排序，然后将拥有最大插值的元素相加得到和即可。
复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(n)$。

代码

class Solution {
public:
    int maxDigitRange(vector<int>& nums) {
        vector<pair<int, int>> arr;
        for (int i = 0; i < nums.size(); i++) {
            string s = to_string(nums[i]);
            sort(s.begin(), s.end());
            arr.emplace_back(s.back() - s[0], nums[i]);
        }
        sort(arr.begin(), arr.end());
        int maxVal = arr.back().first;
        int sum = 0;
        for (auto [x, val] : arr) {
            if (x == maxVal){
                sum += val;
            }
        }

        return sum;
    }
};

Q2. Subsequence After One Replacement

You are given two strings s and t consisting of lowercase English letters.

You may choose at most one index in s and replace the character at that index with any lowercase English letter.

Return true if it is possible to make s a subsequence of t; otherwise, return false.

Example 1:

Input: s = “cat”, t = “chat”

Output: true

Explanation:

Replace s[1] from 'a' to 'h'. The resulting string is "cht".
"cht" is a subsequence of "chat" because we can match 'c', 'h', and 't' in order.

Example 2:

Input: s = “plane”, t = “apple”

Output: false

Explanation:

The characters 'p', 'l', and 'e' can be matched in t, but the remaining characters cannot be matched while preserving the required order.
Even after replacing any one character in s, it is impossible to make s a subsequence of t.

Constraints:

1 <= s.length, t.length <= 105
s and t consist only of lowercase English letters.

地址

https://leetcode.com/contest/weekly-contest-509/problems/subsequence-after-one-replacement/description/

题意

动态规划

思路

设 $lcp_l[i]$ 标识字符串 $t$ 的前 $i$ 个字符与 $s$ 的前缀构成的最长公共子序列的最大长度， $lcp_r[i]$ 标识字符串 $t$ 的 $i$ 以后的后缀与 $s$ 的后缀构成的最长公共子序列的最大长度，此时我们可以知道：
- 如果最长公共子序列的长度等于 $s$ 的长度 $n$, 一定可以满足题目条件；
- 如果索引 $i$ 左侧前缀的公共子序列长度加上其右侧后缀的公共子序列的长度等于 $n-1$，此时我们可以直接修改字符串 $t[i]$,即可是的字符串 $s,t$ 相等，此时仅仅修改一次即可满足题目条件；
复杂度分析：

时间复杂度：$O(n + m)$，其中 $n,m$ 标识给定字符串 $s,t$ 的长度。
空间复杂度：$O(m)$，其中 $m$ 表示给定字符串 $t$ 的长度；

代码

class Solution {
public:
    bool canMakeSubsequence(string s, string t) {
        int n = s.size();
        int m = t.size();
        if (n > m) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        vector<int> left(m);
        vector<int> right(m);
        for (int i = 0, j = 0; i < m; i++) {
            if (j == n) {
                left[i] = n;
                continue;
            } else if (j < n) {
                if (t[i] == s[j]) {
                    left[i] = j + 1;
                    j++;
                }
            }
        }
        for (int i = m - 1, j = n - 1; i >= 0; i--) {
            if (j < 0) {
                right[i] = n;
                continue;
            } else if (j >= 0) {
                if (t[i] == s[j]) {
                    right[i] = n - j;
                    j--;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            if (i + 1 < m && right[i + 1] >= n - 1) {
                return true;
            }
            if (i - 1 >= 0 && left[i - 1] >= n - 1) {
                return true;
            }
            if (i - 1 >= 0 && i + 1 < m && left[i - 1] + right[i + 1] >= n - 1) {
                return true;
            }
        }

        return false;
    }
};

Q3. Divisible Game

You are given an integer array nums of length n.

Alice and Bob are playing a game. Alice chooses:

An integer k such that k > 1.
Two integers l and r such that 0 <= l <= r < n.

Initially, both Alice’s and Bob’s scores are 0.

For each index i in the range [l, r] (inclusive):

If nums[i] is divisible by k, Alice’s score increases by nums[i].
Otherwise, Bob’s score increases by nums[i].

The score difference is Alice’s score minus Bob’s score.

Alice wants to maximize the score difference. If there are multiple values of k that achieve the maximum score difference, she chooses the smallest such k.

Return the product of the maximum score difference and the chosen value of k. Since the result can be large, return it modulo 109 + 7.

Example 1:

Input: nums = [1,4,6,8]

Output: 36

Explanation:

Alice can choose k = 2, l = 1, and r = 3.
All values in nums[1..3] are divisible by 2, so Alice’s score is 4 + 6 + 8 = 18, while Bob’s score is 0.
The score difference is 18, which is the maximum possible. Among all values of k that achieve this score difference, the smallest is 2.
Therefore, the answer is 18 * 2 = 36.

Example 2:

Input: nums = [2,1,2]

Output: 6

Explanation:

Alice can choose k = 2, l = 0, and r = 2.
The values nums[0] and nums[2] are divisible by 2, so Alice’s score is 2 + 2 = 4. The value nums[1] is not divisible by 2, so Bob’s score is 1.
The score difference is 4 - 1 = 3, which is the maximum possible. Among all values of k that achieve this score difference, the smallest is 2.
Therefore, the answer is 3 * 2 = 6.

Example 3:

Input: nums = [1]

Output: 1000000005

Explanation:

Alice must choose some k > 1. The smallest possible choice is k = 2.
Since nums[0] is not divisible by 2, Alice’s score is 0, while Bob’s score is 1.
The score difference is -1, which is the maximum possible.
Therefore, the answer is -1 * 2 = -2. Modulo 109 + 7, this equals 1000000005.

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 106

地址

https://leetcode.com/contest/weekly-contest-509/problems/divisible-game/description/

题意

枚举

思路

求出所有的质因数，为啥只枚举质因数即可，因为如果能被 $x$ 整数，则一定能被 $x$ 的质因子整除，因此我们只需要枚举质因子即可。我们计算出数组所有的质因子，并枚举每个质因子 $d$，此时可以得到如下：
- 如果能被 $d$ 整除则替换为 $x$, 否则则替换为 $-x$，此时就转换为了经典求最大连续子数组和的问题；
复杂度分析：

时间复杂度：$𝑂(n \log U)$，其中 $n$ 表示给定的数组的长度, $U$ 表示给定数组中的最大元素。
空间复杂度：$𝑂(𝑛)$，其中 𝑛 表示给定的数组的长度。

代码

class Solution {
public:
    int divisibleGame(vector<int>& nums) {
        int maxVal = *max_element(nums.begin(), nums.end());
        long long mod = 1e9 + 7;
        set<int> factor;

        for (int x : nums) {
            for (int i = 2; i * i <= x; i++) {
                if (x % i == 0) {
                    factor.emplace(i);
                    while (x % i == 0) {
                        x /= i;
                    }
                }
            }
            if (x > 1) {
                factor.emplace(x);
            }
        }
        if (factor.empty()) {
            return mod - 2;
        }

        auto get = [&](int x) -> int {
            int ans = INT_MIN;
            int curr = 0;
            for (int num : nums) {
                curr = max(curr, 0) + (num % x ? -num : num);
                ans = max(ans, curr);
            }

            return ans;
        };

        int max_diff = INT_MIN;
        int best = 0;
        for (int d : factor) {
            int curr = get(d);
            if (curr > max_diff) {
                max_diff = curr;
                best = d;
            }
        }

        return 1LL * best * max_diff % mod;
    }
};

Q4. Palindromic Subarray Sum

You are given an integer array nums.

Return the maximum possible sum of a subarray of nums that is a palindrome.

Example 1:

Input: nums = [10,10]

Output: 20

Explanation:

The whole array [10,10] is a palindrome. Therefore, the maximum sum is 10 + 10 = 20.

Example 2:

Input: nums = [1,2,3,2,1,5,6]

Output: 9

Explanation:

The contiguous subarray [1,2,3,2,1] is a palindrome. Its sum is 1 + 2 + 3 + 2 + 1 = 9 and it is the maximum sum.

Example 3:

Input: nums = [7,1,2,1,7,3,4,3,4]

Output: 18

Explanation:

The contiguous subarray [7,1,2,1,7] is a palindrome. Its sum is 7 + 1 + 2 + 1 + 7 = 18 and it is the maximum sum.

Example 4:

Input: nums = [1,2,3,4,5]

Output: 5

Explanation:

No subarray with length greater than 1 is a palindrome. The largest element in the array is 5. Therefore, the answer is 5.

Example 5:

Input: nums = [1000]

Output: 1000

Explanation:

The subarray with only one element is a palindrome. Therefore, the answer is 1000.

Constraints:

1 <= nums.length <= 105
1 <= nums[i] <= 109

地址

https://leetcode.cn/problems/minimum-time-to-reach-target-with-limited-power/description/

题意

1	`字符串哈希算法、马拉车算法、二分查找`

思路

题目基本上算是非常模板的题目，由于给定的数组中所有的元素都满足大于等于 $0$，所以越长的回文子数组则其元素和肯定越大，因此我们枚举回文子数组的中心即可，每次中心确定后，我们希望回文子数组越长越好，此时有两种情形：
- 回文子数组长度为奇数，此时枚举回文子数组的中心 $i$，假设区间 $[i-l,i+l]$ 为回文子数组，我们可以用二分查找找到最大的 $l$ 即可，我们可以用字符串哈希算法，即可在 $O(1)$ 的时间比较 $[i-l,i-1]$ 与区间 $[i+1,i+l]$ 的子数组是否相等；
- 回文子数组长度为偶数，此时假设区间 $[i-l+1,i+l]$ 为回文子数组，我们可以用二分查找找到最大的 $l$ 即可，我们可以用字符串哈希算法，即可在 $O(1)$ 的时间比较 $[i-l + 1,i]$ 与区间 $[i+1,i+l]$ 的子数组是否相等；
- 更快的方法是我们可以是使用 $manacher$ 算法，可以在 $O(n)$ 时间复杂度求出最长的回文子数组；
复杂度分析：

时间复杂度：$𝑂(n \log n)$，其中 𝑛 表示给定数组的长度.
空间复杂度：$𝑂(n)$，其中 𝑛 表示给定数组的长度.

代码

class Solution {
public:
    long long getSum(vector<int>& nums) {
        int n = nums.size();
        vector<long long> psum(n + 1);
        for (int i = 0; i < n; i++) {
            psum[i + 1] = psum[i] + nums[i];
        }

        long long MOD = 998244353;
        long long BASE = 1315423911;
        vector<long long> hash1(n + 1);
        vector<long long> hash2(n + 1);
        vector<long long> pow1(n + 1, 1);
        // 顺序
        for (int i = 0; i < n; i++) {
            hash1[i + 1] = (hash1[i] * BASE + nums[i]) % MOD;
            pow1[i + 1] = (pow1[i] * BASE) % MOD;
        }
        // 逆序反转
        for (int i = n - 1; i >= 0; i--) {
            hash2[n - i] = (hash2[n - i - 1] * BASE + nums[i]) % MOD;
        }

        // 获取顺序的哈希值
        auto get1 = [&](int l, int r) -> long long {
            long long val = hash1[r + 1] - (hash1[l] * pow1[r - l + 1] % MOD);
            return (val + MOD) % MOD;
        };

        // 获取逆序的哈希值
        auto get2 = [&](int l, int r) -> long long {
            int rl = n - 1 - r;
            int rr = n - 1 - l;
            long long val = hash2[rr + 1] - (hash2[rl] * pow1[rr - rl + 1] % MOD);
            return (val + MOD) % MOD;
        };

        long long ans = 0;
        for (int i = 0; i < n; i++) {
            // 奇数回文数组
            do {
                int lo = 0, hi = min(i, n - 1 - i);
                int best = 0;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    if (get1(i - mid, i + mid) == get2(i - mid, i + mid)) {
                        best = mid;
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
                int l = i - best, r = i + best;
                ans = max(ans, psum[r + 1] - psum[l]);
            } while(0);

            // 偶数回文数组
            if (i < n - 1) {
                int lo = -1, hi = min(i, n - 2 - i);
                int best = -1;
                while (lo <= hi) {
                    int mid = (lo + hi) / 2;
                    if (get1(i - mid, i + 1 + mid) == get2(i - mid, i + 1 + mid)) {
                        best = mid;
                        lo = mid + 1;
                    } else {
                        hi = mid - 1;
                    }
                }
                if (best >= 0) {
                    int l = i - best, r = i + 1 + best;
                    ans = max(ans, psum[r + 1] - psum[l]);
                }
            } 
        }

        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: https://mike-box.github.io/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 哪些奋斗者

力扣周赛

#力扣周赛赛 #题解

leetcode biweekly contest 509

http://example.com/1970/01/01/力扣周赛题解/233/

Author

Mike Meng

Posted on

January 1, 1970

Updated on

July 6, 2026

Licensed under

leetcode biweekly contest 508 Previous

leetcode biweekly contest 507 Next