1. 数组序号转换

给你一个整数数组arr,请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下:

  • 序号从 1 开始编号。
  • 元素越大,序号越大。如果两个元素相等,那么它们的序号相同。
  • 每个数字的序号都应该尽可能地小。

样例

示例 1:

输入:arr = [40,10,20,30]
输出:[4,1,2,3]
解释:40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。

示例 2:

输入:arr = [100,100,100]
输出:[1,1,1]
解释:所有元素有相同的序号。

示例 3:

输入:arr = [37,12,28,9,100,56,80,5,12]
输出:[5,3,4,2,8,6,7,1,3]

提示

  • 0 <= arr.length <= 105
  • -109?<= arr[i] <= 109

代码

viv丑陋版

几个月没写代码后正式写的第一题。我是猪。在相同大小数字那里纠结好久。
其实只需要引入一个变量id,初始为1,遍历排完序的数组,如果为一个新值则id+1并赋值。
考虑到要通过值反向查询序号,用map比较方便。

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        int len = arr.size();
        vector<int> tmp = arr;
        sort(arr.begin(), arr.end());
        map<int, int> mp;
        
        int id = 1;
        for(int i=0; i<len; i++) {
            if(i==0 || arr[i]!=arr[i-1]) mp[arr[i]] = id++; 
            else mp[arr[i]] = mp[arr[i-1]];
        }
        
        vector<int> ans;
        for(int i=0; i<len; i++) ans.push_back(mp[tmp[i]]);
        return ans;  
    } 
};

zz美丽版

人与人之间的差距怎么这么大呢TAT。zz说这是离散化常规操作。
首先遍历arr塞进一个set,实现去重和排序。
然后遍历set记录下序号和数值的对应关系。

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        set<int> pool;
        for(auto v: arr) pool.insert(v);

        map<int, int> rev;
        int tot = 0;
        for(auto v: pool) rev[v] = ++tot;

        vector<int> ans;
        for(auto v: arr) ans.push_back(rev[v]);

        return ans;
    }
};

2. 破坏回文串

给你一个回文字符串?palindrome ,请你将其中?一个 字符用任意小写英文字母替换,使得结果字符串的字典序最小,且 不是?回文串。
请你返回结果字符串。如果无法做到,则返回一个空串。

样例

示例 1:

输入:palindrome = "abccba"
输出:"aaccba"

示例 2:

输入:palindrome = "a"
输出:""

提示

  • 1 <= palindrome.length <= 1000
  • palindrome?只包含小写英文字母。

代码

viv丑陋版

比赛的时候错了几次,因为想不全,我好菜TAT。
第一眼想到如果长度是1,就直接返回空串。否则如果是回文串,将第一个非a字母变成a就ok。
错完之后想到了如果类似aabaa这种,需要将最后一个a改成b。
错完之后又想到了如果是一长串a,同样将最后一个a改成b即可。
综上,如果长度为1,返回空串。
否则遍历,遍历到不是a的字母,如果为中间位,将其变成a。
否则,说明为aabaa或aaaaa情况,将最后一个a改为b。

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int len = palindrome.size();
        if(len == 1) return "";

        for(int i=0; i<len; i++) {
            if(palindrome[i] != 'a') {
                if(i == len / 2) break;
                palindrome[i] = 'a'; return palindrome;
            }
        }

        palindrome[len - 1] = 'b';
        return palindrome;
    }
};

zz美丽版

其实zz和我想法是一样的。
首先从前往后找,不考虑长度为奇数时的中心字符,把第一个不是a的字符换成a。
这时只有一种情况不符合,就是全是a的情况,单独判断,将最后一位替换为b。
无法做到的情况只有1种同上。

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int len = palindrome.size();
        if(len == 1) return "";

        bool flag = false;
        for(int i=0; i<len; i++) {
            if((len & 1) && (i == len / 2)) continue;
            if(palindrome[i] != 'a') {
                palindrome[i] = 'a';
                flag = true;
                break;
            }
        }
        if(!flag) palindrome[len - 1] = 'b';
        return palindrome;
    }
};

3. 将矩阵按对角线排序

给你一个 m * n 的整数矩阵 mat ,请你将同一条对角线上的元素(从左上到右下)按升序排序后,返回排好序的矩阵。

样例

示例 1:

输入:mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
输出:[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

提示

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 100
  • 1 <= mati <= 100

代码

viv丑陋版

非常暴力的想法。比赛的时候把n和m搞反了。我真的无语我每一次都要搞反……
遍历第一行&第一列所有的点,以每个点为起点考察对角线。
把对角线塞进vector排序然后再依次放入位置。

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int mx = max(m, n);
        for(int i=0; i<m; i++) {
            int bx = 0, by = i;
            vector<int> ori;
            for(int j=0; j<mx; j++) {
                int cx = bx + j, cy = by + j;
                if(cx < 0 || cx >=n || cy < 0 || cy >= m) break;
                ori.push_back(mat[cy][cx]);
            }
            sort(ori.begin(), ori.end());
            for(int j=0; j<mx; j++) {
                int cx = bx + j, cy = by + j;
                if(cx < 0 || cx >=n || cy < 0 || cy >= m) break;
                mat[cy][cx] = ori[j];
            }
        }
        for(int i=1; i<n; i++) {
            int bx = i, by = 0;
            vector<int> ori;
            for(int j=0; j<mx; j++) {
                int cx = bx + j, cy = by + j;
                if(cx < 0 || cx >=n || cy < 0 || cy >= m) break;
                ori.push_back(mat[cy][cx]);
            }
            sort(ori.begin(), ori.end());
            for(int j=0; j<mx; j++) {
                int cx = bx + j, cy = by + j;
                if(cx < 0 || cx >=n || cy < 0 || cy >= m) break;
                mat[cy][cx] = ori[j];
            }
        }
        return mat;
    }
};

zz美丽版

zz和我思路一样!
只不过比我优雅一丢丢。

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(i > 0 && j > 0) continue;
                int x = i, y = j, c = 0;
                vector<int> cur;
                while(x < n && y < m) {
                    cur.push_back(mat[x][y]);
                    x++; y++;
                }
                sort(cur.begin(), cur.end());
                x = i; y = j;
                while(x < n && y < m) {
                    mat[x][y] = cur[c++];
                    x++; y++;
                }
            }
        }
        return mat;
    }
};

4. 翻转子数组得到的最大数组值

给你一个整数数组?nums 。
「数组值」定义为所有满足?0 <= i < nums.length-1?的?|nums[i]-nums[i+1]|?的和。
你可以选择给定数组的任意子数组,并将该子数组翻转。但你只能执行这个操作?一次
请你找到可行的最大 数组值?。

样例

示例 1:

输入:nums = [2,3,1,5,4]
输出:10
解释:通过翻转子数组 [3,1,5] ,数组变成 [2,5,1,3,4] ,数组值为 10 。

示例 2:

输入:nums = [2,4,9,24,2,1,10]
输出:68

提示

  • 1 <= nums.length <= 3*10^4
  • -10^5 <= nums[i] <= 10^5

代码

viv丑陋版

想法就是,一次操作只改变子数组的头尾绝对值。但是不知道如何实现TAT。

zz美丽版

假设原数组为$...a|b...c|d$,数组值为$sum$。
翻转子区间后的数组为$...a|c...b|d$,数组值为$sum-|a-b|-|c-d|+|a-c|+|b-d|$。
令$a=x0$, $b=y0$, $c=x1$, $d=y1$。
则翻转后数组值为$sum-|x0-y0|-|x1-y1|+|x0-x1|+|y0-y1|$。
转换为求曼哈顿距离的最大值。
$|x0-x1|+|y0-y1|$
$=max((x0-x1)+(y0-y1), (x1-x0)+(y1-y0), $
$\ \ \ \ \ \ \ \ \ \ \ \ \ (x0-x1)+(y1-y0), (x1-x0)+(y0-y1))$

$|x0-x1|+|y0-y1|$
$=max((x0+y0)-(x1+y1), -(x0+y0)+(x1+y1), $
$\ \ \ \ \ \ \ \ \ \ \ \ \ (x0-y0)-(x1-y1), -(x0-y0)+(x1-y1))$

$|x0-x1|+|y0-y1|=max(|(x0+y0)-(x1+y1)|, |(x0-y0)-(x1-y1)|)$

除此以外,我们还需将点独立的信息考虑进去,即$(-|x0-y0|-|x1-y1|)$。
$|x0-x1|+|y0-y1|-|x0-y0|-|x1-y1|=?$,分为前后两部分考虑。
第一部分:
$max|(x0+y0)-(x1+y1)|-|x0-y0|-|x1-y1|$
$= max((x0+y0-|x0-y0|)-(x1+y1+|x1-y1|), $
$\ \ \ \ \ \ \ \ \ \ \ \ (-x0-y0-|x0-y0|)-(-x1-y1+|x1-y1|))$
第二部分:
$max|(x0-y0)-(x1-y1)|-|x0-y0|-|x1-y1|$
$=max((x0-y0-|x0-y0|)-(x1-y1+|x1-y1|),$
$\ \ \ \ \ \ \ \ \ \ \ \ (-x0+y0-|x0-y0|)-(-x1+y1+|x1-y1|))$
注意子数组如果从开头开始或从结尾结束,需要特殊判断。

class Solution {
public:
    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++) {
            // b...c|d... => c...b|d...
            ans = max(ans, sum-abs(nums[i]-nums[i+1])+abs(nums[0]-nums[i+1]));
            // ...a|b...c => ...a|c...b
            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;
    }
};
最后修改:2020 年 03 月 18 日 11 : 18 AM
如果觉得我的文章对你有用,请随意赞赏