• Leetcode刷题笔记--Hot71--80

    目录

    1--会议室II（253）

    2--完全平方数（279）

    3--移动零（283）

    4--寻找重复数（287）

    5--二叉树的序列化与反序列化（297）

    6--最长递增子序列（300）

    7--删除无效的括号（301）

    8--买卖股票的最佳时机含冷冻期（309）

    9--戳气球（312）

    10--零钱兑换（322）

    1--会议室II（253）

    2--完全平方数（279）

    主要思路：

            完全背包问题，每一个平方数可以选取多次。

            本题的物品组合与顺序无关，对应于组合问题，因此先遍历物品，再遍历背包。

            定义dp[j]表示背包容量为j时，装满背包所需完全平方数的最少数量。

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int numSquares(int n) {
    7.         std::vector<int>dp(n+1, n); // 求最少数量，因此初始化不应该为0
    8.         dp[0] = 0;
    9.         for(int i = 1; i*i <= n; i++){ // 遍历物品
    10.             for(int j = i*i; j <= n; j++){ // 遍历背包
    11.                 dp[j] = std::min(dp[j], dp[j - i*i] + 1); // dp[j]表示不选取物品i*i
    12.             }
    13.         }
    14.         return dp[n];
    15.     }
    16. };
    17.  
    18. int main(int argc, char* argv[]){
    19.     // n = 12
    20.     int test = 12;
    21.     Solution S1;
    22.     int res = S1.numSquares(test);
    23.     std::cout << res << std::endl;
    24.     return 0;
    25. }

    3--移动零（283）

    主要思路：

            本题只是要保持非零元素的相对顺序，没要求保持零元素的相对顺序（卡了很久，没看清楚题意）；

            用双指针算法即可，左指针和右指针初始化为0，左指针指向已处理元素序列的尾部（左指针左边全是非零值），右指针指向待处理元素序列的头部；当右指针遇到非零值，交换左右指针的值即可；

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

    4--寻找重复数（287）

    主要思路：

            对于数组nums，定义cnt[i]表示nums数组中小于等于i的数的数量，假设重复的数是target，则对于[1, target-1]里所有的数满足cnt[i] <= i；对于[target, n]里的所有数满足cnt[i] > i；

            不断二分，直到找到target即可。

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int findDuplicate(std::vector<int>& nums) {
    7.         int left = 1, right = nums.size() - 1;
    8.         int ans;
    9.         while(left <= right){
    10.             int mid = left + (right - left) / 2;
    11.             int count = 0;
    12.             for(int num : nums){
    13.                 if(num <= mid) count++; // 统计小于mid的元素个数
    14.             }
    15.             if(count <= mid){ // 表面mid在目标元素左侧
    16.                 left = mid + 1;
    17.             }
    18.             else{ // mid可能是目标元素，也可能在目标元素右侧
    19.                 right = mid - 1;
    20.                 ans = mid; // 记录目标元素
    21.             }
    22.         }
    23.         return ans;
    24.     }
    25. };
    26.  
    27. int main(int argc, char* argv[]){
    28.     // nums = [1, 3, 4, 2, 2]  001 011 100 010 010 
    29.     std::vector<int> test = {1, 3, 4, 2, 2};
    30.     Solution S1;
    31.     int res = S1.findDuplicate(test);
    32.     std::cout << res << std::endl;
    33.     return 0;
    34. }

    5--二叉树的序列化与反序列化（297）

    主要思路：

            基于层次遍历序列化和反序列化；

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. struct TreeNode {
    7.     int val;
    8.     TreeNode *left;
    9.     TreeNode *right;
    10.     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    11. };
    12.  
    13. class Codec {
    14. public:
    15.     std::string serialize(TreeNode* root) {
    16.         // 层次遍历序列化
    17.         std::queue q;
    18.         std::string res;
    19.         q.push(root);
    20.         while(!q.empty()){
    21.             TreeNode* cur = q.front();
    22.             q.pop();
    23.             if(cur != nullptr){
    24.                 res.append(std::to_string(cur->val) + ',');
    25.                 q.push(cur->left);
    26.                 q.push(cur->right);
    27.             }
    28.             else{
    29.                 res.append("#,"); // 使用"#"表示nullptr
    30.             }
    31.         }
    32.         return res;
    33.     }
    34.  
    35.     TreeNode* deserialize(std::string data){
    36.         if(data[0] == '#') return nullptr;
    37.         std::vector vec;
    38.         std::string tmp = "";
    39.         for(int i = 0; i < data.length(); i++){
    40.             if(data[i] != ','){
    41.                 tmp += data[i];
    42.             }
    43.             else{
    44.                 vec.push_back(tmp);
    45.                 tmp = "";
    46.             }
    47.         }
    48.         // 层次遍历反序列化
    49.         std::queue q;
    50.         TreeNode *root = new TreeNode(std::stoi(vec[0])); // i = 0 作为根节点 
    51.         q.push(root);
    52.         int i = 1; // 从1开始
    53.         while(!q.empty()){
    54.             TreeNode* cur = q.front();
    55.             q.pop();
    56.             if(vec[i] != "#"){ // 重构左孩子
    57.                 TreeNode* left = new TreeNode(std::stoi(vec[i]));
    58.                 cur->left = left;
    59.                 q.push(left);
    60.             }
    61.             i++;
    62.             if(vec[i] != "#"){ // 重构右孩子
    63.                 TreeNode* right = new TreeNode(std::stoi(vec[i]));
    64.                 cur->right = right;
    65.                 q.push(right);
    66.             }
    67.             i++;
    68.         }
    69.         return root;
    70.     }
    71. };
    72.  
    73. int main(int argc, char* argv[]){
    74.     // root = [1, 2, 3, null, null, 4, 5]
    75.     TreeNode *Node1 = new TreeNode(1);
    76.     TreeNode *Node2 = new TreeNode(2);
    77.     TreeNode *Node3 = new TreeNode(3);
    78.     TreeNode *Node4 = new TreeNode(4);
    79.     TreeNode *Node5 = new TreeNode(5);
    80.  
    81.     Node1->left = Node2;
    82.     Node1->right = Node3;
    83.     Node3->left = Node4;
    84.     Node3->right = Node5;
    85.  
    86.     Codec S1;
    87.     std::string test1 = S1.serialize(Node1);
    88.     std::cout << test1 << std::endl;
    89.     TreeNode* res = S1.deserialize(test1);
    90.  
    91.     std::queue q;
    92.     q.push(res);
    93.     while(!q.empty()){
    94.         TreeNode* cur = q.front();
    95.         q.pop();
    96.         if(cur != nullptr){
    97.             std::cout << cur->val << " ";
    98.             q.push(cur->left);
    99.             q.push(cur->right);
    100.         }
    101.         else{ // nullptr
    102.             std::cout << "null" << " ";
    103.         }
    104.     }
    105.     std::cout << std::endl;
    106.     return 0;
    107. }

    6--最长递增子序列（300）

    主要思路：

            dp[i]表示以nums[i]结尾的子序列的最大长度；

            状态转移方程：

            dp[i] = std::max(dp[i], dp[j] + 1) if nums[i] > nums[j] && i > j;

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int lengthOfLIS(std::vector<int>& nums) {
    7.         int res = 1;
    8.         std::vector<int> dp(nums.size(), 1); // dp[i]表示以第i个字符结尾的子序列的最长长度
    9.         for(int i = 1; i < nums.size(); i++){
    10.             for(int j = 0; j <= i; j++){
    11.                 if(nums[i] > nums[j]){
    12.                     dp[i] = std::max(dp[i], dp[j]+1);
    13.                 }
    14.             }
    15.             res = std::max(res, dp[i]);
    16.         }
    17.         return res;
    18.     }
    19. };
    20.  
    21. int main(int argc, char* argv[]){
    22.     // nums = [10, 9, 2, 5, 3, 7, 101, 18]
    23.     std::vector<int> test = {10, 9, 2, 5, 3, 7, 101, 18};
    24.     Solution S1;
    25.     int res = S1.lengthOfLIS(test);
    26.     std::cout << res << std::endl;
    27.     return 0;
    28. }

    7--删除无效的括号（301）

    主要思路：

            基于回溯法，递归删除每一个字符，判断最后的字符串是否合法。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     std::vector removeInvalidParentheses(std::string s) {
    8.         // 首先计算最少需要删除的左括号和右括号个数
    9.         int lmove = 0, rmove = 0;
    10.         for(int i = 0; i < s.length(); i++){
    11.             if(s[i] == '(') lmove++;
    12.             else if(s[i] == ')'){
    13.                 if(lmove > 0) lmove--;
    14.                 else rmove++;
    15.             }
    16.         }
    17.         std::vector res; // 返回结果
    18.         dfs(s, 0, lmove, rmove, res);
    19.         return res;
    20.     }
    21.  
    22.     // 递归回溯
    23.     void dfs(std::string &s, int start, int lmove, int rmove, std::vector& res){
    24.         if(lmove == 0 && rmove == 0){ // 收获结果
    25.             if(isValid(s)){
    26.                 res.push_back(s);
    27.             }
    28.             return;
    29.         }
    30.  
    31.         for(int i = start; i < s.length(); i++){
    32.             if(i != start && s[i] == s[i-1]) continue; // 去重
    33.             // 还需要删除的括号个数小于能删除的字符个数
    34.             if(lmove + rmove > s.length() - i) return; // 提前剪枝
    35.  
    36.             // 删除当前字符
    37.             if(s[i] == '(' && lmove > 0){ // 当前字符是左括号
    38.                 s.erase(i, 1);
    39.                 dfs(s, i, lmove-1, rmove, res); // 删除后，下一次开始还是第cur个字符
    40.                 s.insert(s.begin() + i, '('); // 回溯恢复
    41.             }
    42.             else if(s[i] == ')' && rmove > 0){ // 当前字符是右括号
    43.                 s.erase(i, 1);
    44.                 dfs(s, i, lmove, rmove-1, res);
    45.                 s.insert(s.begin() + i, ')'); // 回溯恢复
    46.             }
    47.         }
    48.     }
    49.  
    50.     // 判断字符串是否有效
    51.     bool isValid(std::string str){
    52.         int left = 0;
    53.         for(int i = 0; i < str.length(); i++){
    54.             if(str[i] == '(') left++;
    55.             else if(str[i] == ')') left--;
    56.             if(left < 0){ // 当某次 left < 0 时，表明当前右括号的个数多于左括号，即 ()())( 的情况
    57.                 return false;
    58.             }
    59.         }
    60.         if(left == 0) return true;
    61.         else return false;
    62.     }
    63. };
    64.  
    65. int main(int argc, char* argv[]){
    66.     // s = "()())()"
    67.     std::string test = "()())()";
    68.     Solution S1;
    69.     std::vector res = S1.removeInvalidParentheses(test);
    70.     for(std::string str : res) std::cout << str << " ";
    71.     std::cout << std::endl;
    72.  
    73.     return 0;
    74. }

    8--买卖股票的最佳时机含冷冻期（309）

    主要思路：

            对于每一天，都有三种状态，处于买入状态，处于卖出状态，处于冷冻期状态。

            定义dp[i][0]表示第 i 天处于买入状态，dp[i][1]处于卖出状态，dp[i][2]处于冷冻期状态。

            初始化dp[0][0] = -prices[0]，dp[0][1] = 0, dp[0][2] = 0;

            状态转移方程：

            dp[i][0] = max(dp[i-1][2] - prices[i], dp[i-1][0]); // 前一天可以是冷冻期，也可以是处于买入状态；

            dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i], dp[i-1][2]); // 前一天可以是卖出状态，也可以是买入状态和冷冻期状态。

            dp[i][2] = dp[i-1][1]; // 前一天只能是卖出状态。 

    1. #include 
    2. #include 
    3.  
    4. class Solution {
    5. public:
    6.     int maxProfit(std::vector<int>& prices) {
    7.         // dp[i][0]买入、dp[i][1]卖出、dp[i][2]冷冻期三种状态
    8.         std::vectorint>> dp(prices.size(), std::vector<int>(3, 0));
    9.         // 初始化
    10.         dp[0][0] = -prices[0];
    11.         dp[0][1] = 0;
    12.         dp[0][2] = 0;
    13.         // 状态转移
    14.         for(int i = 1; i < prices.size(); i++){
    15.             dp[i][0] = std::max(dp[i-1][2] - prices[i], dp[i-1][0]); // dp[i-1][0]表示第i-1天就是买入的状态
    16.             dp[i][1] = std::max(dp[i-1][1], std::max(dp[i-1][0] + prices[i], dp[i-1][2]));
    17.             dp[i][2] = dp[i-1][1];
    18.         }
    19.         return std::max(dp[prices.size() - 1][1], dp[prices.size() - 1][2]);
    20.     }
    21. };
    22.  
    23. int main(int argc, char* argv[]){
    24.     // prices = [1, 2, 3, 0, 2]
    25.     std::vector<int> test = {1, 2, 3, 0, 2};
    26.     Solution S1;
    27.     int res = S1.maxProfit(test);
    28.     std::cout << res << std::endl;
    29.     return 0;
    30. }

    9--戳气球（312）

    主要思路：

            基于动态规划，dp[i][j] 表示戳爆在区间 [i, j] 内所有气球能获得的最大硬币数；

            状态转移方程：dp[i][j] = std::max(dp[i][j], dp[i][k-1] + dp[k+1][j] + a[i-1]*a[k]*a[j+1]);

            k 表示在区间[i, j]中最后戳爆的气球。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int maxCoins(std::vector<int>& nums){
    8.         int n = nums.size();
    9.         std::vector<int> a(n+2); // 在两个边界填充1
    10.         for(int i = 1; i <= n; i++){
    11.             a[i] = nums[i - 1];
    12.         }
    13.         a[0] = a[n + 1] = 1;
    14.  
    15.         // dp[i][j] 表示戳爆在区间[i, j]内所有气球能获得的最大硬币数
    16.         std::vectorint>> dp(nums.size() + 2, std::vector<int>(nums.size() + 2, 0)); 
    17.         for(int i = 1; i <= n; i++){ // 初始化区间长度为1时的最大硬币数
    18.             dp[i][i] = a[i-1] * a[i] * a[i+1];
    19.         }
    20.         for(int len = 2; len <= n; len++){ // 枚举区间长度
    21.             for(int i = 1; i + len - 1 <= n; i++){  // 枚举起点
    22.                 int j = i + len - 1; // 区间终点
    23.                 for(int k = i; k <= j; k++){ // 枚举最后一个戳爆的气球
    24.                     dp[i][j] = std::max(dp[i][j], dp[i][k-1] + dp[k+1][j] + a[i-1]*a[k]*a[j+1]);
    25.                 }
    26.             }
    27.         }
    28.         return dp[1][n];
    29.     }
    30. };
    31.  
    32. int main(int argc, char* argv[]){
    33.     // nums = [3, 1, 5, 8]
    34.     Solution S1;
    35.     std::vector<int> test = {3, 1, 5, 8};
    36.     int res = S1.maxCoins(test);
    37.     std::cout << res << std::endl;
    38.     return 0;
    39. }

    10--零钱兑换（322）

    主要思路：

            经典完全背包问题；本题的结果与顺序无关，属于组合问题，因此先遍历物品，再遍历背包。

    1. #include 
    2. #include 
    3. #include 
    4.  
    5. class Solution {
    6. public:
    7.     int coinChange(std::vector<int>& coins, int amount) {
    8.         std::vector<int> dp(amount+1, INT_MAX);
    9.         dp[0] = 0;
    10.         for(int i = 0; i < coins.size(); i++){ // 遍历物品
    11.             for(int j = coins[i] ; j <= amount; j++){ // 遍历背包
    12.                 if(dp[j - coins[i]] != INT_MAX){ // 确保dp[j-coins[i]]恰好可以由硬币构成
    13.                     dp[j] = std::min(dp[j], dp[j - coins[i]] + 1);
    14.                 }
    15.             }
    16.         }
    17.         if(dp[amount] == INT_MAX) return -1;
    18.         return dp[amount];
    19.     }
    20. };
    21.  
    22. int main(int argc, char* argv[]){
    23.     // coins = [1, 2, 5], amount = 11
    24.     std::vector<int> test = {1, 2, 5};
    25.     int target = 11;
    26.     Solution S1;
    27.     int res = S1.coinChange(test, target);
    28.     std::cout << res << std::endl;
    29.     return 0;
    30. }

  • 相关阅读:
    springcloudalibaba架构(30):Dubbo的使用入门
    Qt窗体边框阴影的绘制
    计算机视觉+人工智能面试笔试总结——卷积网络压缩面试题
    velero 迁移k8s集群资源
    Java类加载机制
    世界杯海信再出圈，三星：“谈不上愉悦”
    10.DesignForSymbols\ExportPadstack
    （离散数学）命题公式的等价
    【JVM技术专题】网络问题分析和故障排查规划指南「实战篇」
    windows服务器热备、负载均衡配置
  • 原文地址：https://blog.csdn.net/weixin_43863869/article/details/133972402