2道easy+10道medium+3道hard，今天都是偏回溯的部分，做的还行吧。
(medium)39. 组合总和
也是一道回溯版题，稍微注意的点就是下一个搜索点依然从当前点pos开始而不是pos+1，位置范围是[pos,n)。代码如下：
class Solution {
public:
void dfs(int now, int res , vector<int> tmp)
{
if(res == cnt)
{
ans.push_back(tmp);
return ;
}
for(int i = now ; i < n ; i++)
{
if(res + num[i] <= cnt)
{
tmp.push_back(num[i]);
dfs(i , res + num[i] , tmp);
tmp.pop_back();
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
cnt = target;
n = candidates.size();
for(int i = 0 ; i < n ; i++)
num.push_back(candidates[i]);
dfs(0 , 0 , {});
return ans;
}
private:
int cnt , n;
vector<int> num;
vector<vector<int>> ans;
};(hard)52. N 皇后 II
简单回溯，每次布放点就判断其行 列 斜角有无即可。代码如下：
class Solution {
public:
//判断斜角
bool isok(int x, int y)
{
if(vis[xie1_x[x][y]][xie1_y[x][y]] || vis2[xie2_x[x][y]][xie2_y[x][y]])
return 0;
return 1;
}
void dfs(int x , int y)
{
if(x < 0 || y < 0 || x >= m || y >= m || row[x] || col[y] || !isok(x , y))
return ;
if(x == m - 1)
{
ans++;
return ;
}
row[x] = 1;
col[y] = 1;
vis[xie1_x[x][y]][xie1_y[x][y]] = 1;
vis2[xie2_x[x][y]][xie2_y[x][y]] = 1;
for(int i = 0 ; i < m ; i++)
{
//下一行放皇后的位置
dfs(x + 1 , i);
}
row[x] = 0;
col[y] = 0;
vis[xie1_x[x][y]][xie1_y[x][y]] = 0;
vis2[xie2_x[x][y]][xie2_y[x][y]] = 0;
}
void pre(int x , int y)
{
//左上角
int minl = min(x , y);
xie1_x[x][y] = x - minl;
xie1_y[x][y] = y - minl;
//右上角
minl = min(x , m - y - 1);
xie2_x[x][y] = x - minl;
xie2_y[x][y] = y + minl;
return ;
}
int totalNQueens(int n) {
ans = 0;
m = n;
for(int i = 0 ; i < m ; i++)
{
for(int j = 0 ; j < m ; j++)
pre(i , j);
}
for(int i = 0 ; i < m ; i++)
dfs(0 , i);
return ans;
}
private:
int ans;
int m;
//vis记录左上角的访问，vi2记录右上角的访问
bool vis[10][10];
bool vis2[10][10];
bool row[10];
bool col[10];
//xie1是左上角的x y坐标，xie2是右上角的。
int xie1_x[10][10];
int xie1_y[10][10];
int xie2_x[10][10];
int xie2_y[10][10];
};(hard)51. N 皇后
顺便把N皇后原题做了，无非就是维护一个tmp表示当下放置情况，上题ans++变为ans.push_back(tmp)。代码如下：
class Solution {
public:
//判断斜角
bool isok(int x, int y)
{
if(vis[xie1_x[x][y]][xie1_y[x][y]] || vis2[xie2_x[x][y]][xie2_y[x][y]])
return 0;
return 1;
}
void dfs(int x , int y)
{
if(x < 0 || y < 0 || x >= m || y >= m || row[x] || col[y] || !isok(x , y))
return ;
if(x == m - 1)
{
tmp[x][y] = 'Q';
ans.push_back(tmp);
tmp[x][y] = '.';
return ;
}
row[x] = 1;
col[y] = 1;
vis[xie1_x[x][y]][xie1_y[x][y]] = 1;
vis2[xie2_x[x][y]][xie2_y[x][y]] = 1;
tmp[x][y] = 'Q';
for(int i = 0 ; i < m ; i++)
{
//下一行放皇后的位置
dfs(x + 1 , i);
}
row[x] = 0;
col[y] = 0;
vis[xie1_x[x][y]][xie1_y[x][y]] = 0;
vis2[xie2_x[x][y]][xie2_y[x][y]] = 0;
tmp[x][y] = '.';
}
void pre(int x , int y)
{
//左上角
int minl = min(x , y);
xie1_x[x][y] = x - minl;
xie1_y[x][y] = y - minl;
//右上角
minl = min(x , m - y - 1);
xie2_x[x][y] = x - minl;
xie2_y[x][y] = y + minl;
return ;
}
vector<vector<string>> solveNQueens(int n) {
m = n;
for(int i = 0 ; i < m ; i++)
{
tmp.push_back({});
for(int j = 0 ; j < m ; j++)
{
pre(i , j);
tmp[i].push_back('.');
}
}
for(int i = 0 ; i < m ; i++)
dfs(0 , i);
return ans;
}
private:
vector<vector<string>> ans;
vector<string> tmp;
int m;
//vis记录左上角的访问，vi2记录右上角的访问
bool vis[10][10];
bool vis2[10][10];
bool row[10];
bool col[10];
//xie1是左上角的x y坐标，xie2是右上角的。
int xie1_x[10][10];
int xie1_y[10][10];
int xie2_x[10][10];
int xie2_y[10][10];
};(medium)22. 括号生成
也是很简单的回溯版题，需要注意的就是当前的左括号数量必须大于等于右括号的数量，这样才合法。代码如下：
class Solution {
public:
void dfs(int l , int r , string s)
{
if(l == m && r == m)
{
ans.push_back(s);
return ;
}
if(l < r)
return ;
if(l < m)
dfs(l + 1 , r , s + '(');
if(r < m)
dfs(l , r + 1 , s + ')');
}
vector<string> generateParenthesis(int n) {
m = n;
dfs(0 , 0 , {});
return ans;
}
private:
int m;
vector<string> ans;
};(medium)79. 单词搜索
做出来900ms+，细想剪枝不知道咋剪，看题解我的做法就是已经剪完枝的了，那就这样吧，代码如下：
class Solution {
public:
bool dfs(int x , int y , int pos , string s , int end)
{
if(x < 0 || y < 0 || x >= m || y >= n || vis[x][y] || tmp[x][y] != s[pos])
return 0;
if(pos == end)
return 1;
vis[x][y] = 1;
for(int i = 0 ; i < 4 ; i++)
{
if(dfs(x + xx[i] , y + yy[i] , pos + 1 , s , end))
{
vis[x][y] = 0;
return 1;
}
}
vis[x][y] = 0;
return 0;
}
bool exist(vector<vector<char>>& board, string word) {
m = board.size();
tmp.resize(m);
vis.resize(m);
n = board[0].size();
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < n ; j++)
{
tmp[i].push_back(board[i][j]);
vis[i].push_back(0);
}
int t = word.length();
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < n ; j++)
{
if(dfs(i , j , 0 , word , t - 1))
return 1;
}
return 0;
}
private:
int m , n;
vector<vector<char>> tmp;
vector<vector<int>> vis;
int xx[4] = {0 , 0 , -1 , 1};
int yy[4] = {1 , -1 , 0 , 0};
};(easy)108. 将有序数组转换为二叉搜索树
一道很简单的二分，每个点mid的左边就是其左子树，右边就是其右子树，一直下去就是了。代码如下：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* dfs(int l, int r)
{
if(l > r)
return NULL;
if(l == r)
{
TreeNode* root = new TreeNode(num[l]);
return root;
}
int mid = (l + r) >> 1;
//二分，左为左子树，右为右子树
TreeNode* root = new TreeNode(num[mid]);
root->left = dfs(l , mid - 1);
root->right = dfs(mid + 1 , r);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int n = nums.size();
num.resize(n);
for(int i = 0 ; i < n ; i++)
num[i] = nums[i];
return dfs(0 , n - 1);
}
private:
vector<int> num;
};(medium)148. 排序链表
忘了归并怎么写，不过看题解也学到了尽量别直接new非永久性使用的指针，而是直接定义，这样内存会自动释放，代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l , ListNode* r)
{
ListNode root;
ListNode* now = &root;
while(l != NULL && r != NULL)
{
if(l->val < r->val)
{
now->next = l;
l = l->next;
}
else
{
now->next = r;
r = r->next;
}
now = now->next;
}
if(l != NULL)
now->next = l;
if(r != NULL)
now->next = r;
now = &root;
return now->next;
}
ListNode* sortList(ListNode* head) {
if(head == NULL || head->next == NULL)
return head;
ListNode* l = head;
ListNode* r = head;
while(r->next != NULL && r->next->next != NULL)
{
l = l->next;
//l每次+1，r每次+2，当r是最后一位/倒数第二位时，l为mid
r = r->next->next;
}
//把0-mid切为一条链，mid+1-end切为第二条链，切完之后r代表第二条链的起点
r = l->next;
l->next = NULL;
//归并
return merge(sortList(head) , sortList(r));
}
};(medium)427. 建立四叉树
题目翻译的是牛魔，byd看题解才看懂，题就是给你一个正方形矩阵，让你判断左上 右上 左下 右下四块是否相等，如果当前root指针的四块的值不等，则root不是叶子节点，值随便取；否则则isLeaf值为1，val取当前四块任意值。代码如下：
/*
// Definition for a QuadTree node.
class Node {
public:
bool val;
bool isLeaf;
Node* topLeft;
Node* topRight;
Node* bottomLeft;
Node* bottomRight;
Node() {
val = false;
isLeaf = false;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
Node(bool _val, bool _isLeaf) {
val = _val;
isLeaf = _isLeaf;
topLeft = NULL;
topRight = NULL;
bottomLeft = NULL;
bottomRight = NULL;
}
Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) {
val = _val;
isLeaf = _isLeaf;
topLeft = _topLeft;
topRight = _topRight;
bottomLeft = _bottomLeft;
bottomRight = _bottomRight;
}
};
*/
class Solution {
public:
bool check(int top , int bottom , int left , int right)
{
int target = tmp[top][left];
for(int i = top ; i <= bottom ; i++)
for(int j = left ; j <= right ; j++)
if(tmp[i][j] != target)
return 0;
return 1;
}
//顺序是上下左右
Node* build(int top , int bottom , int left , int right)
{
Node* root = new Node();
if(check(top , bottom , left , right))
{
root->val = tmp[top][left];
root->isLeaf = 1;
}
else
{
int mid1 = (top + bottom) >> 1;
int mid2 = (left + right) >> 1;
root->isLeaf = 0;
root->val = 1;
root->topLeft = build(top , mid1 , left , mid2);
root->topRight = build(top , mid1 , mid2 + 1 , right);
root->bottomLeft = build(mid1 + 1 , bottom , left , mid2);
root->bottomRight = build(mid1 + 1 , bottom , mid2 + 1 , right);
}
return root;
}
Node* construct(vector<vector<int>>& grid) {
n = grid.size();
tmp.resize(n);
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
tmp[i].push_back(grid[i][j]);
}
return build(0 , n - 1 , 0 , n - 1);
}
private:
int n;
vector<vector<bool>> tmp;
};(hard)23. 合并 K 个升序链表
最开始就单纯归并，但想了想用二分的思路也能做，效率更高，因为每个链表理论只会在合并过程中访问logn次。代码如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l , ListNode* r)
{
ListNode root;
ListNode* ptr = &root;
while(l != NULL && r != NULL)
{
if(l->val < r->val)
{
ptr->next = l;
l = l->next;
}
else
{
ptr->next = r;
r = r->next;
}
ptr = ptr->next;
}
if(l != NULL)
ptr->next = l;
else
ptr->next = r;
return root.next;
}
ListNode* erfen(int l , int r)
{
if(l > r)
return NULL;
if(l == r)
return tmp[l];
int mid = (l + r) >> 1;
return merge(erfen(l , mid) , erfen(mid + 1 , r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
int n = lists.size();
tmp.resize(n);
for(int i = 0 ; i < n ; i++)
{
tmp[i] = lists[i];
}
return erfen(0 , n - 1);
}
private:
vector<ListNode*> tmp;
};(medium)53. 最大子数组和
最开始思路是很简单的递推，代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
maxn.resize(n);
ans = -INT_MAX;
for(int i = n - 1 ; i >= 0 ; i--)
{
maxn[i] = nums[i];
if(i < n - 1)
maxn[i] = max(maxn[i] , nums[i] + maxn[i + 1]);
ans = max(ans , maxn[i]);
}
return ans;
}
private:
//maxn[i]表示自i点起始的最大连续子数组和
vector<int> maxn;
int ans;
};后来发现并不需要维护maxn[n]，每次只调用了maxn[i]和maxn[i+1]，即仅需两个变量。修改代码如下：
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
int sum = 0;
ans = -INT_MAX;
//sum表示经过i点的最大
for(int i = n - 1 ; i >= 0 ; i--)
{
sum = max(sum + nums[i] , nums[i]);
ans = max(ans , sum);
}
return ans;
}
private:
int ans;
};分治代码如下：
class Solution {
public:
//表示在l~r区间中，必须经过mid点的最大连续值
int get(int l , int mid , int r)
{
int ans = maxn[mid];
int sum = 0;
//左区间最大
for(int i = mid ; i >= l ; i--)
{
sum += maxn[i];
ans = max(ans , sum);
}
sum = ans;
//右区间最大
for(int i = mid + 1 ; i <= r ; i++)
{
sum = sum + maxn[i];
ans = max(ans , sum);
}
return ans;
}
int maxx(int a , int b , int c)
{
return max(max(a , b) , c);
}
int getmax(int l , int r)
{
if(l > r)
return -INT_MAX;
if(l == r)
return maxn[l];
int mid = (l + r) >> 1;
int l_max = getmax(l , mid);
int r_max = getmax(mid + 1 , r);
int mid_max = get(l , mid , r);
//l,r区间最大只可能是只经过左区间 只经过右区间 经过中间区间三种情况
return maxx(l_max , mid_max , r_max);
}
int maxSubArray(vector<int>& nums) {
int n = nums.size();
maxn.resize(n);
for(int i = n - 1 ; i >= 0 ; i--)
{
maxn[i] = nums[i];
}
return getmax(0 , n - 1);
}
private:
//maxn[i]表示i点的值
vector<int> maxn;
int ans;
};(medium)918. 环形子数组的最大和
很有趣的一道题。分为两种情况，一种是最大和为单向数组中扫描得到，则和上题相同；另一种是最大和为环形扫描得到，这时候可以发现，正常求环形扫描的值不好求，那我们反向思考，因为是环形扫描得到的最大值，所以剩余未在子数组中的值必为单向扫描一遍中可全部访问完，且结果为所有数组的和-最小连续子数组和，即sum-(nums[i]~nums[j])。当然，最后要特判一下，如果sum=最小连续子数组和，说明全为负数，这时候所得到的0这个值并非是取得的最大和，而是并没有取任何值，这种情况就返回第一种的值了。代码如下：
class Solution {
public:
int maxSubarraySumCircular(vector<int>& nums) {
int cnt;
int n = nums.size();
int maxn = -INT_MAX;
int minl = INT_MAX;
int now_max = 0;
int now_min = 0;
int i = 0;
int sum = 0;
for(cnt = 0 ; cnt < n ; cnt++)
{
sum = sum + nums[i];
now_max = max(now_max + nums[i] , nums[i]);
now_min = min(now_min + nums[i] , nums[i]);
maxn = max(maxn , now_max);
minl = min(minl , now_min);
i = (i + 1) % n;
}
if(sum != minl)
return max(maxn , sum - minl);
else
return maxn;
}
};后面想继续实现我想的拓展为一条长度为2n的链的思路，就想到滑动窗口，长度必须小于等于n`。懒得写了，大致思路是这样。
(easy)35. 搜索插入位置
一道很简单的二分查找板子，代码如下：
class Solution {
public:
void getpos(int l , int r , vector<int>& nums)
{
if(l > r)
return ;
if(l == r)
{
if(target != nums[l])
{
pos = target > nums[l] ? l + 1 : l;
}
else
{
pos = l;
flag = 1;
}
return ;
}
int mid = (l + r) >> 1;
if(nums[mid] == target)
{
pos = mid;
flag = 1;
return ;
}
if(nums[mid] > target)
getpos(l , mid , nums);
else
getpos(mid + 1 , r , nums);
}
int searchInsert(vector<int>& nums, int t) {
target = t;
int n = nums.size();
flag = 0;
getpos(0 , n - 1 , nums);
return pos;
}
private:
int pos , target;
bool flag;
};(medium)74. 搜索二维矩阵
我的想法是转成一维队列即可，代码如下：
class Solution {
public:
bool find(int l , int r , int target)
{
if(l == r)
{
return q[l] == target;
}
int mid = (l + r) >> 1;
if(q[mid] == target)
return 1;
if(q[mid] > target)
return find(l , mid , target);
else
return find(mid + 1 , r , target);
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
for(int i = 0 ; i < m ; i++)
for(int j = 0 ; j < n ; j++)
q.push_back(matrix[i][j]);
return find(0 , m * n - 1 , target);
}
private:
vector<int> q;
};(medium)162. 寻找峰值
虽然乍一看并非递增/递减序列不好用二分，但由于需要找峰值，因此每次就寻找比当前点的值大的区间即可。代码如下：
class Solution {
public:
void find(int l , int r , vector<int>& nums)
{
if(l > r)
return ;
if(l == r)
{
pos = l;
return ;
}
int mid = (l + r) >> 1;
int k1;
if(mid != 0)
k1 = nums[mid - 1];
else
k1 = INT_MIN;
int k2 = nums[mid + 1];
if(nums[mid] > k1 && nums[mid] > k2)
{
pos = mid;
return ;
}
if(nums[mid] < k1)
find(l , mid , nums);
if(nums[mid] < k2)
find(mid + 1 , r , nums);
return ;
}
int findPeakElement(vector<int>& nums) {
int n = nums.size();
find(0 , n - 1 , nums);
return pos;
}
private:
int pos;
};(medium)33. 搜索旋转排序数组
二分版子题，唯一就是需要找到旋转点位置，然后分开进行搜索即可。代码如下：
class Solution {
public:
void find(int l , int r , vector<int>& nums)
{
if(l > r)
return ;
if(l == r)
{
if(nums[l] == num)
cur = l;
return ;
}
int mid = (l + r) >> 1;
if(nums[mid] == num)
{
cur = mid;
return ;
}
find(l , mid , nums);
if(cur == -1)
find(mid + 1 , r , nums);
return ;
}
int search(vector<int>& nums, int target) {
int n = nums.size();
num = target;
cur = -1;
pos = 0;
for(int i = 1 ; i < n ; i++)
{
if(nums[i] < nums[i - 1])
{
pos = i;
break;
}
}
find(0 , pos - 1 , nums);
if(cur == -1)
find(pos , n - 1 , nums);
return cur;
}
private:
int pos;
int cur;
int num;
};