第 18 场双周赛

Posted on | In , | |
Words count in article: 578 | Reading time ≈ 3

1331. 数组序号转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        map<int, int> mp;
        vector<int> arr2 = arr;
        sort(arr2.begin(), arr2.end());
        int k = 1;
        for(int i=0; i<arr2.size(); i++){
            if(mp[arr2[i]]) continue;
            mp[arr2[i]] = k++;
        }
        vector<int> res;
        for(int i=0; i<arr.size(); i++){
            res.push_back(mp[arr[i]]);
        }
        return res;
    }
};

1328. 破坏回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    string breakPalindrome(string p) {
        if(p == "" || p.size() <= 1) return "";
        for(int i=0; i<p.size()/2; i++){
            if(p[i] != 'a'){
                p[i] = 'a';
                return p;
            }
        }
        p[p.size()-1] = 'b';
        return p;
    }
};

1329. 将矩阵按对角线排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
        int Col = mat[0].size();
        int Row = mat.size();
        if(Row==1 || Row==0 || Col==1)
            return mat;
        for(int i = Row-2;i >= 0;i--)
        {
            int col = 0;
            vector<int> temp;
            for(int j = i;j < Row && col < Col;++j,col++)
                temp.push_back(mat[j][col]);
            sort(temp.begin(),temp.end());
            col = 0;
            for(int j = i;j < Row && col < Col;++j,col++)
                mat[j][col] = temp[col];
        }
        for(int i = 1;i <Col-1;++i)
        {
            int row = 0;
            vector<int> temp;
            for(int j = i;j < Col && row < Row;++j,row++)
                temp.push_back(mat[row][j]);
            sort(temp.begin(),temp.end());
            row = 0;
            for(int j = i;j < Col && row <Row;++j,row++)
                mat[row][j] = temp[row];
        }
        return mat;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef long long ll;
class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int ans = 0;
        int n = nums.size();
        if (n == 1)
            return 0;
        for (int i = 0; i < n - 1; ++i) {
            ans += abs(nums[i] - nums[i + 1]);
        }
        int raw = ans;
        for (int i = 1; i <= n - 2; ++i) {
            ans = max(ans,raw+abs(nums[n-1]-nums[i-1])-abs(nums[i]-nums[i-1]));
            ans = max(ans,raw+abs(nums[i+1]-nums[0])-abs(nums[i+1]-nums[i]));
        }
        int mx1 = INT_MIN;
        int mx2 = INT_MIN;
        int mx3 = INT_MIN;
        int mx4 = INT_MIN;
        for(int i = 1; i < n; ++i){
            ans = max(ans,raw + mx1 + nums[i] + nums[i-1] - abs(nums[i]-nums[i-1]));
            ans = max(ans,raw + mx2 - nums[i] + nums[i-1] - abs(nums[i]-nums[i-1]));
            ans = max(ans,raw + mx3 + nums[i] - nums[i-1] - abs(nums[i]-nums[i-1]));
            ans = max(ans,raw + mx4 - nums[i] - nums[i-1] - abs(nums[i]-nums[i-1]));
            mx1 = max(mx1,-(nums[i]+nums[i-1])-abs(nums[i]-nums[i-1]));
            mx2 = max(mx2,-(-nums[i]+nums[i-1])-abs(nums[i]-nums[i-1]));
            mx3 = max(mx3,-(nums[i]-nums[i-1])-abs(nums[i]-nums[i-1]));
            mx4 = max(mx4,-(-nums[i]-nums[i-1])-abs(nums[i]-nums[i-1]));
        } 
        return ans;
    }
};
Donate? comment?