LeetCode Contest 435

欢迎大家加QQ群：623375442，可以方便群里面交流。第一题读题过于失败，没看清题目，连续WA。。。

100566. Maximum Difference Between Even and Odd Frequency I

给你一个由小写英文字母组成的字符串 s 。请你找出字符串中两个字符的出现频次之间的 最大 差值，这两个字符需要满足：

• 一个字符在字符串中出现 偶数次 。
• 另一个字符在字符串中出现 奇数次 。

返回 最大 差值，计算方法是出现 奇数次 字符的次数 减去 出现 偶数次 字符的次数。

测试样例：

输入：s = "aaaaabbc"

输出：3

解释：字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。最大差值为 5 - 2 = 3 。

解答：看了第四题，一直以为这题也是子串最大。。。原来只看整个s。。。暴力计算。

class Solution {
    public int maxDifference(String s) {
        int[] count = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            count[s.charAt(i) - 'a'] += 1;
        }
        int maxOdd = 0, minEven = Integer.MAX_VALUE;
        for (int n : count) {
            if (n > 0) {
                if (n % 2 == 1) maxOdd = Math.max(maxOdd, n);
                if (n % 2 == 0) minEven = Math.min(minEven, n);
            }
        }
        return maxOdd - minEven;
    }
}

100567. Maximum Manhattan Distance After K Changes

给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：

• 'N'：向北移动 1 个单位。
• 'S'：向南移动 1 个单位。
• 'E'：向东移动 1 个单位。
• 'W'：向西移动 1 个单位。

初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。

请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。

曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。

测试样例：

输入：s = "NWSE", k = 1

输出：3

解释：将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。

解答：一路遍历过程中，查看最大距离。最大曼哈顿距离，其实就是把NS尽量改的一样，把WE改的一样。

class Solution {
    public int maxDistance(String s, int k) {
        int[] c1 = {0,0}, c2 = {0,0};
        int res = 0;
        for (int i = 0; i < s.length(); ++i) {
            switch (s.charAt(i)) {
                case 'N' -> c1[0] += 1;
                case 'S' -> c1[1] += 1;
                case 'W' -> c2[0] += 1;
                case 'E' -> c2[1] += 1;
            }
            int[] tmp = calculate(c1, k);
            int cur = 0;
            cur += tmp[0];
            tmp = calculate(c2, tmp[1]);
            cur += tmp[0];
            res = Math.max(res, cur);
        }

        return res;
    }

    // 尽量利用k把相反方向修改成一致。
    private int[] calculate(int[] c, int k) {
        int max = Math.max(c[0], c[1]);
        int min = Math.min(c[0], c[1]);
        if (k >= min) {
            return new int[]{max + min, k - min};
        } else {
            return new int[]{max + k - (min - k), 0};
        }
    }
}

100520. Minimum Increments for Target Multiples in an Array

给你两个数组 nums 和 target 。

在一次操作中，你可以将 nums 中的任意一个元素递增 1 。

返回要使 target 中的每个元素在 nums 中 至少 存在一个倍数所需的 最少操作次数 。

测试样例：

输入：nums = [1,2,3], target = [4]

输出：1

解释：满足题目条件的最少操作次数是 1 。将 3 增加到 4 ，需要 1 次操作，4 是目标值 4 的倍数。

解答：状态压缩的动态规划，target的长度非常短，我们直接计算各种可能下的LCM数值。注意target可能取值到100000，4个数的LCM可能会炸Integer.MAX_VALUE。使用long比较安全。

class Solution {
    public int minimumIncrements(int[] nums, int[] target) {
        int max = 1 << target.length;
        // 状态压缩，计算target已经被拿走的最小情况。
        long[] lcm = new long[max];
        for (int i = 1; i < max; ++i) {
            long current = -1;
            for (int j = 0; j < target.length; ++j) {
                if (isAppear(i, j)) {
                    if (current == -1) {
                        current = target[j];
                    } else {
                        long tmp = gcd(current, target[j]);
                        current = current / tmp * target[j];
                    }
                }
            }
            lcm[i] = current;
        }
        long[] dp = new long[max];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0;
        for (int n : nums) {
            long[] nextDp = new long[max];
            Arrays.fill(nextDp, Long.MAX_VALUE);
            nextDp[0] = 0;
            // 符合当前target取法，已经完成的最小情况
            for (int i = 1; i < max; ++i) {
                nextDp[i] = dp[i];
                for (int j = 0; j < max; ++j) {
                    if (i != j && dp[j] != Long.MAX_VALUE && (i | j) == i) {
                        long l = lcm[i ^ j];
                        if (n % l == 0) {
                            nextDp[i] = Math.min(nextDp[i], dp[j]);
                        } else {
                            nextDp[i] = Math.min(nextDp[i], dp[j] + (n / l + 1) * l - n);
                        }
                    }
                }
            }
            dp = nextDp;
        }
        return (int)dp[max - 1];
    }

    private long gcd(long x, long y) {
        while (y != 0) {
            long tmp = x % y;
            x = y;
            y = tmp;
        }
        return x;
    }

    private boolean isAppear(int key, int offset) {
        int tmp = (key >> offset) & 1;
        return tmp == 1;
    }
}

补充一个Rust写法

impl Solution {
    pub fn minimum_increments(nums: Vec<i32>, target: Vec<i32>) -> i32 {
        let max = 1 << target.len();
        let mut lcm_arr = vec![1 as i64 ; max];
        for i in 1..max {
            let mut current: i64 = -1;
            for j in 0..target.len() {
                if Self::is_used(i, j) {
                    if current == -1 {
                        current = target[j] as i64;
                    } else {
                        current = current / Self::gcd(current, target[j] as i64) * (target[j] as i64);
                    }
                }
            }
            lcm_arr[i] = current;
        }
        let mut dp = [std::i64::MAX / 2 as i64 ; 16];
        dp[0] = 0;
        for n in &nums {
            let mut next_dp = [std::i64::MAX / 2 as i64 ; 16];
            let n_i64 = *n as i64;
            for i in 0..max {
                for j in 0..max {
                    if i | j == i {
                        let cur_lcm = lcm_arr[i ^ j];
                        if n_i64 % cur_lcm == 0 {
                            next_dp[i] = next_dp[i].min(dp[j]);
                        } else {
                            next_dp[i] = next_dp[i].min(dp[j] + (n_i64 / cur_lcm + 1) * cur_lcm - n_i64);
                        }
                    }
                }
            }
            dp = next_dp;
        }
        dp[max - 1] as i32
    }

    fn gcd(mut x: i64, mut y: i64) -> i64 {
        while y != 0 {
            let tmp = x % y;
            x = y;
            y = tmp;
        }
        x
    }

    fn is_used(key: usize, offset: usize) -> bool {
        let tmp = (key >> offset) & 1;
        tmp == 1
    }
}

100573. Maximum Difference Between Even and Odd Frequency II

给你一个字符串 s 和一个整数 k 。请你找出 s 的子字符串 subs 中两个字符的出现频次之间的 最大 差值，freq[a] - freq[b] ，其中：

• subs 的长度 至少 为 k 。
• 字符 a 在 subs 中出现奇数次。
• 字符 b 在 subs 中出现偶数次。

返回 最大 差值。

注意 ，subs 可以包含超过 2 个 互不相同 的字符。.

子字符串 是字符串中的一个连续字符序列。

测试样例：

输入：s = "12233", k = 4

输出：-1

解释：对于子字符串 "12233" ，'1' 的出现次数是 1 ，'3' 的出现次数是 2 。差值是 1 - 2 = -1 。

解答：这题s 仅由数字 '0' 到 '4' 组成。我们直接暴力枚举s集合中，一个数出现奇数次，另一个数出现偶数次时，最大数值。

class Solution {
    private static final char[] arr = {'0','1','2','3','4'};

    public int maxDifference(String s, int k) {
        int res = Integer.MIN_VALUE;
        int[] count = new int[s.length()];
        int[] mark = new int[s.length()];
        // 状态压缩10代表l出现奇数次，r出现偶数次
        // 00代表l出现偶数次，r出现偶数次
        // 01代表l出现偶数次，r出现奇数次
        // 00代表l出现奇数次，r出现奇数次
        int[] minMem = new int[4];
        for (char l : arr) {
            for (char r : arr) {
                if (l == r) continue;
                int sum = 0, currentMark = 0;
                // lMet和rMet确保区间内必须存在一个对应的数字。
                int lMet = -1, rMet = -1, pos = 0;
                Arrays.fill(minMem, Integer.MAX_VALUE);
                minMem[0] = 0;
                for (int i = 0; i < s.length(); ++i) {
                    if (s.charAt(i) == l) {
                        ++sum;
                        lMet = i;
                        currentMark ^= 2;
                    } else if (s.charAt(i) == r) {
                        --sum;
                        rMet = i;
                        currentMark ^= 1;
                    }
                    count[i] = sum;
                    mark[i] = currentMark;
                    if (i >= k - 1 && lMet != -1 && rMet != -1) {
                        for (int j = 0; j < 4; ++j) {
                            // 必须确保左数出现奇数次，右数出现偶数次。
                            if ((currentMark ^ j) == 2 && minMem[j] != Integer.MAX_VALUE) {
                                res = Math.max(res, sum - minMem[j]);
                            }
                        }
                        int min = Math.min(i - k + 1, lMet - 1);
                        min = Math.min(min, rMet - 1);
                        while (pos <= min) {
                            minMem[mark[pos]] = Math.min(minMem[mark[pos]], count[pos]);
                            ++pos;
                        }
                    }
                }
            }
        }
        return res;
    }
}

补充一个Rust版本

static DEFAULT_DELETE: i32 = 48;
static TARGET_MAP: [usize;4] = [2,3,0,1];

impl Solution {
    pub fn max_difference(s: String, k: i32) -> i32 {
        let s_arr = s.as_bytes();
        let mut sum_arr: Vec<i32> = vec![0;s.len()];
        let mut key_arr: Vec<usize> = vec![0;s.len()];
        let k_u = k as usize;
        let mut res = std::i32::MIN;
        for l in 0..5 {
            for r in 0..5 {
                if l == r {
                    continue;
                }
                let mut dp = [std::i32::MAX / 2;4];
                dp[0] = 0;
                let mut l1: i32 = -1;
                let mut l2: i32 = -1;
                let mut sum: i32 = 0;
                let mut key: usize = 0;
                let mut pos: usize = 0;
                for (i, val) in s_arr.iter().enumerate() {
                    let tmp = *val as i32 - DEFAULT_DELETE;
                    if tmp == l {
                        sum += 1;
                        key ^= 2;
                        l1 = i as i32;
                    } else if tmp == r {
                        sum -= 1;
                        key ^= 1;
                        l2 = i as i32;
                    }
                    sum_arr[i] = sum;
                    key_arr[i] = key;
                    let next_pos = l1.min(l2).min(i as i32 - k + 1);
                    if next_pos >= 0 {
                        let next_pos_u = next_pos as usize;
                        while pos < next_pos_u {
                            dp[key_arr[pos]] = dp[key_arr[pos]].min(sum_arr[pos]);
                            pos += 1;
                        }
                    }
                    if l1 >= 0 && l2 >= 0 && i >= k_u - 1 {
                        res = res.max(sum - dp[TARGET_MAP[key]]);
                    }
                }
            }
        }
        res
    }
}