LeetCode HOT 100 --- 2021/8/4

旧城等待， 2022-09-02 15:48 95阅读 0赞

### 目录 ###

*  最长递增子序列
 *  前K个高频元素
 *  字符串解码
 *  回文子串

# 最长递增子序列 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
方法一：  
  动态规划：设dp\[i\]是以nums\[i\]结尾的最长递增子序列的长度。首先dp\[i\]的最小值肯定是1，接着遍历i左边的元素j，如果nums\[i\]大于nums\[j\]说明在以j结尾的递增子序列的最后可以加上nums\[i\]，即：

if(nums[i] > nums[j]) { 
        dp[i] = max(dp[i], dp[j] + 1);
    }

代码：

class Solution { 
    public:
        int lengthOfLIS(vector<int>& nums) { 
            int n = nums.size();
            vector<int> dp(n);
            int res = 0;
            for(int i = 0; i < n; i++) { 
                dp[i] = 1;
                for(int j = 0; j < i; j++) { 
                    if(nums[i] > nums[j]) { 
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
                res = max(res, dp[i]);
            }
            return res;
        }
    };

方法二：  
  贪心+二分法，参考官方题解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
代码：

class Solution { 
    public:
        int lengthOfLIS(vector<int>& nums) { 
            int len = 1, n = (int)nums.size();
            if (n == 0) { 
                return 0;
            }
            vector<int> d(n + 1, 0);
            d[len] = nums[0];
            for (int i = 1; i < n; ++i) { 
                if (nums[i] > d[len]) { 
                    d[++len] = nums[i];
                } else { 
                    int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                    while (l <= r) { 
                        int mid = (l + r) >> 1;
                        if (d[mid] < nums[i]) { 
                            pos = mid;
                            l = mid + 1;
                        } else { 
                            r = mid - 1;
                        }
                    }
                    d[pos + 1] = nums[i];
                }
            }
            return len;
        }
    };

# 前K个高频元素 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
方法一：  
  暴力求解：利用哈希表保存下每个数出现的个数，然后进行排序输出。  
代码：

class Solution { 
    public:
        struct Compare { 
          bool operator()(const pair<int, int>& x, const pair<int, int>& y) { 
              return x.second > y.second;
          }  
        };
        vector<int> topKFrequent(vector<int>& nums, int k) { 
            vector<int> res;
            map<int, int> mp;
            for(int x : nums) { 
                mp[x]++;
            }
            vector<pair<int, int>> temp(mp.begin(), mp.end());
            sort(temp.begin(), temp.end(), Compare());
            for(int i = 0; i < k; i++) { 
                res.push_back(temp[i].first);
            }
            return res;
        }
    };

方法二：  
  建堆：同样用一个哈希表保存每个数字出现的次数，然后遍历次数数组，如果堆的元素个数小于k，就可以直接插入堆中。如果堆的元素个数等于k，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有k个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。遍历结束后堆中的元素就是答案。  
代码：

class Solution { 
    public:
        static bool cmp(pair<int, int>& m, pair<int, int>& n) { 
            return m.second > n.second;
        }
    
        vector<int> topKFrequent(vector<int>& nums, int k) { 
            unordered_map<int, int> occurrences;
            for (auto& v : nums) { 
                occurrences[v]++;
            }
            // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
            for (auto& [num, count] : occurrences) { 
                if (q.size() == k) { 
                    if (q.top().second < count) { 
                        q.pop();
                        q.emplace(num, count);
                    }
                } else { 
                    q.emplace(num, count);
                }
            }
            vector<int> ret;
            while (!q.empty()) { 
                ret.emplace_back(q.top().first);
                q.pop();
            }
            return ret;
        }
    };

# 字符串解码 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]  
分析：  
  见代码注释。  
代码：

class Solution { 
    public:
        string decodeString(string s) { 
            int n = s.size(), num = 0;
            stack<int> numstack;  //数字栈
            stack<string> stringstack;  //字符串栈
            string res = "";
            string temp = "";
            for(char x : s) { 
                if(x >= '0' && x <= '9') {   //遇到数字直接进数字栈
                    num = num * 10 + x - '0'; //可能连续遇到多个数字，比如32c
                }else if(x == '[') { 
                    numstack.push(num);  //数字遍历结束，如32[ca]
                    num = 0;//归零
                    stringstack.push(temp);  //需要重复的字符串进栈
                    temp.clear();
                }else if((x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z')) { 
                    temp += x;  //保存要重复的字符串
                }else {  //右括号 32[ca]
                    int k = numstack.top();  //弹出要重复的次数
                    numstack.pop();
                    string re = stringstack.top(); //弹出要重复的字符串
                    stringstack.pop();
                    for(int i = 0; i < k; i++) {   //累加重复
                        re += temp; 
                    }
                    temp = re;
                }
            }
            return temp;  //返回
        }
    };

# 回文子串 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
方法一：  
  暴力枚举所有子串。  
代码：

class Solution { 
    public:
        int countSubstrings(string s) { 
            int n = s.size();
            int cnt = 0;
            for(int i = 0; i < n; i++) { 
                for(int j = 1; j <= n - i; j++) { 
                    string str = s.substr(i, j);
                    string re = str;
                    reverse(str.begin(), str.end());
                    if(str == re) { 
                        cnt++;
                    }
                }
            }
            return cnt;
        }
    };

方法二：  
  中心扩展枚举：我们可以枚举回文子串的中心，如acca中cc为中心，aca中c为中心，枚举时每次从中心向两边扩展，然后判断是否是回文字符串。  
代码：

class Solution { 
    public:
        int countSubstrings(string s) { 
            int n = s.size();
            int cnt = 0;
            for(int i = 0; i < n; i++) {   //枚举奇数
                int l = i, r = i;
                while(l >= 0 && r < n && s[l] == s[r]) { 
                    cnt++;
                    l--;
                    r++;
                }
            }
            for(int i = 0; i < n - 1; i++) {   //枚举偶数
                int l = i, r = i + 1;
                if(s[l] != s[r]) { 
                    continue;
                }
                while(l >= 0 && r < n && s[l] == s[r]) { 
                    cnt++;
                    l--;
                    r++;
                }
            }
            return cnt;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/3a70ad9e53f24673939488f4d6582eae.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/888652a0cc9446d2ac040044e239d7db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/c5e04fc9b3f54eb9a10a79cf2f186777.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/a24f55d4188640838e1a81904928874d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20220829/25fe90975d8c4712827b2625c8bf1364.png