首页 > 代码库 > leetcode题目思路以及部分解答(二)

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

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


1.Rotate Image

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

主要思路就是第一层循环按层次深入。第二层把旋转后对应替代的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

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

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

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

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.Search a 2D Matrix

这题属于简单的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

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

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

证明的思路就是设一个最大的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

开始感觉就是用两个指针,但半天没想出来。。。思路是看的讨论的。简单来说设置两个指针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。清零的时候先按照非第一行第一列元素清空,然后再把第一行第一列清空即可。我一开始按照的是讨论里面的第一种思路写,写的一般才发现可以这么做。果然还是要开始写才能让好算法出现。。

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

本来准备直接用递推公式算出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

直接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

这题做了半天不让过!发现是生成全排的数组大小初始化错了。。。。后来可以正常提交,结果又说什么内存超了。。。所以算了,换一种写法吧。。原先的思路就是先生成全排,但只生成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步即可。注意有可能最后删除的是头结点的情况

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

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

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;
    }
};


小结:

1.编程习惯还是不行。变量名,变量类型,内聚,inline,空格与tab,什么的还是要多注意。

2.如果没思路,从简单的开始写,再一点点优化。

3.多画图,不要怕画太多东西。说白了就是懒。。。