文章目录
【LC刷题】DAY22：491 46 47 332 51 37 491. 非递减子序列 [link](https://leetcode.cn/problems/non-decreasing-subsequences/description/) 46. 全排列 [link](https://leetcode.cn/problems/permutations/description/) 332. 重新安排行程 [link](https://leetcode.cn/problems/reconstruct-itinerary/description/) 51. N 皇后 [link](https://leetcode.cn/problems/n-queens/description/) 37. 解数独 [link](https://leetcode.cn/problems/sudoku-solver/description/)
491. 非递减子序列 link
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex){
if(path.size() > 1){
result.push_back(path);
}
unordered_set<int> uset;
for(int i = startIndex; i < nums.size(); i ++){
if ((!path.empty() && nums[i] < path.back())
|| uset.find(nums[i]) != uset.end()) {
continue;
}
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};
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(used[i] == true) continue;
used[i] = true;
path.push_back(nums[i]);
backtracking(nums, used);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
332. 重新安排行程 link
class Solution {
public:
unordered_map<string,map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result){
if(result.size() == ticketNum + 1){
return true;
}
for(pair<const string, int>& target :targets[result[result.size() - 1]]){
if(target.second > 0){
result.push_back(target.first);
target.second --;
if(backtracking(ticketNum, result)) return true;
result.pop_back();
target.second++;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
vector<string> result;
for(const vector<string>& vec:tickets){
targets[vec[0]][vec[1]] ++;
}
result.push_back("JFK");
backtracking(tickets.size(), result);
return result;
}
};
51. N 皇后 link
class Solution {
public:
vector<vector<string>> result;
void backtracking(int n, int row, vector<string> &chessboard) {
if (row == n) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < n; col++) {
if (isvalid(row, col, chessboard, n)) {
chessboard[row][col] = 'Q';
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
}
bool isvalid(int row, int col, vector<string> &chessboard, int n) {
// 检查列
for (int i = 0; i < row; i++) {
if (chessboard[i][col] == 'Q') {
return false;
}
}
// 检查左上到右下的对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查右上到左下的对角线
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查水平方向的对角线
for (int i = row - 1, k = 1; i >= 0 && col + k < n; i--, k++) {
if (chessboard[i][col + k] == 'Q') {
return false;
}
}
for (int i = row - 1, k = 1; i >= 0 && col - k >= 0; i--, k++) {
if (chessboard[i][col - k] == 'Q') {
return false;
}
}
return true;
}
vector<vector<string>> solveNQueens(int n) {
vector<string> chessboard(n, string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};
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] != '.') continue ;
for(char k = '1'; k <= '9'; k ++){
if(isvalid(i, j, k, board)){
board[i][j] = k;
if(backtracking(board)) 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< 9; i ++){
if(board[row][i] == val){
return false;
}
}
for(int j = 0; j < 9; j ++){
if(board[j][col] == val){
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for(int i = startRow; i < startRow + 3; i ++){
for(int j = startCol; j < startCol+3; j ++){
if(board[i][j] == val){
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
