leetcode题目思路以及部分解答(二)

怼烎@ 2022-08-10 21:28 205阅读 0赞

又刷了30题了，这速度还不错。因为还有别的东西要复习，所以进度并不快。感觉还是能学到很多新东西的。早知道这个就不用去其他地方刷了。这个难度不高，还可以知道哪些情况没考虑。比其他OJ那种封闭式的好多了。还是进入正题吧。

1.[Rotate Image][]

题目意思:将二维数组旋转顺时针循环90度

这个做过两三次了，但每次还是得重新开始推导。。这次又推导了很久。。不过好在做过，代码也写得比较简洁。

主要思路就是第一层循环按层次深入。第二层把旋转后对应替代的4个位置循环更新。swap就是用来更新用的。做完发现讨论里的最高票代码就是我这样子= = 我好像还写复杂了。自己可以看一看。

class Solution {
    public:
        void rotate(vector<vector<int> > &matrix) {
            int len = matrix.size();
            if( len == 1 ) return ;
            int n = len - 1;
            for( int j = len ,k = 0; j > 1 && k < len/2 ; j -= 2, k ++ ){
                for(int i = 0; i < j -1 ; i++){
                    int temp = swap(matrix[k][k+i],matrix[k+i][n-k]);  //1
                    temp = swap(temp, matrix[n-k][n-k-i]);   //2
                    temp = swap(temp, matrix[n - i - k][k]);   // 3
                    temp = swap(temp, matrix[k][k+i]);  //4
                }
            }   
        }
        int swap(int &a,int &b){
            int temp = b;
            b = a;
            return temp;
        }
    };

2.[Generate Parentheses][]

题目意思:给出n对括号所有合法匹配的情况.

我用递归做的。做的时候突然发现，如果把递归里面的变量全部变为全局的，并且将递归函数用一个函数封装起来并初始化全局变量。栈空间就可以节约不少！对于比较深层次的递归效率也高一些。

class Solution {
    public:
        char mystack[100];       
        vector<string>  answer;
        int deep;
        int flag;
        int maxdeep;
        vector<string> generateParenthesis(int n) {
            memset(mystack,0,sizeof(mystack));
            deep = 0;
            maxdeep = n*2;
            flag = 0;
            DFS();
            return answer;
        }
        void DFS(){
            if( deep == maxdeep){
                if( !flag ){
            		string temp(mystack);
            		answer.push_back(temp);
            	}
            	return;
            } else {
            	if( flag < 0 || flag > maxdeep)  return;  
                deep++;
            
                mystack[deep - 1] = '(';
                flag ++;
                DFS();
            	flag --;
                
                mystack[deep - 1] = ')';
                flag --;
                DFS();
            	flag ++;
            
                deep--;
            }
        }
    };

3.[Permutations][]

题目意思:给出一个数组,求出它所有的全排列.

这一题就是全排。用交换法或者回溯都可以。我就用交换法了。思路网上很多，可以自己去搜。

class Solution {
    public:
        vector<vector<int> > answer;
        unsigned int length;
        unsigned int deep;
        vector<vector<int> > permute(vector<int> &num) {
            length = num.size();
            if ( length == 0 )  return answer;
            deep = 0;
            DFS(num);
            return  answer;
        }
        void DFS(vector<int> &my_num){
            if( deep == length ){
                answer.push_back(my_num);
            }
            for(int i = deep ; i < length ; i++){
                swap(my_num[i], my_num[deep]);
                deep++;
        
                DFS(my_num);
        
                deep--;
                swap(my_num[i], my_num[deep]);
            }
        }
        inline void swap(int &a,int &b){
            int temp = a;
            a = b;
            b = temp;
        }
    };

坑爹。。swap里面的b = temp写成b = a了。。在VC上是对的。。结果提交错了好多次。。

4.[Unique Paths][]

题目意思:从二维数组的左上角(0,0)只能向下,向右走.最后走到最右下角总共有多少种走法.

这个也是直接递归的。和二叉树判断平衡差不多。记录下往右和往下走的路径数，然后递归。为了效率可以用一个二位数组记录递归结果，避免不必要的递归。勉强算是动态规划的题目。。

class Solution {
    public:
        int mymap[101][101];
        int uniquePaths(int m, int n) {
        	memset(mymap,0,sizeof(mymap));
        	return DFS(m,n);
        }
        int DFS(int m,int n){
            if ( m == 1 && n == 1) return 1;
        	if ( !m || !n)  return 0;
        	int right,down;
            if( mymap[m][n - 1] )   right = mymap[m][n - 1];
            else    right = DFS(m, n-1), mymap[m][n - 1] = right;
            if( mymap[m - 1][n] )   down  = mymap[m - 1][n];
            else    down = DFS(m - 1,n), mymap[m - 1][n] = down;
            
        	return right + down;
        }
        
    };

5.[Search a 2D Matrix][]

题目意思:在一个横向排列的顺序二维数组中判断一个数是否存在.

这个就是先在矩阵中纵向二分，再横向二分即可。关键是要注意，纵向二分的时候，如果targe大于当前行的头元素，小于下一行头元素，直接返回。再就是二分完了，start==end的时候记得判断这个元素是否是目标元素。

class Solution {
    public:
    #define RIGHT 0
    #define DOWN 1
        int target;
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            int col = matrix.size();
            if( col == 0 ) return false;
            int row = matrix[0].size();
            if( row == 0 ) return false;
            
            this->target = target;
            int start;
            int end;
            if( col == 1 && row == 1){
                return matrix[0][0] == target;
            } else if(col == 1) {
                start = 0;
                end = row - 1;
                return twopart(start, end, col - 1, matrix, RIGHT);
            } else if(row == 1) {
                start = 0;
                end = col - 1;
                return twopart(start, end, row - 1, matrix, DOWN);
            } else {
                start = 0;
                end = col - 1;
                bool flag = twopart(start, end, 0, matrix, DOWN);
                int in_col = start;
                start = 0;
                end = row - 1;
                return flag || twopart(start, end, in_col, matrix, RIGHT);
            }
        }
        bool twopart(int &start,int &end,int in,vector<vector<int> > &matrix,bool dir){
            if( dir == RIGHT ){
                while( start < end ){
                    int middle = (start + end)/2;
                    if( matrix[in][middle] == target)
                        return true;
                    else if( matrix[in][middle] < target ){
        				if( matrix[in][middle+1] > target){
        					start = middle;
        					return false;
        				}
                        start = middle + 1;
                    } else {
                        end = middle - 1;
                    }            
                }
                return target == matrix[in][start];
            } else {
                while( start < end ){
                    int middle = (start + end)/2;
                    if( matrix[middle][in] == target)
                        return true;
                    else if( matrix[middle][in] < target ){
        				if( matrix[middle+1][in] > target){
        					start = middle;
        					return false;
        				}
                        start = middle + 1;
                    } else {
                        end = middle - 1;
                    }            
                }
                return target == matrix[start][in];
            }
        }
    };

6.[Best Time to Buy and Sell Stock][]

题目意思:给出股票的价格表,只能进行一次买卖,怎么交易利润最大.

这一题是很经典的动态规划的题目。思路就是从后向前，记录最大元素，并将当前元素与最大元素的差记录并保留最大值。

class Solution {
    public:
        int maxProfit(vector<int> &prices) {
            unsigned int length = prices.size();
            if( length == 0 ) return 0;
            int maxPrices = prices[length - 1];
            int answer = 0;
            for(int i = length -1 ; i >= 0 ;i--){
                maxPrices = max(maxPrices, prices[i]);
                answer = max(answer, maxPrices - prices[i]);
            }
            return answer;
        }
        inline int max(int a,int b){
            return (a > b ? a : b);
        }
    };

7.[Binary Tree Level Order Traversal II][]

题目意思: 返回每个层次的节点,并且是从叶子节点层往上,从左往右顺序输出.

这一题开始比较纠结。到底是直接遍历还是弄两个队列一个栈，还是把代码写简单点多一倍的内存操作。考虑面试，所以还是用简洁的方法吧。思路也很简单，就是先序遍历，然后按照层次来插入到对应的行中。最后再反序创建一个结果。

class Solution {
    public:
        vector<vector<int> > answer;
        vector<vector<int> > levelOrderBottom(TreeNode *root) {
            DFS(root, 0);
            return vector<vector<int> > (answer.rbegin(), answer.rend());
        }
        void DFS(TreeNode *root,int level){
            if( root == NULL ) return;
            if( level == answer.size())  answer.resize(level+1);
            
            answer[level].push_back(root->val);
            DFS(root->left, level + 1);
            DFS(root->right, level + 1);
        }
    };

8.[Minimum Path Sum][]

题目意思: 从二维数组的左上角到右下角,找出一条最短路径.只能是向下或向右走

这题属于简单的DP。直接把每个点左边和上边的值比较，然后取一个最小的加到当前节点中。最后直接返回右下角的值即可。

class Solution {
    public:
        int minPathSum(vector<vector<int> > &grid) {
            int col = grid.size();
            if( col == 0)   return -1;
            int row = grid[0].size();
            if( row == 0)   return -1;
            
            
            for(int i = 1 ; i < row ; i++){
                grid[0][i] += grid[0][i - 1];
            }
            for(int j = 1 ; j < col ; j++){
                grid[j][0] += grid[j - 1][0];
            }
            
            for(int i = 1 ; i < col ; i++ ){
                for(int j = 1 ; j < row ;j++ ){
                    grid[i][j] += min(grid[i - 1][j],grid[i][j - 1]);
                }
            }
            return grid[col - 1][row - 1];
        }
        inline int min(int a,int b){
            return a > b ? b : a;
        }
    };

9.[Container With Most Water][]

题目意思: 给出垂直于X轴的线段的最高点,求出这些线段中能装水最多的面积.

这一题没看懂。。。以为是求梯形面积。。百度了下，结果是求梯形中矩形的面积。

这一题最直观的思路就是双循环，但感觉应该没这么简单。。百度了一下，就是从两边往中间靠紧，长度在缩短，所以要保证高要增长。

证明的思路就是设一个最大的C =min(ai,aj)\*(j-i)。证明j是右边最大，i是左边极小，两个指针逐步逼近最优解。讨论里面有具体证明，我就不多说了。

class Solution {
    public:
        int maxArea(vector<int> &height) {
            int start = 0;
            int end = height.size() - 1;
            if( start >= end )  return -1;
            
            int max = 0;
            for(; start < end ;){
                int temp = min(height[start], height[end]) * (end - start);
                if( temp > max )    max = temp;
                if( height[start] > height[end])    end --;
                else start++;
            }
            return max;
        }
        inline int min(int a,int b){
            return a > b ? b : a;
        }
    };

10.[Binary Tree Postorder Traversal][]

题目意思:非递归的后序遍历二叉树.

这题我记得算导上面见过。不过好像没答案。。。我的思路就是先设计一个结构，保存指针和flag。用flag判断当前节点遍历的次数。

typedef struct {
        struct TreeNode * p;
        int flag;
    }my_node;
    
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode *root) {
            vector<int> answer;
            if(root == NULL)    return answer;
            stack<my_node>  for_node;
            my_node temp;
            temp.p = root;
            temp.flag = 0; 
            for_node.push(temp);
            while(!for_node.empty()){
                temp = for_node.top();
                for_node.pop();
                if( temp.flag == 1){
                    temp.flag++;
                    for_node.push(temp);
                    
                    if( !temp.p->right )    continue;
                    
                    temp.p = temp.p->right;
                    temp.flag = 0;
                    for_node.push(temp);
                } else if(temp.flag == 0){
                    temp.flag++;
                    for_node.push(temp);
                    
                    if( !temp.p->left )    continue;
                    
                    temp.p = temp.p->left;
                    temp.flag = 0;
                    for_node.push(temp);
                } else {
                    answer.push_back(temp.p->val);
                }   
            }
            return answer;
        }
    };

11.[Linked List Cycle II][]

题目意思: 给出一个部分循环的链表的循环头,如果不是循环链表返回null

开始感觉就是用两个指针，但半天没想出来。。。思路是看的讨论的。简单来说设置两个指针a,b，a每次走一步，b走两步。假设链表从表头到循环的头结点长度为k。ab相遇时总路程为S,F。相遇点距离表头为x，环剩余路程大小为y。那么

S=k+x

F=k+x+x+y

2S=F

联合解得x = k。讨论里面比较严谨，但我没看懂。。我这就按超一圈来说明了。有点像奥赛题。。。估计我真正要自己做得够想吧。。。

class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if( head == NULL || head->next == NULL)  return NULL;
            ListNode *slow = head->next;
            ListNode *fast = head->next->next;
            while( slow != fast ){
                if( !slow || !fast )    return NULL;
                slow = slow->next;
                fast = fast->next;
                if( fast )  fast = fast->next;
                else    return NULL;
            }
            slow = head;
            while( slow != fast){
                slow = slow->next;
                fast = fast->next;
            }
            return fast;
        }
    };

12.[Spiral Matrix II][]

题目意思:按照顺时针方向,从方阵的外围向内填数.

这道题原来做过两三次。但每次都写的很复杂。。原来的思路是推出需要填充的四边形的边框上4个角的公式，然后按方向顺序填充。。但太麻烦了。这次想了半天，决定直接用坐标。这一下简单了很多。

算法思路：一个n\*n的正方型嵌套多个正方形框，每个正方形边框从左上角按照右，下，左，上的顺序依次填充。并且右下左方向都是循环边框长减一，上方向则是减二。这么一来只用控制边框长和边框层次即可。

class Solution {
    public:
        vector<vector<int> > matrix;
        vector<vector<int> > generateMatrix(int n) {
            if(n == 0)  return matrix;
            
            matrix.resize(n);
            for(int i = 0 ; i < n ;i++) matrix[i].resize(n);
        
            unsigned int cnt = 1;
            int max = n/2;
            if( n & 1 ) matrix[max][max] = n*n;
            int i,j;
        	for(int level = 0 ; level < max ;level ++){
        		i = j = level;
        		matrix[i][j] = cnt++;
        		for(int k = 0 ; k < n-1 ; k++)	matrix[i][++j] = cnt++;
        		for(int k = 0 ; k < n-1 ; k++)	matrix[++i][j] = cnt++;
        		for(int k = 0 ; k < n-1 ; k++)	matrix[i][--j] = cnt++;
        		for(int k = 0 ; k < n-2 ; k++)	matrix[--i][j] = cnt++;
        		n -= 2;
        	}
            return matrix;
        }
    };

13.[Binary Tree Level Order Traversal][]

题目意思:层次遍历,但是返回顺序是从上到下.

这题的思路就是原来写过的反序层次遍历。这个还简单一些。。不知道为什么错误率还高些。。

class Solution {
    public:
        vector<vector<int> > answer;
        vector<vector<int> > levelOrder(TreeNode *root) {
            DFS(root,0);
            return answer;
        }
        void DFS(TreeNode *root, int level){
            if( root == NULL )  return;
            if( level == answer.size()) answer.resize(level+1);
            answer[level].push_back(root->val);
            DFS(root->left, level + 1);
            DFS(root->right, level + 1);
        }
    };

14.[Set Matrix Zeroes][]

题目意思:将一个数组中0元素的行与列都置为0

这一题我记得在哪本书上看到过。主要是不能对存在0的行列过早更新，不然就很容易把错误的地方也清零了。思路就是扫两遍，先记录下有零的行和列，再来清空。

按照题目要求，不准用额外空间。那就只能用数组内的空间了。所以就先把第一行和第一列先遍历，用两个标记量标记，然后扫剩余的矩阵。如果遇到0，那么就用把第一行第一列中的数据清零0。清零的时候先按照非第一行第一列元素清空，然后再把第一行第一列清空即可。我一开始按照的是讨论里面的第一种思路写，写的一般才发现可以这么做。果然还是要开始写才能让好算法出现。。

class Solution {
    public:
        void setZeroes(vector<vector<int> > &matrix) {
            int row = matrix.size();
            if( row == 0 )  return ;
            int col = matrix[0].size();
            if( col == 0 ) return ;
            
            bool firstrow = false;
            bool firstcol = false;
            for(int i = 0 ; i < row ; i++){
                if(matrix[i][0] == 0){
                    firstrow = true;
                    break;
                }
            }
            for(int i = 0 ; i < col ; i++){
                if(matrix[0][i] == 0){
                    firstcol = true;
                    break;
                }
            }
            for(int i = 1; i < row ; i++){
                for(int j = 1 ; j < col ; j++){
                    if(matrix[i][j] == 0){
                        matrix[i][0] = 0;
                        matrix[0][j] = 0;
                    }
                }
            }
            for(int i = 1;i < row ; i++){
                for(int j = 1; j < col ;j++){
                    if( matrix[i][0] == 0 || matrix[0][j] == 0){
                        matrix[i][j] = 0;
                    }
                }
            }
            if(firstrow){
                for(int i = 0 ; i < row ;i++){
                    matrix[i][0] = 0;
                }
            }
            if(firstcol){
                for(int j = 0 ; j < col ;j++){
                    matrix[0][j] = 0;
                }
            }
        }
    };

15.[Search in Rotated Sorted Array II][]

题目意思: 在旋转数组中找到某个数,数组中存在重复元素.

变形的旋转数组。我是先做的下面题，然后改一下就好了，就是改个等号去掉判断即可

class Solution {
    public:
        bool search(int A[], int n, int target) {
            if( A == NULL || n == 0)  return false;
            if( A[0] == target ||  A[n - 1] == target)    return true;
            
            int start = 0;
            int end = n - 1;
                
            while(start < end && A[start] <= A[start + 1]){
                if( A[start] == target)
                    return true;
                start++;
            }
            if( A[start] == target )    return true;
            start++;
            
            while( start <= end ){
                int middle = (start + end)/2;
                int comp = A[middle];
                if( target > comp ){
                    start = middle + 1;
                } else if (target == comp){
                    return true;
                } else {
                    end = middle - 1;
                }
            }
            return false;
                
        }
    };

16.[Search in Rotated Sorted Array][]

题目意思: 无重复的旋转数组.

顺带做了这题算了。就是正常的旋转数组，我的第一个思路就是先扫到最大的一个数i，然后在i+1~i+n之间二分。记得取模就是。

class Solution {
    public:
        int search(int A[], int n, int target) {
            if( A == NULL || n == 0)  return -1;
            if( A[0] == target )    return 0;
            if( A[n - 1] == target )    return n - 1;
            
            int start = 0;
            int end = n - 1;
            if( A[0] > A[n - 1]){
                
                while(start < n - 1 && A[start] < A[start + 1]){
                    if( A[start] == target)
                        return start;
                    start++;
                }
                if( A[start] == target )    return start;
                start++;
            }
            
            while( start <= end ){
                int middle = (start + end)/2;
                int comp = A[middle];
                if( target > comp ){
                    start = middle + 1;
                } else if (target == comp){
                    return middle;
                } else {
                    end = middle - 1;
                }
            }
            return -1;
        }
    };

17.[Pascal's Triangle II][Pascal_s Triangle II]

题目意思:返回杨辉三角的指定行.

本来准备直接用递推公式算出C(n,m)的值，但这题要求说不用额外空间。用组合公式算感觉又容易造成溢出，但也没什么好办法，所以就按公式来看一看了。高中时候就没怎么学明白这个组合公式。不过推一下还是可以的。可以化为(m\*...\*(n+1))/((m-n)\*...1).随着n增加一，相当于\*(m-n+1)/(n).这里的n是加一后的n。所以算法就很明了了。组合公式是对称的，所以还可以简单的优化一下。需要注意的就是

class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> answer;
            if( rowIndex == 0){
                answer.push_back(1);
                return answer;
            }
            answer.resize(rowIndex + 1);
            answer[0] = 1;
            int n = 1;
            int m = rowIndex;
            int max = rowIndex/2;
            while(n <= max){
                answer[n] = (double)answer[n - 1] * (rowIndex - n + 1) / n;
                n++;
            }
            int i;
            if(rowIndex & 1)    i = n - 1;
            else    i = n - 2;
            while(n < rowIndex){
                answer[n] = answer[i];
                n++;
                i--;
            }
            answer[rowIndex] = 1;
            return answer;
        }
    };

18.[Path Sum][]

题目意思:找到从根节点到叶子节点的路径中,和又没有值为sum的.

直接DFS做就好了。要注意的是，这一题必须是到叶子结点的路径为sum才行。做了点优化，只要找到一条路径了就不递归了。

class Solution {
    public:
        bool answer;
        int count;
        bool hasPathSum(TreeNode *root, int sum) {
            if( root == NULL ) return false;
            answer = false;
            count = sum;
            DFS(root, 0);
            return answer;
        }
        void DFS(TreeNode *root, int sum){
            if( root == NULL)   return;
            
            int curcnt = sum + root->val;
            if( root->left == NULL && root->right == NULL && curcnt == count)
                    answer = true;
            if(!answer)   DFS(root->left, curcnt);
            if(!answer)   DFS(root->right, curcnt);
            
        }
    };

19.[Remove Duplicates from Sorted Array II][]

题目意思:取出重复元素,但是重复元素允许出现两次.

做到这里我感觉怎么题目越来越简单。。。还是设置一个变量用于指向最后一个合法的长度。

class Solution {
    public:
        int removeDuplicates(int A[], int n) {
            if( A == NULL || n == 0)  return 0;
            bool flag = false;
            int begin = 1;
            for(int i = 1 ; i < n ; i++ ){
                if(A[i] != A[i - 1]){
                    A[begin++] = A[i];
                    flag = false;
                } else {
                    if( !flag ){
                        flag = true;
                        A[begin++] = A[i];
                    }
                }
            }
            return begin;
        }
    };

20.[Populating Next Right Pointers in Each Node II][]

题目意思: 给出一个任意的二叉树,将其节点,指向其右边的兄弟节点.

做到这里很多思路就很清楚了，直接用DFS得到每个层次的指针。然后再把每个指针连起来。当然你想省空间可以用两个队列循环着连接，但我就图简单这么写算了。。。

用之前的每次遍历的方式也可以，就是每次要保存一个前驱指针和头指针。反正我两个方法交上去，发现时间都是120ms。。。我这里还是贴第一个思路的代码好了

class Solution {
    public:
        vector<vector<TreeLinkNode*> > myqeue;
        
        void connect(TreeLinkNode *root) {
            if( root == NULL )  return ;
            DFS(root, 0);
            int maxrow = myqeue.size();
            for(int i = 0 ;i < maxrow ; i++){
                int maxcol = myqeue[i].size() - 1;
                for(int j = 0 ; j < maxcol ; j++){
                    myqeue[i][j]->next = myqeue[i][j + 1];
                }
            }
        }
        void DFS(TreeLinkNode *root,int level){
            if( root == NULL )  return ;
            if( level == myqeue.size() ) myqeue.push_back(vector<TreeLinkNode *>());
            
            myqeue[level].push_back(root);
            DFS(root->left, level + 1);
            DFS(root->right, level + 1);
        }
    };

21.[Combinations][]

题目意思: 给出1..n的全排列,但长度只有k

这题做了半天不让过！发现是生成全排的数组大小初始化错了。。。。后来可以正常提交，结果又说什么内存超了。。。所以算了，换一种写法吧。。原先的思路就是先生成全排，但只生成k位就push\_back到answer中。不知道哪里内存超了。。所以就用algorithm中的全排了。这是参考的讨论里的代码。第一次用next\_permutation，发现其结果是从end处开始一点点的变化的。所以初始化flag必须从后向前初始化。

class Solution {
    public:
        vector<vector<int> > answer;
        vector<vector<int> > combine(int n, int k) {
            
            vector<bool> flag(n, 0);
            for(int i = n - 1 ; i >= n - k ; i--)
                flag[i] = true;
            vector<int> temp;
            do{
                temp.clear();
                for(int i = 0 ; i < n ; i++)
                    if( flag[i] )   temp.push_back(i+1);
                answer.push_back(temp);
            }while(next_permutation(flag.begin(), flag.end()));
            return answer;
        }
    };

22.[Remove Nth Node From End of List][]

题目意思: 去除链表中倒数第n个节点.

思路就是弄两个指针，一个慢n步即可。注意有可能最后删除的是头结点的情况

class Solution {
    public:
        ListNode *removeNthFromEnd(ListNode *head, int n) {
            if( head == NULL )   return NULL;
            if( head->next == NULL && n == 1)   return NULL;
            ListNode *pre  = NULL;
            ListNode *fast = head;
            if( n == 1){
                while(fast->next){
                    pre = fast;
                    fast = fast->next;
                }
                pre->next = NULL;
                free(fast);
            } else {
                for(int i = 0 ; i < n ; i++){
                    pre  = fast;
                    fast = fast->next;
                }
                if( !fast ){
                    fast = head->next;
                    free(head);
                    head = fast ;
                } else {
                    ListNode *slow = head;
                    while(fast){
                        fast = fast->next;
                        pre = slow;
                        slow = slow->next;
                    }
                    pre->next = slow->next;
                    free(slow);
                }
            }
            return head;
        }
    };

23.[Sum Root to Leaf Numbers][]

题目意思: 每条从根节点到叶子节点的值组成一个数(不是路径和),返回其所有数的和.

这题很简单，一次性AC。。就是DFS直接搜索所有叶子结点，然后算路径值就可以了。

class Solution {
    public:
        int answer;
        int sumNumbers(TreeNode *root) {
            answer = 0;
            DFS(root, 0);
            return answer;
        }
        void DFS(TreeNode *root,int sum){
            if( root == NULL ) return ;
            if( root->left == NULL && root->right == NULL ){
                answer += sum*10 + root->val;
                return ;
            }
            sum = sum*10 + root->val;
            DFS(root->left, sum);
            DFS(root->right, sum);
        }
    };

24.[Minimum Depth of Binary Tree][]

题目意思: 找到二叉树深度最浅的那一条路经长.

这一题也简单。。。直接DFS用全局变量来保存最小值即可。怎么按AC率排序的，越做越简单了呢。。

class Solution {
    public:
        int min;
        int minDepth(TreeNode *root) {
            if( root == NULL)   return 0;
            min = 1000000;
            DFS(root, 1);
            return min;
        }
        void DFS(TreeNode *root,int level){
            if(root == NULL)    return ;
            if( root->left == NULL && root->right == NULL && min > level)
                    min = level;
            DFS(root->left, level + 1);
            DFS(root->right, level + 1);
        }
    };

25.[Length of Last Word][]

题目意思:返回最后一个单词的意思.字符串中有空格和大小写字符

这一题看似很简单，所以要多注意边界条件。我最开始就只注意到了最后有多个空格的情况，但是忘了用循环把控制变量i更新到最新的非空格的地方。。总的来说还是比较简单的。

class Solution {
    public:
        int lengthOfLastWord(const char *s) {
            if( s == NULL ) return 0;
            int pre = 0;
            int cur = 0;
            int i = 0 ;
            while(s[i]){
                if( s[i] == ' '){
                    pre = cur;
                    cur = 0;
                    while(s[i] == ' ')  i++;
                    continue;
                } else {
                    cur ++;
                }
                i++;
            }
            if( i && s[i - 1] == ' ' )   return pre;
            else    return cur;
        }
    };

26.[Palindrome Number][]

题目意思:判断数字是否是回文.

我都不想说了。。直接上代码吧。。

class Solution {
    public:
        bool isPalindrome(int x) {
            if( x < 0)  return false;
            int temp = x;
            int re = 0;
            while(temp){
                re *= 10;
                re += temp % 10;
                temp /= 10;
            }
            return re == x;
        }
    };

27.[Trapping Rain Water][]

题目意思: 找出能储水的最大面积.

![Center][]

这一题一看很复杂，但能用之前那个左右同时向中间找最大值的思路.其实也没有多像....就是分别从两边向中间逼近,然后遇到比之前大的记录下这个值,遇到小的则加入到结果中.

class Solution {
    public:
        int trap(int A[], int n) {
            if( A == NULL || n < 3)  return 0;
            int left = 0 ;
            int leftmax;
            int right = n - 1;
            int rightmax;
            int answer = 0;
        	while(A[left] == 0)	left++;
        	while(A[right] == 0 ) right--;
        	leftmax = A[left];
        	rightmax = A[right];
        
            while(left < right){
                if( leftmax < rightmax ){
        			left ++;
                    while(left < right && A[left] < leftmax){
                        answer += leftmax - A[left];
                        left++;
                    }
                    leftmax = A[left];
                } else {
        			right--;
                    while(left < right && A[right] < rightmax){
                        answer += rightmax - A[right];
                        right--;
                    }
                    rightmax = A[right];
                }
            }
            return answer;
        }
    };

28.[Valid Parentheses][]

题目意思: 判断串中的三种括号是否匹配.

这个也很简单。之前用C一写就是至少半个小时，用C++很快就搞定了。

class Solution {
    public:
        bool isValid(string s) {
            stack<char> my_stack;
            int length = s.size();
            if( length & 1) return false;
            my_stack.push(s[0]);
            for(int i = 1 ; i < length ; i++){
                if( s[i] == '(' || s[i] == '{' || s[i] == '[')
                    my_stack.push(s[i]);
                else {
                    if( my_stack.empty() )  return false;
                    switch(my_stack.top()){
                        case '(':
                            if(s[i] != ')')
                                return false;
                            break;
                        case '{':
                            if(s[i] != '}')
                                return false;
                            break;
                        case '[':
                            if(s[i] != ']')
                                return false;
                            break;
                    }
                    my_stack.pop();
                }
            }
            if( my_stack.empty() )  return true;
            else    return false;
        }
    };

29.[Flatten Binary Tree to Linked List][]

题目意思: 按顺序,把二叉树展开成排序链表.

这个题目很有趣。。居然是把树展平。。。。想着直接后序递归变形一下即可。结果左节点没有置为NULL。。错了半天。。。。。我还写了个层次构造树的程序。。。

思路很简单就是先递归的将左右结点设置，这样最多就从两层的时候开始考虑了。然后再把左节点放到右结点，再将原来的右结点放到最后。即可。

class Solution {
    public:
        void flatten(TreeNode *root) {
            switch_to(root);
        }
        void switch_to(TreeNode *root){
            if( root == NULL )  return;
            
            if( root->left ){
                switch_to(root->left);
                switch_to(root->right);
                
                TreeNode *right = root->right;
                TreeNode *temp;
                
                root->right = root->left;
                root->left = NULL;
                temp = root;
                
                while( temp->right )    temp = temp->right;
                temp->right = right;
                    
            } else {
                switch_to(root->right);
            }
        }
    };

30.[Longest Consecutive Sequence][]

题目意思: 在无序的数组中找到最长的连续数字的长度.

这一题最先想到的就是hash和排序了。我搜STL的hash发现标准里面不是自带的。。。于是想到了排序。。提交一个还AC了。。我看了一下讨论里有unordered\_map。原来C++11里面已经支持了hash了，而且迭代器也不用写那么一长串了，直接auto。。。所以又写了一遍。最后的差距也不是很大，排序是88ms，这个是68ms。

思路就是先插入，不重复插入。

1.如果插入值的前一个值存在。那么就把这个子数组对应的键值为第一个的值的hash值设置为这个链中最小的值。

2.如果插入值的后一个值存在。那么就把这个子数组对应的键值为最后一个元素的值的hash值设置为这个链中最小的值。

最后遍历hash，然后求键值之差。最大的就是结果。这个数组中间的值都不用管。还是贴效率高的代码吧。

class Solution {
    public:
        int longestConsecutive(vector<int> &num) {
            unordered_map<int, int> my_map;
            int n = num.size();
            for(int i = 0 ; i < n ; i++){
                int val = num[i];
                if(my_map.count(val))    continue;
                my_map[val] = val;
                if( my_map.count(val - 1)){
                    my_map[val] = my_map[val - 1];
                    my_map[my_map[val]] = val;
                }
                if( my_map.count(val + 1)){
                    int last = my_map[val + 1];
                    my_map[last] = my_map[val];
                    my_map[my_map[val]] = last;
                }
            }
            int max = 0;
            for(auto i = my_map.begin() ; i != my_map.end() ; i ++){
                int temp = i->second - i->first;
                if( temp > max )
                    max = temp; 
            }
            return max + 1;
        }
    };

[Rotate Image]: https://oj.leetcode.com/problems/rotate-image/
[Generate Parentheses]: https://oj.leetcode.com/problems/generate-parentheses/
[Permutations]: https://oj.leetcode.com/problems/permutations/
[Unique Paths]: https://oj.leetcode.com/problems/unique-paths/
[Search a 2D Matrix]: https://oj.leetcode.com/problems/search-a-2d-matrix/
[Best Time to Buy and Sell Stock]: https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/
[Binary Tree Level Order Traversal II]: https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
[Minimum Path Sum]: https://oj.leetcode.com/problems/minimum-path-sum/
[Container With Most Water]: https://oj.leetcode.com/problems/container-with-most-water/
[Binary Tree Postorder Traversal]: https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
[Linked List Cycle II]: https://oj.leetcode.com/problems/linked-list-cycle-ii/
[Spiral Matrix II]: https://oj.leetcode.com/problems/spiral-matrix-ii/
[Binary Tree Level Order Traversal]: https://oj.leetcode.com/problems/binary-tree-level-order-traversal/
[Set Matrix Zeroes]: https://oj.leetcode.com/problems/set-matrix-zeroes/
[Search in Rotated Sorted Array II]: https://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
[Search in Rotated Sorted Array]: https://oj.leetcode.com/problems/search-in-rotated-sorted-array/
[Pascal_s Triangle II]: https://oj.leetcode.com/problems/pascals-triangle-ii/
[Path Sum]: https://oj.leetcode.com/problems/path-sum/
[Remove Duplicates from Sorted Array II]: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
[Populating Next Right Pointers in Each Node II]: https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
[Combinations]: https://oj.leetcode.com/problems/combinations/
[Remove Nth Node From End of List]: https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/
[Sum Root to Leaf Numbers]: https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/
[Minimum Depth of Binary Tree]: https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
[Length of Last Word]: https://oj.leetcode.com/problems/length-of-last-word/
[Palindrome Number]: https://oj.leetcode.com/problems/palindrome-number/
[Trapping Rain Water]: https://oj.leetcode.com/problems/trapping-rain-water/
[Center]: /images/20220810/27cb3dd35fd14aa783d8fae170d3001a.png
[Valid Parentheses]: https://oj.leetcode.com/problems/valid-parentheses/
[Flatten Binary Tree to Linked List]: https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
[Longest Consecutive Sequence]: https://oj.leetcode.com/problems/longest-consecutive-sequence/