On the shoulders of giants.

biweekly-contest-18

数组序号转换

给你一个整数数组 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
题解

排序去重后二分查找。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    int num[100010];
    vector<int> arrayRankTransform(vector<int>& arr) {
        int n = arr.size();
        vector<int> result(n);
        for(int i = 0; i < n; i++) {
            num[i] = arr[i];
        }
        sort(num, num + n);
        int m = unique(num, num + n) - num;
        for(int i = 0; i < n; i++) {
            int x = lower_bound(num, num + m, arr[i]) - num + 1;
            result[i] = x;
        }
        return result;
    }
};

破坏回文串

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

请你返回结果字符串。如果无法做到,则返回一个空串。

示例 1:

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

示例 2:

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

提示:

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

贪心模拟,从小到大枚举代填的字符,填入比待填入字符大的的位置,如果没有则填入最后一位。

时间复杂度:\(O(26n^2)\)

class Solution {
public:
    string breakPalindrome(string palindrome) {
        int n = palindrome.length(), m = (n - 1) / 2;
        int p1 = m, p2 = (n % 2 ? m : m + 1);
        for(char c = 'a'; c <= 'z'; c++) {
            for(int i = 0; i < n; i++) {
                if(palindrome[i] == c) continue;
                if(palindrome[i] < c && i != n - 1) continue;
                char tmp = palindrome[i];
                palindrome[i] = c;
                bool flag = false;
                for(int k = 0; k <= p1 && !flag; k++) {
                    if(palindrome[p1-k] != palindrome[p2+k])
                        flag = true;
                }
                if(!flag) {
                    palindrome[i] = tmp;
                    continue;
                } else return palindrome;
            }
        }
        return (string)"";
    }
};

将矩阵按对角线排序

给你一个 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 <= mat[i][j] <= 100
题解

取出每条对角线上的元素,然后排序,再填回对角线。

时间复杂度:\(O(nm+(n+m)\log \max(n,m))\)

class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size(), k = n + m - 1;
        vector<vector<int>> num(k);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                num[m - 1 + i - j].push_back(-mat[i][j]);
            }
        }
        for(int i = 0; i < k; i++) {
            sort(num[i].begin(), num[i].end());
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                mat[i][j] = -num[m - 1 + i - j].back();
                num[m - 1 + i - j].pop_back();
            }
        }
        return mat;
    }
};

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

给你一个整数数组 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
题解

显然,子区间翻转代价只与区间两边的差值有关,代价为:

\(=-|num_{x-1}-num_x|- |num_y-num_{y+1}|+|num_{x-1}-num_y|+|num_x-num_{y+1}|\)

对于曼哈顿距离:

\(|num_{x-1}-num_y|+|num_x-num_{y+1}|\) , 等价于四种情况结合求最大值:

  • \( num_{x-1}+num_x -num_y -num_{y+1} \)
  • \( num_{x-1}-num_x -num_y +num_{y+1} \)
  • \( -num_{x-1}+num_x +num_y -num_{y+1} \)
  • \( -num_{x-1}-num_x +num_y +num_{y+1} \)

结合代价,即求下列四种情况的最大值:

  • \( (num_{x-1}+num_x-|num_{x-1}-num_x|)-(num_y +num_{y+1}+|num_y-num_{y+1}|)\)
  • \( (num_{x-1}-num_x -|num_{x-1}-num_x|) -(num_y-num_{y+1} +|num_y-num_{y+1}|) \)
  • \( (-num_{x-1}+num_x -|num_{x-1}-num_x|) -(-num_y +num_{y+1}+|num_y-num_{y+1}|) \)
  • \( (-num_{x-1}-num_x -|num_{x-1}-num_x|) -(-num_y -num_{y+1} +|num_y-num_{y+1}|) \)

最后求出的即使最大代价。

时间复杂度:\(O(n)\)

const int dt[2][4] = {{1, 1, -1, -1}, {1, -1, 1, -1}};
class Solution {
private:
    int getMax(vector<int>& nums) {
        int result = -1E9;
        for(auto num : nums) {
            result = max(result, num);
        }
        return result;
    }
    int getMin(vector<int>& nums) {
        int result = 1E9;
        for(auto num : nums) {
            result = min(result, num);
        }
        return result;
    }
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int sum = 0, ans = 0, n = nums.size();
        vector<int> v1(n - 1), v2(n - 1);
        for(int i = 0; i < n - 1; i++) {
            sum += abs(nums[i] - nums[i + 1]);
        }
        for(int i = 0; i < n; i++) {
            if(i != n - 1) 
                ans = max(ans, -abs(nums[i] - nums[i + 1]) + abs(nums[0] - nums[i + 1]));
            if(i != 0)
                ans = max(ans, -abs(nums[i] - nums[i - 1]) + abs(nums[n - 1] - nums[i - 1]));
        }
        for(int k = 0; k < 4; k++) {
            for(int i = 0; i < n - 1; i++) {
                int p = dt[0][k] * nums[i];
                int q = dt[1][k] * nums[i + 1];
                int tmp = abs(nums[i] - nums[i + 1]); 
                v1[i] = p + q - tmp;
                v2[i] = p + q + tmp;
            }
            ans = max(ans, getMax(v1) - getMin(v2));
        }
        return sum + ans;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注