DailyPractice.2023.10.22

DailyPractice.2023.10.22

文章目录

• 1.[39. 组合总和]
• 2.[22. 括号生成]
• 3.[79. 单词搜索]
• 4.[131. 分割回文串]

1.[39. 组合总和]

39. 组合总和

class Solution {
public:
vector<vector<int>> res;
vector<int> path;void dfs(vector<int>& candidates,int target,int start,int sum) {if (sum == target) {res.push_back(path);return ;}for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++) {path.push_back(candidates[i]);dfs(candidates,target,i,sum + candidates[i]);path.pop_back();}}vector<vector<int>> combinationSum(vector<int>& candidates, int target) {if (candidates.size() == 0) return res;sort(candidates.begin(),candidates.end());dfs(candidates,target,0,0);return res;}
};

2.[22. 括号生成]

22. 括号生成

class Solution {
public:
vector<string> res;
string path;void process(int open,int close,int n) {if (path.size() == n * 2) {res.push_back(path);return ;}if (open < n) {path.push_back('(');process(open + 1,close,n);path.pop_back();}if (close < open) {path.push_back(')');process(open,close + 1,n);path.pop_back();}}vector<string> generateParenthesis(int n) {if (n == 0) return res;if (n == 1) return {"()"};process(0,0,n);return res;}
};

3.[79. 单词搜索]

class Solution {
public:
int m, n;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
vector<vector<bool>> visited;bool solveHelper(vector<vector<char>>& board, int x, int y, string& word, int idx)  {if (idx == word.size() - 1 && board[x][y] == word[idx]) {return true;}else if(board[x][y]!=word[idx]){return false;}visited[x][y] = true;for (int i = 0; i < 4; i++) {int nx=x+dx[i], ny=y+dy[i];if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]){if(solveHelper(board, nx, ny, word, idx+1)){return true;}}}visited[x][y] = false;return false;}bool exist(vector<vector<char>>& board, string word) {m = board.size(), n=board[0].size();visited = vector<vector<bool>>(m, vector<bool>(n, false));for(int i=0; i<m; i++){for(int j=0; j<n; j++){if(solveHelper(board, i, j, word, 0)){return true;}}}return false;}
};

4.[131. 分割回文串]

131. 分割回文串

class Solution {
public:
vector<vector<string>> res;
string path;void process(string &s,int index) {if (index >= s.size()) {res.push_back(path);return ;}for (int i = index; i < s.size(); i++) {if (isVaild(s,index,i) {string str = s.substr(index,i - index + 1);path.push_back(str);}else {continue;}process(s,i + 1);path.pop_back();}}bool isVaild(string &s,int open,int close) {for (int i = open,j = close; i < j; i ++,j --） {if (s[i] != s[j]) {return false;}}return true;}vector<vector<string>> partition(string s) {if (s.size() == 1) return res;process(s,0);return res;}
};