LeetCode刷题总结50~100

53. Maximum Subarray

分治法思路：

if 满足条件
	 递归出口
递归计算左边最大和
递归计算右边最大和
判断返回最大和

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 20.10
        int ans=getMaxSubArray(nums,0,nums.size()-1);
        return ans;
    }
    int getMaxSubArray(vector<int> nums,int left,int right){
        int maxsum=0;
        if(left==right){
            maxsum=nums[left];
        }
        else{
            int mid=(left+right)/2,i=mid,j=mid+1;;
            int leftMaxSum=getMaxSubArray(nums,left,mid);
            int rightMaxSum=getMaxSubArray(nums,mid+1,right);
            int lsum=0,rsum=0;
            int max1=-99,max2=-99;
            while(i>=left){
                lsum+=nums[i];
                
                if(lsum>=max1)
                    max1=lsum;
                
                i--;
            }
            while(j<=right){
				rsum+=nums[j];
            	if(rsum>=max2)
                    max2=rsum;
				j++;
			}
            maxsum=max1+max2;
            if(maxsum<=leftMaxSum)
                maxsum=leftMaxSum;
            if(maxsum<=rightMaxSum)
                maxsum=rightMaxSum;           
        }
        return maxsum;
    }
};

dp版本：
该版本有个问题，当nums={-1}时，dp中加入nums[0]的两个方式中，**只有下面那种方式是正确的。**为什么？
回答：
方式一相当于在末尾添加，由于vector 在初始化时已经指明了数组大小，因而默认数组大小空间内全为0，在数组最后在另外加上-1，此时前面已经存在0了，因而第一种方法返回错误的0；
方式二是正确的写法。
注意，vector可以不初始化内存大小，此时当做vector来用可以，但若是使用数组赋值的方式，则会越界，例如：

vector<int>dp
for(int i=1;i<nums.size();i++){
            dp[i]=dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
        };

int maxSubArray(vector<int> nums) {
	   vector<int>dp(nums.size());
       // dp.push_back(nums[0]);
       dp[0]=nums[0];   // 此处不能理解
        for(int i=1;i<nums.size();i++){
            dp[i]=dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
        }
		sort(dp.begin(),dp.end());
		return dp[dp.size()-1];
}

54. Spiral Matrix

Approach 1: Simulation
Intuition

Draw the path that the spiral makes. We know that the path should turn clockwise whenever it would go out of bounds or into a cell that was previously visited.

Algorithm

Let the array have R rows and C columns.seen[r][c]denotes that the cell on ther-th row andc-th column was previously visited. Our current position is (r, c), facing direction di, and we want to visit R * Ctotal cells.

As we move through the matrix, our candidate next position is (cr, cc). If the candidate is in the bounds of the matrix and unseen, then it becomes our next position; otherwise, our next position is the one after performing a clockwise turn.

注意下标的巧妙使用
通过控制双指针，顺时针遍历整个二维矩阵，记录访问结点，依次加入。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>> matrix) {

         vector<int> ans;
        if(matrix.size()==0)
            return ans;             
        int n=matrix.size(); // 行
        int m=matrix[0].size(); // 列
        int dx[]={0,1,0,-1};  // 右下左上
        int dy[]={1,0,-1,0};
        int x=0,y=0,newx=0,newy=0,di=0;
        for(int i=0;i<n*m;i++){
            ans.push_back(matrix[x][y]);  // add
            matrix[x][y]=-999;
            newx=x+dx[di];
            newy=y+dy[di];
            if(newx>=0&&newx<n&&newy>=0&&newy<m&&matrix[newx][newy]!=-999){
                // update
                x=newx;
                y=newy;
                
            }
            else{
                di=(di+1)%4;
                x=x+dx[di];
                y=y+dy[di];  // 把xy拉回来
            }
            
        }
        return ans;
    }
};

62. Unique Paths

注意此题的特征，首先题目说的是只能向下走和向右走，为典型的dp结构；其次，题目要求找出所有走法的可能性，如果使用dfs会不停的重复计算，时间复杂度爆栈了。
解题方法：dp[i][j]=dp[i-1][j]+dp[i][j-1]

class Solution {
public:
int uniquePaths(int m, int n) {
    //dp[i][j]=dp[i-1][j]+dp[i][j-1];
    int dp[100][100];
    //dp[0][0]=0;
    for(int i=0;i<n;i++)
        dp[i][0]=1;
    for(int i=0;i<m;i++)
        dp[0][i]=1;
    for(int i=1;i<n;i++){
        for(int j=1;j<m;j++){
            dp[i][j]=dp[i-1][j]+dp[i][j-1];
        }
    }
    return dp[n-1][m-1];
}

};

63. Unique Paths II

此题与上一题的区别在于，当第一行和第一列以外的位置出现障碍物时，该位dp[i][j]=0
当第一行和第一列出现障碍物时，后面的点均到达不了。

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        //dp[i][j]=dp[i-1][j]+dp[i][j-1];
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        long dp[100][100];
        int n=obstacleGrid.size();
        int m=obstacleGrid[0].size();
        //dp[0][0]=0;
        for(int i=0;i<n;i++){
            if(obstacleGrid[i][0]==1){
                while(i<n){
                    dp[i][0]=0;
                    i++;
                }
            }
                
            else
                dp[i][0]=1;
        }
            
        for(int i=0;i<m;i++){
            if(obstacleGrid[0][i]==1){
                while(i<m){                  
                    dp[0][i]=0;
                     i++;
                }
                break;
            }
            else
                dp[0][i]=1;
        }
            
        
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                if(obstacleGrid[i][j]==1)
                    dp[i][j]=0;
                else
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[n-1][m-1];
    }
};

74. Search a 2D Matrix

思路：
写一个for循环，对每层遍历，遍历时只需要比较target是否满足
target>=matrix[i][0]&&target<=matrix[i][m-1],若满足则进入该行继续查找，使用#include<algorithm>下的函数find()（vector中并没有实现find函数）
find()使用方法如下：

  vector<int>::iterator res=find(a.begin(),a.end(),待查找值);
  if(res!=a.end())
  	cout<<"查找成功";

另外注意，对于二维vector，有

vector<vector<int>> matrix={};
vector<vector<int>> arr={{}};
cout<<matrix.size()<<matrix.size();   // 前者输出0，后者不规范，无输出
cout<<a.size()<<a[0].size();   // 前者输出1，后者输出0

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
    	if(matrix.size()==0||(matrix.size()==1&&matrix[0].size()==0))
            return false;

        int n=matrix.size();  // 行
        int m=matrix[0].size();  //列
        vector<int>::iterator res;
        for(int i=0;i<n;i++){
            if(target>=matrix[i][0]&&target<=matrix[i][m-1]){
            	 res=find(matrix[i].begin(),matrix[i].end(),target);
              //  if(matrix[i].find(target)!=matrix[i].end())
              	if(res!=matrix[i].end())
                    return true;
                else
                    return false;
            }
		}
        // 全部都查找了，仍然没有
        return false;
    }
};

75. Sort Colors

思路：
此题要求给出一种O(N)的算法，我们使用双指针来调整。具体如下：
定义左指针left用来记录左方位，右指针right用来记录右方位。
当nums[i]==0时，交换i和left的数组值，使得0全部往左靠；
当nums[i]==1时，交换i和right的数组值，使得2全部往右靠，遇到1则不处理。
值得一提的是，我们不应该拘泥于标准的i<a.size()类型的for循环，有时可以巧妙使用数值指针作为循环边界。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0, right = nums.size() - 1; // 定义左右指针
        for (int i = 0; i <= right; i++) {
            // 若碰到0，则往左边交换
            if(nums[i]==0&&i>=left){
                swap(nums[i],nums[left++]);
            }
            else if(nums[i]==2){
                swap(nums[i--],nums[right--]);            
            }
        }
    }
};

77. Combinations

模拟法：
初始化数组为k个全0的数，通过循环不断给值++。分为三种情况：

当到达最后一位则加入结果集合中；
若当前为越过n的界限，则往回退；
不满足以上两种情况，则处于中间集，此时指针往右移，令右边邻位等于左边邻位的值，保证++。

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> temp(k,0);
        int i=0;
        // 初始化为k个全0的数
        while(i>=0){
            // 一进来则++
            temp[i]++;
            if(temp[i]>n)
                i--;  // 超过了则往回退一位
            else if(i==k-1){
                res.push_back(temp);
            }//如果到达末尾则加入
            else{
                i++;
                temp[i]=temp[i-1];
            }
                
        }
        return res;
    }
};

79. Word Search

注意非void型dfs的写法,另外对于访问数组以及深搜的四个方向的设定可以用以下两种方式：

// 方式一
char c = board[i][j];
if (c == word[pos]) {
        board[i][j] = '#';
        if (dfs(board, word, i-1, j, pos+1)) return true;
        if (dfs(board, word, i+1, j, pos+1)) return true;
        if (dfs(board, word, i, j-1, pos+1)) return true;
        if (dfs(board, word, i, j+1, pos+1)) return true;
        board[i][j] = c;
 }
// 方式二
    for(int i=0;i<4;i++){
    	int newx=x+dx[i];
    	int newy=y+dy[i];
    	if(newx>=0&&newx<board.size()&&newy>=0&&newy<board[0].size())
    		if(vis[newx][newy]==0){
    			vis[newx][newy]=1;
    			dfs();
    			vis[newx][newy]=0;
			}
    	
	} 

完整代码如下：

class Solution {
public:
    bool dfs(vector<vector<char>>& board, string word, int i, int j, int pos) {
    if (pos == word.size()) return true;
    if ((i<0) || (i >= board.size()) || (j <0) || (j >= board[i].size())) return false;
    char c = board[i][j];
    if (c == word[pos]) {
        board[i][j] = '#';
        if (dfs(board, word, i-1, j, pos+1)) return true;  // 此处为逻辑或的关系，有一方满足即为true
        if (dfs(board, word, i+1, j, pos+1)) return true;
        if (dfs(board, word, i, j-1, pos+1)) return true;
        if (dfs(board, word, i, j+1, pos+1)) return true;
        board[i][j] = c;
    }
    return false;
}
bool exist(vector<vector<char>>& board, string word) {
    if (board.size() == 0) return false;
    for (int i=0; i<board.size();i++){
        for (int j=0; j<board[i].size(); ++j){
        	if(board[i][j]==word[0]){
        		if (dfs(board, word, i, j, 0))
					return true;
			}
            
        }
    }
    return false;
}
};

80. Remove Duplicates from Sorted Array II

此题比较灵活的一个地方在于有两项重复，我们一层循环即可，定义指针ct用来做结果集数组的下标，对数组遍历的同时用ct更新数组。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int ct=0;
        for(int i=0;i<nums.size();i++){
        //前两个数等于自己，一定不需要变
        // 若第i个数大于前两位，则没有重复，继续等于自身
            if(ct<2||nums[i]>nums[ct-2])
                nums[ct++]=nums[i];
        }
    // for (int n : nums)
    //     if (i < 2 || n > nums[i-2])

    //         nums[i++] = n;  
        
    return ct;
}
};

82. Remove Duplicates from Sorted List II

此类单链表题目较为简单，只需做好模拟，记录下需要操作的结点指针即可。
注意，我们统一添加头结点以方便操作。
其中结构体的写法如下，结构体需要提前申请空间。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * }ListNode;
 */
  ListNode* head1=(ListNode*)malloc(sizeof(ListNode));

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * }ListNode;
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL)
            return head;
        ListNode* head1=(ListNode*)malloc(sizeof(ListNode));
        ListNode* temp=new ListNode(0);
        ListNode* p=new ListNode(0);
        head1->next=head;head=head1;
        p=head->next;
        temp=head;
        while(p->next){
            // 记录下重复点的前一个结点和后一个结点 
            if(p->val==p->next->val){          
                p=p->next;
                while(p->next&&p->val==p->next->val)
                {
                    p=p->next;
                }// 循环结束会停留在最后一个重复位
                if(!p->next){
                    temp->next=NULL;
                    break;
                }
                else{
                    p=p->next;
                    temp->next=p;
                }
            } 
            else{
                 temp=p;  // temp为前一个不重复的数字
                 p=p->next;
            }                      
        }
        return head->next;
    }
};

91. Decode Ways

此题有明显的动态规划的特征，正常状态下dp转移方程如下：
dp[i]=dp[i-1]+dp[i-2]，但注意此处需要判断，判断写的比较繁琐，详情见代码：

class Solution {
public:
    int numDecodings(string s) {
        //long long dp[1000];
        vector<int> dp(s.size()+1);
        dp[0]=1;
        dp[1]=1;  // 第i位,对应s下标i-1
        int len=s.size();
        if(len==0)
            return 0;
        if(s[0]=='0')
            return 0;
        for(int i=2;i<=len;i++){
            int x=(s[i-1]-'0')+(s[i-2]-'0')*10;
            if(x>=11&&x<=26&&x!=20)
                dp[i]=dp[i-1]+dp[i-2];
            if(x==20||x==10)
                dp[i]=dp[i-2];
            if(x>=1&&x<=9)
                dp[i]=dp[i-1];
            if(x>26)
                dp[i]=dp[i-1];
            if(x==0)   
                return 0;
            if(x>26&&x%10==0)
                return 0;
        }
        return dp[len];
    }
};

92. Reverse Linked List II

单链表翻转思路：
由于单链表只存在后指针不存在前指针，导致链表在遍历的过程中只可以往后遍历，不可以往前遍历。因此我们需要额外的申请空间作为指针使用，用来记录关键的结点。
定义指针pre、cur、next，分别指向当前结点前一个、当前结点、当前结点后一个，一次循环，使得当前指针指向前一个指针，更新当前指针往后移动，迭代此过程，最终只需修改前后结点指向即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (head == NULL)
            return NULL;         
        ListNode *q = NULL;
        ListNode *p = head;
        for(int i = 0; i < m - 1; i++)
        {
            q = p;
            p = p->next;
        } //q 记录了要翻转元素的前一位
        
        ListNode *end = p;
        ListNode *pPre = p; //p指向翻转元素的起始位
        p = p->next;
        for(int i = m + 1; i <= n; i++)
        {
            ListNode *pNext = p->next;          
            p->next = pPre;
            pPre = p;
            p = pNext;
        }       
        end->next = p;
        if (q)
            q->next = pPre;
        else
            head = pPre;        
        return head;
    }
};

94. Binary Tree Inorder Traversal

中序遍历思路：

先左子树一直遍历压入栈中
而后取栈顶元素出栈并访问该元素的的右子树，迭代求解

class Solution {
public:
    vector<int> inorderTraversal(TreeNode *root) {
        vector<int> vector;
        stack<TreeNode *> stack;     
        while(!stack.empty() || root)
        {
            if(root)
            {
                stack.push(root);
                root = root->left;
            }
            else
            {
                TreeNode *pNode = stack.top();
                vector.push_back(pNode->val);
                stack.pop();
                root = pNode->right;
            }
        }
        return vector;
    }
};

100. Same Tree

注意此题递归求解的时候，自顶向下递归，遇到叶子结点则返回结果，此时的结果即为最初的结果（不需要再从底部自底向上返回任何数值）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 递归出口
        if (p == NULL && q == NULL) 
            return true;
        if (p == NULL || q == NULL||p->val != q->val) 
            return false;
        //判断左子树是否相同
        bool leftflag=isSameTree(p->left,q->left);
        bool rightflag=isSameTree(p->right,q->right);     
        //判断右子树是否相同
        if(leftflag&&rightflag) // 左右都true，范围true
            return true;
        return false;
    }
};