发表更新算法 / 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();
}
发表更新算法 / LeetCode7 分钟读完 (大约979个字)

第 358 场力扣周赛

数组中的最大数对和

赛时直接暴力做，赛后优化代码参考自灵神。就是维护每个最大数位对应的最大值，然后可以优化掉一个 \(n\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSum(int[] nums) {
        int ans = -1;
        int[] maxVal = new int[10];
        Arrays.fill(maxVal, Integer.MIN_VALUE);
        for (int x : nums) {
            int maxD = 0;
            for (int y = x; y > 0; y /= 10) {
                maxD = Math.max(maxD, y % 10);
            }
            ans = Math.max(ans, x + maxVal[maxD]);
            maxVal[maxD] = Math.max(maxVal[maxD], x);
        }
        return ans;
    }
}

翻倍以链表形式表示的数字

做乘法惯性思维，就想着从最低位开始乘然后进位，结果可以从高位开始乘，因为乘二时低位最多就进一位。（如果从低位开始乘，就转数组或者反转链表吧）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode doubleIt(ListNode head) {
        if (head.val > 4) head = new ListNode(0, head);
        for (ListNode cur = head; cur != null; cur = cur.next) {
            cur.val = cur.val * 2 % 10;
            if (cur.next != null && cur.next.val > 4) {
                cur.val++;
            }
        }
        return head;
    }
}

限制条件下元素之间的最小绝对差

一开始没反应过来，以为找最大值和最小值就行。结果发现是让绝对值最小，要找最接近当前值的那个值，那就可以使用 TreeSet。但是我又搞复杂了，其实只要维护一个方向就可以，但是我维护了左右方向距离为 \(x\) 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        int n = nums.size(), ans = Integer.MAX_VALUE;
        TreeSet<Integer> set = new TreeSet<>();
        set.add(Integer.MAX_VALUE);
        set.add(Integer.MIN_VALUE / 2);
        for (int i = x; i < n; i++) {
            set.add(nums.get(i - x));
            int cur = nums.get(i);
            ans = Math.min(ans, Math.min(cur - set.floor(cur), set.ceiling(cur) - cur));
        }
        return ans;
    }
}

操作使得分最大

吐血吐血，赛后 Debug 发现分解质因数的代码打错一个变量，改了就能 AC。一开始也看错题目了，以为答案是乘质数分数，结果答案是乘数组中的值，那么优先选最大的数就是最优的。问题就变成给定某个数，选择它为目标值的数组有多少个。数组的个数等于左边质数分数小于当前值能到达的最远位置，乘右边质数分数大于等于当前值能到达的最远位置。所以我们可以先对质数分数降序排序，相同分数再对下标升序排序，按照这个顺序处理元素，使用 TreeSet 维护已处理的值，就可以比较方便的得到左右两边的边界，从而得到以当前值为目标值的数组个数。最后，按照值从大到小来做乘法。

计算每个位置有多少数组还可以使用单调栈（更快），详情见题解区。

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
class Solution {
    private static final int MOD = (int) 1e9 + 7;
    private static final int N = (int) 1e5 + 1;
    private static int[] f = new int[N];

    // 素数筛
    static {
        for (int i = 2; i < N; i++) {
            if (f[i] == 0) {
                for (int j = i; j < N; j += i) {
                    f[j]++;
                }
            }
        }
    }

    public int maximumScore(List<Integer> nums, int k) {
        // 计算每个位置有多少个数组
        int n = nums.size();
        TreeSet<Integer> set = new TreeSet<>();
        set.add(-1); set.add(n);
        var aux = new Integer[n];
        for (int i = 0; i < n; i++) aux[i] = i;
        Arrays.sort(aux, (a, b) -> {
            int x = nums.get(a), y = nums.get(b);
            return f[x] != f[y] ? f[y] - f[x] : a - b;
        });
        long[] cnt = new long[n];
        for (int i : aux) {
            long l = i - set.ceiling(i);
            long r = set.floor(i) - i;
            cnt[i] = l * r;
            set.add(i);
        }
        // 从大到小枚举值，计算答案
        long ans = 1L;
        for (int i = 0; i < n; i++) aux[i] = i;
        Arrays.sort(aux, (a, b) -> nums.get(b) - nums.get(a));
        for (int i = 0; k > 0; i++) {
            int t = (int) Math.min(cnt[aux[i]], k);
            ans = (ans * power(nums.get(aux[i]), t)) % MOD;
            k -= t;
        }
        return (int) ans;
    }
    
    private long power(long x, int n) {
        long res = 1L;
        while (n != 0) {
            if (n % 2 == 1) res = res * x % MOD;
            x = x * x % MOD;
            n >>= 1;
        }
        return res;
    }
}
关注我

链接

分类

最新文章

归档

标签

Debugging2
Draft1
Hexo1

链接

×