前言

一定，每个人都没有责任，都没有错，每个人都拼尽了全力。

整体评价

t2不错，前缀和有时也是快速寻求最优解的技巧，t4是道不错的DP解，需要优化。

推荐VP。

更多解题报告详见：珂朵莉MM的解题报告汇总

1. 唯一元素的和

1748. 唯一元素的和

解法蛮多的，数据结构也蛮多的。

因为数据范围较小( $v a l \leq 100$ )，所以用数组来直接代替Hash表。

Java

class Solution {
    
    public int sumOfUnique(int[] nums) {

        int[] used = new int[101];
        for (int v: nums) {
            used[v]++;
        }
        
        int ans = 0;
        for (int v: nums) {
            if (used[v] == 1) {
                ans += v;
            }
        }
        return ans;
        
    }
    
}

2. 任意子数组和的绝对值的最大值

1749. 任意子数组和的绝对值的最大值

前缀和的优化技巧，感觉蛮重要的.

区间和绝对值最大，等价于区间和要么最大，要么最小。

这边固定右端点，那么结果等价于

以 $i$ 端点为右端点的区间绝对值最大和为：

$ma x (ab s (p res u m [i + 1] - ma x P res u m_{i}), ab s (p res u m [i + 1] - min P res u m_{i}))$
其中：
$ma x P res u m_{i} = ma x (p res u m [0], p res u m [1], ..., p res u m [i])$
$min P res u m_{i} = min (p res u m [0], p res u m [1], ..., p res u m [i])$

而这个 $ma x P res u m_{i}, min P res u m_{j}$ 有点像DP优化中，常见到的单调队列优化技巧。

Java

class Solution {
    
    public int maxAbsoluteSum(int[] nums) {

        long ans = Math.abs(nums[0]);
        
        long max = 0, min = 0;
        long acc = 0;
        
        for (int i = 0; i < nums.length; i++) {
            acc += nums[i];
            max = Math.max(max, acc);
            min = Math.min(min, acc);
            
            ans = Math.max(ans, Math.max(Math.abs(acc - max), Math.abs(acc - min)));
        }
    
        return (int)ans;
        
    }

}

3. 删除字符串两端相同字符后的最短长度

1750. 删除字符串两端相同字符后的最短长度

简单的贪心题，用双指针就行。

Java

class Solution {
    
    public int minimumLength(String s) {
    
        // 贪心算法
        char[] buf = s.toCharArray();
        
        int i = 0, j = buf.length - 1;
        
        while (i < j) {
        
            char c = buf[i];
            if (buf[j] != c) break;
            
            // 左边移动
            while (i <= j) {
                if (buf[i] == c) {
                    i++;
                } else {
                    break;
                }
            }
            // 右边移动
            while (i <= j) {
                if (buf[j] == c) {
                    j--;
                } else {
                    break;
                }
            }    
        }
        
        return j - i + 1;
        
        
    }
    
}

4. 最多可以参加的会议数目 II

1751. 最多可以参加的会议数目 II

最优化问题，要么是贪心，要么是DP。

但无论贪心，还是DP，首先要排序，这边按右端点作为排序的第一基准。

在看数据范围，特别有意思，一般两个变量相乘表示的范围，往往是DP。

$1 <= k <= e v e n t s . l e n g t h$
$1 <= k * e v e n t s . l e n g t h <= 1 0^{6}$

那么这个最优化问题，其DP解就非常的清晰了。

$o pt [i] [k] = ma x (o pt [j] [k - 1] + e v e n t s [i] . v a l, o pt [i - 1] [k])$
$s_{.} t_{.}$ $e v e n t [i] [0] > e v e n t [j] [1]$
$s_{.} t_{.}$ $i > j$

其中 $i > j$ 容易处理，合并项即可，但是区间不想交，这个时候之前的排序就其作用了，因为根据右端点排序，只要找到当前区间的左端点为基准，二分找到最近的右端点j即可。

在LC中的dp题中，这个dp算是比较特殊的。

Java

class Solution {

    // 二分找到 lowerbound界
    int search(int[][] events, int idx) {
        int x = events[idx][0];
        int l = 0, r = idx;

        while (l <= r) {
            int m = l + (r - l) / 2;
            if (events[m][1] >= x) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return r;
    }

    public int maxValue(int[][] events, int k) {
        int n = events.length;
        long[][] opt = new long[n][k + 1];

        // 先排序
        Arrays.sort(events, (a, b) -> {
            if (a[1] != b[1]) return a[1] < b[1] ? -1 : 1;
            if (a[0] != b[0]) return a[0] < b[0] ? -1 : 1;
            return 0;
        });

        Arrays.fill(opt[0], -1); 
        opt[0][0] = 0;
        opt[0][1] = events[0][2];

        for (int i = 1; i < n; i++) {
            // 复制(这个很重要)
            for (int j = 0; j <= k; j++) {
                opt[i][j] = opt[i - 1][j];
            }

            // 然后优化
            int p = search(events, i);
            if (p == -1) {
                opt[i][1] = Math.max(opt[i][1], events[i][2]);
            } else {
                for (int j = 0; j < k; j++) {
                    if (opt[p][j] == -1) {
                        break;
                    }
                    if (opt[i][j + 1] == -1 || opt[i][j + 1] < opt[p][j] + events[i][2]) {
                        opt[i][j + 1] = opt[p][j] + events[i][2];
                    }
                }
            }
        }
        long ans = 0;
        for (int i = 1; i <= k; i++) {
            if (opt[n - 1][i] != -1) {
                ans = Math.max(ans, opt[n - 1][i]);
            }
        }

        return (int)ans;

    }

}