Leetcode刷题笔记--Hot31-40

1--颜色分类（75）

主要思路：

快排

#include <iostream>
#include <vector>class Solution {
public:void sortColors(std::vector<int>& nums) {quicksort(nums, 0, nums.size()-1);}void quicksort(std::vector<int>& nums, int left, int right){if(left >= right) return;int pivot = nums[left];int l = left, r = right;while(l < r){while(l < r && nums[r] >= pivot) r--;nums[l] = nums[r];while(l < r && nums[l] <= pivot) l++;nums[r] = nums[l];}nums[l] = pivot;quicksort(nums, left, l-1);quicksort(nums, l+1, right);}
};int main(int argc, char *argv[]){// nums = [2,0,2,1,1,0]std::vector<int> test = {2, 0, 2, 1, 1, 0};Solution S1;S1.sortColors(test);for(auto item : test){std::cout << item << " ";}return 0;
}

主要思路：

#include <iostream>
#include <vector>class Solution {
public:void sortColors(std::vector<int>& nums) {int n = nums.size();int p0 = 0, p2 = n - 1;for (int i = 0; i <= p2; ++i) {while (i <= p2 && nums[i] == 2) {std::swap(nums[i], nums[p2]);--p2;}if (nums[i] == 0) {std::swap(nums[i], nums[p0]);++p0;}}}
};int main(int argc, char *argv[]){// nums = [2,0,2,1,1,0]std::vector<int> test = {2, 0, 2, 1, 1, 0};Solution S1;S1.sortColors(test);for(auto item : test){std::cout << item << " ";}return 0;
}

2--最小覆盖子串（76）

主要思路：

参考思路：视频讲解

#include <iostream>
#include <string>
#include <unordered_map>class Solution {
public:std::unordered_map<char, int> t_map;std::unordered_map<char, int> min_map;
public:std::string minWindow(std::string s, std::string t) {if(s.length() < t.length()) return "";for(int i = 0; i < t.length(); i++){if(t_map.find(t[i]) == t_map.end()) t_map[t[i]] = 1;else t_map[t[i]] += 1; }int l = 0, r = 0;int min_l = 0, min_len = s.length() + 1;while(r < s.length()){if(min_map.find(s[r]) == min_map.end()) min_map[s[r]] = 1;else min_map[s[r]] += 1;while(check()){if(r - l + 1 < min_len){min_l = l;min_len = r - l + 1;}min_map[s[l]]--;l++; // 左指针右移}r++;}return min_len == s.length() + 1 ? "" : s.substr(min_l, min_len);}bool check(){if(t_map.size() > min_map.size()) return false;for(auto kv : t_map){char key = kv.first;int value = kv.second;if(min_map.find(key) == min_map.end() || min_map[key] < t_map[key]){return false;}}return true;}
};int main(int argc, char *argv[]){// s = "ADOBECODEBANC", t = "ABC"std::string s = "ADOBECODEBANC";std::string t = "ABC";Solution S1;std::string res = S1.minWindow(s, t);std::cout << res << std::endl;return 0;
}

3--子集（78）

主要思路：

整体思路有点类似全排列，对于数组中的元素，加入（递归）或不加入（回溯）到记录数组中；

不同于全排列的是，本题 dfs 的时候不需要重头遍历所有元素，整个加入过程是前向的；

#include <iostream>
#include <vector>class Solution {
public:std::vector<std::vector<int>> subsets(std::vector<int>& nums) {std::vector<int> tmp;res.push_back(tmp); // []dfs(nums, 0, tmp);return res;}void dfs(std::vector<int>& nums, int idx, std::vector<int>& tmp){if(idx == nums.size()) {return;}tmp.push_back(nums[idx]); // 加入当前的值res.push_back(tmp);dfs(nums, idx+1, tmp);tmp.pop_back(); // 回溯剔出当前加入的值dfs(nums, idx+1, tmp);return;   }
private:std::vector<std::vector<int>> res;
};int main(int arc, char *argv[]){std::vector<int> test = {1, 2, 3};Solution S1;std::vector<std::vector<int>> res = S1.subsets(test);for(auto v : res){std::cout << "[";for(int item : v){std::cout << item << " ";}std::cout << "]" << std::endl;}return 0;
}

4--单词搜索（79）

主要思路：

递归+回溯，遍历从board[i][j]出发，能否匹配给定的字符串；

需要使用一个记录数组来标记当前 board[i][j] 是否被访问，回溯时还原访问状态；

#include <iostream>
#include <vector>
#include <string>class Solution {
public:bool exist(std::vector<std::vector<char>>& board, std::string word) {int m = board.size(), n = board[0].size();std::vector<std::vector<bool>> vis(m, std::vector<bool>(n, false));bool res;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){res = dfs(i, j, 0, board, word, vis);if(res) return true;}}return false;}bool dfs(int i, int j, int cur, std::vector<std::vector<char>>& board, std::string word, std::vector<std::vector<bool>>& vis){if(cur == word.length()) return true;if(i >= board.size() || j >= board[0].size() || i < 0 || j < 0 || board[i][j] != word[cur] || vis[i][j] == true){return false;}vis[i][j] = true;bool res = dfs(i+1, j, cur+1, board, word, vis) || dfs(i, j+1, cur+1, board, word, vis)|| dfs(i-1, j, cur+1, board, word, vis) || dfs(i, j-1, cur+1, board, word, vis);vis[i][j] = false; // 回溯return res;}
};int main(int arc, char *argv[]){// board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]// word = "ABCCED"std::vector<std::vector<char>> board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};std::string word = "ABCCED";Solution S1;bool res = S1.exist(board, word);if(res) std::cout << "true" << std::endl;else std::cout << "false" << std::endl;return 0;
}