代码随想录算法训练营第1天|704. 二分查找、27. 移除元素
39. 组合总和
题目链接
提交代码
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int> candidates, int index, int sum, int target)
{
if(target < sum) return;
if(target == sum)
{
result.push_back(path);
return;
}
for(int i = index; i < candidates.size() && sum + candidates[i] <= target; i++)
{
path.push_back(candidates[i]);
sum += candidates[i];
backtracking(candidates, i, sum, target);
sum -= candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
backtracking(candidates, 0, 0, target);
return result;
}
};
40. 组合总和II
题目链接
提交代码
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) continue;
sum += candidates[i];
path.push_back(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used);
used[i] = false;
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
result.clear();
path.clear();
vector<bool> used(candidates.size(), false);
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
};
131.分割回文串
题目链接
提交代码
class Solution {
public:
vector<vector<string>> result;
vector<string> path;
bool ispal(string s, int start, int end)
{
for(int i = start, j = end; i < j; i++, j--)
if(s[i] != s[j])
return false;
return true;
}
void backtracking(string s, int index)
{
if(index == s.size())
{
result.push_back(path);
return;
}
for(int i = index; i < s.size(); i++)
{
if(ispal(s, index, i))
{
string substr = s.substr(index, i - index + 1);
path.push_back(substr);
}
else
continue;
backtracking(s, i + 1);
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
backtracking(s, 0);
return result;
}
};
93.复原IP地址
题目链接
提交代码
class Solution {
public:
vector<string> result;
string path;
void backtracking(string s, int index, int count)
{
if(index == s.size() && count == 4)
{
result.push_back(path);
return;
}
if(count >= 4) return;
for(int i = index; i < s.size(); i++)
{
if(isillegal(s, index, i))
continue;
path += s.substr(index, i - index + 1);
if(count < 3) path += ".";
if(count + 1 > 4) continue;
backtracking(s, i + 1, count + 1);
int size = i - index + 1;
if(count < 3) size++;
while(size--) path.pop_back();
}
}
bool isillegal(string s, int left, int right)
{
if(right - left + 1 > 3 || right - left + 1 <= 0) return true;
string substr = s.substr(left, right - left + 1);
vector<int> nums;
for(int i = 0; i < substr.size(); i++)
{
int num = substr[i] - '0';
nums.push_back(num);
}
if(nums[0] == 0 && nums.size() > 1) return true;
int sum = 0;
for(int num:nums)
sum = 10 * sum + num;
if(sum > 255 || sum < 0) return true;
return false;
}
vector<string> restoreIpAddresses(string s) {
int count = 0;
backtracking(s, 0, count);
return result;
}
};
78.子集
题目链接
提交代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> nums, int startIndex, int count)
{
result.push_back(path);
for(int i = startIndex; i < nums.size(); i++)
{
path.push_back(nums[i]);
backtracking(nums, i + 1, count + 1);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
int count = 0;
backtracking(nums, 0, count);
return result;
}
};
90.子集II
题目链接
提交代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> nums, int startIndex, vector<bool>& used)
{
result.push_back(path);
for(int i = startIndex; i < nums.size(); i++)
{
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtracking(nums, 0, used);
return result;
}
};
46.全排列
题目链接
提交代码
class Solution {
public:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int> nums, vector<bool> used)
{
if(path.size() == nums.size())
result.push_back(path);
for(int i = 0; i < nums.size(); i++)
{
if(used[i] == false)
path.push_back(nums[i]);
else
continue;
used[i] = true;
backtracking(nums, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
47全排列II
题目链接
提交代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> nums, vector<bool> used)
{
if(path.size() == nums.size())
{
result.push_back(path);
return;
}
for(int i = 0; i < nums.size(); i++)
{
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) continue;
if(used[i]) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
used[i] = false;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(nums, used);
return result;
}
};
491.递增子序列
题目链接
提交代码
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int> nums, int startIndex)
{
if(path.size() >= 2)
result.push_back(path);
unordered_set<int> set;
for(int i = startIndex; i < nums.size(); i++)
{
if((!path.empty() && nums[i] < path[path.size() - 1]) || set.find(nums[i]) != set.end()) continue;
path.push_back(nums[i]);
set.insert(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
vector<bool> used(nums.size());
backtracking(nums, 0);
return result;
}
};
332.重新安排行程
题目链接
提交代码
class Solution {
public:
vector<string> result;
vector<vector<string>> allResults;
void backtracking(vector<vector<string>>& tickets, vector<bool> used, string end)
{
if(result.size() == tickets.size() + 1)
{
allResults.push_back(result);
return;
}
for(int i = 0; i < tickets.size(); i++)
{
if(used[i] == true) continue;
if(tickets[i][0] == end)
used[i] = true;
else
continue;
result.push_back(tickets[i][1]);
backtracking(tickets, used, tickets[i][1]);
result.pop_back();
}
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
vector<bool> used(tickets.size(), false);
string end = "JFK";
result.push_back(end);
backtracking(tickets, used, end);
return result;
}
};
51.N皇后
题目链接
提交代码
class Solution {
public:
vector<vector<string>> result;
void backtracking(vector<string>& chessboard, int n, int row)
{
if(row == n)
{
result.push_back(chessboard);
return;
}
for(int j = 0; j < n; j++)
{
if(isvalid(chessboard, row, j))
{
chessboard[row][j] = 'Q';
backtracking(chessboard, n , row + 1);
chessboard[row][j] = '.';
}
}
}
bool isvalid(vector<string>& chessboard, int i, int j)
{
int n = chessboard.size();
for(int k = 0; k < chessboard.size(); k++)
if(chessboard[k][j] == 'Q') return false;
for(int curi = i - 1, curj = j - 1; curi >= 0 && curj >= 0; curi--, curj--)
if(chessboard[curi][curj] == 'Q') return false;
for(int curi = i - 1, curj = j + 1; curi >= 0 && curj < n; curi--, curj++)
if(chessboard[curi][curj] == 'Q') return false;
return true;
}
vector<vector<string>> solveNQueens(int n) {
vector<string> chessboard(n, string(n, '.'));
backtracking(chessboard, n, 0);
return result;
}
};
37.解数独
题目链接
提交代码
class Solution {
public:
bool backtracking(vector<vector<char>>& board)
{
for(int i = 0; i < board.size(); i++)
{
for(int j = 0; j < board[0].size(); j++)
{
if(board[i][j] == '.')
{
for(char ch = '1'; ch <= '9'; ch++)
{
if(isValid(i, j, ch, board))
{
board[i][j] = ch;
bool result = backtracking(board);
if(result) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
for(int i = 0; i < board.size(); i++)
if(board[i][col] == val) return false;
for(int j = 0; j < board[0].size(); j++)
if(board[row][j] == val) return false;
int startx = (row / 3) * 3;
int starty = (col / 3) * 3;
int endx = (row / 3 ) * 3 + 3;
int endy = (col / 3 ) * 3 + 3;
for(int i = startx; i < endx; i++)
{
for(int j = starty; j < endy; j++)
{
if(board[i][j] == val)
return false;
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
总结
日期： 2023 年 4 月 11 日
学习时长： 5 h 30 m
难度：
★
\bigstar
★
累计完成题目数量： 76
距离目标还有数量： 224
小结：
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
