• Leetcode刷题笔记--Hot81--90

    目录

    1--打家劫舍III（337）

    2--比特位计数（338）

    3--前K个高频元素（347）

    4--字符串解码（394）

    5--除法求值（399）

    6--根据身高重建队列（406）

    7--分割等和子集（416）

    8--路径总和III（437）

    9--找到字符串中所有字母异位词（438）

    10--找到所有数组中消失的数字（448）

    1--打家劫舍III（337）

    主要思路：

            基于从下到上的 dp 回溯法，每一个节点只有两种状态，dp[0]表示被打劫，dp[1]表示不被打劫；

            当前节点被打劫时，其孩子只能都不被打劫；dp[0] = left[1] + right[1] + cur->val；

            当前节点不被打劫时，其孩子可以都被打劫，也可以都不被打劫，或者一个被打劫另一个不被打劫。

            dp[1] = max(left[0] + right[0], left[1] + right[1], left[0] + right[1], left[1] + right[0])；

    1. #include 
    2. #include 
    3.  
    4. struct TreeNode {
    5.     int val;
    6.     TreeNode *left;
    7.     TreeNode *right;
    8.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    9.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    11. };
    12.  
    13. class Solution {
    14. public:
    15.     int rob(TreeNode* root) {
    16.         // 对于每一间房屋，有被打劫和不被打劫两种状态
    17.         std::vector<int> res = dfs(root);
    18.         return std::max(res[0], res[1]);
    19.     }
    20.  
    21.     std::vector<int> dfs(TreeNode* cur){
    22.         if(cur == nullptr) return {0, 0};
    23.         std::vector<int> left = dfs(cur->left);
    24.         std::vector<int> right = dfs(cur->right);
    25.         std::vector<int> dp(2, 0); // dp[0]表示被打劫 dp[1]表示不被打劫
    26.         dp[0] = left[1] + right[1] + cur->val; // 当前房屋被打劫，其孩子只能不被打劫
    27.         // 当前房屋不被打劫，其孩子可以同时被打劫，也可以同时不被打劫
    28.         // 当前房屋不被打劫，其孩子可以一个被打劫，另一个不被打劫
    29.         dp[1] = std::max(std::max(std::max(left[0] + right[0], left[1] + right[1]), left[0] + right[1]), left[1] + right[0]); 
    30.         return dp;
    31.     }
    32. };
    33.  
    34. int main(int argc, char* argv[]){
    35.     // root = [3, 2, 3, null, 3, null, 1]
    36.     TreeNode *Node1 = new TreeNode(3);
    37.     TreeNode *Node2 = new TreeNode(2);
    38.     TreeNode *Node3 = new TreeNode(3);
    39.     TreeNode *Node4 = new TreeNode(3);
    40.     TreeNode *Node5 = new TreeNode(1);
    41.  
    42.     Node1->left = Node2;
    43.     Node1->right = Node3;
    44.     Node2->right = Node4;
    45.     Node3->right = Node5;
    46.  
    47.     Solution S1;
    48.     int res = S1.rob(Node1);
    49.     std::cout << res << std::endl;
    50.     return 0;
    51. }

    2--比特位计数（338）

    主要思路： 

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vector<int> countBits(int n) {
    7.         std::vector<int> dp(n + 1, 0);
    8.         int high_valid = 0;
    9.         for(int i = 1; i <= n; i++){
    10.             if((i & (i - 1)) == 0){ // i是2的指数幂，更新最高有效位
    11.                 high_valid = i;
    12.             }
    13.             dp[i] = dp[i - high_valid] + 1;
    14.         }
    15.         return dp;
    16.     }
    17. };
    18.  
    19. int main(int argc, char* argv[]){
    20.     // n = 5
    21.     int n = 5;
    22.     Solution S1;
    23.     std::vector<int> res = S1.countBits(n);
    24.     for(auto num : res) 
    25.         std::cout << num << " ";
    26.     std::cout << std::endl;
    27.     return 0;
    28. }

    3--前K个高频元素（347）

    主要思路：

            维护一个小根堆，存储k个高频元素；

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. class Solution{
    7. public:
    8.     std::vector<int> topKFrequent(std::vector<int>& nums, int k){
    9.         std::unordered_map<int, int> hash_map;
    10.         for(int i = 0; i < nums.size(); i++){
    11.             hash_map[nums[i]] += 1;
    12.         }
    13.  
    14.         // 小顶堆
    15.         std::priority_queueint, int>, std::vectorint, int>>, mycompare> pri_q; 
    16.         for(auto i = hash_map.begin(); i != hash_map.end(); i++){
    17.             if(pri_q.size() >= k){
    18.                 if(i->second > pri_q.top().second){
    19.                     pri_q.pop();
    20.                     pri_q.emplace(i->first, i->second);
    21.                 }
    22.             }
    23.             else{
    24.                 pri_q.emplace(i->first, i->second);
    25.             }
    26.         }
    27.  
    28.         std::vector<int> res;
    29.         while(!pri_q.empty()){
    30.             res.push_back(pri_q.top().first);
    31.             pri_q.pop();
    32.         }
    33.         return res;
    34.     }
    35.  
    36.     class mycompare{
    37.     public:
    38.         bool operator()(std::pair<int, int>& item1, std::pair<int, int>& item2){
    39.             return item1.second > item2.second;
    40.         }
    41.     };
    42. };
    43.  
    44. int main(int argc, char argv[]){
    45.     // nums = [1, 1, 1, 2, 2, 3], k = 2
    46.     std::vector<int> test = {1, 1, 1, 2, 2, 3};
    47.     int k = 2;
    48.     Solution S1;
    49.     std::vector<int> res = S1.topKFrequent(test, k);
    50.     for(int num : res) std::cout << num << " ";
    51.     std::cout << std::endl;
    52.     return 0;
    53. }

    4--字符串解码（394）

    主要思路：

            从后开始遍历，用一个栈存储访问的字符，遇到左括号就处理字符串和重复次数；

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::string decodeString(std::string s) {
    8.         std::stack stk;
    9.         int i = s.length() - 1; // 从后开始遍历
    10.         while(i >= 0){
    11.             if(s[i] == ']' || ('a' <= s[i] && s[i] <= 'z')){
    12.                 stk.push(s.substr(i, 1));
    13.                 i--; // 移到下一个字符
    14.             }
    15.             else{ // 遇到 '['
    16.                 // 取出栈中的所有字符串（除']'）
    17.                 std::string tmp;
    18.                 while(!stk.empty() && stk.top() != "]"){
    19.                     tmp += stk.top();
    20.                     stk.pop();
    21.                 }
    22.                 if(!stk.empty()) stk.pop(); // 弹出 "]"
    23.  
    24.                 i--; // 移到数字位
    25.                 // 处理数字
    26.                 int val = 0, base = 1;
    27.                 while(i >= 0 && s[i] >= '0' && s[i] <= '9'){
    28.                     val += (s[i] - '0') * base;
    29.                     base = base * 10;
    30.                     i--;
    31.                 }
    32.  
    33.                 // 存储字符串到栈中
    34.                 while(val > 0){
    35.                     stk.push(tmp);
    36.                     val--;
    37.                 }
    38.             }
    39.         }
    40.         std::string res;
    41.         // 将栈中的字符串取出
    42.         while(!stk.empty()){
    43.             res += stk.top();
    44.             stk.pop();
    45.         }
    46.         return res;
    47.     }
    48. };
    49.  
    50. int main(int argc, char* argv[]){
    51.     // s = "3[a]2[bc]"
    52.     std::string test = "3[a]2[bc]";
    53.     Solution S1;
    54.     std::string res = S1.decodeString(test);
    55.     std::cout << res << std::endl;
    56.     return 0;
    57. }

    5--除法求值（399）

    主要思路：

            基于带权重的并查集。I think this is a hard question....

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. class Solution {
    7. public:
    8.     int findf(std::vector<int>& f, std::vector<double>& w, int x) { // 引用传递，方便递归更新
    9.         if (f[x] != x) { // 递归查找父亲节点
    10.             int father = findf(f, w, f[x]);
    11.             w[x] = w[x] * w[f[x]]; // 更新权重
    12.             f[x] = father; // 更新父亲节点
    13.         }
    14.         return f[x];
    15.     }
    16.  
    17.     void merge(std::vector<int>& f, std::vector<double>& w, int x, int y, double val) {
    18.         int fx = findf(f, w, x); // 查找父亲节点
    19.         int fy = findf(f, w, y); // 查找父亲节点
    20.         f[fx] = fy; // 对于x节点的父亲节点，其父亲节点设置为y的父亲节点
    21.         w[fx] = val * w[y] / w[x]; // 同时更新权重, x / y = val, 而 y/f[y] = w[y], x / f[x] = w[x] 则 f[x] / f[y] = val * w[y] / w[x]
    22.     } // x / f[y] = val*w[y], x = f[x]*w[x] -> f[x]*w[x] / f[y] = val * w[y] -> f[x] / f[y] = val * w[y] / w[x]
    23.  
    24.     std::vector<double> calcEquation(std::vector>& equations, std::vector<double>& values, std::vector>& queries) {
    25.         // 为每个字符节点记录其对应的id
    26.         int nvars = 0;
    27.         std::unordered_mapint> variables;
    28.         int n = equations.size();
    29.         for (int i = 0; i < n; i++) {
    30.             if (variables.find(equations[i][0]) == variables.end()) {
    31.                 variables[equations[i][0]] = nvars++;
    32.             }
    33.             if (variables.find(equations[i][1]) == variables.end()) {
    34.                 variables[equations[i][1]] = nvars++;
    35.             }
    36.         }
    37.  
    38.         std::vector<int> f(nvars);
    39.         std::vector<double> w(nvars, 1.0);
    40.         for (int i = 0; i < nvars; i++){ // 初始化字符节点的父亲节点
    41.             f[i] = i;
    42.         }
    43.  
    44.         for (int i = 0; i < n; i++) {
    45.             int va = variables[equations[i][0]], vb = variables[equations[i][1]];
    46.             merge(f, w, va, vb, values[i]); // 合并
    47.         }
    48.  
    49.         std::vector<double> ret;
    50.         for (const auto& q: queries) { // 遍历queries
    51.             double result = -1.0;
    52.             if (variables.find(q[0]) != variables.end() && variables.find(q[1]) != variables.end()) { // 同时存在
    53.                 int ia = variables[q[0]], ib = variables[q[1]]; // 取出对应的id
    54.                 int fa = findf(f, w, ia), fb = findf(f, w, ib); // 计算对应的父亲
    55.                 if (fa == fb) { // 具有相同的父亲，表明联通
    56.                     result = w[ia] / w[ib];
    57.                 }
    58.             }
    59.             ret.push_back(result);
    60.         }
    61.         return ret;
    62.     }
    63. };
    64.  
    65. int main(int argc, char* argv[]){
    66.     // equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
    67.     std::vector> equations = {{"a", "b"}, {"b", "c"}};
    68.     std::vector<double> values = {2.0, 3.0};
    69.     std::vector> queries = {{"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
    70.     Solution S1;
    71.     std::vector<double> res = S1.calcEquation(equations, values, queries);
    72.     for(double num : res) std::cout << num << " ";
    73.     std::cout << std::endl;
    74.     return 0;
    75. }

    6--根据身高重建队列（406）

    主要思路：

            对数组按身高从大到小排序，身高相同按k从小到大排序；

            遍历数组，根据k来插入到结果数组中。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vectorint>> reconstructQueue(std::vectorint>>& people) {
    8.         std::sort(people.begin(), people.end(), [](std::vector<int> a, std::vector<int> b){
    9.             if(a[0] == b[0]) return a[1] < b[1];
    10.             return a[0] > b[0];
    11.         });
    12.         std::vectorint>> res;
    13.         for(int i = 0; i < people.size(); i++){
    14.             int pos = people[i][1];
    15.             res.insert(res.begin() + pos, people[i]);
    16.         }
    17.         return res;
    18.     }
    19. };
    20.  
    21. int main(int argc, char* argv[]){
    22.     // people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    23.     std::vectorint>> test = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
    24.     Solution S1;
    25.     std::vectorint>> res = S1.reconstructQueue(test);
    26.     for(auto vec : res){
    27.         for(int num : vec) std::cout << num << " ";
    28.         std::cout << std::endl;
    29.     }
    30.     return 0;
    31. }

    7--分割等和子集（416）

    主要思路：

            转化成0 - 1背包问题，一半的子集和vec作为背包容量，另一半的子集和作为物品，只需判断最后 dp[vec] 是否等于 vec 即可；

            这道题使用 0-1 背包问题的 1 维解法时，需要先正序遍历物品，再倒序遍历背包，防止物品被多次选择（回看背包问题的笔记）。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     bool canPartition(std::vector<int>& nums) {
    8.         int sum = 0;
    9.         for(int i = 0; i < nums.size(); i++){
    10.             sum += nums[i];
    11.         }
    12.         if(sum % 2 != 0) return false;
    13.  
    14.         // 转化为背包问题
    15.         int vec = int(sum / 2); // 背包容量
    16.         std::vector<int> dp(vec+1, 0); // dp[i] 背包容量为i时装的物品价值
    17.         dp[0] = 0; 
    18.         for(int j = 0; j < nums.size(); j++){ // 遍历物品
    19.             for(int i = vec; i >= 0; i--){ // 遍历背包
    20.                 if(i >= nums[j]){
    21.                     dp[i] = std::max(dp[i - nums[j]] + nums[j], dp[i]); 
    22.                 } 
    23.             }
    24.         }
    25.         if(dp[vec] == vec) return true;
    26.         else return false;
    27.     }
    28. };
    29.  
    30. int main(int argc, char* argv[]){
    31.     // nums = [1, 5, 11, 5]
    32.     std::vector<int> test = {1, 5, 11, 5};
    33.     Solution S1;
    34.     bool res = S1.canPartition(test);
    35.     if(res) std::cout << "true" << std::endl;
    36.     else std::cout << "false" << std::endl;
    37.     return 0;
    38. }

    8--路径总和III（437）

    主要思路：

            经典二叉树深搜，本题需要向下传递每一个节点的加和值（因为每一个节点都可以作为起始节点）。

    1. #include 
    2. #include 
    3.  
    4. struct TreeNode {
    5.     int val;
    6.     TreeNode *left;
    7.     TreeNode *right;
    8.     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    9.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    10.     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    11. };
    12.  
    13. class Solution {
    14. public:
    15.     int pathSum(TreeNode* root, int targetSum) {
    16.         int res = 0, num = 0; // 结果
    17.         dfs(root, targetSum, {}, res);
    18.         return res;
    19.     }
    20.  
    21.     void dfs(TreeNode* root, int targetSum, std::vector<long long> sum, int& res){
    22.         if(root == nullptr) return;
    23.         for(long long& num : sum) {
    24.             if(num + root->val == targetSum){ // 上面的节点作为起始节点，以当前节点作为终点，匹配成功
    25.                 res++; // 结果+1
    26.             }
    27.             num += root->val; // 更新路径和：加上当前节点
    28.         }
    29.         if(root->val == targetSum) res++; // 判断单个当前节点是否匹配
    30.         sum.push_back(root->val); // 更新路径和（当前节点可以作为新的起始节点）
    31.         dfs(root->left, targetSum, sum, res); // 深搜
    32.         dfs(root->right, targetSum, sum, res);
    33.         return;
    34.     }
    35. };
    36.  
    37. int main(int argc, char* argv[]){
    38.     // root = [10, 5, -3, 3, 2, null, 11, 3, -2, null, 1], targetSum = 8
    39.     TreeNode *Node1 = new TreeNode(10);
    40.     TreeNode *Node2 = new TreeNode(5);
    41.     TreeNode *Node3 = new TreeNode(-3);
    42.     TreeNode *Node4 = new TreeNode(3);
    43.     TreeNode *Node5 = new TreeNode(2);
    44.     TreeNode *Node6 = new TreeNode(11);
    45.     TreeNode *Node7 = new TreeNode(3);
    46.     TreeNode *Node8 = new TreeNode(-2);
    47.     TreeNode *Node9 = new TreeNode(1);
    48.  
    49.     Node1->left = Node2;
    50.     Node1->right = Node3;
    51.     Node2->left = Node4;
    52.     Node2->right = Node5;
    53.     Node3->right = Node6;
    54.     Node4->left = Node7;
    55.     Node4->right = Node8;
    56.     Node5->right = Node9;
    57.     
    58.     int targetSum = 8;
    59.  
    60.     Solution S1;
    61.     int res = S1.pathSum(Node1, targetSum);
    62.     std::cout << res << std::endl;
    63.  
    64.     return 0;
    65. }

    9--找到字符串中所有字母异位词（438）

    主要思路：

            基于滑动窗口，判断s串滑动窗口的元素是否与p串匹配；

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.  
    7.     bool check(std::vector<int> cnts, std::vector<int> cntp){
    8.         for(int i = 0; i < 26; i++){
    9.             if(cnts[i] != cntp[i]) return false;
    10.         }
    11.         return true;
    12.     }
    13.  
    14.     std::vector<int> findAnagrams(std::string s, std::string p) {
    15.         // 基于滑动窗口
    16.         // 先统计p串各字符出现的次数
    17.         std::vector<int> cntp(26);
    18.         for(int i = 0; i < p.length(); i++){
    19.             cntp[p[i] - 'a']++;
    20.         }
    21.  
    22.         // 初始化s串第一个滑动窗口各字符出现的次数
    23.         std::vector<int> cnts(26);
    24.         for(int i = 0; i < std::min(p.length(), s.length()); i++){ // s串可能会小于p串
    25.             cnts[s[i] - 'a']++;
    26.         }
    27.  
    28.         std::vector<int> res;
    29.         if(check(cnts, cntp)) res.push_back(0); // 判断第一个窗口是否合法
    30.  
    31.         for(int r = p.length(); r < s.length(); r++){ // 枚举右边界
    32.             int l = r - p.length() + 1; // 当前窗口左边界
    33.             cnts[s[l-1] - 'a']--; // 移除上一个窗口左边界元素
    34.             cnts[s[r] - 'a']++; // 移入右边界元素
    35.             if(check(cnts, cntp)) res.push_back(l); // 匹配，记录当前窗口的左边界索引
    36.         }
    37.         return res;
    38.     }
    39. };
    40.  
    41. int main(int argc, char* argv[]){
    42.     // s = "cbaebabacd", p = "abc"
    43.     std::string s = "cbaebabacd";
    44.     std::string p = "abc";
    45.     Solution S1;
    46.     std::vector<int> res = S1.findAnagrams(s, p);
    47.     for(int num : res) std::cout << num << " ";
    48.     std::cout << std::endl; 
    49.     return 0;
    50. }

    10--找到所有数组中消失的数字（448）

    主要思路：

            原地修改数组，遍历数组，根据数组的值修改对应原数组索引的值，具体对应关系是 1对应坐标0，2对应坐标1；修改数组时，将对应坐标的值加上 nums.size()，最后只需判断哪个坐标的值 <= nums.size()，就可以知道哪些值没有出现过。

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     std::vector<int> findDisappearedNumbers(std::vector<int>& nums) {
    7.         std::vector<int> res;
    8.         for(int i = 0; i < nums.size(); i++){
    9.             int pos = (nums[i] - 1) % nums.size();
    10.             nums[pos] += nums.size();
    11.         }
    12.         for(int i = 0; i < nums.size(); i++){
    13.             if (nums[i] <= nums.size()) res.push_back(i+1);
    14.         }
    15.         return res;
    16.     }
    17. };
    18.  
    19. int main(int argc, char* argv[]){
    20.     // nums = [4, 3, 2, 7, 8, 2, 3, 1]
    21.     std::vector<int> test = {4, 3, 2, 7, 8, 2, 3, 1};
    22.     Solution S1;
    23.     std::vector<int> res = S1.findDisappearedNumbers(test);
    24.     for(int num : res) std::cout << num << " ";
    25.     std::cout << std::endl;
    26.     return 0;
    27. }

  • 相关阅读:
    如何在 ELEMENTOR 中创建、编辑和设置列样式
    基于权限控制的Kubernetes容器远程连接方法
    [附源码]计算机毕业设计基于springboot在线影院系统
    2022第五空间WEB&MISC
    英语——分享篇——每日200词——2601-2800
    opencv-python 印刷质量缺陷的视觉检测
    17 OpenCv Canny算子
    java基于springboot+vue+elementui的会员制在线读书图书购物管理平台
    ELK日志分析系统
    翻译软件排行榜-免费翻译软件排行榜-翻译软件推荐排行榜
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/134075395