首页 > 代码库 > 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; } };
我用递归做的。做的时候突然发现,如果把递归里面的变量全部变为全局的,并且将递归函数用一个函数封装起来并初始化全局变量。栈空间就可以节约不少!对于比较深层次的递归效率也高一些。
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; } };
这一题没看懂。。。以为是求梯形面积。。百度了下,结果是求梯形中矩形的面积。
这一题最直观的思路就是双循环,但感觉应该没这么简单。。百度了一下,就是从两边往中间靠紧,长度在缩短,所以要保证高要增长。
证明的思路就是设一个最大的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.多画图,不要怕画太多东西。说白了就是懒。。。