leetcode解题思路分析（一百二十八）1053 - 1078 题

1053. 交换一次的先前排列
      给你一个正整数的数组 A（其中的元素不一定完全不同），请你返回可在 一次交换（交换两数字 A[i] 和 A[j] 的位置）后得到的、按字典序排列小于 A 的最大可能排列。如果无法这么操作，就请返回原数组。

贪心算法，先从后往前找到第一个可以变的位置，然后在从该位置往后找到最大的值进行调整

class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int n = arr.size(), idx = -1;
        for(int i=n-1; i>=1; i--){
            if(arr[i] < arr[i-1]){
                idx = i-1;
                break;
            }
        }
        if(idx == -1) return arr;
        int maxv = 0, t = arr[idx], pos = idx;
        for(int i = idx+1; i<n; i++){
            if(arr[i] < arr[idx]){
                if(arr[i] > maxv){
                    maxv = arr[i];
                    pos = i;
                }
            }
        }
        swap(arr[idx], arr[pos]);
        return arr;
    }
};


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

1054. 距离相等的条形码
      在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。请你重新排列这些条形码，使其中任意两个相邻的条形码不能相等。 你可以返回任何满足该要求的答案，此题保证存在答案。

哈希+堆

class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& barcodes) {
        unordered_map<int,int>num2cnt;
        int n=barcodes.size();
        for(int i=0;i<n;i++){
            num2cnt[barcodes[i]]++;
        }
        priority_queue<pair<int,int>>maxHeap;
        for(auto mPair:num2cnt)maxHeap.push({mPair.second,mPair.first});
        vector<int>ans;
        while(maxHeap.empty()==false){
            auto [firstCnt,firstNum]=maxHeap.top();maxHeap.pop();
            if(ans.empty()||ans.back()!=firstNum){
                ans.push_back(firstNum);
                firstCnt--;
                if(firstCnt==0)continue;
                maxHeap.push({firstCnt,firstNum});
            }else {
                auto [secondCnt,secondNum]=maxHeap.top();maxHeap.pop();
                maxHeap.push({firstCnt,firstNum});
                ans.push_back(secondNum);
                secondCnt--;
                if(secondCnt==0)continue;
                maxHeap.push({secondCnt,secondNum});
            }
            
        }
        return ans;
    }
};

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

1071. 字符串的最大公因子
      对于字符串 s 和 t，只有在 s = t + … + t（t 自身连接 1 次或多次）时，我们才认定 “t 能除尽 s”。
      给定两个字符串 str1 和 str2 。返回 最长字符串 x，要求满足 x 能除尽 str1 且 X 能除尽 str2 。

字符串两种顺序拼接后相等，则一定是可以找到公共子串，然后求其长度的公约数，即为最大字串。

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if (str1 + str2 != str2 + str1) return "";
        return str1.substr(0, __gcd((int)str1.length(), (int)str2.length())); // __gcd() 为c++自带的求最大公约数的函数
    }
};


1
2
3
4
5
6
7
8
9

1072. 按列翻转得到最大值等行数
      给定 m x n 矩阵 matrix 。你可以从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）返回 经过一些翻转后，行与行之间所有值都相等的最大行数 。

1、每一行都是一个0-1串，计算各行的特征，特征可以用字符串形式表示
2、建立哈希表，key为特征值，value为特征是key的行的个数
3、最大的value即为所求

class Solution {
public:
    int maxEqualRowsAfterFlips(vector<vector<int>>& matrix) {
        int m=matrix.size(), n=matrix[0].size();
        unordered_map<string, int> map; // 统计具有某特征的行的个数
        for(int i=0;i<m;++i){
            string feature; // 特征以字符串表示
            for(int j=0;j<n;++j)
                feature.push_back(matrix[i][j]);
            // 若当前行的首位为0，需要进行翻转
            if(feature[0]==0){
                for(int j=0;j<n;++j)
                    feature[j]=1-feature[j];
            }
            ++map[feature]; // 计数
        }
        int ans=0;
        for(auto p:map)
            ans=max(ans, p.second);// 取最大值
        return ans;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1073. 负二进制数相加
      给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        int n1 = arr1.size();
        int n2 = arr2.size();
        int n = max(n1,n2)+4;
        vector<int> res(n, 0);
        // 和arr1和arr2 倒序的计算，低位在前面
        for (int i = n1-1; i >= 0; --i)
        {
            res[n1-1-i] += arr1[i];
        }
        for (int i = n2-1; i >= 0; --i)
        {
            res[n2-1-i] += arr2[i];
        }

        // 从低位开始计算
        for (int i = 0; i +2 < n; ++i)
        {
            // 进位
            int carry = res[i] >> 1;
            res[i] &= 1;
            res[i+1] += carry;
            res[i+2] += carry;
        }
        // 观察最高位连续零需要移除
        int k = n-3;
        // 这里结束是0，来避免0,0->空的情况
        while (k > 0 && res[k] == 0)
        {
            --k;
        }
        reverse(res.begin(), res.begin()+k+1);
        // 移除末尾的为0的部分
        int i = n-k-1;
        while(i > 0)
        {
            --i;
            res.pop_back();
        }

        return res;
    }
};


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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

1074. 元素和为目标值的子矩阵数量
      给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

前缀和的二维应用

class Solution {
private:
    int subarraySum(vector<int> &nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto &x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }

public:
    int numSubmatrixSumTarget(vector<vector<int>> &matrix, int target) {
        int ans = 0;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) { // 枚举上边界
            vector<int> sum(n);
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                ans += subarraySum(sum, target);
            }
        }
        return ans;
    }
};
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

1078. Bigram 分词
      给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 “first second third” 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。对于每种这样的情况，将第三个词 “third” 添加到答案中，并返回答案。

先按空格分组单词，然后遍历即可

class Solution {
public:
    vector<string> findOcurrences(string text, string first, string second) {
        vector<string> words;
        int s = 0, e = 0, len = text.length();
        while (true) {
            while (s < len && text[s] == ' ') {
                s++;
            }
            if (s >= len) {
                break;
            }
            e = s + 1;
            while (e < len && text[e] != ' ') {
                e++;
            }
            words.push_back(text.substr(s, e - s));
            s = e + 1;
        }
        vector<string> ret;
        for (int i = 2; i < words.size(); i++) {
            if (words[i - 2] == first && words[i - 1] == second) {
                ret.push_back(words[i]);
            }
        }
        return ret;
    }
};

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