第一题：岛屿数量
第一想法：dfs
每一次dfs都是要先从’1’开始出发，向上下左右四个方向不断拓展的过程，直到四个边界都遇到了’0’，那么递归过程结束。
一共递归了几次就是有几座岛屿。
要注意在递归过程中把遍历到的’1’置为0，不然会重复。
class Solution {
public:
int col;
int row;
void dfs(vector<vector<char>>& grid,int x,int y){
grid[x][y]='0';
if(x-1>=0&&grid[x-1][y]=='1'){
grid[x-1][y]='0';
dfs(grid,x-1,y);
}
if(x+1<row&&grid[x+1][y]=='1'){
grid[x+1][y]='0';
dfs(grid,x+1,y);
}
if(y-1>=0&&grid[x][y-1]=='1'){
grid[x][y-1]='0';
dfs(grid,x,y-1);
}
if(y+1<col&&grid[x][y+1]=='1'){
grid[x][y+1]='0';
dfs(grid,x,y+1);
}
}
int numIslands(vector<vector<char>>& grid) {
int res=0;
row=grid.size();
col=grid[0].size();
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j]=='1'){
dfs(grid,i,j);
res++;
}
}
}
return res;
}};
再写的时候俺发现if(x-1>=0&&grid[x-1][y]==‘1’)这里x-1>=0一定要放在前面……是的，if的判断逻辑有先后顺序的
第二题：全排列
全排列问题拆解：
对[1,2,3]进行全排列
交换[1,1] 全排列[2,3]……交换回去，依旧是[1,2,3]（[1,2,3],[1,3,2]）
交换[1,2]全排列[1,3]……([2,1,3],[2,3,1])
交换[1,3]全排列[2,1]……([3,2,1],[3,1,2])
over
其实，全排列这个问题，就是每一位放前面，后面的位数开始全排列。
class Solution{
public:
vector<vector<int>> res;
void ssort(vector<int>&nums,int start,int end){
if(start==end){
res.emplace_back(nums);
return;
}
//重要的循环过程
for(int i=start;i<end;i++){
swap(nums[i],nums[start]);
ssort(nums,start+1,end);
swap(nums[i],nums[start]);
}
}
vector<vector<int>> permute(vector<int>&nums){
int n=nums.size();
ssort(nums,0,n);
return res;
}
};
首先二维数组后要插入一维数组用emplace_back；
其次还记得我们昨天日记说的递归边界吧（传送门link）,左闭右开，返回条件就是start==end
第三题：搜索插入位置
这题是二分搜索+插入
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n=nums.size();
int left=0,right=n-1;
int mid=0;
while(left<=right){
mid=left+(right-left)/2;
if(target<=nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
}
return left;
}
};
再写的时候我发现，只能这样写：
if(target<=nums[mid]){
right=mid-1;
}else{
left=mid+1;
}
return left之前解释过了，因为退出条件是left<=right，left=right+1，这就是插入位置
不能写成if(target<nums[mid])这又是为什么呢？
target==nums[mid]的时候，现在是right=mid-1;
最后退出时候，left就是mid
如果写成了if(target<nums[mid])就是left=mid+1;
左边界朝右边走，而最后return left的时候又没办法退回去。
第四题：买卖股票的最佳时期
股票：低买高卖
class Solution {
public:
int maxProfit(vector<int>& prices) {
int maxx=0;
int minn=100000;
int n=prices.size();
for(int i=0;i<n;i++){
minn=min(prices[i],minn);
maxx=max(maxx,prices[i]-minn);
}
return maxx;
}
};
第五题：爬楼梯
超时bug版：
class Solution{
public:
int climbStairs(int n){
if(n==1||n==0){
return 1;
}
return climbStairs(n-1)+climbStairs(n-2);
}
};
dp过版：
class Solution{
public:
int climbStairs(int n){
vector<int>dp(n+1);
dp[0]=dp[1]=1;
for(int n=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
第六题：不同路径
动态规划，dp[m][n]=dp[m-1][n]+dp[m][n-1]
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>>dp(m+1,vector<int>(n+1));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0&&j==0){
dp[1][1]=1;
}else{
dp[i+1][j+1]=dp[i][j+1]+dp[i+1][j];
}
}
}
return dp[m][n];
}
};
第七题：数组中的第K个最大元素
堆！先利用数组前k个数字构建一个大小为K的小顶堆，继续遍历数组，如果有比堆顶元素大的就替换掉这个堆顶，继续维持小顶堆……到最后这个小顶堆的堆顶就是数组中的第K个最大元素
class Solution{
public:
void adjust(vector<int>&heap,int pos){
int left=2*pos+1,right=2*pos+2;
int minn=pos,n=heap.size();
if(left<n&&heap[left]<heap[minn]){
minn=left;
}
if(right<n&&heap[right]<heap[minn]){
minn=right;
}
if(minn!=pos){
swap(heap[minn],heap[pos]);
adjust(heap,minn);
}
}
void build(vector<int>&heap){
//最后一个根节点计算：size/2-1
for(int i=heap.size()/2-1;i>=0;i--){
adjust(heap,i);
}
}
int findKthLargest(vector<int>& nums, int k) {
vector<int>heap(nums.begin(),nums.begin()+k);//初始化堆
build(heap);//构建小顶堆
for(int i=k;i<nums.size();i++){
if(heap[0]<nums[i]){
heap[0]=nums[i];
adjust(heap,0);//调整小顶堆
}
}
return heap[0];
}
};
第八题：对称二叉树
检查左边的右节点是不是和右边的左节点相等
右边的左节点是不是和左边的右节点相等
递归
class Solution {
public:
bool check(TreeNode *left,TreeNode *right){
if(left==nullptr&&right!=nullptr){
return false;
}
else if(left!=nullptr&&right==nullptr){
return false;
}
else if(left==nullptr&&right==nullptr){
return true;
}else{
//别忘了检查当前节点值是否相等
return left->val==right->val&&check(left->left,right->right)&&check(left->right,right->left);
}
}
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
};
队列来做：
class Solution {
public:
bool check(TreeNode *left,TreeNode *right){
queue<TreeNode*>q;
q.push(left);
q.push(right);
while(!q.empty()){
left=q.front();q.pop();
right=q.front();q.pop();
if(!left&&!right)
continue;
if((!left||!right)||(left->val!=right->val))
return false;
q.push(left->left);
q.push(right->right);
q.push(left->right);
q.push(right->left);
}
return true;
}
bool isSymmetric(TreeNode* root) {
return check(root,root);
}
};