代碼隨想錄算法訓練營第十三天|n皇后&數獨老經典了-創新互聯
鏈接：https://leetcode.cn/problems/subsets-ii/
那么這道題和上一道題有什么區別呢？
沒什么區別，就是僅僅多了重復元素而已，那怎么搞？
實際上[1,4,4]和[4,1,4]是同一個子集，所以就還要去重
不急，在遞歸的下面加上這句話
while(i+1< nums.size() && vec[vec.size()-1] == nums[i+1]在pop元素之前，如果我們發現要pop的元素和下一個push進來的元素一毛一樣，那么我們就讓i++
class Solution {public:
vector>ans;
vectorvec;
void recursion(vector& nums,int k,int step)
{// 元素收集滿了，記錄當前vec然后return
if(vec.size() == k)
{ans.push_back(vec);
return;
}
for(int i = step;ivec.push_back(nums[i]);
recursion(nums,k,i + 1); // 是取搜下一個元素了
while(i+1< nums.size() && vec[vec.size()-1] == nums[i+1]) i++; // 那么就跳過重復的數據唄
vec.pop_back();
}
}
vector>subsetsWithDup(vector& nums)
{sort(nums.begin(),nums.end());
for(int i = 1; i< nums.size() ;i++)
{vec.clear();
recursion(nums,i,0);
}
//vector>res (ans.begin(),ans.end());
ans.push_back({});
ans.push_back(nums);
return ans;
}
}; 鏈接：https://leetcode.cn/problems/increasing-subsequences/description/
注意，這個題目比較特別
因為要求輸出遞增序列，因此是不可以排序的，而我們之前推崇的辦法
while(i + 1< nums.size() && nums[i+1] == vec[vec.size()-1]) i++;也僅僅在排好序的數組上管用
所以我們需要重新思考去重的方式——set
同時因為題目要求遞增，所以需要在push之前判斷當前元素是不是比vector中的最后一個元素大
class Solution {public:
set>ans;
vectorvec;
void recursion(vector& nums,int k,int step)
{if(vec.size() == k)
{ans.insert(vec);
return;
}
for(int i=step;iif(!vec.empty() && nums[i] >= vec[vec.size()-1] || vec.empty()) // 如果滿足遞增，再把元素給push進來
{vec.push_back(nums[i]);
recursion(nums,k,i + 1);
//while(i + 1< nums.size() && nums[i+1] == vec[vec.size()-1]) i++; // 不能排序這個辦法基本上就死了，所以需要set
vec.pop_back();
}
}
}
vector>findSubsequences(vector& nums) {//sort(nums.begin(),nums.end()); // 注意這個題目是不允許排序的
for(int i=2;i<=nums.size();i++)
{vec.clear();
recursion(nums,i,0);
}
vector>res(ans.begin(),ans.end());
return res;
}
}; 鏈接：https://leetcode.cn/problems/permutations/
確實是需要used數組了，記錄當前哪些元素用過哪些元素沒有用過
值得注意的一點是：used中的索引值需要是當前元素在nums中的索引而不能是當前元素的值，因為當前元素可能是負值···
class Solution {public:
// 想返回全排列最好的辦法就是用數組記重了
vector>res;
vectorvec;
int used[100];
void recurison(vector& nums)
{if(vec.size() == nums.size())
{res.push_back(vec);
return;
}
for(int i = 0;iif(!used[i]) // 最好是記錄索引而不是值，因為值有可能是負的
{vec.push_back(nums[i]);
used[i] = 1;
recurison(nums);
used[i] = 0;
vec.pop_back();
}
}
}
vector>permute(vector& nums) {recurison(nums);
return res;
}
}; 鏈接：https://leetcode.cn/problems/permutations-ii/
加個set去重咯，沒有新意~
class Solution {public:
set>ans;
vectorvec;
int used[100];
void recurison(vector& nums)
{if(vec.size() == nums.size())
{ans.insert(vec);
return;
}
for(int i = 0;iif(!used[i]) // 最好是記錄索引而不是值，因為值有可能是負的
{vec.push_back(nums[i]);
used[i] = 1;
recurison(nums);
used[i] = 0;
vec.pop_back();
}
}
}
vector>permuteUnique(vector& nums) {recurison(nums);
vector>res(ans.begin(),ans.end());
return res;
}
}; 鏈接：https://leetcode.cn/problems/reconstruct-itinerary/
孫哥講的真很好，很細
class Solution {unordered_map>targets;
bool backtracking(int ticketNum, vector& result) {if (result.size() == ticketNum + 1) {return true;
}
for (pair& 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;
}
public:
vectorfindItinerary(vector>& tickets)
{targets.clear();
vectorresult;
for (const vector& vec : tickets)
{targets[vec[0]][vec[1]]++; // 記錄映射關系
}
result.push_back("JFK"); // 起始機場
backtracking(tickets.size(), result);
return result;
}
}; 鏈接：https://leetcode.cn/problems/n-queens/
經典練手題
// 區區n皇后是困難？？？
class Solution {public:
vector>res;
// 首先我們枚舉行，從左到右，看行上的哪個元素可以放置Q
bool check(int n,int row,int column,vector&test)
{// [row,column]
// 若是在row這行有元素，我們就直接return false
for(int i=0;iif(test[i][column] == 'Q') return false;
if(row - i >= 0 && column + iif(test[row - i][column + i] == 'Q') return false;}
if(row - i >= 0 && column - i >=0) {if(test[row - i][column - i] == 'Q') return false;}
}
return true;c
}
void recursion(int n,int step,vector&test) // 直接修改test數組
{// 如果當前枚舉的行數已經超過了n，那么我們直接就記錄當前答案然后return
if(step >n-1)
{res.push_back(test);
return;
}
for(int i=0;iif(check(n,step,i,test)) // 如果當前位置是合法的
{test[step][i] = 'Q';
recursion(n,step + 1,test);
test[step][i] = '.';
}
}
}
vector>solveNQueens(int n) // 此處的n給的是棋盤的大小
{// 首先需要初始化數組，答案是用三維數組裝填的
vectortest(n , string(n,'.')); // 剛開始我們將數組全部都用'.'裝填之
recursion(n,0,test);
return res;
}
}; 經典練手題2，主要看細不細
首先我們考慮如何遞歸的問題：按理說是9*9的方格逐個位置搜索，那用for循環枚舉位置不是有點多余？因為移動挺有規律的，所以我們這里就沒有用兩層for循環去枚舉位置（加上枚舉數字就有三層循環了），我們只要枚舉當前位置需要填入的值就OK了
至于行數和列數，一般都是遞歸到當前行的下一列，只有當前行所有列全都遍歷完畢才會去下一行，根據這個規律就能得到下一次遞歸的位置在哪
還有一個需要注意的點：數獨數組本來就是有值的，并且我們在填充數獨的過程中是不可以改變原來數獨中的值的，因此我們在遞歸的過程中發現當前位置若是有值，就直接遞歸到下一層。并且，從此處回溯是不合理的，所以在遞歸操作的后面直接加上return避免此處回溯進入到后面的for循環，同時也提高了效率
除此之外，我設計了一個check函數，用來判斷在當前位置填入num是否合法——還是為了提高效率，開始的時候我們就得到了不完全的數獨數組，為了避免重復值出現在“同一行”，“同一列”，“同一個3 * 3矩陣”中，我們還要定義三個數組用來記錄“當前行”，“當前列”，“當前的3 * 3矩陣中哪些數字被使用過
最后還有一個需要注意的點：數獨填充完畢后是要return的，但是真的return回來所有被填充的數字又會變成’.'，所以在填充完畢后，我們定義標志位flag為1，并且在回溯的時候加上判斷——只有在標志位不為1的時候才回溯，這樣我們return回來的數組就是完整的
class Solution {public:
int rows[10][10];
int cols[10][10];
int cell[10][10][10];
int flag = 0;
// 首先先遍歷一遍數獨，將其中都是1的位置全都置為1，表示這個元素已經被使用過了
bool check(int row, int col, vector>& board, int num)
{// 若是行中列中包括cell中都沒有出現過這個元素，那么return true
if (rows[row][num]) return false;
if (cols[col][num]) return false;
if (cell[row/3][col/3][num]) return false;
return true;
}
void recursion(vector>& board, int row, int col)
{if (flag) return;
if (col == 9) {col = 0; row += 1; }
if (row == 9 && col == 0) // 已經將數組填充完畢
{flag = 1;
return;
}
if (board[row][col]!='.') {recursion(board, row, col + 1); return; } // 如果當前有元素，直接跳過，并且不允許回溯，直接return
// 你覺得需要用for循環枚舉位置嗎，是不是所有順序都是固定的
for (int num = 1; num<= 9; num++) // num是當前準備填充的元素
{if (check(row, col, board, num))
{ board[row][col] = num + '0';
rows[row][num] = 1; // 第row行的num已經用過了
cols[col][num] = 1; // 第col列的num已經用過了
cell[row/3][col/3][num] = 1;
recursion(board, row, col + 1);
if (flag) return;
board[row][col] = '.';
rows[row][num] = 0; // 第row行的num沒用過
cols[col][num] = 0; // 第col列的num沒用過
cell[row/3][col/3][num] = 0;
}
}
}
void solveSudoku(vector>& board)
{memset(rows, 0, sizeof(rows));
memset(cols, 0, sizeof(cols));
memset(cell, 0, sizeof(cell));
for (int i = 0; i<9; i++)
for (int j = 0; j<9; j++)
{ if (board[i][j] != '.')
{ int num = board[i][j] - '0';
rows[i][num] = 1; // 第i行的num已經用過了
cols[j][num] = 1; // 第j列的num已經用過了;
cell[i/3][j/3][num] = 1;
}
}
recursion(board, 0, 0);
}
}; 你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
新聞標題：代碼隨想錄算法訓練營第十三天|n皇后&數獨老經典了-創新互聯
本文路徑：http://vcdvsql.cn/article14/jjede.html
成都網站建設公司_創新互聯，為您提供網站設計、做網站、電子商務、定制網站、網站設計公司、面包屑導航
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯
- 網站制作是什么？網站制作的主要內容有哪些？ 2022-07-18
- B2B網站制作如何制作好網站內容 2021-09-21
- 成都網站制作怎樣建設一個簡單的網站平臺? 2013-08-10
- 成都網站優化怎樣讓自己的網站排名更加穩定 2017-01-04
- 外賣網站制作怎樣才能贏得用戶的青睞 2013-12-10
- 為什么在建設企業網站的時候要考慮到網站改版的問題？ 2016-11-06
- 單頁營銷型網站制作對于中小型企業有什么優勢 2022-02-15
- 免費網站制作-網站建設安全注意事項 2013-05-20
- 成都企業網站制作需要遵循哪些原則? 2016-12-30
- 網站建設會給企業帶來的潛在利益-成都網站制作 2023-01-31
- 網站制作前為什么要備案？ 2022-06-30
- 記住網站制作這幾個步驟，開發網站不用愁 2021-11-13