讨论/题目交流/🐱 第 18 场夜喵双周赛/
🐱 第 18 场夜喵双周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 数组序号转换
4 分 - 破坏回文串
5 分 - 将矩阵按对角线排序
10 分 - 翻转子数组得到最大的数组值

展开讨论
力扣 (LeetCode)发起于 2020-01-25

时间紧迫,丢一个最后一题的题解。

题目大意

给你一个数组 AA, 你可以将它的一个子区间翻转(也可以不翻转),求最大的

∑i∣Ai−Ai+1∣\sum_i |A_i - A_{i + 1}|

分析

首先,题目有一些特殊情况:

  • 不反转
  • 翻转区间从原区间头开始
  • 翻转区间到原区间尾结束

不看上面的三种特殊情况,普通情况可以被描述成这样(虚线是包裹住的是要翻转的区间):

分割序列.PNG

很容易知道一点:翻转区间操作仅与边界处的四个数字有关系。因为目标式是相邻两个元素差值之和,翻转操作仅改变边界四个数字的相邻关系,其他都不改变。

假设不翻转时目标式的值为 sumsum,我们其实是要求一个 sum+max⁡{delta}sum + \max\{delta\},其中 deltadelta 时翻转操作对于答案的改变。

假设,不翻转时目标式的值为 sumsum,我们其实是要求一个 sum+max⁡{delta}sum + \max\{delta\},其中 deltadelta 时翻转操作对于答案的改变。

看一下 deltadelta 等于什么:

delta=−∣Aa−Ab∣−∣Ac−Ad∣+∣Aa−Ac∣+∣Ab−Ad∣delta = -|A_a - A_b| - |A_c - A_d| + |A_a - A_c| + |A_b - A_d|

乍一看好像没啥,但其实 Aa,AbA_a, A_b 与Ac,AdA_c,A_d 在原数组中分别相邻,图中的虚线分别可以确定它们。那么 −∣Aa−Ab∣-|A_a - A_b| 与 −∣Ac−Ad∣-|A_c - A_d| 其实是一个虚线独立项,∣Aa−Ac∣+∣Ab−Ad∣|A_a - A_c| + |A_b - A_d| 是一个有交叉信息项。

说白一点,翻转区间的左端点与右端点知其一就可以知道对应的虚线独立项的值,左右端点必须同时知道才可以知道交叉信息项的值。独立项简单,交叉项难搞需要 O(n2)O(n^2) 枚举才行。

交叉项的形式其实是一个曼哈顿距离的形式,我们令:

{Aa=x0,Ab=y0,Ac=x1,Ad=y1.\begin{cases} A_a = x_0,\\ A_b = y_0,\\ A_c = x_1,\\ A_d = y_1. \end{cases}

那么,原来的 deltadelta 表示为:

delta=−∣x0−y0∣−∣x1−y1∣+∣x0−x1∣+∣y0−y1∣=−∣x0−y0∣−∣x1−y1∣+(∣x0−x1∣+∣y0−y1∣)\begin{aligned} delta = -|x_0 - y_0| - |x_1 - y_1| + |x_0 - x_1| + |y_0 - y_1|\\ = -|x_0 - y_0| - |x_1 - y_1| + (|x_0 - x_1| + |y_0 - y_1|) \end{aligned}

后面就是一个曼哈顿距离,前面是点独立的信息,我们要求 deltadelta 的最大值。

这样这道题目就解出来了,我们可以套用求曼哈顿距离最大的是方法求这题的答案。

曼哈顿距离有一个转化形式:

∣x0−x1∣+∣y0−y1∣=max⁡{(x0+y0)−(x1+y1),(x0−y0)−(x1−y1),(−x0+y0)−(−x1+y1),(−x0−y0)−(−x1−y1)}\begin{aligned} |x_0 - x_1| + |y_0 - y_1| = \max\{&(x_0+y_0) - (x_1+y_1),\\ &(x_0-y_0) - (x_1-y_1),\\ &(-x_0+y_0) - (-x_1+y_1),\\ &(-x_0-y_0) - (-x_1-y_1) \} \end{aligned}

所以求一堆点之间的最大曼哈顿距离,只需要将点按四种情况(+x+y+x+y,−x+y-x+y,+x−y+x-y,−x−y-x-y)分别计算值,然后求得每种情况下的最大差取 Max 即可。

针对这道题目,每个点还有自己独立的信息,也是很容易加入的,并使用一样的处理方法,就可以求得 deltadelta 的最大值:

−∣x0−y0∣−∣x1−y1∣+(∣x0−x1∣+∣y0−y1∣)=max⁡{(x0+y0−∣x0−y0∣)−(x1+y1+∣x1−y1∣),(x0−y0−∣x0−y0∣)−(x1−y1+∣x1−y1∣),(−x0+y0−∣x0−y0∣)−(−x1+y1+∣x1−y1∣),(−x0−y0−∣x0−y0∣)−(−x1−y1+∣x1−y1∣)}\begin{aligned} -|x_0 - y_0| - |x_1 - y_1| + (|x_0 - x_1| + |y_0 - y_1|) = \max\{&(x_0+y_0-|x_0 - y_0|) - (x_1+y_1+ |x_1 - y_1|),\\ &(x_0-y_0-|x_0 - y_0|) - (x_1-y_1+ |x_1 - y_1|),\\ &(-x_0+y_0-|x_0 - y_0|) - (-x_1+y_1+ |x_1 - y_1|),\\ &(-x_0-y_0-|x_0 - y_0|) - (-x_1-y_1+ |x_1 - y_1|) \} \end{aligned}

至此,剩余就是几种特殊情况了,都是 O(n)O(n) 级别的,直接暴力比一比就行了。

代码

class Solution {
public:
    int Abs(int x){
        if (x < 0) return -x;
        return x;
    }
    
    int maxValueAfterReverse(vector<int>& nums) {
        int n = nums.size();
        
        int sum = 0;
        for (int i = 0; i < n - 1; i++) sum += Abs(nums[i] - nums[i + 1]);
        
        int ans = sum;
        
        for (int i = 0; i < n - 1; i++){
            ans = max(ans, sum - Abs(nums[i] - nums[i + 1]) + Abs(nums[0] - nums[i + 1]));
            ans = max(ans, sum - Abs(nums[i] - nums[i + 1]) + Abs(nums[i] - nums[n - 1]));
        }
        
        for (int a = 0; a < 2; a++){
            for (int b = 0; b < 2; b++){
                vector<int> arrA, arrB;
                for (int i = 0; i < n - 1; i++){
                    int x = nums[i], y = nums[i + 1];
                    int cur = 0;
                    if (a == 0) cur -= x; else cur += x;
                    if (b == 0) cur -= y; else cur += y;
                    arrA.push_back(cur + Abs(x - y));
                    arrB.push_back(cur - Abs(x - y));
                }
                sort(arrA.begin(), arrA.end());
                sort(arrB.begin(), arrB.end());
                ans = max(ans, sum + arrB[n - 2] - arrA[0]);
            }
        }
        
        return ans;
    }
};
8
展开全部 6 讨论