5.回文串
几种方法：
暴力：枚举每一个字串，判断是否为回文串，复杂度O(n^3)，暴力月莫不可取
dp：区间dp思想，O(n^2)
中心扩展：找每一个字符，然后往两边扩展，O(n^2)
manacher算法：主要是中心扩展的一个优化，链接，这篇讲的易懂
6.ZigZag Conversion
P A H N A P L S I I G Y I R
之前用了数学方法，累死了，直接搞个每行的string存一下就行
11. Container With Most Water
Start by evaluating the widest container, using the first and the last line. All other possible containers are less wide, so to hold more water, they need to be higher. Thus, after evaluating that widest container, skip lines at both ends that don't support a higher height. Then evaluate that new container we arrived at. Repeat until there are no more possible containers left.
22.Generate Parentheses
递归
1 class Solution { 2 public: 3 vector<string> generateParenthesis(int n) { 4 vector<string> ans; 5 vector<string> ans1; 6 vector<string> ans2; 7 for(int i=1;i<2*n;i+=2){ 8 ans1=generateParenthesis((i-1)/2); 9 ans2=generateParenthesis((2*n-i-1)/2); 10 ans1.push_back(""); 11 ans2.push_back(""); 12 for(int j=0;j<ans1.size();j++){ 13 for(int k=0;k<ans2.size();k++){ 14 string m='('+ans1[j]+')'+ans2[k]; 15 if(m.length()!=2*n) continue; 16 ans.push_back(m); 17 } 18 } 19 } 20 return ans; 21 } 22 };
23.**
一堆链表的合并 优先队列，学习了一个在class怎么用
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 11 public: 12 struct cmp { 13 bool operator()(const ListNode* l, const ListNode* r) { 14 return l->val > r->val; 15 } 16 }; 17 18 ListNode* mergeKLists(vector<ListNode*>& lists) { 19 priority_queue<ListNode *,vector<ListNode *>,cmp> q; 20 for(int i=0;i<lists.size();i++){ 21 if(lists[i]) q.push(lists[i]); 22 } 23 if(q.empty()) return NULL; 24 ListNode *ans=q.top(); 25 26 q.pop(); 27 if(ans->next) q.push(ans->next); 28 ListNode *aans=ans; 29 while(!q.empty()){ 30 aans->next=q.top(); 31 q.pop(); 32 aans=aans->next; 33 if(aans->next) q.push(aans->next); 34 } 35 return ans; 36 37 } 38 };
24.**
交换链表相邻元素的值
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode* swapPairs(ListNode* head) { 12 ListNode **ans=&head,*a; //ans是指向head的指针 13 ListNode *ha=NULL; 14 while(a=*ans){ 15 if(a->next==NULL){ 16 break; 17 } 18 ha=a->next; 19 a->next=a->next->next; 20 ha->next=a; 21 *ans = ha; 22 ans=&(a->next); 23 } 24 return head; 25 } 26 };
25.***
24的加强版，交换一个区间内的元素，方法很巧妙
26.Given input array nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.
1 class Solution { 2 public: 3 int removeDuplicates(vector<int>& nums) { 4 if(nums.size()==0) return 0; 5 int w=nums[0],ans=1; 6 for(int i=1;i<nums.size();i++){ 7 if(nums[i]!=w){ 8 w=nums[i]; 9 nums[ans]=w; 10 ans++; 11 } 12 } 13 return ans; 14 } 15 };
27.Given input array nums = [3,2,2,3], val = 3
Your function should return length = 2, with the first two elements of nums being 2.
1 class Solution { 2 public: 3 int removeElement(vector<int>& nums, int val) { 4 if(nums.size()==0) return 0; 5 int ans=0; 6 for(int i=0;i<nums.size();i++){ 7 if(val!=nums[i]){ 8 nums[ans++]=nums[i]; 9 } 10 } 11 return ans; 12 } 13 };
28.KMP
1 class Solution { 2 public: 3 int strStr(string haystack, string needle) { 4 5 string x=needle; 6 string y=haystack; 7 int m=needle.length(); 8 int n=haystack.length(); 9 if(m==0) return 0; 10 int next[100010]; 11 int i,j; 12 j=next[0]=-1; 13 i=0; 14 while(i<m) 15 { 16 while(-1!=j && x[i]!=x[j])j=next[j]; 17 next[++i]=++j; 18 } 19 20 int ans=0; 21 i=j=0; 22 while(i<n) 23 { 24 //printf("%d ",i); 25 while(-1!=j && y[i]!=x[j])j=next[j]; 26 i++;j++; 27 if(j>=m) 28 { 29 ans=i; 30 break; 31 } 32 if(ans) break; 33 } 34 if(ans-m<0) return -1; 35 return ans-m; 36 } 37 38 };
30.给定字符串s和一堆相同长度字符串words，如果这个s里有一段字符串包含了words里所有的字符串，并且没有间隔，则输出这段字符串的首位
没有时间限制真的爽，随便怎么写
1 class Solution { 2 public: 3 vector<int> findSubstring(string s, vector<string>& words) { 4 vector<int> ans; 5 map<string,int> word; 6 int siz=words.size(); 7 int len=s.length(); 8 int wl=words[0].length(); 9 for(int i=0;i<siz;i++){ 10 word[words[i]]++; 11 } 12 for(int i=0;i<len-siz*wl+1;i++){ //需要遍历的次数 13 map<string,int> word2; 14 int j=0; 15 for(;j<siz;j++){ 16 string w=s.substr(i+j*wl,wl); 17 if(word.find(w)!=word.end()){ 18 word2[w]++; 19 if(word2[w]>word[w]){ 20 break; 21 } 22 } 23 else break; 24 } 25 if(j==siz) ans.push_back(i); 26 } 27 return ans; 28 } 29 };
31.生成下一个排列，用STL一行解决，爽歪歪
1 class Solution { 2 public: 3 void nextPermutation(vector<int>& nums) { 4 next_permutation(nums.begin(),nums.end()); 5 } 6 };
32.找到字符串中正确的最长括号串，用stack消除括号，并累计数字到它的栈顶，如果这个栈顶继续消除的话，就会继续累计的下一个地方
1 class Solution { 2 public: 3 int longestValidParentheses(string s) { 4 int len=s.length(); 5 int ans=0; 6 stack<int> st; 7 vector<int> f; 8 f.push_back(0); 9 st.push(6); 10 for(int i=0;i<len;i++){ 11 int w; 12 if(s[i]=='(') w=-1; 13 else w=1; 14 if(w==-st.top()&&w==1){ //可消除 15 st.pop(); 16 int o=st.size(); 17 o--; 18 f[o]=2+f[o+1]+f[o]; 19 f.erase(f.begin()+o+1); 20 if(f[o]>ans){ 21 ans=f[o]; 22 } 23 } 24 else{ //无法消除 25 st.push(w); 26 f.push_back(0); 27 } 28 } 29 return ans; 30 } 31 };
33.在一个重新排了一半的有序序列中，找到目标值，23333，好题！需要多做几遍 ********************
34.在一个有序序列中，找到目标值的范围 ，写了个logn的方法居然还没On的方法快。。。然后加了点剪枝
1 class Solution { 2 public: 3 vector<int> searchRange(vector<int>& nums, int target) { 4 int n=nums.size(); 5 int l=0,r=n-1,mid,ans1=-1,ans2=-1; 6 vector<int> ans; 7 while(l<=r){ 8 mid=(l+r)>>1; 9 if(nums[mid]==target){ 10 ans1=mid; 11 l=mid+1; 12 } 13 else if(nums[mid]<target)l=mid+1; 14 else r=mid-1; 15 } 16 if(ans1==-1){ 17 ans.push_back(ans2); 18 ans.push_back(ans1); 19 return ans; 20 } 21 l=0,r=ans1; 22 while(l<=r){ 23 mid=(l+r)>>1; 24 if(nums[mid]==target){ 25 ans2=mid; 26 r=mid-1; 27 } 28 else if(nums[mid]<target)l=mid+1; 29 else r=mid-1; 30 } 31 32 ans.push_back(ans2); 33 ans.push_back(ans1); 34 return ans; 35 } 36 };
35.找到一个数或插入到有序序列中，裸二分
1 class Solution { 2 public: 3 int searchInsert(vector<int>& nums, int target) { 4 int n=nums.size(); 5 int l=0,r=n-1,mid; 6 while(l<=r){ 7 mid=(l+r)>>1; 8 if(nums[mid]<target) l=mid+1; 9 else r=mid-1; 10 } 11 return l; 12 } 13 };
36.判断一个数组是否合理，模拟即可
1 class Solution { 2 public: 3 bool isValidSudoku(vector<vector<char>>& board) { 4 //检验的基准就是每9个中是否存在重复数字 5 //先检验横行 6 int vis[15]; 7 int i,j,k,u,v; 8 bool flag=1; 9 for(i=0;i<9;i++){ 10 for(k=0;k<10;k++) vis[k]=0; 11 for(j=0;j<9;j++){ 12 if(board[i][j]=='.') continue; 13 int w=board[i][j]-'0'; 14 if(vis[w]){ 15 flag=0; 16 break; 17 } 18 else vis[w]=1; 19 } 20 if(!flag){ 21 break; 22 } 23 } 24 if(!flag) return 0; 25 26 //再检验纵行 27 for(i=0;i<9;i++){ 28 for(k=0;k<10;k++) vis[k]=0; 29 for(j=0;j<9;j++){ 30 if(board[j][i]=='.') continue; 31 int w=board[j][i]-'0'; 32 if(vis[w]){ 33 flag=0; 34 break; 35 } 36 else vis[w]=1; 37 } 38 if(!flag){ 39 break; 40 } 41 } 42 if(!flag) return 0; 43 44 //再检验九宫格 45 for(u=0;u<3;u++){ 46 for(v=0;v<3;v++){ 47 for(k=0;k<10;k++) vis[k]=0; 48 for(i=u*3;i<=u*3+2;i++){ 49 for(j=v*3;j<=v*3+2;j++){ 50 if(board[i][j]=='.') continue; 51 int w=board[i][j]-'0'; 52 if(vis[w]){ 53 flag=0; 54 break; 55 } 56 else vis[w]=1; 57 } 58 } 59 if(!flag) break; 60 } 61 if(!flag) break; 62 } 63 return flag; 64 } 65 };
37.dancing link解数独
38.水
39.数的组合，dfs即可
1 class Solution { 2 public: 3 int n; 4 vector<vector<int>> finans; 5 vector<int> nums; 6 void fun(int pos,int target,vector<int> w){ 7 /* 8 printf("------%d %d ",pos,target); 9 for(int i=0;i<w.size();i++){ 10 printf("%d ",w[i]); 11 } 12 printf(" "); 13 */ 14 if(target<0) return; 15 if(target==0){ 16 finans.push_back(w); 17 return; 18 } 19 if(pos+1!=n) fun(pos+1,target,w); 20 w.push_back(nums[pos]); 21 fun(pos,target-nums[pos],w); 22 } 23 vector<vector<int>> combinationSum(vector<int>& candidates, int target) { 24 sort(candidates.begin(),candidates.end()); 25 n=candidates.size(); 26 vector<int> ans; 27 nums.assign(candidates.begin(),candidates.end()); 28 fun(0,target,ans); 29 return finans; 30 } 31 };
40. 和上一题类似，不过每个数只能被选一次，比较不错的题 ***************
1 class Solution { 2 public: 3 int n; 4 void fun(vector<int>& nums,int pos,int target,vector<int>& w,vector<vector<int>>& finans){ 5 if(target==0){ 6 finans.push_back(w); 7 return; 8 } 9 for(int i=pos;i<n;i++){ 10 if(i!=pos&&nums[i]==nums[i-1]) continue; //不选之前选过的 11 if (nums[i]>target) return; 12 w.push_back(nums[i]); 13 fun(nums,i+1,target-nums[i],w,finans); 14 w.pop_back(); 15 } 16 } 17 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { 18 sort(candidates.begin(),candidates.end()); 19 n=candidates.size(); 20 vector<int> ans; 21 vector<vector<int>> finans; 22 fun(candidates,0,target,ans,finans); 23 return finans; 24 } 25 };
41.遍历一遍，该放的数字放到该放的地方
1 class Solution { 2 public: 3 int firstMissingPositive(vector<int>& nums) { 4 int n=nums.size(),i,ans; 5 if(n==0) return 1; 6 for(i=0;i<n;i++){ 7 while(nums[i]!=i+1){ 8 if(nums[i]>n||nums[i]<=0||nums[i]==nums[nums[i]-1]) break; 9 swap(nums[i],nums[nums[i]-1]); 10 } 11 } 12 for(i=0;i<n;i++){ 13 if(nums[i]!=i+1){ 14 ans=i+1; 15 break; 16 } 17 } 18 if(i==n) return n+1; 19 return ans; 20 } 21 };
42. 不错的题，一开始的想法是找出递减递增的序列，计算一下，后来发现5,1,2,1,5这样的计算不出来，达到顶点的值仍然可能有水 *****************
44.总之是一个比较复杂的题，题意就是给两串字符，看是否匹配，有？代表单个字符，*代表连续字符（可以为空）代码里有比较详细的解释 *******
1 /* 2 看一下例子 3 s=abbcb 4 p=a*bcb 5 6 首先肯定匹配s1,p1，两个相同，继续匹配，这时候i=2,j=2 7 接下来p遇到*,这里标记fi=1,fj=1，但是j我们需要++，j会变成3,因为此时我们默认*代表的是空,所以接下来匹配的应该是s2,p3 8 s2==p3，这时候i=3,p=4,我们发现不匹配，但是之前有*号，那么可能*号会被用到，因此，令i，j等于之前我们标记的地方,i=2,j=1 9 这里++fi的原因是因为我们用到了*号，所以i里的字符会被匹配一个，自然fi就需要++ 10 这时候p1依旧等于*，因此继续标记fi=2,fj=1,i=3,j=3; 11 这时候s3=p3，匹配成功,相对于之前的s2==p3，我们是往*号的地方添加了一个s[fi]，也就是b 12 之后剩下的都继续匹配成功 13 14 15 */ 16 class Solution { 17 public: 18 bool isMatch(string s, string p) { 19 int i=0,j=0,fi=-1,fj=-1; 20 int l1=s.length(),l2=p.length(); 21 while(i<l1){ 22 if(s[i]==p[j]||p[j]=='?') i++,j++; //单个字符匹配成功 23 else if(p[j]=='*'){ 24 fi=i; 25 fj=j++; //暂且将其*设为空 26 } 27 else{ //都不匹配，看之前的*能不能用,前提是有*存在 28 if(fj!=-1){ 29 i=++fi; 30 j=fj; 31 } 32 else return false; 33 } 34 } 35 while(p[j]=='*')j++; 36 return j==l2; 37 } 38 };
45. *****************
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
1 class Solution { 2 public: 3 int jump(vector<int>& nums) { 4 int n=nums.size(); 5 int ans=0; 6 int curMax=0; 7 int curreach=0; 8 for(int i=0;i<n;i++){ 9 if(curreach<i){ 10 ans++; 11 curreach=curMax; 12 } 13 14 curMax=max(curMax,nums[i]+i); 15 } 16 return ans; 17 } 18 };
50.做快一点，水题就不记录了，double的快速幂，原理一样，注意n为负的情况
1 class Solution { 2 public: 3 double myPow(double x, int n) { 4 double ret=1; 5 double tmp=x; 6 bool flag=0; 7 long long nn=n; 8 if(nn<0) nn=-nn,flag=1; 9 while(nn){ 10 if(nn&1) ret=(ret*tmp); 11 tmp=tmp*tmp; 12 nn>>=1; 13 } 14 if(flag) return 1.0/ret; 15 return ret; 16 } 17 };
51.N皇后问题，小白书上有，比较巧妙的地方就是判断斜线处是否合理
1 class Solution { 2 public: 3 int c[10],tot=0; 4 vector<vector<string>> ans; 5 void search(int cur,int n){ 6 int i,j; 7 if(cur==n){ 8 vector<string> anss; 9 for(i=0;i<n;i++){ 10 string s=""; 11 for(j=0;j<n;j++){ 12 if(j==c[i]) s+='Q'; 13 else s+='.'; 14 } 15 anss.push_back(s); 16 } 17 ans.push_back(anss); 18 } 19 else for(i=0;i<n;i++){ 20 int ok=1; 21 c[cur]=i; 22 for(j=0;j<cur;j++){ 23 if(c[cur]==c[j]||c[cur]-cur==c[j]-j||c[cur]+cur==c[j]+j){ 24 ok=0; 25 break; 26 } 27 } 28 if(ok) search(cur+1,n); 29 } 30 } 31 vector<vector<string>> solveNQueens(int n) { 32 search(0,n); 33 return ans; 34 } 35 };
56. cmp要加上static
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
1 /** 2 * Definition for an interval. 3 * struct Interval { 4 * int start; 5 * int end; 6 * Interval() : start(0), end(0) {} 7 * Interval(int s, int e) : start(s), end(e) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 static bool cmp(Interval A,Interval B){ 13 if(A.start!=B.start) return A.start<B.start; 14 else return A.end<B.end; 15 } 16 vector<Interval> merge(vector<Interval>& intervals) { 17 vector<Interval> ans; 18 int n=intervals.size(); 19 if(intervals.empty()) 20 return ans; 21 sort(intervals.begin(),intervals.end(),cmp); 22 int st=0,ed=0,stval=intervals[0].start,edval=intervals[0].end; 23 for(int i=1;i<n;i++){ 24 if(intervals[i].start<=edval){ 25 edval=max(edval,intervals[i].end); 26 } 27 else{ 28 ans.push_back(Interval(stval,edval)); 29 stval=intervals[i].start; 30 edval=intervals[i].end; 31 } 32 } 33 ans.push_back(Interval(stval,edval)); 34 return ans; 35 } 36 };
57.写成一坨
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
1 /** 2 * Definition for an interval. 3 * struct Interval { 4 * int start; 5 * int end; 6 * Interval() : start(0), end(0) {} 7 * Interval(int s, int e) : start(s), end(e) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) { 13 vector<Interval> ans; 14 int n=intervals.size(); 15 int flag=0; 16 if(intervals.empty()){ 17 ans.push_back(newInterval); 18 return ans; 19 } 20 int st=0,ed=0,stval=newInterval.start,edval=newInterval.end; 21 for(int i=0;i<n;i++){ 22 if(intervals[i].end>=stval&&flag==0){ //find the newInterval 23 if(intervals[i].start>edval){ //the newInterval does not cover any of intervals,this can be seen as an individual interval 24 ans.push_back(Interval(stval,edval)); 25 flag=-1; 26 i--; 27 continue; 28 } 29 flag=1; 30 stval=min(stval,intervals[i].start); 31 edval=max(intervals[i].end,edval); 32 if(i==n-1){ 33 ans.push_back(Interval(stval,edval)); 34 } 35 continue; 36 } 37 38 if(intervals[i].start<=edval&&flag==1){ //the end of the newinterval can be extended 39 edval=max(edval,intervals[i].end); 40 if(i==n-1){ 41 ans.push_back(Interval(stval,edval)); 42 } 43 continue; 44 } 45 else if(flag==1){ 46 flag=-1; 47 ans.push_back(Interval(stval,edval)); 48 } 49 50 ans.push_back(Interval(intervals[i].start,intervals[i].end)); 51 52 } 53 if(!flag){ 54 ans.push_back(newInterval); 55 } 56 if(flag!=-1){ 57 58 } 59 return ans; 60 } 61 };
60.找出第k个排列 *************************
62.从左上角到右下角的路径数目，数学方法看一下 ***
68. Text Justification 比较无聊的一题 就是按要求搞就行
1 class Solution { 2 public: 3 vector<string> fullJustify(vector<string>& words, int maxWidth) { 4 int i,j,k,num; 5 int numspace,avnumspace,extraspace; 6 int n=words.size(); 7 vector<string> ans; 8 for(i=0;i<n;i+=num){ //k means how many word you use in this line 9 int len=0; 10 for(j=i;j<n;j++){ //there have j-i words which will be use in this line from i to j-i 11 if(len+(j==i?words[j].length():words[j].length()+1)>maxWidth) break; 12 else len+=(j==i?words[j].length():words[j].length()+1); 13 //cout<<words[j]<<" "<<len<<endl; 14 } 15 num=j-i; 16 //the next step is to caculate the number of " "between each words 17 numspace=maxWidth-len+num-1; 18 if(num!=1) avnumspace=numspace/(num-1); 19 else avnumspace=numspace; 20 if(num!=1) extraspace=numspace%(num-1); 21 else extraspace=0; 22 //printf("%d %d %d %d %d ",num,numspace,avnumspace,extraspace,len); 23 string s=words[i]; 24 if(i+num==n){ 25 for(j=i+1;j<i+1+num-1;j++){ 26 s=s+" "+words[j];} 27 numspace-=num-1; 28 while(numspace>0)s+=" ",numspace--; 29 30 } 31 else{ 32 33 if(num==1){ 34 for(int u=0;u<avnumspace;u++){ 35 s=s+" "; 36 } 37 } 38 for(j=i+1;j<i+1+num-1;j++){ 39 for(int u=0;u<avnumspace;u++){ 40 s=s+" "; 41 } 42 if(extraspace>0) s+=" ",extraspace--; 43 s+=words[j]; 44 } 45 } 46 47 //cout<<s<<endl; 48 ans.push_back(s); 49 } 50 return ans; 51 } 52 };
71.哇！这题厉害了，大意就是unix路径简化，以前好像在CCF上写过，但是写的一坨，看了discuss后发现C++有个分离函数，爽死了 ****
72 修改字符串使之成为相同的，可以增改删 ******************
1 class Solution { 2 public: 3 int minDistance(string word1, string word2) { 4 int dp[1005][1005]; 5 int len1 = word1.length(); 6 int len2 = word2.length(); 7 int i,j; 8 for(i=0;i<=len1;i++){ 9 dp[i][0]=i; 10 } 11 for(i=0;i<=len2;i++){ 12 dp[0][i]=i; 13 } 14 for(int i=1;i<=len1;i++){ 15 for(int j=1;j<=len2;j++){ 16 dp[i][j]=min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1))); 17 } 18 } 19 return dp[len1][len2]; 20 } 21 };
75.对于只包含0,1,2的数组排序，一种方法是设置01,2的分解index，另一种是记录前面的0，1,2个数，值得一看的题**************
76. 想了个方法但比较难实现，先mark
79.观察一个二维字符数组中是否存在一个字符串 回溯
1 class Solution { 2 public: 3 bool flag=0; 4 int n,m; 5 int len; 6 vector<vector<char>> board1; 7 string word1; 8 bool vis[1000][1000]; 9 void dfs(int h,int w,int pos){ 10 //printf("%d %d %d ",h,w,pos); 11 bool b1=0,b2=0,b3=0,b4=0; 12 if(flag==1) return; 13 if(pos==len){ 14 flag=1; 15 return; 16 } 17 if(h+1<n&&board1[h+1][w]==word1[pos]&&!vis[h+1][w]) b1=1,vis[h+1][w]=1,dfs(h+1,w,pos+1); 18 if(b1) vis[h+1][w]=0; 19 if(h-1>=0&&board1[h-1][w]==word1[pos]&&!vis[h-1][w]) b2=2,vis[h-1][w]=1,dfs(h-1,w,pos+1); 20 if(b2) vis[h-1][w]=0; 21 if(w-1>=0&&board1[h][w-1]==word1[pos]&&!vis[h][w-1]) b3=3,vis[h][w-1]=1,dfs(h,w-1,pos+1); 22 if(b3) vis[h][w-1]=0; 23 if(w+1<m&&(board1[h][w+1]==word1[pos])&&!vis[h][w+1]) b4=4,vis[h][w+1]=1,dfs(h,w+1,pos+1); 24 if(b4) vis[h][w+1]=0; 25 26 } 27 28 bool exist(vector<vector<char>>& board, string word) { 29 n=board.size(); 30 m=board[0].size(); 31 len=word.length(); 32 board1=board; 33 word1=word; 34 memset(vis,0,sizeof(vis)); 35 if(n*m<len) return false; 36 for(int i=0;i<n;i++){ 37 for(int j=0;j<m;j++){ 38 if(board[i][j]==word[0]) vis[i][j]=1,dfs(i,j,1); 39 vis[i][j]=0; 40 } 41 } 42 return flag; 43 } 44 };
84.嘎嘎嘎，单调栈水题
1 class Solution { 2 public: 3 int largestRectangleArea(vector<int>& heights) { 4 pair<int,int> ele[50000]; 5 int height, n; 6 n=heights.size(); 7 int w; 8 int i,j,k; 9 int ans, tot, tmp; 10 int top=0; 11 ans = 0; 12 for(i=0;i<n;i++){ 13 tmp=0; 14 w=heights[i]; 15 while(top>0&&w<ele[top-1].first){ 16 int aans=ele[top-1].first*(ele[top-1].second+tmp); 17 ans=max(ans,aans); 18 tmp+=ele[top-1].second; //这个比较容易忘，这是当前累计的加上之前累计的 19 top--; 20 } 21 ele[top].first=w; 22 ele[top].second=1+tmp; 23 top++; 24 } 25 tmp=0; 26 while(top>0){ 27 int aans=ele[top-1].first*(ele[top-1].second+tmp); 28 ans=max(ans,aans); 29 tmp+=ele[top-1].second; 30 top--; 31 } 32 return ans; 33 } 34 };
87.递归
1 class Solution { 2 public: 3 int c[30]; 4 bool isScramble1(string s1, string s2) { 5 //cout<<s1<<" "<<s2<<endl; 6 for(int i=0;i<26;i++){ 7 c[i]=0; 8 } 9 for(int i=0;i<s1.length();i++){ 10 c[s1[i]-'a']++; 11 c[s2[i]-'a']--; 12 } 13 for(int i=0;i<26;i++){ 14 if(c[i]!=0) return false; 15 } 16 string ss1=s1; 17 reverse(ss1.begin(),ss1.end()); 18 if(ss1==s2) return true; 19 if(s1==s2) return true; 20 else if(s1!=s2&&s1.length()==1) return false; 21 else{ 22 bool flag=0; 23 for(int i=1;i<s1.length();i++){ 24 //printf("%d %d ",i,s1.length()); 25 string s1l,s2l,s1r,s2r,s1lr,s1rr; 26 27 s1l=s1.substr(0,i); 28 s1r=s1.substr(i); 29 s2l=s2.substr(0,i); 30 s2r=s2.substr(i); 31 s1lr=s1l; 32 reverse(s1lr.begin(),s1lr.end()); 33 s1rr=s1r; 34 reverse(s1rr.begin(),s1rr.end()); 35 //cout<<s1l<<" "<<s1r<<" "<<s2l<<" "<<s2r<<" "<<s1lr<<" "<<s1rr<<" "<<s1<<" "<<s2<<endl; 36 if( (isScramble1(s1l,s2l)||isScramble1(s1lr,s2l))&&(isScramble1(s1r,s2r)||isScramble1(s1rr,s2r))){ 37 flag=1; 38 if(flag) break; 39 } 40 } 41 return flag; 42 43 } 44 } 45 bool isScramble(string s1,string s2){ 46 string ss1=s1; 47 reverse(ss1.begin(),ss1.end()); 48 return isScramble1(s1,s2)||isScramble1(ss1,s2); 49 } 50 };
89.格雷码 *****
90.interesting
1 /* 2 I think it's a truly interesting problem. In the last problem----Subsets,it's integers are dinstinct, so there is no need to consider the duplicate subsets, but in this problem, we need to take this into acount. 3 Let's try to see why does duplicate subsets emerge. 4 For example, For the nums=[1,2,2,3,3],we use primary ways to solve it, we can get [],[1],[1,2],[1,2,2],[1,2,2,3],[1,2,2,3,3] in turn, and from now on, we should backtrack, we got [1,2,2,3], this '3' comes from the second of '3's,and the duplicae subsets emerge. 5 So how can we avoid situation? Try to think about this, we have used '3', so we can't use it again, it means we can't use '3' if we have used it before. so we can add "if(nums[i]==nums[i-1]) continue;", but another problem happened, the subset[1,2,2,3] is abosolutely fit in the require, but '2' happened twice, so we must reserve the succussive value i!=num+1. Finally, we got the right answer successfully! 6 */ 7 8 class Solution { 9 public: 10 void dfs(int pos,int num,vector<int> ans1,vector<vector<int> >&finans,int n,vector<int> nums){ 11 finans.push_back(ans1); 12 for(int i=num+1;i<n;i++){ 13 if(nums[i]==nums[i-1]&&i!=num+1) continue; 14 ans1.push_back(nums[i]); 15 dfs(pos+1,i,ans1,finans,n,nums); 16 ans1.pop_back(); 17 } 18 } 19 vector<vector<int>> subsetsWithDup(vector<int>& nums) { 20 vector<vector<int> > finans; 21 sort(nums.begin(),nums.end()); 22 int n=nums.size(); 23 vector<int> ans1; 24 finans.push_back(ans1); 25 for(int i=0;i<n;i++){ 26 if(nums[i]==nums[i-1]&&i!=0) continue; 27 ans1.push_back(nums[i]); 28 dfs(0,i,ans1,finans,n,nums); 29 ans1.pop_back(); 30 } 31 return finans; 32 } 33 };
98.判断二叉查找树， 中序遍历二叉查找树可得到一个关键字的有序序列。或者记录low high