Maximum Product Subarray
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4]
,
the contiguous subarray [2,3]
has the largest product = 6
.
耗时 25 分钟 ac
解法
loop 逻辑如下:
如果遇到负数t: 最小负数’ = 最大正数 * t 最大正数’ = <u>最小负数 * t</u> 或 1(无最小负数) 如果遇到正数t: 最小负数’ = 最小负数 * t 或 无(无最小负数) 最大正数’ = <u>最大正数 * t</u> 如果遇到0: 最小负数 = 无, 最大正数 = 1 // 下划线位置都可能更新最终结果(最大积)
代码
class Solution { public: int maxProduct(int A[], int n) { int m = A[0]; int mz = 1, mf = 1; for(int i=0; i<n; i++){ int t = A[i]; int a = mz, b = mf; if(t<0) { if(b<0) mz = b*t, m = max(m, mz); else mz = 1; mf = a*t; } else if(t>0){ mz = a*t, m = max(m, mz); if(b < 0) mf = b*t; } else{ m = max(0, m); mz = 1, mf = 1; } } return m; } };
str2int
class Solution { public: #define MAXN 0x7fffffff int atoi(const char *str) { bool fh = true; int i = 0, j =0; long long int t = 0; while(str[i]==' ') i++; if(str[i]=='-') fh = false, i++; else if(str[i]=='+') i++; while(str[i]=='0') i++; while(str[i]<='9' && str[i]>= '0') { t*=10, t+=str[i]-'0', i++; if(t>MAXN) break; } if(t>MAXN) // t over-flow if(fh) return MAXN; else return MAXN+1; // MINN return fh? t : 0-t; } };
two-sum
左l右r往中间扫描,注意使用一个pair<int, int> 保存以前的下标
class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { vector<int> res; int n = numbers.size(); typedef pair<int, int> Pair; vector<Pair> ns; for(int i=0; i<n; i++){ ns.push_back(Pair(numbers[i], i+1));} sort(ns.begin(), ns.end());///@error: lost int l = 0, r = n - 1; while(l<r){ int m = ns[l].first + ns[r].first; if( m > target){ r --; }else if (m < target){ l ++; }else{ int a = ns[l].second, b = ns[r].second; res.push_back(min(a, b)), res.push_back(max(a, b)); return res; } } return res; } };
four-sum
解法一 i+j+twoSum([l, r])
class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<vector<int> > res; int n = num.size(); sort(num.begin(), num.end()); for(int i=0; i<=n-4; i++){ if(i>0 && num[i] == num[i-1]) continue; // unique for(int j=i+1; j<=n-3; j++){ if(j>i+1 && num[j] == num[j-1]) continue; // unique int s = target - num[i] - num[j]; int l = j+1, r = n-1; while(true){ // unique while(l>j+1 && num[l]==num[l-1]) l++; while(r<n-1 && num[r]==num[r+1]) r--; if(l >= r) break; int t = num[l]+num[r]; if(t < s) l++; else if(t > s) r--; else { vector<int> tmp; tmp.push_back(num[i]), tmp.push_back(num[j]), tmp.push_back(num[l]), tmp.push_back(num[r]); res.push_back(tmp); l++, r--; } } } } return res; } };
解法二 twoSum( [<i, j>] )
class Solution { public: vector<vector<int> > fourSum(vector<int> &num, int target) { vector<vector<int> > res; vector<vector<int> > tmp; sort(num.begin(), num.end()); typedef pair<int, int> Pair; typedef pair<int, Pair > PP; vector<pair<int, Pair> > s; int n = num.size(); for(int i=0; i<n; i++){ for(int j=i+1; j<n; j++){ int t= num[i]+num[j]; s.push_back(PP(t, Pair(i, j))); } } sort(s.begin(), s.end()); vector<pair<int, vector<Pair> > > vs; int lst = 0; for(int i=0; i<s.size(); i++){ if(i>0 && s[i].first==lst ){ vs[vs.size()-1].second.push_back(s[i].second); } else lst=s[i].first, vs.push_back(pair<int, vector<Pair> > (lst, vector<Pair>(1, s[i].second))) ;//@error } int l =0, r=vs.size()-1; while(l<=r){ //@error: l<=r not l<r (may be a[l] + a[l] = target) int a = vs[l].first, b = vs[r].first; vector<Pair> &c = vs[l].second, &d = vs[r].second; if(a+b<target) l++; else if(a+b>target) r--; else{ for(int i=0; i<c.size(); i++){ for(int j=0; j<d.size(); j++){ vector<int> t; t.push_back(c[i].first);t.push_back(c[i].second); t.push_back(d[j].first);t.push_back(d[j].second); //@error j not i sort(t.begin(), t.end()); int k; for(k=0; k<3; k++) if(t[k] == t[k+1]) break; if(k==3) tmp.push_back(t); } } l++; r--; } } sort(tmp.begin(), tmp.end()); vector<vector<int> >::iterator it = unique(tmp.begin(), tmp.end()); tmp.erase(it, tmp.end()); for(int i=0; i<tmp.size(); i++){ vector<int> &t = tmp[i]; vector<int> s; for(int j=0; j<4; j++) s.push_back(num[t[j]]); res.push_back(s); } sort(res.begin(), res.end()); it = unique(res.begin(), res.end()); res.erase(it, res.end()); return res; } };
ReverseWord
方法一
char * reverse(char *a){ int n = strlen(a); for(int i=0; i<=(n-1)/2; i++){ char c = a[i]; a[i] = a[n-1-i]; a[n-1-i] = c; } int i =0; while(a[i]){ while(a[i]==' ') i++; int j =i; while(a[j] && a[j]!=' ') j++; if(j==i) break; j--; for(int k =i; k<=(i+j)/2; k++){ char c = a[k]; a[k] = a[i+j-k]; a[i+j-k] = c; } i = j+1; } return a; }
方法二
class Solution { public: void reverseWords(string &s) { char buf[100000]; int idx = 0; int i = s.length()-1; while(i>=0){ // spaces while(i>=0 && s[i]==' ') i--; int j = i; if(i<0) break; while(i>=0 && s[i]!=' ') i--; if(idx>0) buf[idx++]=' '; for(int k=i+1; k<=j; k++, idx++){ buf[idx]=s[k]; } } buf[idx]=0; s = buf; } };
链表操作
k旋转链表
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
解答:
注意有这么几个局部变量:
全局首尾节点: head, tail,
用于指向本section首节点:pp,
用于指向下一个k-section:q,
指向当前节点: p,
用于逆转:p1, p2,
复杂loop内部逻辑语义是分层的。合理使用多层的局部变量(全局的,section的,当前的等等)是复杂loop的关键。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *reverseKGroup(ListNode *head, int k) { if(k<=0) return head; ListNode *tail=NULL, *p=head, *q, *np; head = NULL; while(true){ q = p; int i;for(i=0; i<k; i++){ if(!q) break; q = q->next; } if(i==k){ ListNode *p1 = p->next, *p2, *pp=p;//@error: p2, pp=p while(p1!=q){ p2 = p1->next; p1->next = p; p = p1, p1 = p2; } if(!head) head = p; if(tail) tail->next=p; tail=pp; tail->next = NULL; p = p1; } else { if(!head) head = p; if(tail) tail->next=p; break; } } return head; } };
找环并返回环入口节点
- 1步指针p和2步指针p2同时从头向后扫描,如果再次相遇于点p ( 2*(n + x) = n + x + k*m, so n + x = k*m )
- 则用两个1步指针分别从头和位置p向后扫描,再次相遇的点为环的入口 ( 由上式得出 n = k*m + (m-x) 所以,两个指针相遇时已经走过长度n)
- 否则无环
struct ListNode{ int val; ListNode *next; ListNode(int a):val(a),next(NULL){} }; typedef pair<ListNode*, ListNode*> Pair; typedef Pair List; List make(int a[], int n){ ListNode *head=NULL, *tail=NULL, *p; for(int i=0; i<n; i++){ p = new ListNode(a[i]); if(i==0) head = p; if(tail) tail->next = p; tail = p; } return List(head, tail); } // return the entrance-node of the circle in list ListNode *getCircle(ListNode *l){ ListNode *p = l, *p2 = l; while(p2 && p2->next){ p = p->next, p2 = p2->next->next; if(p==p2) break; } if(!p2 || !p2->next) return NULL; /* n + x = k * m, so n = j *m +(m-x). n is the length of the non-circle part of the list; x is the length from circle-entrance to p, m is the length of the circle, (m-x) is the length from p to circle-entrance */ p = l; while(p!=p2){ p=p->next, p2=p2->next; } return p; } int main(){ int a[10]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; List l= make(a, 10); ListNode *head = l.first, * tail = l.second; tail->next = head; cout<<getCircle(head)->val<<endl; tail->next = head->next->next; cout<<getCircle(head)->val<<endl; return 0; }
蛇形访问
回形访问矩阵
class Solution { public: vector<int> spiralOrder(vector<vector<int> > &matrix) { vector<int> res; if(!matrix.size()) return res; int len_x = matrix.size(), len_y = matrix[0].size(); int x = 0, y = -1; while(len_x>0 && len_y>0){ for(int i=0; i<len_y; i++) y++, res.push_back(matrix[x][y]); len_x -- ; if(!len_x || !len_y) break; for(int i=0; i<len_x; i++) x++, res.push_back(matrix[x][y]); len_y -- ; if(!len_x || !len_y) break; for(int i=0; i<len_y; i++) y--, res.push_back(matrix[x][y]); len_x -- ; if(!len_x || !len_y) break; for(int i=0; i<len_x; i++) x--, res.push_back(matrix[x][y]); len_y --; if(!len_x || !len_y) break; } return res; } };
蛇形访问矩阵
vector<int> snakeOrder(vector<vector<int> > &matrix) { vector<int> res; if(!matrix.size()) return res; int len_x = matrix.size(), len_y = matrix[0].size(); int x = 0, y = -1; for(int i =0; i<=len_x+len_y-2; i++){ if(i%2){ x = min(len_x-1, i), y = i - x; while(y<len_y && x>=0) res.push_back(matrix[x--][y++]); }else{ y = min(len_y-1, i), x = i - y; while(x<len_x && y>=0) res.push_back(matrix[x++][y--]); } } return res; }
最大蓄水池
y0 y1 .... yn-1, 找到 yi, yj,使得 min(yi, yj) *(j-i) 最大
思路一(O(n)):
两边向中间线性扫描:类似于2sum,左右指针往中间扫描。每次改变较小的那个数对应的指针,直到左右指针相遇。
int maxArea(vector<int> &height) { int l=0, r= height.size()-1; int mn =0 ; while(l<r){ mn = max(mn, (r-l)*min(height[l], height[r])); if(height[l]<height[r]) l++; else r--; } return mn; }
思路二(非最优):
借助于增长序列,线性扫描枚举。
- 从左到右扫描(维护一个递增序列),扫描到i时二分查找增长序列中第一个大于等于yI的元素yk,
- 找到yk,则以yi为右边且是较短边的蓄水池的最大面积是 由yk yi构成。
- 如果未找到,则增长序列都比yi小,则直接把yi加入到序列末尾。
- 同样的道理从右到左扫描,找到以yi为左边且是较短边的蓄水池最大面积。
int maxArea(vector<int> &height) { typedef pair<int,int> Pair; vector<Pair> bigger; int mn = 0; for(int i=0; i<height.size(); i++){ vector<Pair>::iterator it = upper_bound(bigger.begin(), bigger.end(),Pair(height[i], i)); int idx = it - bigger.begin(); if(idx>0) { if(bigger[idx-1].first == height[i]) idx--; } if(idx<bigger.size()) mn = max(mn, (i - bigger[idx].second) * height[i]); else bigger.push_back(Pair(height[i], i)); } bigger = vector<Pair>(); for(int i=height.size()-1; i>=0; i--){ vector<Pair>::iterator it = upper_bound(bigger.begin(), bigger.end(),Pair(height[i], i)); int idx = it - bigger.begin(); if(idx>0) { if(bigger[idx-1].first == height[i]) idx--; } if(idx<bigger.size()) mn = max(mn, (bigger[idx].second - i) * height[i]); else bigger.push_back(Pair(height[i], i)); } return mn; }
直方图中最大矩阵
正确思路:
class Solution { public: int largestRectangleArea(vector<int> &height) { height.push_back(0);//@important stack<pair<int,int> > ss; int mm = 0; for(int i =0; i<height.size(); i++){ int t = height[i]; int width = 0; while(!ss.empty() && ss.top().first >= t){ width += ss.top().second; // @important mm = max(mm, width*ss.top().first); ss.pop(); } width += 1; mm = max(mm, width*t); ss.push(pair<int, int>(t, width));///@important } height.pop_back(); //把最后额外加入的条条弹出 return mm; } };
思路二(来自九章算法):
class Solution { public: int largestRectangleArea(vector<int> &height) { int n = height.size(); typedef pair<int, int> Pair; stack<Pair> bigger; vector<int> len(n, 0); for(int i=0; i<n; i++){ Pair p(height[i], i); while(!bigger.empty() && bigger.top()>= p) bigger.pop(); if(bigger.empty()) len[i]+=(i-(-1)); else len[i] += (i-bigger.top().second);// first h[j] smaller than height[i] in the left direction bigger.push(p); } bigger = stack<Pair>(); for(int i=n-1; i>=0; i--){ Pair p(height[i], i); while(!bigger.empty() && bigger.top()>= p) bigger.pop(); if(bigger.empty()) len[i] += (n-i-1); else len[i] += (bigger.top().second-i-1);// first h[j] smaller than height[i] in the right direction bigger.push(p); } int mn = 0; for(int i=0; i<n; i++){ mn = max(mn, height[i]*len[i]); } return mn; } };