首先记录下nums1中出现过的数字，如果nums2中也出现就将其加入到集合中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : vector <int > intersection (vector <int >& nums1, vector <int >& nums2) unordered_map <int ,int > map ; unordered_set <int > set ; for (auto var :nums1) { map [var] = 1 ; } for (auto var :nums2) { if (map .find(var)!=map .end()) { set .insert(var); } } return vector <int >(set .begin(),set .end()); } };
845-数组中的最长山脉 的简化版本
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : bool validMountainArray (vector <int >& A) if (A.size()<3 ) return false ; int i,j; for (i=1 ;i<A.size()&&A[i]>A[i-1 ];i++); for (j=i;j<A.size()&&A[j]<A[j-1 ];j++); if (i!=1 && j !=i && j==A.size()) return true ; return false ; } };
虽然标记是hard，感觉还是挺简单的，只是条件处理稍稍多了一点
判断要插入的区间的左右端点，在原先的区间列表中的位置，在分各种情况讨论，选择插入区间或者合并区间插入。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution {public : vector <vector <int >> insert(vector <vector <int >>& intervals, vector <int >& newInterval) { vector <vector <int >> rets; int i=0 ; while (i<intervals.size()&&intervals[i][1 ]<newInterval[0 ]) { rets.push_back(intervals[i]); i++; } int j= i; while (j<intervals.size()&&intervals[j][1 ]<newInterval[1 ]) j++; if (i==intervals.size()) { rets.push_back(newInterval); return rets; } if (j==intervals.size()) { if (intervals[i][0 ]>newInterval[0 ]) rets.push_back(newInterval); else rets.push_back(vector <int >({intervals[i][0 ],newInterval[1 ]})); return rets; } if (intervals[i][0 ]>newInterval[0 ]&&intervals[j][0 ]>newInterval[1 ]) rets.push_back(newInterval); else if (intervals[i][0 ]>newInterval[0 ]) { rets.push_back(vector <int >({newInterval[0 ],intervals[j][1 ]})); j++; } else if (intervals[j][0 ]>newInterval[1 ]) { rets.push_back(vector <int >({intervals[i][0 ],newInterval[1 ]})); } else { rets.push_back(vector <int >({intervals[i][0 ],intervals[j][1 ]})); j++; } while (j<intervals.size()) { rets.push_back(intervals[j]); j++; } return rets; } };
补上昨天的
采用图的广度优先遍历算法，但是一直是最后一个用例超时
采用双端广度优先算法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 class Solution {public : int ladderLength (string beginWord, string endWord, vector <string >& wordList) int len = wordList.size(); int str_len = beginWord.size(); vector <int > visit (len) vector <int > visit1 (len) int layer = 0 ; queue <string > q,q1; q.push(beginWord); for (int i=0 ;i<wordList.size();i++) { if (wordList[i]==endWord) { q1.push(endWord); visit1[i] = 1 ; } } if (q1.empty()) return 0 ; while ((!q.empty())&&(!q1.empty())) { layer++; for (int sz = q.size();sz>0 ;sz--) { string j = q.front(); q.pop(); for (int k=0 ;k<len;k++) { if (visit[k] ==0 && Judge(j,wordList[k],str_len)) { visit[k] = 1 ; q.push(wordList[k]); if (visit1[k]==1 ) return layer*2 ; } } } for (int sz = q1.size();sz>0 ;sz--) { string j = q1.front(); q1.pop(); for (int k=0 ;k<len;k++) { if (visit1[k] ==0 && Judge(j,wordList[k],str_len)) { visit1[k] = 1 ; q1.push(wordList[k]); if (visit[k]==1 ) return layer*2 + 1 ; } } } } return 0 ; } int Judge (string key,string end,int len) { int sum = 0 ; for (int i=0 ;i<len;i++) { if (key[i]!=end[i]) sum++; } return sum==1 ; } };
先统计每个数字的二进制下1的数目，计数可以参考338. 比特位计数 ,或者直接位运算
对每个数字根据1的数目进行排序，可以选用计数排序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : vector <int > sortByBits (vector <int >& arr) vector <int > res (arr.size()) vector <int > cnt (arr.size()) int dt[34 ]={0 }; sort(arr.begin(),arr.end()); for (int i=0 ;i<arr.size();i++) { cnt[i] = GetBits(arr[i]); dt[cnt[i]+1 ]++; } for (int i=1 ;i<34 ;i++) { dt[i] += dt[i-1 ]; } for (int i=0 ;i<arr.size();i++) { res[dt[cnt[i]]++] = arr[i]; } return res; } int GetBits (int i) { int sum = 0 ; while (i) { sum += i&1 ; i=i>>1 ; } return sum; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int countRangeSum (vector <int >& nums, int lower, int upper) int res = 0 ; int len = nums.size(); for (int i=0 ;i<len;i++) { long sum = 0 ; for (int j=i;j<len;j++) { sum+=nums[j]; res += sum>=lower&&sum<=upper; } } return res; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 class Solution {public : int Merge (vector <long > &sum,int lower,int upper,int left,int right) { if (left==right) return 0 ; int mid = (left+right)/2 ; int res=Merge(sum,lower,upper,left,mid)+Merge(sum,lower,upper,mid+1 ,right); int i=left; int l = mid+1 ; int r = mid+1 ;; while (i<=mid) { while (l<=right&&sum[l]-sum[i]<lower) l++; while (r<=right&&sum[r]-sum[i]<=upper) r++; res+=r-l; i++; } vector <long > sort (right-left+1 ) int p=0 ,p1 = left,p2 = mid+1 ; while (p1<=mid||p2<=right) { if (p1>mid) sort[p++] = sum[p2++]; else if (p2>right) sort[p++]= sum[p1++]; else { if (sum[p1]>sum[p2]) sort[p++] = sum[p2++]; else sort[p++]= sum[p1++]; } } for (int i=left;i<=right;i++) { sum[i] = sort[i-left]; } return res; } int countRangeSum (vector <int >& nums, int lower, int upper) vector <long > sum (nums.size()+1 ) long s = 0 ; sum[0 ]=0 ; for (int i=0 ;i<nums.size();i++) { s+=nums[i]; sum[i+1 ] = s; } return Merge(sum,lower,upper,0 ,sum.size()-1 ); } };
如果今天比昨天售价低，就假设今天买入，然后找到与今天连续的价格最高的点，然后卖出加到盈利里面，然后再假设在最高点后一天再买入，如果没有连续的比今天价格高的点，就假设明天买入。
另一种的是简化，只要今天比昨天大，就卖出。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int maxProfit (vector <int >& prices) if (prices.size()<2 ) return 0 ; int buy= prices[0 ]; int profit = 0 ; for (int i=1 ;i<prices.size();i++) { if (prices[i]<prices[i-1 ]) { profit += prices[i-1 ]-buy>0 ? prices[i-1 ]-buy:0 ; buy = prices[i]; } } profit += prices[prices.size()-1 ]-buy>0 ? prices[prices.size()-1 ]-buy:0 ; return profit; } };
先计算出所有的欧几里德距离
然后将他们的索引进行排序，前K个就是题目所求
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : vector <vector <int >> kClosest(vector <vector <int >>& points, int K) { vector <double > keys (points.size()) vector <int > indexes (points.size()) for (int i=0 ;i<keys.size();i++) { keys[i] = sqrt (points[i][0 ]*points[i][0 ] +points[i][1 ]*points[i][1 ] ); indexes[i] = i; } sort(indexes.begin(),indexes.end(),[&](int x,int y){return keys[x]<keys[y];}); vector <vector <int >> res(K); for (int i=0 ;i<K;i++) { res[i] = points[indexes[i]]; } return res; } };
第二部排序中可以借鉴使用快速排序，边排序边排除不符合要求的。期望的时间复杂度O(n)
题目的意思是，对于一个排列组成的数，找到一个只比这个数大的
从后往前找，找到第一个n u m s [ i ] > n u m s [ i − 1 ] nums[i]>nums[i-1] n u m s [ i ] > n u m s [ i − 1 ]
然后从i开始往后找，找一个最小的，但是比n u m s [ i − 1 ] nums[i-1] n u m s [ i − 1 ] n u m s [ i − 1 ] nums[i-1] n u m s [ i − 1 ]
对于i以及之后的数，必然是一个降序的序列，进行反转后就得到这个数了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution {public : void nextPermutation (vector <int >& nums) int len = nums.size(); int i; for (i=len-1 ;i>0 ;i--) { if (nums[i]>nums[i-1 ]) { int j=i; for (;j<len&&nums[j]>nums[i-1 ];j++); swap(nums[j-1 ],nums[i-1 ]); reverse(nums.begin()+i,nums.end()); break ; } } if (i==0 ) sort(nums.begin(),nums.end()); } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : int findRotateSteps (string ring, string key) return key.size() + min(Deep(ring,key,0 ,0 ,0 ),Deep(ring,key,0 ,0 ,1 )); } int Deep (string ring, string key,int ri,int ki,int direct) { if (ki==key.size()) return 0 ; int i=0 ,k; if (direct==0 ) { while (i<ring.size()&&ring[(ri+i)%ring.size()]!=key[ki]) i++; k = (ri+i)%ring.size(); } else { while (i<ring.size()&&ring[(ri+ring.size()-i)%ring.size()]!=key[ki]) i++; k = (ri+ring.size()-i)%ring.size(); } return i + min(Deep(ring,key,k,ki+1 ,0 ),Deep(ring,key,k,ki+1 ,1 )); } };
-动态规划，见题解
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int findRotateSteps (string ring, string key) vector <vector <int >> dp(key.size(),vector <int >(ring.size(),0x3f3f3f3f )) ; vector <int > pos[26 ]; int m = key.size(); int n = ring.size(); for (int i=0 ;i<ring.size();i++) { pos[ring[i]-'a' ].push_back(i); } for (auto & var :pos[key[0 ]-'a' ]) { dp[0 ][var] = min(var, n - var) + 1 ; } for (int i=1 ;i<key.size();i++) { for (auto & j : pos[key[i]-'a' ]) { for (auto &k :pos[key[i-1 ]-'a' ]) dp[i][j] = min(dp[i][j],dp[i-1 ][k]+min(abs (j-k),(n-abs (j-k)))+1 ); } } return *min_element(dp[dp.size() - 1 ].begin(), dp[dp.size() - 1 ].end()); } };
==的优先级要高于&，再用这两个符号求一个数的奇偶性的时候，&运算符两侧操作数外要加()
从开始遍历，找到奇数偶数两种分别不符合条件的数，进行交换。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : vector <int > sortArrayByParityII (vector <int >& A) int i=0 ,j=1 ; while (i<A.size()&&j<A.size()) { while (i<A.size()&&(A[i]&1 )==0 ) i+=2 ; while (j<A.size()&&(A[j]&1 )==1 ) j+=2 ; if ((i<A.size()&&j<A.size())) swap(A[i],A[j]); i+=2 ; j+=2 ; } return A; } };
有一点点像昨天的题目，一次遍历分别奇偶节点串起来，最后两个链表连接
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution {public : ListNode* oddEvenList (ListNode* head) { if (!head) return head; ListNode *tail = head,*cur = head->next,*head2 = head->next; while (cur&&cur->next) { tail->next = cur->next; tail = tail->next; cur->next = tail->next; cur = cur->next; } tail->next = head2; return head; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : vector <int > relativeSortArray (vector <int >& arr1, vector <int >& arr2) unordered_map <int ,int > map ; for (auto var:arr1) { auto it = map .find(var); if (it==map .end()) map [var]=1 ; else map [var]++; } vector <int > res; for (auto var:arr2) { res.insert(res.end(),map [var],var); map .erase(var); } int x = res.size(); for (auto var:map ) res.insert(res.end(),var.second,var.first); sort(res.begin()+x,res.end()); return res; } };
从前向后遍历，如果前面一个数比后面大就将前面的这个数删掉。
前面一位变化的即使是 1 也比后面的变化为 9 的数变化大。
然后剩下的就是一些边界条件问题了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution {public : string removeKdigits (string num, int k) if (num.size()==k) return "0" ; int i; for (i=0 ;i<num.size()-1 ; i++) { if (num[i]>num[i+1 ] && k>0 ) { num.erase(num.begin()+i); k--; if (i>0 ) i--; i--; } } while (k-->0 ) num.erase(num.end()-1 ); i=0 ; while (i<num.size()-1 &&num[i]=='0' ) i++; num.erase(num.begin(),num.begin()+i); return num; } };
以身高为第一关键字，个数为第二关键字排序，
插入结果vector中，从最矮的人开始，对于一个人(h,k)，此时前面还未插入的/vector为空的人的身高一定高于h，没经过一个空时，k-1，直到k==0的这个空位就是这个人(h,k)所应该在的位置。
从目标所给点的曼哈顿距离为0开始，直到最大，每次将所有曼哈顿距离为此值的一圈矩阵值加到向量中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 class Solution {public : vector <vector <int >> allCellsDistOrder(int R, int C, int r0, int c0) { vector <vector <int >>res; res.push_back(vector <int >({r0,c0})); for (int i=1 ;i<=R+C;i++) { for (int x=0 ;x<=i;x++) { int y = i-x; int x1=r0+x,y1=c0+y; int x2=r0+x,y2=c0-y; int x3=r0-x,y3=c0+y; int x4=r0-x,y4=c0-y; if (x!=0 &&y!=0 ) { if (x1>=0 &&x1<R&&y1>=0 &&y1<C) res.push_back(vector <int >({x1,y1})); if (x2>=0 &&x2<R&&y2>=0 &&y2<C) res.push_back(vector <int >({x2,y2})); if (x3>=0 &&x3<R&&y3>=0 &&y3<C) res.push_back(vector <int >({x3,y3})); if (x4>=0 &&x4<R&&y4>=0 &&y4<C) res.push_back(vector <int >({x4,y4})); } else if (x==0 ) { if (x1>=0 &&x1<R&&y1>=0 &&y1<C) res.push_back(vector <int >({x1,y1})); if (x2>=0 &&x2<R&&y2>=0 &&y2<C) res.push_back(vector <int >({x2,y2})); } else { if (x2>=0 &&x2<R&&y2>=0 &&y2<C) res.push_back(vector <int >({x2,y2})); if (x3>=0 &&x3<R&&y3>=0 &&y3<C) res.push_back(vector <int >({x3,y3})); } } } return res; } };
如果汽车从某个点开始，他必须能到达所有加油站，先假设汽车从某个加油站开始，如果能到达下一个加油站就继续走，如果不能就再假设从下一个加油站开始走
汽车总耗油量必须小于等于加油站能加的汽油和
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int canCompleteCircuit (vector <int >& gas, vector <int >& cost) int run=0 ,all=0 ,begin=0 ; for (int i=0 ;i<gas.size();i++) { run+=gas[i]-cost[i]; all+=gas[i]-cost[i]; if (run<0 ) { run=0 ; begin=i+1 ; } } if (all<0 ) return -1 ; return begin; } };
双指针移动
对0进行计数，然后把数字发放到该放的位置
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution {public : void moveZeroes (vector <int >& nums) int begin=0 ; for (int i=0 ;i<nums.size();i++) { if (nums[i]) nums[begin++] = nums[i]; } for (;begin<nums.size();begin++) nums[begin]=0 ; } };
插入排序转化成链表的形式，维护一个有序列表，每次选择未排序部分的一个值插入到有序列表中对应的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 class Solution {public : ListNode* insertionSortList (ListNode* head) { if (!head) return head; ListNode *cur = head->next,*pos = head; pos->next=NULL ; while (cur!=NULL ) { while (pos->next&&pos->next->val<cur->val) pos=pos->next; if (pos->val>cur->val) { head=cur; cur=cur->next; head->next=pos; pos=head; } else { ListNode *temp = cur; cur=cur->next; temp->next=pos->next; pos->next=temp; pos=head; } } return head; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 class Solution {public : bool isAnagram (string s, string t) vector<int> sc(26),tc(26); for (auto c :s) sc[c-'a' ]++; for (auto c :t) tc[c-'a' ]++; for (int i=0 ;i<26 ;i++) { if (sc[i]!=tc[i]) return false ; } return true ; } };
首先对气球数组进行排序，排序的第一个key是气球开始坐标，第二个key是气球结束坐标。
贪心，首先，尽量往气球的结束位置射，对于两个有重叠部分的气球，前面的结束位置一定是大于后面的开始位置的，对于这种有重叠部分的气球，射箭的位置取这两个气球中结束位置较小的结束位置。否则只能射一支新箭。
解析中直接对气球结束坐标排序的思路更简便一些。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution {public : int findMinArrowShots (vector <vector <int >>& points) if (points.size()==0 ) return 0 ; if (points.size()==1 ) return 1 ; sort(points.begin(),points.end(),[&](vector <int > &x,vector <int > &y) { if (x[0 ]==y[0 ]) return x[1 ]<y[1 ]; return x[0 ]<y[0 ]; }); int arrs=1 ; int end = points[0 ][1 ]; for (int i=1 ;i<points.size();i++) { if (points[i][0 ]>end) { arrs++; end = points[i][1 ]; } else end = min(end,points[i][1 ]); } return arrs; } };
暴力直接求解
利用完全二叉树的性质和位运算，首先找到二叉树的层数，根据完全二叉树的性质通过二分法找到树最底层的最后一个节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution {public : int countNodes (TreeNode* root) if (!root) return 0 ; int n=0 ; TreeNode* cur=root; while (cur) {n++;cur=cur->left;} int low = 1 <<(n-1 ),high=(1 <<n)-1 ,mid; while (low<high) { mid = (high + low + 1 ) / 2 ; if (Exist(root,n-1 ,mid)) low = mid; else high = mid-1 ; } return low ; } bool Exist (TreeNode *root,int lev,int pos) { int bit = 1 <<(lev-1 ); while (root&&bit) { if (bit&pos) root = root->right; else root = root->left; bit=bit>>1 ; } return root!=NULL ; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution {public : string sortString (string s) vector <int > cnt (26 ) for (auto c:s) cnt[c-'a' ]++; int last = s.size(); string res = "" ; while (res.size()<s.size()) { for (int i=0 ;i<26 ;i++) { if (cnt[i]>0 ) { res+='a' +i; cnt[i]--; } } for (int i=25 ;i>=0 ;i--) { if (cnt[i]>0 ) { res+='a' +i; cnt[i]--; } } } return res; } };
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int maximumGap (vector <int >& nums) if (nums.size()<2 ) return 0 ; map <int ,bool > cnt; for (auto num:nums) { cnt[num]=true ; } int res=0 ,count=0 ; auto begin = cnt.begin(); for (auto it=++cnt.begin();it!=cnt.end();it++) { res=max(res,(it->first)-(begin->first)); begin=it; } return res; } };
使用桶排序完成数组在时间复杂度n内的排序，然后找到结果
先计算前两个组中的数相加，存到哈希表中，在计算后两个组中的数相加时，在哈希表中查看是否有四组之和为0的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution {public : int fourSumCount (vector <int >& A, vector <int >& B, vector <int >& C, vector <int >& D) int res=0 ; unordered_map <int ,unsigned short int > CD; for (int i=0 ;i<C.size();i++) { for (int j=0 ;j<D.size();j++) { CD[C[i]+D[j]]++; } } for (int i=0 ;i<A.size();i++) { for (int j=0 ;j<B.size();j++) { if (CD.find(-A[i]-B[j])!=CD.end()) res+=CD[-A[i]-B[j]]; } } return res; } };
1 2 3 4 5 6 7 8 9 10 class Solution {public : int largestPerimeter (vector <int >& A) sort(A.begin(),A.end()); for (int i=A.size()-1 ;i>1 ;i--) if (A[i-1 ]+A[i-2 ]>A[i]) return A[i]+A[i-1 ]+A[i-2 ]; return 0 ; } };
先判断字符串能否重构，出现次数最多的不能超过总数的一半(上取整)
然后以出现次数最多的字符构成字符串，其他的字符往这个字符串插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 class Solution {public : string reorganizeString (string S) vector <int > cnt (26 ) string res; int max_num=0 ; for (auto c :S) { cnt[c-'a' ]++; max_num = max(max_num,cnt[c-'a' ]); } if (2 *max_num>S.size() + 1 ) return "" ; for (int i=0 ;i<cnt.size(); i++) if (max_num==cnt[i]) { res = string (max_num,i+'a' ); cnt[i]=0 ; break ; } int pos=1 ; for (int i=0 ;i<cnt.size(); i++) { while (cnt[i]--) { res.insert(pos,1 ,'a' +i); pos+=2 ; if (pos>res.size()) pos=1 ; } } return res; } };
