鏈接：https://leetcode.cn/problems/subsets-ii/
那么這道題和上一道題有什么區(qū)別呢？
沒什么區(qū)別，就是僅僅多了重復(fù)元素而已，那怎么搞？
實(shí)際上[1,4,4]和[4,1,4]是同一個子集，所以就還要去重
不急，在遞歸的下面加上這句話
重慶分公司
重慶分公司
while(i+1< nums.size() && vec[vec.size()-1] == nums[i+1]在pop元素之前，如果我們發(fā)現(xiàn)要pop的元素和下一個push進(jìn)來的元素一毛一樣，那么我們就讓i++
class Solution {public:
vector>ans;
vectorvec;
void recursion(vector& nums,int k,int step)
{// 元素收集滿了，記錄當(dāng)前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++; // 那么就跳過重復(fù)的數(shù)據(jù)唄
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/
注意，這個題目比較特別
因?yàn)橐筝敵鲞f增序列，因此是不可以排序的，而我們之前推崇的辦法
while(i + 1< nums.size() && nums[i+1] == vec[vec.size()-1]) i++;也僅僅在排好序的數(shù)組上管用
所以我們需要重新思考去重的方式——set
同時因?yàn)轭}目要求遞增，所以需要在push之前判斷當(dāng)前元素是不是比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進(jìn)來
{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/
確實(shí)是需要used數(shù)組了，記錄當(dāng)前哪些元素用過哪些元素沒有用過
值得注意的一點(diǎn)是：used中的索引值需要是當(dāng)前元素在nums中的索引而不能是當(dāng)前元素的值，因?yàn)楫?dāng)前元素可能是負(fù)值···
class Solution {public:
// 想返回全排列最好的辦法就是用數(shù)組記重了
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]) // 最好是記錄索引而不是值，因?yàn)橹涤锌赡苁秦?fù)的
{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]) // 最好是記錄索引而不是值，因?yàn)橹涤锌赡苁秦?fù)的
{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/
孫哥講的真很好，很細(xì)
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 )
{// 記錄到達(dá)機(jī)場是否飛過了
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]]++; // 記錄映射關(guān)系
}
result.push_back("JFK"); // 起始機(jī)場
backtracking(tickets.size(), result);
return result;
}
}; 鏈接：https://leetcode.cn/problems/n-queens/
經(jīng)典練手題
// 區(qū)區(qū)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數(shù)組
{// 如果當(dāng)前枚舉的行數(shù)已經(jīng)超過了n，那么我們直接就記錄當(dāng)前答案然后return
if(step >n-1)
{res.push_back(test);
return;
}
for(int i=0;iif(check(n,step,i,test)) // 如果當(dāng)前位置是合法的
{test[step][i] = 'Q';
recursion(n,step + 1,test);
test[step][i] = '.';
}
}
}
vector>solveNQueens(int n) // 此處的n給的是棋盤的大小
{// 首先需要初始化數(shù)組，答案是用三維數(shù)組裝填的
vectortest(n , string(n,'.')); // 剛開始我們將數(shù)組全部都用'.'裝填之
recursion(n,0,test);
return res;
}
}; 經(jīng)典練手題2，主要看細(xì)不細(xì)
首先我們考慮如何遞歸的問題：按理說是9*9的方格逐個位置搜索，那用for循環(huán)枚舉位置不是有點(diǎn)多余？因?yàn)橐苿油τ幸?guī)律的，所以我們這里就沒有用兩層for循環(huán)去枚舉位置（加上枚舉數(shù)字就有三層循環(huán)了），我們只要枚舉當(dāng)前位置需要填入的值就OK了
至于行數(shù)和列數(shù)，一般都是遞歸到當(dāng)前行的下一列，只有當(dāng)前行所有列全都遍歷完畢才會去下一行，根據(jù)這個規(guī)律就能得到下一次遞歸的位置在哪
還有一個需要注意的點(diǎn)：數(shù)獨(dú)數(shù)組本來就是有值的，并且我們在填充數(shù)獨(dú)的過程中是不可以改變原來數(shù)獨(dú)中的值的，因此我們在遞歸的過程中發(fā)現(xiàn)當(dāng)前位置若是有值，就直接遞歸到下一層。并且，從此處回溯是不合理的，所以在遞歸操作的后面直接加上return避免此處回溯進(jìn)入到后面的for循環(huán)，同時也提高了效率
除此之外，我設(shè)計(jì)了一個check函數(shù)，用來判斷在當(dāng)前位置填入num是否合法——還是為了提高效率，開始的時候我們就得到了不完全的數(shù)獨(dú)數(shù)組，為了避免重復(fù)值出現(xiàn)在“同一行”，“同一列”，“同一個3 * 3矩陣”中，我們還要定義三個數(shù)組用來記錄“當(dāng)前行”，“當(dāng)前列”，“當(dāng)前的3 * 3矩陣中哪些數(shù)字被使用過
最后還有一個需要注意的點(diǎn)：數(shù)獨(dú)填充完畢后是要return的，但是真的return回來所有被填充的數(shù)字又會變成’.'，所以在填充完畢后，我們定義標(biāo)志位flag為1，并且在回溯的時候加上判斷——只有在標(biāo)志位不為1的時候才回溯，這樣我們return回來的數(shù)組就是完整的
class Solution {public:
int rows[10][10];
int cols[10][10];
int cell[10][10][10];
int flag = 0;
// 首先先遍歷一遍數(shù)獨(dú)，將其中都是1的位置全都置為1，表示這個元素已經(jīng)被使用過了
bool check(int row, int col, vector>& board, int num)
{// 若是行中列中包括cell中都沒有出現(xiàn)過這個元素，那么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) // 已經(jīng)將數(shù)組填充完畢
{flag = 1;
return;
}
if (board[row][col]!='.') {recursion(board, row, col + 1); return; } // 如果當(dāng)前有元素，直接跳過，并且不允許回溯，直接return
// 你覺得需要用for循環(huán)枚舉位置嗎，是不是所有順序都是固定的
for (int num = 1; num<= 9; num++) // num是當(dāng)前準(zhǔn)備填充的元素
{if (check(row, col, board, num))
{ board[row][col] = num + '0';
rows[row][num] = 1; // 第row行的num已經(jīng)用過了
cols[col][num] = 1; // 第col列的num已經(jīng)用過了
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已經(jīng)用過了
cols[j][num] = 1; // 第j列的num已經(jīng)用過了;
cell[i/3][j/3][num] = 1;
}
}
recursion(board, 0, 0);
}
}; 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧
