LeetCode 第 45 场双周赛题解

输入：nums = [1,2,3,2]
输出：4
解释：唯一元素为 [1,3] ，和为 4 。
复制代码

输入：nums = [1,1,1,1,1]
输出：0
解释：没有唯一元素，和为 0 。
复制代码

输入：nums = [1,2,3,4,5]
输出：15
解释：唯一元素为 [1,2,3,4,5] ，和为 15 。
复制代码

class Solution {
    public int sumOfUnique(int[] nums) {
        int[] cnt = new int[110];
        for (int i : nums) cnt[i]++;
        int ans = 0;
        for (int i = 0; i < 110; i++) {
            if (cnt[i] == 1) ans += i;
        }
        return ans;
    }
}
复制代码

输入：nums = [1,-3,2,3,-4]
输出：5
解释：子数组 [2,3] 和的绝对值最大，
     为 abs(2+3) = abs(5) = 5 。
复制代码

输入：nums = [2,-5,1,-4,3,-2]
输出：8
解释：子数组 [-5,1,-4] 和的绝对值最大，
     为 abs(-5+1-4) = abs(-8) = 8 。
复制代码

class Solution {
    public int maxAbsoluteSum(int[] nums) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
        int max = 0, min = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, Math.abs(sum[i] - min));
            ans = Math.max(ans, Math.abs(sum[i] - max));
            max = Math.max(max, sum[i]);
            min = Math.min(min, sum[i]);
        }
        return ans;
    }
}
复制代码

输入：s = "ca"
输出：2
解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。
复制代码

输入：s = "cabaabac"
输出：0
解释：最优操作序列为：
- 选择前缀 "c" 和后缀 "c" 并删除它们，
  得到 s = "abaaba" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，
  得到 s = "baab" 。
- 选择前缀 "b" 和后缀 "b" 并删除它们，
  得到 s = "aa" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，
  得到 s = "" 。
复制代码

输入：s = "aabccabba"
输出：3
解释：最优操作序列为：
- 选择前缀 "aa" 和后缀 "a" 并删除它们，
  得到 s = "bccabb" 。
- 选择前缀 "b" 和后缀 "bb" 并删除它们，
  得到 s = "cca" 。
复制代码

class Solution {
    public int minimumLength(String s) {
        int n = s.length();
        char[] cs = s.toCharArray();
        int ans = n;
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            if (cs[i] != cs[j]) break;
            while (i + 1 < j && cs[i + 1] == cs[i]) i++;
            while (j - 1 > i && cs[j - 1] == cs[j]) j--;
            ans = Math.max(0, j - i - 1);
        }
        return ans;
    }
}
复制代码

输入：events = [[1,2,4],[3,4,3],[2,3,1]], 
     k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，
     得到总价值和为 4 + 3 = 7 。
复制代码

输入：events = [[1,2,4],[3,4,3],[2,3,10]], 
     k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
     你没法再参加别的会议了，因为跟会议 2 有重叠。
     你不需要参加满 k 个会议。
复制代码

输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], 
     k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，
     所以选择价值最大的 3 个会议。
复制代码

class Solution {
    public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        // f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
        int[][] f = new int[n + 1][k + 1]; 
        for (int i = 1; i <= n; i++) {
            int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            // 找到第 i 件事件之前，与第 i 件事件不冲突的事件
            // 对于当前事件而言，冲突与否，与 j 无关
            int last = 0;
            for (int p = i - 1; p >= 1; p--) {
                int[] prev = es[p - 1];
                if (prev[1] < s) {
                    last = p;
                    break;
                }
            }
            for (int j = 1; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);    
            }
        }
        return f[n][k];
    }
}
复制代码

class Solution {
    public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        // f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
        int[][] f = new int[n + 1][k + 1]; 
        for (int i = 1; i <= n; i++) {
            int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            // 通过「二分」，找到第 i 件事件之前，与第 i 件事件不冲突的事件
            // 对于当前事件而言，冲突与否，与 j 无关
            int l = 1, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                int[] prev = es[mid - 1];
                if (prev[1] < s) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            int last = (r > 0 && es[r - 1][1] < s) ? r : 0;
            for (int j = 1; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);    
            }
        }
        return f[n][k];
    }
}
复制代码