1.两数之和
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { map<int,int> st; int len=nums.size(); for (int i=0;i<len;i++){ if (st.find(target-nums[i])==st.end()) st[nums[i]]=i; else return {st[target-nums[i]],i}; } return {-1,-1}; } };
2.两数相加
给你两个非空的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。
请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *head=NULL; ListNode *tail=NULL; int c=0; int sum=0; while(l1!=NULL||l2!=NULL){ int num1=l1?l1->val:0; int num2=l2?l2->val:0; sum=num1+num2+c; if(!head) head=tail=new ListNode(sum%10); else{ tail->next=new ListNode(sum%10); tail=tail->next; } c=sum/10; if(l1) l1=l1->next; if(l2) l2=l2->next; } if(c>0) tail->next=new ListNode(c); return head; } };
3. 无重复字符的最长子串
class Solution { public: int lengthOfLongestSubstring(string s) { set<char> st; int len=s.size(); int ans=0; int r=-1; for(int i=0;i<len;i++){ if (i!=0) st.erase(s[i-1]); while(r+1<len&&st.find(s[r+1])==st.end()) st.insert(s[++r]); ans=max(ans,r-i+1); } return ans; } };
4. 寻找两个正序数组的中位数
给定两个大小分别为 m 和 n 的正序(从小到大)数组nums1 和 nums2。请你找出并返回这两个正序数组的中位数.算法的时间复杂度应该为 O(log(m+n))。
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int tot=nums1.size()+nums2.size(); if (tot%2==0){ int left=find(nums1,0,nums2,0,tot/2); int right=find(nums1,0,nums2,0,tot/2+1); return (left+right)/2.0; } else return (double)find(nums1,0,nums2,0,tot/2+1); } int find(vector<int> &nums1,int i,vector<int> &nums2,int j,int k){ if (nums1.size()-i>nums2.size()-j) return find(nums2,j,nums1,i,k); if (k==1){ if (nums1.size()==i) return nums2[j]; else return min(nums1[i],nums2[j]); } if (nums1.size()==i) return nums2[j+k-1]; int si=min((int)nums1.size(),i+k/2); int sj=j+k/2; if (nums1[si-1]>nums2[sj-1]) return find(nums1,i,nums2,sj,k-(sj-j)); else return find(nums1,si,nums2,j,k-(si-i)); } };
5.最长回文子串
class Solution { public: string longestPalindrome(string s) { int n=s.size(); string res; for(int i=0;i<n;i++){ int l=i-1,r=i+1; while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++; if (r-1-l>res.size()) res=s.substr(l+1,r-1-l); l=i,r=i+1; while(l>=0&&r<s.size()&&s[l]==s[r]) l--,r++; if (r-1-l>res.size()) res=s.substr(l+1,r-1-l); } return res; } };
10. 正则表达式匹配
给你一个字符串s 和一个字符规律p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
class Solution { public: bool f[35][35]; bool isMatch(string s, string p) { int n=s.size(); int m=p.size(); s=' '+s; p=' '+p; f[0][0]=1; for(int i=0;i<=n;i++){ for(int j=1;j<=m;j++){ if (j+1<=m&&p[j+1]=='*') continue; if (i&&p[j]!='*') f[i][j]=f[i-1][j-1]&&(s[i]==p[j]||p[j]=='.'); else if (p[j]=='*') f[i][j]=f[i][j-2]||(i&&f[i-1][j])&&(s[i]==p[j-1]||p[j-1]=='.'); } } return f[n][m]; } };
11. 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第i 条线的两个端点是(i,0) 和 (i,height[i]) 。
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
class Solution { public: int maxArea(vector<int>& height) { int i=0; int j=height.size()-1; int maxa=min(height[i],height[j])*(j-i); while(i<j){ int a=min(height[i],height[j])*(j-i); maxa=max(maxa,a); if(height[i]<height[j]) i++; else j--; } return maxa; } };
15. 三数之和
给你一个包含 n 个整数的数组 nums,判断nums 中是否存在三个元素a,b,c ,使得a+b+c=0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { set<vector<int>> resbuf; int n=nums.size(); sort(nums.begin(),nums.end()); for(int i=0;i<n-1;i++){ if (i>0&&nums[i]==nums[i-1]) continue; int l=i+1,r=n-1; while(l<r){ if (nums[l]+nums[i]+nums[r]>0) r--; else if (nums[l]+nums[i]+nums[r]<0) l++; else if (nums[l]+nums[i]+nums[r]==0){ resbuf.insert({nums[i],nums[l],nums[r]}); l++; } } } vector<vector<int> > res; for(auto node:resbuf) res.push_back(node); return res; } };
17. 电话号码的字母组合
给定一个仅包含数字2−9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意1 不对应任何字母。
class Solution { public: set<char> sc[11]; int n; vector<string> ans; string digits; void dfs(int i,string res){ if (i==n){ ans.push_back(res); return; } for (char ch:sc[digits[i]-'0']) dfs(i+1,res+ch); return; } vector<string> letterCombinations(string digits) { if (digits=="") return ans; this->digits=digits; sc[2]={'a','b','c'}; sc[3]={'d','e','f'}; sc[4]={'g','h','i'}; sc[5]={'j','k','l'}; sc[6]={'m','n','o'}; sc[7]={'p','q','r','s'}; sc[8]={'t','u','v'}; sc[9]={'w','x','y','z'}; n=digits.size(); string res=""; dfs(0,res); return ans; } };
19. 删除链表的倒数第 N NN 个结点
class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode* dummy=new ListNode(0,head); ListNode *first=head; for(int i=0;i<n;i++) first=first->next; ListNode *second=dummy; while(first!=NULL){ first=first->next; second=second->next; } ListNode *p=second->next; second->next=p->next; delete p; head=dummy->next; return head; } };
20. 有效的括号
class Solution { public: bool check(char c1,char c2){ if (c1=='('&&c2==')'||c1=='{'&&c2=='}'||c1=='['&&c2==']') return true; else return false; } bool isValid(string s) { int i=0; stack<char> stk; for (int i=0;i<s.size();i++){ if (!stk.empty()&&check(stk.top(),s[i])) stk.pop(); else stk.push(s[i]); } if (stk.empty()) return true; else return false; } };
21. 合并两个有序链表
class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode *dummy=new ListNode(-1); ListNode *tail=dummy; while(list1&&list2){ if (list1->val<list2->val){ tail->next=list1; tail=tail->next; list1=list1->next; } else { tail->next=list2; tail=tail->next; list2=list2->next; } } if (list1!=NULL) tail->next=list1; if (list2!=NULL) tail->next=list2; return dummy->next; } };
22. 括号生成
class Solution { public: string str; vector<string> res; int len; void dfs(int left,int right){ if (len*2==str.size()){ res.push_back(str); return ; } if (left<len){ str.push_back('('); dfs(left+1,right); str.pop_back(); } if (right<left){ str.push_back(')'); dfs(left,right+1); str.pop_back(); } } vector<string> generateParenthesis(int n) { len=n; dfs(0,0); return res; } };
23. 合并K KK个升序链表
class Solution { public: struct cmp{ bool operator()(ListNode *a,ListNode*b){ return a->val>b->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode *,vector<ListNode *>,cmp> pq; ListNode *dummy=new ListNode(-1,NULL); ListNode *tail=dummy; for(auto list:lists) if (list) pq.push(list); while(!pq.empty()){ auto p=pq.top(); pq.pop(); tail->next=p; tail=tail->next; if (p->next!=NULL){ pq.push(p->next); p=p->next; } } return dummy->next; } };
31. 下一个排列
class Solution { public: void nextPermutation(vector<int>& nums) { int n=nums.size(); int k=n-1; while(k>0&&nums[k-1]>=nums[k]) k--; if (k<=0){ reverse(nums.begin(),nums.end()); return; } int t=k; while(t<n&&nums[t]>nums[k-1]) t++; swap(nums[t-1],nums[k-1]); sort(nums.begin()+k,nums.end()); return; } };
32. 最长有效括号
class Solution { public: int longestValidParentheses(string s) { stack<int> stk; int ans=0; stk.push(-1); int maxlen=s.size(); for (int i=0;i<maxlen;i++){ if (s[i]=='(') stk.push(i); else{ stk.pop(); if (stk.empty()) stk.push(i); else ans=max(ans,i-stk.top()); } } return ans; } };
33. 搜索旋转排序数组
class Solution { public: int search(vector<int>& nums, int target) { if (nums.empty()) return -1; int l = 0, r = nums.size() - 1; while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] >= nums[0]) l = mid; else r = mid - 1; } if (target >= nums[0]) l = 0; else l = r + 1, r = nums.size() - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } if (nums[r] == target) return r; return -1; } };
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if(nums.size()==0) return {-1,-1}; int l=0; int r=nums.size()-1; while(l<r){ int m=(l+r)/2; if (nums[m]>=target) r=m; else l=m+1; } int L=l; if(nums[l]!=target) return {-1,-1}; l=0; r=nums.size()-1; while(l<r){ int m=(l+r+1)/2; if(nums[m]<=target) l=m; else r=m-1; } int R=r; return {L,R}; } };
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数target ,找出candidates 中可以使数字和为目标数 target 的所有不同组合 ,并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同,则两种组合是不同的。
对于给定的输入,保证和为target 的不同组合数少于 150 个。
class Solution { public: vector<int> candidates; vector<vector<int>> res; vector<int> tempres; int n; void dfs(int sum,int i){ if (i>=n) return; if (sum==0){ res.push_back(tempres); return; } if (sum>=candidates[i]){ tempres.push_back(candidates[i]); dfs(sum-candidates[i],i); tempres.pop_back(); dfs(sum,i+1); } else dfs(sum,i+1); } vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end(),greater<int>()); n=candidates.size(); this->candidates=candidates; dfs(target,0); return res; } };
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
class Solution { public: int trap(vector<int>& height) { int ans=0; stack<int> stk; int maxlen=height.size(); for (int i=0;i<maxlen;i++){ while(!stk.empty()&&height[i]>height[stk.top()]){ int h=stk.top(); stk.pop(); if (stk.empty()) break; int left=stk.top(); int w=i-left-1; int ht=min(height[left],height[i])-height[h]; ans+=w*ht; } stk.push(i); } return ans; } };
46. 全排列
class Solution { vector<vector<int> >res; bool st[10]; int len; vector<int> vct; vector<int> nm; public: void dfs(int n){ if (n==len) res.push_back(vct); for (int i=0;i<len;i++){ if(!st[i]){ st[i]=true; vct.push_back(nm[i]); dfs(n+1); st[i]=false; vct.pop_back(); } } } vector<vector<int>> permute(vector<int>& nums) { len=nums.size(); nm=nums; dfs(0); return res; } };
48. 旋转图像
给定一个 $n × n $的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
class Solution { public: void rotate(vector<vector<int>>& matrix) { int n=matrix.size(); for(int i=0;i<n/2;i++){ for(int j=0;j<n;j++) swap(matrix[i][j],matrix[n-i-1][j]); } for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ swap(matrix[i][j],matrix[j][i]); } } } };
49. 字母异位词分组
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母通常恰好只用一次。
class Solution { public: map<map<char,int>,vector<string>> resbuf; vector<vector<string>> groupAnagrams(vector<string>& strs) { for(auto str:strs){ map<char,int> tempset; for(auto ch:str) tempset[ch]++; resbuf[tempset].push_back(str); } vector<vector<string> > res; for(auto node:resbuf){ vector<string> resbuf; for(auto str:node.second) resbuf.push_back(str); res.push_back(resbuf); } return res; } };
53. 最大子数组和
class Solution { public: int maxSubArray(vector<int>& nums) { int len=nums.size(); vector<int> dp(len); dp[0]=nums[0]; for (int i=1;i<len;i++){ if (dp[i-1]>=0) dp[i]=dp[i-1]+nums[i]; else dp[i]=nums[i]; } int res=-0x3f3f3f3f; for (int i=0;i<len;i++) res=max(res,dp[i]); return res; } };
55. 跳跃游戏
给定一个非负整数数组nums ,你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
class Solution { public: bool canJump(vector<int>& nums) { int n=nums.size(); int rightmost=0; for(int i=0;i<=rightmost;i++){ rightmost=max(rightmost,i+nums[i]); if (rightmost>=n-1) return true; } return false; } };
56. 合并区间
以数组intervals 表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { sort(intervals.begin(),intervals.end()); int st=intervals[0][0],ed=intervals[0][1]; vector<vector<int>> res; int n=intervals.size(); for(int i=0;i<n;i++){ if (i&&intervals[i][0]>ed){ res.push_back({st,ed}); st=intervals[i][0]; ed=intervals[i][1]; } if (intervals[i][0]<=ed&&intervals[i][1]>=ed) ed=intervals[i][1]; } res.push_back({st,ed}); return res; } };
72. 编辑距离
给你两个单词word1 和 word2, 请返回将 word1 转换成 word2 所使用的最少操作数 。
可以对一个单词进行如下三种操作:
插入一个字符
删除一个字符
替换一个字符
class Solution { public: int dp[501][501]; int minDistance(string word1, string word2) { int len1=word1.size(); int len2=word2.size(); if(len1*len2==0) return len1+len2; for(int i=0;i<=len1;i++) dp[i][0]=i; for(int j=0;j<=len2;j++) dp[0][j]=j; for(int i=1;i<=len1;i++) for(int j=1;j<=len2;j++){ if (word1[i-1]==word2[j-1]) dp[i][j]=dp[i-1][j-1]; else dp[i][j]=min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1; } return dp[len1][len2]; } };
75. 荷兰国旗
class Solution { public: void sortColors(vector<int>& nums) { for(int i=0,j=0,k=nums.size()-1;i<=k;){ if (nums[i]==0) swap(nums[i++],nums[j++]); else if (nums[i]==2) swap(nums[i],nums[k--]); else i++; } } };
76. 最小覆盖子串
给你一个字符串s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t tt所有字符的子串,则返回空字符串 “” 。
class Solution { public: string minWindow(string s, string t) { map<char,int> hs,ht; for(auto c:t) ht[c]++; string res; int n=s.size(); int cnt=0; for(int i=0,j=0;i<n;i++){ hs[s[i]]++; if (hs[s[i]]<=ht[s[i]]) cnt++; while(hs[s[j]]>ht[s[j]]) hs[s[j++]]--; if (cnt==t.size()) if (res.empty()||i-j+1<res.size()) res=s.substr(j,i-j+1); } return res; } };
78. 子集
给你一个整数数组nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; int n=nums.size(); for(int mask=0;mask<(1<<n);mask++){ vector<int> tempres; for(int i=0;i<n;i++) if (mask>>i&1) tempres.push_back(nums[i]); res.push_back(tempres); } return res; } };
79. 单词搜索
给定一个mxn 二维字符网格 board 和一个字符串单词 word 。如果word 存在于网格中,返回 true ;否则,返回 false 。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
class Solution { public: bool st[10][10]; string word; vector<vector<char>> board; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int m,n; bool dfs(int i,int j,int pos){ if (pos==word.size()) return true; for(int k=0;k<4;k++){ int px=i+dx[k]; int py=j+dy[k]; if (px<0||px>=m||py<0||py>=n) continue; if (st[px][py]) continue; if (word[pos]==board[px][py]){ st[px][py]=1; if (dfs(px,py,pos+1)) return true; st[px][py]=0; } } return false; } bool exist(vector<vector<char>>& board, string word) { m=board.size(); n=board[0].size(); this->word=word; this->board=board; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if (board[i][j]==word[0]){ st[i][j]=1; if (dfs(i,j,1)) return true; st[i][j]=0; } } } return false; } };