leetcode解题思路分析（八十七）764 - 770 题

红太狼 2022-09-04 03:47 147阅读 0赞

1.  最大加号标志  
    在一个大小在 (0, 0) 到 (N-1, N-1) 的2D网格 grid 中，除了在 mines 中给出的单元为 0，其他每个单元都是 1。网格中包含 1 的最大的轴对齐加号标志是多少阶？返回加号标志的阶数。如果未找到加号标志，则返回 0。

**四方遍历求一边即可**

class Solution { 
    public:
        int orderOfLargestPlusSign(int N, vector<vector<int>>& mines) { 
            if (mines.size() == N * N) return 0;
            if (mines.size() > N * N - 5) return 1;
            int grid[N][N];
            int arm[N][N][4];
            // set all the value of grid to be "1", this is a trick to use "-1"
            memset(grid, -1, sizeof(grid));
            // set all the value of arm to be "0"
            memset(arm, 0, sizeof(arm));
            for (auto& v : mines) { 
                grid[v[0]][v[1]] = 0;
            }
            for (int i = 0; i < N; ++i) { 
                for (int j = 0; j < N; ++j) { 
                    if (grid[i][j] == 0) continue;
                    arm[i][j][0] = 1 + ((i > 0) ? arm[i - 1][j][0] : 0);
                    arm[i][j][1] = 1 + ((j > 0) ? arm[i][j - 1][1] : 0);
                }
            }
            for (int i = N - 1; i >= 0; --i) { 
                for (int j = N - 1; j >= 0; --j) { 
                    if (grid[i][j] == 0) continue;
                    arm[i][j][2] = 1 + ((i < N - 1) ? arm[i + 1][j][2] : 0);
                    arm[i][j][3] = 1 + ((j < N - 1) ? arm[i][j + 1][3] : 0);
                }
            }
            int res = 0;
            for (int i = 0; i < N; ++i) { 
                for (int j = 0; j < N; ++j) { 
                    if (grid[i][j] == 0) continue;
                    int s = min(min(arm[i][j][0], arm[i][j][1]), min(arm[i][j][2], arm[i][j][3]));
                    res = max(res, s);
                }
            }
            return res;
        }
    };

1.  情侣牵手  
    N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。  
    人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。  
    这些情侣的初始座位 row\[i\] 是由最初始坐在第 i 个座位上的人决定的。

**实际是一个数学题，至少交换的次数 = 所有情侣的对数 - 并查集里连通分量的个数**

class Solution { 
    public:
        int minSwapsCouples(vector<int>& row) { 
            unordered_map<int,int> hash;
            int ans=0;
            for(int i=0;i<row.size();++i)
            hash[row[i]]=i;
            for(int i=0;i<row.size();i+=2)//遍历沙发
            { 
                int lover=row[i]^1;//a的情侣
                if(hash[lover]!=i+1)
                { 
                    ++ans;
                    hash[row[i+1]]=hash[lover];
                    swap(row[hash[lover]],row[i+1]);//交换位置
                    hash[lover]=i+1;
                }
            }
            return ans;
        }
    };

1.  托普利兹矩阵  
    给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。  
    如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵 。

**遍历即可**

class Solution { 
    public:
        bool isToeplitzMatrix(vector<vector<int>>& matrix) { 
            int m = matrix.size(), n = matrix[0].size();
            for (int i = 1; i < m; i++) { 
                for (int j = 1; j < n; j++) { 
                    if (matrix[i][j] != matrix[i - 1][j - 1]) { 
                        return false;
                    }
                }
            }
            return true;
        }
    };

1.  重构字符串  
    给定一个字符串S，检查是否能重新排布其中的字母，使得两相邻的字符不同。  
    若可行，输出任意可行的结果。若不可行，返回空字符串。

**贪心法求解**

class Solution { 
    public:
        string reorganizeString(string s) { 
            if (s.length() < 2) { 
                return s;
            }
            vector<int> counts(26, 0);
            int maxCount = 0;
            int length = s.length();
            for (int i = 0; i < length; i++) { 
                char c = s[i];
                counts[c - 'a']++;
                maxCount = max(maxCount, counts[c - 'a']);
            }
            if (maxCount > (length + 1) / 2) { 
                return "";
            }
            string reorganizeArray(length, ' ');
            int evenIndex = 0, oddIndex = 1;
            int halfLength = length / 2;
            for (int i = 0; i < 26; i++) { 
                char c = 'a' + i;
                while (counts[i] > 0 && counts[i] <= halfLength && oddIndex < length) { 
                    reorganizeArray[oddIndex] = c;
                    counts[i]--;
                    oddIndex += 2;
                }
                while (counts[i] > 0) { 
                    reorganizeArray[evenIndex] = c;
                    counts[i]--;
                    evenIndex += 2;
                }
            }
            return reorganizeArray;
        }
    };

1.  最多能完成排序的块 II  
    arr是一个可能包含重复元素的整数数组，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。我们最多能将数组分成多少块？

**贪心算法：  
思路：只有对于某个位置，其左边（包括该数本身）的最大值不大于位置右侧的最小值，在该处就可以分段**

class Solution { 
    public:
        int maxChunksToSorted(vector<int>& arr) { 
            int n = arr.size();
            // map用来记录数字到个数的映射
            unordered_map<int, int> num2cnt;
            // 记录可以拆分的最大个数
            int res = 0;
            // 记录当前窗口数量是否一致，等于0则说明一样
            int isEqual = 0;
            // 排序的arr
            vector<int> sortArr = arr;
            sort(sortArr.begin(), sortArr.end());
            for (int i = 0; i < n; ++i)
            { 
                ++num2cnt[arr[i]];
                // 这里使用技巧就是只有变为0或者1时候才去操作, 这样才能真正按照不同数字来拆分，而不和数字本身数量有关
                if (num2cnt[arr[i]] == 0)
                { 
                    --isEqual;
                }
                else if (num2cnt[arr[i]] == 1)
                { 
                    ++isEqual;
                }
    
                // 需要去减去
                --num2cnt[sortArr[i]];
                // 同理
                if (num2cnt[sortArr[i]] == 0)
                { 
                    --isEqual;
                }
                else if (num2cnt[sortArr[i]] == -1)
                { 
                    ++isEqual;
                }
    
                // 找到元素完全出现的
                if (isEqual == 0)
                { 
                    ++res;
                }
            }
            return res;
        }
    };

1.  最多能完成排序的块  
    数组arr是\[0, 1, …, arr.length - 1\]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。  
    我们最多能将数组分成多少块？

**贪心算法，和上题思路一样**

class Solution { 
    public:
        int maxChunksToSorted(vector<int>& arr) 
        {        
            int leftMax = INT_MIN, size = arr.size(), ret = 1, rightMin = 0;
    
            for (int i = 0; i < size - 1; i++)
            { 
                leftMax = max(leftMax, arr[i]);
                rightMin = i + 1;
    
                if (leftMax < rightMin)
                { 
                    ret++;
                    leftMax = INT_MIN;
                }
            } 
    
            return ret;
    
        }
    };

1.  基本计算器4

**没啥好说的，就一堆细节一个一个来就好**

class Solution { 
        //两个不同的变量名称str1,str2按照字典序组合为一个新的变量名称newVarName
        //例如 str1 = a*c, str2 = b*d ,组合后得到 a*b*c*d
        string combineNewVarName(string str1, string str2) { 
            vector<string> A;
    
            str1 += '*';
            int pos = str1.find("*", 0);
            while (pos != str1.npos) { 
                string temp = str1.substr(0, pos);
                A.push_back(temp);
                str1 = str1.substr(pos + 1, str1.size());
                pos = str1.find("*", 0);
            }
    
            str2 += '*';
            pos = str2.find("*", 0);
            while (pos != str2.npos) { 
                string temp = str2.substr(0, pos);
                A.push_back(temp);
                str2 = str2.substr(pos + 1, str2.size());
                pos = str2.find("*", 0);
            }
    
            sort(A.begin(), A.end());
            string newVarName = A[0];
            for (int i = 1; i < A.size(); i++) { 
                newVarName += "*";
                newVarName += A[i];
            }
            return newVarName;
        }
    
        //从字符串idx位置开始，获取一个新操作数
        map<string, int> getOne(string &str, int& idx) { 
            map<string, int> res;
            res["@"] = 0;
            int n = str.size();
            if (idx >= n) return res;
            int start = idx;
            if (str[idx] == '(') {  //将括号表达式的计算结果返回
                stack<int> s;
                s.push(idx++);
                while (idx < n && !s.empty()) { 
                    if (str[idx] == '(') s.push(idx);
                    if (str[idx] == ')') s.pop();
                    idx++;
                }
                string substr = str.substr(start + 1, idx - start - 2);
                res = calculator(substr);
            } else if (isdigit(str[idx])) {  //操作数是一个数字
                while (idx < n && isdigit(str[idx])) idx++;
                string val = str.substr(start, idx - start);
                res["@"] = stoi(val);
            } else {  //操作数是一个变量
                while (idx < n && str[idx] != ' ') idx++;
                string varName = str.substr(start, idx - start);
                if (hashtable.count(varName)) res["@"] = hashtable[varName];
                else {  res[varName] = 1; }
            }
            idx += 1;
            return res;
        }
    
        //定义新的加法操作
        map<string, int> add(map<string, int> &A, map<string, int> &B) { 
            map<string, int> C = A;
            for (auto &x:B) { 
                if (C.count(x.first)) { 
                    C[x.first] += x.second;
                } else { 
                    C[x.first] = x.second;
                }
            }
            return C;
        }
    
        //定义新的减法操作
        map<string, int> sub(map<string, int> &A, map<string, int> &B) { 
            map<string, int> C = A;
            for (auto &x:B) { 
                if (C.count(x.first)) { 
                    C[x.first] -= x.second;
                } else { 
                    C[x.first] = -x.second;
                }
            }
            return C;
        }
    
        //定义新的乘法操作
        map<string, int> mul(map<string, int> &A, map<string, int> &B) { 
            map<string, int> C;
            C["@"] = 0;
            for (auto &a:A) { 
                for (auto &b:B) {  
                    if (a.first == "@") {  // a是常数
                        if (C.count(b.first)) { 
                            C[b.first] += a.second * b.second;
                        } else { 
                            C[b.first] = a.second * b.second;
                        }
                    } else if (b.first == "@") {  //b是常数
                        if (C.count(a.first)) { 
                            C[a.first] += a.second * b.second;
                        } else { 
                            C[a.first] = a.second * b.second;
                        }
                    } else {  //a b 都不是常数，则需要合成新的变量名称
                        string newVarName = combineNewVarName(a.first, b.first); 
                        if (C.count(newVarName)) { 
                            C[newVarName] += a.second * b.second;
                        } else { 
                            C[newVarName] = a.second * b.second;
                        }
                    }
                }
            }
            return C;
        }
    
        //基于新元素操作的计算器
        map<string,int> calculator(string expression) { 
            if(expression.empty()) return { };
            map<string, int> res, curRes;
            res["@"] = 0;
            curRes["@"] = 0;
            expression += " +";
            int n = expression.size();
            char op = '+';
            for (int i = 0; i < n; i += 2) { 
                map<string, int> x = getOne(expression, i);
                if (expression[i] == '+' || expression[i] == '-' || expression[i] == '*' || i == n - 1) { 
                    switch (op) { 
                        case '+':
                            curRes = add(curRes, x);
                            break;
                        case '-':
                            curRes = sub(curRes, x);
                            break;
                        case '*':
                            curRes = mul(curRes, x);
                            break;
                    }
                    if (expression[i] == '+' || expression[i] == '-' || i == n - 1) { 
                        res = add(res, curRes);
                        curRes.clear();
                        curRes["@"] = 0;
                    }
                    op = expression[i];
                }
            }
            return res;
        }
    
    public:
        unordered_map<string,int> hashtable;
        vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) { 
            //使用哈希表将变量与其值对应起来
            for (int i = 0; i < evalvars.size(); i++) { 
                hashtable[evalvars[i]] = evalints[i];
            }
    
            //使用基于新操作数的计算器计算出表达式的结果，结果以新操作数的形式返回
            map<string, int> tree = calculator(expression);
    
            //整理、排序输出最终的结果
            //排序的规则是：变量排在常数前面，变量名称中含有的子变量越多，排序越靠前；变量名称中的子变量数目相同，则按照字典序进行排序
            // 比如运算结果：-99*z*z*z*z*z 9*a*b*c*d 6*b*b*b 5*a*b 1*a 2*b 3*c 18 是合法的排序
            vector<pair<int,string>> sortVec;
            for(auto &x:tree){ 
                if (x.second != 0 && x.first != "@") { 
                    string str = x.first;
                    str += '*';
                    int cnt = 0;
                    int pos = str.find("*", 0);
                    while (pos != str.npos) { 
                        cnt++;
                        str = str.substr(pos + 1, str.size());
                        pos = str.find("*", 0);
                    }
                    sortVec.push_back({ cnt, x.first});
                }
            }
    
            sort(sortVec.begin(), sortVec.end(),[](pair<int,string> A, pair<int, string> B){ 
                return A.first != B.first ? A.first > B.first : A.second < B.second;
            });
    
            vector<string> ans(sortVec.size());
            int constant = tree["@"];
            for (int i = 0; i < sortVec.size(); i++) { 
                ans[i] = to_string(tree[sortVec[i].second]) + "*" + sortVec[i].second;
            }
    
            if (constant != 0) ans.push_back(to_string(constant));
    
            return ans;
        }
    };