发表更新算法 / 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;
    }
};

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

第 111 场力扣夜喵双周赛

统计和小于目标的下标对数目

使用排序 + 双指针优化。如果 \(nums[lo]+nums[hi]<target\)，那么 \([lo+1,hi]\) 范围内的数都能与 \(nums[lo]\) 组成对，\(lo\) 加一；反之，\([lo,hi-1]\) 范围内的数都不能与 \(nums[hi]\) 组成对，\(hi\) 减一。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int lo = 0, hi = nums.size() - 1, ans = 0;
        while (lo < hi) {
            if (nums.get(lo) + nums.get(hi) < target) {
                ans += hi - lo;
                lo++;
            } else {
                hi--;
            }
        }
        return ans;
    }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0;
        for (int i = 0, j = n - 1; i < j; ) {
            if (nums[i] + nums[j] < target) {
                ans += j - i;
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }
};

循环增长使字符串子序列等于另一个字符串

贪心取就行。

Java

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int m = str1.length(), n = str2.length(), j = 0;
        for (int i = 0; i < m && j < n; i++) {
            if (str1.charAt(i) == str2.charAt(j) || (str1.charAt(i) + 1 - 'a') % 26 == str2.charAt(j) - 'a') {
                j++;
            }
        }
        return j == n;
    }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int m = str1.size(), n = str2.size(), j = 0;
        for (int i = 0; i < m && j < n; i++) {
            if (str1[i] == str2[j] || (str1[i] + 1 - 'a') % 26 == str2[j] - 'a') {
                j++;
            }
        }
        return j == n;
    }
};

将三个组排序

要将 \(nums\) 变为美丽数组，就要将 \(nums\) 变为非递减的形式，所以问题就变为求最长非递减子序列。

Java

动态规划：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minimumOperations(List<Integer> nums) {
        int n = nums.size(), ans = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums.get(i) >= nums.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return n - ans;
    }
}

贪心 + 二分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minimumOperations(List<Integer> nums) {
        int n = nums.size(), maxLen = 0;
        int[] aux = new int[n];
        for (int x : nums) {
            int lo = 0, hi = maxLen - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (aux[mid] <= x) lo = mid + 1;
                else hi = mid - 1;
            }
            aux[lo] = x;
            if (lo == maxLen) maxLen++;
        }
        return n - maxLen;
    }
}

状态机 DP：

有点妙啊，\(dp[i][j]\) 表示将子数组 \([0,i]\) 变为以 \([1,j]\) 为结尾的美丽数组所需的最小修改次数，然后可以空间优化。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
	public int minimumOperations(List<Integer> nums) {
		int[] dp = {Integer.MAX_VALUE, 0, 0, 0};
		for (int x : nums) {
			for (int i = 1; i <= 3; i++) {
				dp[i] = Math.min(dp[i - 1], dp[i] + (x == i ? 0 : 1));
			}
		}
		return dp[3];
	}
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int dp[4] = {INT_MAX, 0, 0, 0};
        for (int x : nums) {
            for (int i = 1; i <= 3; i++) {
                dp[i] = min(dp[i - 1], dp[i] + (x != i));
            }
        }
        return dp[3];
    }
};

范围中美丽整数的数目

经典数位 DP 没什么好说的，主要是记忆化取模，边乘边取模。

Java

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 int numberOfBeautifulIntegers(int low, int high, int k) {
        return f(0, 10, 0, true, false, high + "", k, new Integer[10][20][k])
                - f(0, 10, 0, true, false, low - 1 + "", k, new Integer[10][20][k]);
    }
    
    private int f(int i, int diff, int mod, boolean isLimit, boolean isNum, String s, int k, Integer[][][] dp) {
        if (i == s.length()) {
            return isNum && diff == 10 && mod == 0 ? 1 : 0;
        }
        if (!isLimit && isNum && dp[i][diff][mod] != null) {
            return dp[i][diff][mod];
        }
        int res = 0;
        if (!isNum) res += f(i + 1, diff, mod, false, false, s, k, dp);
        int lo = isNum ? 0 : 1, hi = isLimit ? s.charAt(i) - '0' : 9;
        for (int d = lo; d <= hi; d++) {
            res += f(i + 1, diff + d % 2 * 2 - 1, (mod * 10 + d) % k, isLimit && d == hi, true, s, k, dp);
        }
        if (!isLimit && isNum) {
            dp[i][diff][mod] = res;
        }
        return res;
    }
}

C++

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:
    int numberOfBeautifulIntegers(int low, int high, int k) {
        string s;
        const int BASE = 10;
        int dp[10][20][k];
        
        auto f = [&](auto self, int i, int diff, int mod, bool isLimit, bool isNum) {
            if (i == s.size()) {
                return isNum && diff == 0 && mod == 0 ? 1 : 0;
            }
            if (!isLimit && isNum && dp[i][diff + BASE][mod] != -1) {
                return dp[i][diff + BASE][mod];
            }
            int res = 0;
            if (!isNum) res += self(self, i + 1, diff, mod, false, false);
            int lo = isNum ? 0 : 1, hi = isLimit ? s[i] - '0' : 9;
            for (int d = lo; d <= hi; d++) {
                res += self(self, i + 1, diff + d % 2 * 2 - 1, (mod * 10 + d) % k, isLimit && d == hi, true);
            }
            if (!isLimit && isNum) dp[i][diff + BASE][mod] = res;
            return res;
        };

        auto calc = [&](int x) {
            s = to_string(x);
            memset(dp, -1, sizeof(dp));
            return f(f, 0, 0, 0, true, false);
        };

        return calc(high) - calc(low - 1);
    }
};

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

Codeforces Round 893 (Div. 2)

Buttons

优先选择公共按钮，当且仅当先手的按钮数量大于后手的按钮数量时，先手者胜。

1
2
3
4
5
public static void solve() {
    int a = io.nextInt(), b = io.nextInt(), c = io.nextInt();
    if (a + c % 2 > b) io.println("First");
    else io.println("Second");
}

The Walkway

模拟题，特别需要注意头尾的边界处理，加上哨兵真的会方便很多。可以假设位置 \(1-d\) 和位置 \(n+1\) 有卖家，这样就不用特判，可以直接处理！！！

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
public static void solve() {
    int n = io.nextInt(), m = io.nextInt(), d = io.nextInt();
    int[] s = new int[m + 2];
    for (int i = 1; i <= m; i++) {
        s[i] = io.nextInt();
    }
    s[0] = 1 - d;
    s[m + 1] = n + 1;

    int ans = m - 1, delta = Integer.MAX_VALUE, cnt = 0;
    for (int i = 1; i <= m; i++) {
        int A = (s[i] - s[i - 1] - 1) / d;
        int B = (s[i + 1] - s[i] - 1) / d;
        int C = (s[i + 1] - s[i - 1] - 1) / d;
        int D = C - A - B;

        if (D < delta) {
            delta = D;
            cnt = 1;
        } else if (D == delta) {
            cnt++;
        }
        ans += A;
    }
    ans += (s[m + 1] - s[m] - 1) / d + delta - 1;
    io.println(ans + " " + cnt);
}

Yet Another Permutation Problem

构造题，首先需要发现什么公约数不可能出现，很明显不可能得到 \(d_{i}=\gcd (a_{i},a_{(i\bmod n)+1})> \lfloor \frac{n}{2}\rfloor\)。然后考虑所有小于等于 \(\lfloor \frac{n}{2}\rfloor\) 的数是否能被包含，可以发现对于每个 \(a_{i}=x\leq \lfloor \frac{n}{2}\rfloor\) 总有 \(a_{(i\bmod n)+1}=2\cdot x\leq n\)，所以我们可以枚举所有奇数乘以二的幂来构造答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void solve() {
    int n = io.nextInt(), idx = 0;
    int[] ans = new int[n];
    for (int i = 1; i <= n; i += 2) {
        for (int j = i; j <= n; j *= 2) {
            ans[idx++] = j;
        }
    }
    for (int i = 0; i < n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}

Trees and Segments

难以描述，看代码吧，调试半天。。

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
public static void solve() {
    int n = io.nextInt(), k = io.nextInt();
    char[] s = io.next().toCharArray();
    int[][] prefix = new int[n + 1][k + 1];
    int[][] suffix = new int[n + 1][k + 1];
    // 枚举可以在 k 次操作内变为全 0 的子数组，并将其长度记录到所属的前后缀中
    for (int i = 0; i < n; i++) {
        int cnt1 = 0;
        for (int j = i; j < n; j++) {
            cnt1 += s[j] - '0';
            if (cnt1 > k) break;
            prefix[j + 1][cnt1] = Math.max(prefix[j + 1][cnt1], j - i + 1);
            suffix[i][cnt1] = Math.max(suffix[i][cnt1], j - i + 1);
        }
    }
    // 在前缀 [0, i] 中最多操作 j 次，可以得到的连续 0 的最长长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= k; j++) {
            prefix[i + 1][j] = Math.max(prefix[i + 1][j], prefix[i][j]);
            if (j > 0) prefix[i + 1][j] = Math.max(prefix[i + 1][j], prefix[i + 1][j - 1]);
        }
    }
    // 在后缀 [i, n - 1] 中最多操作 j 次，可以得到的连续 0 的最长长度
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            suffix[i][j] = Math.max(suffix[i][j], suffix[i + 1][j]);
            if (j > 0) suffix[i][j] = Math.max(suffix[i][j], suffix[i][j - 1]);
        }
    }
    // 枚举连续 1 的起点和终点，并记录该连续 1 的长度对应的连续 0 的最长长度（注意包含长度为 0 的情况）
    int[] max0by1 = new int[n + 1];
    Arrays.fill(max0by1, -1);
    max0by1[0] = suffix[0][k];
    for (int i = 0; i < n; i++) {
        int cnt0 = 0;
        for (int j = i; j < n; j++) {
            cnt0 += (s[j] - '0') ^ 1;
            if (cnt0 > k) break;
            max0by1[j - i + 1] = Math.max(max0by1[j - i + 1], prefix[i][k - cnt0]);
            max0by1[j - i + 1] = Math.max(max0by1[j - i + 1], suffix[j + 1][k - cnt0]);
        }
    }
    // 计算答案
    int[] ans = new int[n + 1];
    for (int a = 1; a <= n; a++) {
        for (int i = 0; i <= n; i++) {
            if (max0by1[i] == -1) continue;
            ans[a] = Math.max(ans[a], i + max0by1[i] * a);
        }
    }
    for (int i = 1; i <= n; i++) {
        io.print(ans[i] + " ");
    }
    io.println();
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×