77.
不重复不复选
class Solution {
public:
vector<vector<int>> results;
vector<int> cur;
void backtrack(int n,int k,int level){
if(cur.size()>=k){
results.push_back(cur);
return;
}
for(int i = level;i<=n;i++){
cur.push_back(i);
backtrack(n,k,i+1);
cur.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
backtrack(n,k,1);
return results;
}
};
class Solution {
public:
vector<vector<string>> results;
bool isQualified(vector<string> &map,int i,int j){
for(int k = 0;k<i;k++){
if(map[k][j] == 'Q') return false;
}
for(int k = 0;k<j;k++){
if(map[i][k] == 'Q') return false;
}
int row = i;
int col1 = j;
int col2 = j;
int n = map.size();
while(row>=1 && col1 >= 1){
//left corner
if(map[row-1][col1-1]=='Q') return false;
row--;
col1--;
}
row = i;
while(row>=1 && col2 < n-1){
//left corner
if(map[row-1][col2+1]=='Q') return false;
row--;
col2++;
}
return true;
}
void backtrack(vector<string> &map,int n,int level){
if(level>=n){
results.push_back(map);
return;
}
for(int i = 0;i<n;i++){
map[level][i] = 'Q';
if(isQualified(map,level,i)){
backtrack(map,n,level+1);
}
map[level][i] = '.';
}
}
vector<vector<string>> solveNQueens(int n) {
//generate map
string s(n,'.');
vector<string> map(n,s);
backtrack(map,n,0);
return results;
}
};
class Solution {
public:
vector<vector<int>> results;
vector<int> cur;
void traverse(vector<int>& nums, int level){
if(level > nums.size()){
return;
}
results.push_back(cur);
int n = nums.size();
for(int i = level;i<n;i++){
cur.push_back(nums[i]);
traverse(nums,i+1);
cur.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
traverse(nums,0);
return results;
}
};
岛屿问题(图论)
DFS和BFS下的衍生问题
要在参数列表里传递visited数组,目的是不走回头路
代码模板
一般是返回void,进行递归遍历。一开始特判越界,然后特判是否走过,之后对于可走的每一个方向进行递归。
练习了dfs模板题,需要注意2个点:
1. 特判的位置
首先判断是否已经找到,如果找到后续操作都不进行,尽早return。
如果越界,也不进行后续,return。
2. 怎么利用visited
这道题是当word pivot的字母和当前走位字母一样是才可以下一步,如果不一样是不visit的,需要换方向或往回退步。退步前要backtrack, 即让visited变为否。
3. 针对这道题,起始位置在每个位置都有可能,所以要遍历所有初始位置。
class Solution {
public:
bool flag=false;
vector<vector<bool>> visited;
void dfs(vector<vector<char>>& board, string word,int row,int col,int pivot){
int m = board.size(),n = board[0].size();
if(flag) return;
if(pivot == word.size()){
flag = true;
return;
}
if(row<0||row>=m||col<0||col>=n){
return;
}
if(visited[row][col]) return;
if(word[pivot]==board[row][col]){
visited[row][col] =true;
dfs(board,word,row,col-1,pivot+1);
dfs(board,word,row,col+1,pivot+1);
dfs(board,word,row+1,col,pivot+1);
dfs(board,word,row-1,col,pivot+1);
visited[row][col] = false;
}
}
bool exist(vector<vector<char>>& board, string word) {
int m = board.size(),n = board[0].size();
visited = vector(m,vector(n,false));
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
dfs(board,word,i,j,0);
if(flag) return flag;
}
}
return flag;
}
};
掌握了traverse路径走法就行,判断palindrome,常规题。
class Solution {
public:
vector<vector<string>> results;
vector<string> cur;
bool isPalindrome(string s){
int start = 0, end = s.size()-1;
while(start<=end){
if(s[start]!=s[end]) return false;
start++;
end--;
}
return true;
}
void traverse(string s){
if(s.size() == 0){
results.push_back(cur);
return;
}
int len = s.size();
for(int i = 0;i<len;i++){
string subs = s.substr(0,i+1);
if(isPalindrome(subs)){
cur.push_back(subs);
traverse(s.substr(i+1,len-i-1));
cur.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
traverse(s);
return results;
}
};
dfs的重点是遍历路径!所以需要防止兜圈的visited,以及要回溯来让同一个位置可以多次走(涵盖在不同的路径中)
class Solution {
public:
int num;
vector<vector<bool>> visited;
void dfs(vector<vector<char>>& grid,int row, int col){
int m = grid.size(), n = grid[0].size();
if(row<0||row>=m||col<0||col>=n) return;
if(visited[row][col]) return;
if(grid[row][col]=='1'){
grid[row][col]='0';
visited[row][col] = true;
dfs(grid,row-1,col);
dfs(grid,row+1,col);
dfs(grid,row,col+1);
dfs(grid,row,col-1);
visited[row][col] = false;
}
}
int numIslands(vector<vector<char>>& grid) {
int m = grid.size(), n = grid[0].size();
visited = vector(m,vector<bool>(n,false));
for(int i = 0;i<m;i++){
for(int j = 0; j<n;j++){
if(grid[i][j]=='1'){
num++;
dfs(grid,i,j);//clear an island
}
}
}
return num;
}
};
dfs遍历所有图节点,判断图结构是否有环
遇到edge 集合,考虑做全图(会有一个节点指向多个节点的情况,以及索引统一方便)
class Solution {
public:
vector<bool> onPath;//记录当前路径情况
vector<bool> visited;//记录所有节点情况
bool hasCycle = false;
//建图的作用是为了索引对齐
vector<vector<int>> buildGraph(int numCourses,vector<vector<int>> &prerequisites){
vector<vector<int>> graph(numCourses);
for(auto edge:prerequisites){
graph[edge[1]].push_back(edge[0]);//考虑一对多的情况
}
return graph;
}
void traverse(vector<vector<int>> &graph, int s){
if(onPath[s]){
hasCycle = true;//若有环
//return;
}
if(visited[s]||hasCycle){
return; //若不合法
}
visited[s] = true;
onPath[s] = true;
for(int t:graph[s]){
traverse(graph,t);
}
onPath[s] = false;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph = buildGraph(numCourses,prerequisites);
visited.resize(numCourses,false);
onPath.resize(numCourses,false);
for(int i = 0;i<numCourses;i++){
traverse(graph,i);
}
return !hasCycle;
}
};
这题特殊情况要搞明白,
bfs后存在1返回-1,不存在则返回0,time 无变动返回0, time 有变动返回time
定义拿出来的时候算visit,所以我们的time要从-1开始计时.
class Solution {
public:
int time=-1;
vector<vector<bool>> visited;
queue<pair<int,int>> que;
void bfs(vector<vector<int>>& grid){
int m = grid.size(),n = grid[0].size();
while(!que.empty()){
int num = que.size();
bool add=false;
for(int i = 0;i<num;i++){
pair<int,int> pos = que.front();
que.pop();
if(visited[pos.first][pos.second]) continue;
if(!add) add = true;
visited[pos.first][pos.second] = true;
grid[pos.first][pos.second] = 2;
if(pos.first>=1&&visited[pos.first-1][pos.second]==false&&grid[pos.first-1][pos.second]==1){
que.push({pos.first-1,pos.second});
// grid[pos.first-1][pos.second]=2;
}
if(pos.first<=m-2&&visited[pos.first+1][pos.second]==false&&grid[pos.first+1][pos.second]==1){
que.push({pos.first+1,pos.second});
// grid[pos.first+1][pos.second]=2;
}
if(pos.second>=1&&visited[pos.first][pos.second-1]==false&&grid[pos.first][pos.second-1]==1){
que.push({pos.first,pos.second-1});
// grid[pos.first][pos.second-1]=2;
}
if(pos.second<=n-2&&visited[pos.first][pos.second+1]==false&&grid[pos.first][pos.second+1]==1){
que.push({pos.first,pos.second+1});
// grid[pos.first][pos.second+1]=2;
}
}
if(add) time++;
}
}
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(),n = grid[0].size();
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(grid[i][j]==2) que.push({i,j});
}
}
// if(que.size()==0) return -1;
visited = vector(m,vector(n,false));
bfs(grid);
// find 1
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(grid[i][j]==1) return -1;
}
}
if(time == -1) return 0;
return time;
}
};
贪心
理解:动归特例,满足一些贪心性质,效率更高,达到线性
class Solution {
public:
int currentMax = 0;
bool canJump(vector<int>& nums) {
for(int i = 0; i< nums.size()-1;i++){
currentMax = max(currentMax,i+nums[i]);
if(currentMax<=i) return false;
}
return currentMax >= (nums.size()-1) ? true : false;
}
};
贪心选择性质:(labuladong)
我们不需要「递归地」计算出所有选择的具体结果然后比较求最值,而只需要做出那个最有「潜力」,看起来最优的选择即可
可行域的扩大,当扩大到超过边界的时候直接叫停。jump计数更新是关键
class Solution {
public:
int end = 0, farest = 0;
int count = 0;
int jump(vector<int>& nums) {
int n = nums.size();
for(int i = 0; i< n-1;i++){
farest = max(farest, nums[i]+i);
if(end == i){
count++;
// reach the margin
end = farest;
}
}
return count;
}
};