简单模块#
1、两数之和#
简单题,用unordered_map<int,int> um;key为值,value为数组下标
遍历一遍,看um中是否有和为target的另一半,并且另一半的数组下标不能相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
unordered_map<int,int> um;
for(int i =0;i<nums.size();i++){
um[nums[i]]=i;
}
for(int i=0;i<nums.size();i++){
int k =target-nums[i];
if(um.count(k) && um[k]!=i){ //WA一次,没考虑um[k]!=i
res.push_back(i);
res.push_back(um[k]);
break;
}
}
return res;
}
};
|
20、有效的括号#
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:
bool isValid(string s) {
stack<char> st;
for(int i =0;i<s.length();i++){
if(s[i]=='('){
st.push(')');
}else if(s[i]=='['){
st.push(']');
}else if(s[i]=='{'){
st.push('}');
}else{
if(st.size()&&s[i]==st.top()){ //WA一次,没考虑st.size()
st.pop();
continue;
}else{
return false;
}
}
}
if(st.size()) return false;
else return true;
}
};
|
21、合并2个有序链表#
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:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode * dummy = new ListNode(0); //创建哑结点
ListNode * p = dummy; //新链表的工作指针
//如果两个都不为空
while(list1!=NULL&&list2!=NULL){
//先把list1中小的元素放到新链表中
if(list1->val<=list2->val){
p->next = list1;
list1=list1->next;
p=p->next;
}
else{
p->next = list2;
list2=list2->next;
p=p->next;
}
}
//如果list1空了,list2不空
if(list2!=NULL){
//把list2剩下部分放进去
p->next =list2;
}
//如果list2空了,list1不空
if(list1!=NULL){
//把list1剩下部分放进去
p->next = list1;
}
return dummy->next;
}
};
|
53、最大子数组和#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len = nums.size();
int dp[len];
int res = -10005;
dp[0]=nums[0];
for(int i =1;i<len;i++){
dp[i]=max(dp[i-1]+nums[i],nums[i]);
}
for(int i =0;i<len;i++){
res=max(res,dp[i]);
}
return res;
}
};
|
70、爬楼梯#
递归超时了
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
int get(int n){
if(n==1) return 1;
else if(n==2) return 2;
else return get(n-1)+get(n-2);
}
int climbStairs(int n) {
return get(n);
}
};
|
改用dp
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int dp[48];
int climbStairs(int n) {
dp[1]=1;
dp[2]=2;
for(int i =3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};
|
94、二叉树的中序遍历#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {
public:
vector<int> res;
void dfs(TreeNode* root){
if(root->left) dfs(root->left);
res.push_back(root->val);
if(root->right) dfs(root->right);
}
vector<int> inorderTraversal(TreeNode* root) {
if(root==nullptr) return res;
dfs(root);
return res;
}
};
|
101、对称二叉树#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
bool isSame(TreeNode* l,TreeNode* r){
if(!l&&!r) return true;
if(!l&&r||l&&!r) return false;
if(l->val==r->val){
return isSame(l->left,r->right)&&isSame(l->right,r->left);
}
return false;
}
bool isSymmetric(TreeNode* root) {
if(!root->left&&!root->right) return true;
if(root->left&&root->right) return isSame(root->left,root->right);
return false;
}
};
|
104、二叉树的最大深度#
dfs
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int dfs(TreeNode* root){
if(!root) return 0;
int l = 1+dfs(root->left);
int r = 1+dfs(root->right);
return max(l,r);
}
int maxDepth(TreeNode* root) {
return dfs(root);
}
};
|
bfs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int maxDepth(TreeNode* root) {
int res = 0;
if(!root) return res;
queue<TreeNode*> q;
q.push(root);
while(q.size()){
int len = q.size();
res++;
for(int i =0;i<len;i++){
auto t = q.front();
q.pop();
if(t->left) q.push(t->left);
if(t->right) q.push(t->right);
}
}
return res;
}
};
|
121、买卖股票的最佳时机#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int res =0;
int dp[n]; //dp[i]表示前i个元素中的最小元素
dp[0]=prices[0];
for(int i =1;i<n;i++){
dp[i]=min(prices[i],dp[i-1]);
}
for(int i =0;i<n;i++){
res=max(res,prices[i]-dp[i]);
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
//空间优化版本
class Solution {
public int maxProfit(int[] prices) {
if(prices.length <= 1)
return 0;
int min = prices[0], max = 0;
for(int i = 1; i < prices.length; i++) {
max = Math.max(max, prices[i] - min);
min = Math.min(min, prices[i]);
}
return max;
}
}
|
136、只出现一次的数#
1
2
3
4
5
6
7
8
9
10
|
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res=0;
for(int i =0;i<nums.size();i++){
res^=nums[i]; //2个相同的数异或为0,0异或任意一个数等于这个数
}
return res;
}
};
|
141、环形链表#
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *one =head;
ListNode *two = head;
while(two!=NULL&&two->next!=NULL){
one=one->next;two=two->next->next;
if(one==two) return true;
}
return false;
}
};
|
key:一快一慢 总会想见
155、最小栈#
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 MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
void push(int x) {
if (st.size() == 0) {
st.push({x, x});
} else {
st.push({x, min(x, st.top().second)});
}
}
void pop() {
st.pop();
}
int top() {
return st.top().first;
}
int getMin() {
return st.top().second;
}
private:
stack<pair<int, int>> st;
};
|
key:妙用pair
160、相交链表#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == NULL || headB == NULL) return NULL;
ListNode* curA = headA;
ListNode* curB = headB;
while(curA != curB) {
curA = curA == NULL ? headB : curA->next;
curB = curB == NULL ? headA : curB->next;
}
return curA;
}
};
|
key:我走过你来时的路
169、多数元素#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int majorityElement(vector<int>& nums) {
int m = nums[0];
int count =1;
for(int i =1;i<nums.size();i++){
if(nums[i]==m) count++;
else count--;
if(count==0){
m=nums[i];
count =1;
}
}
return m;
}
};
|
key:摩尔投票法
有一个对摩尔投票法非常形象的比喻:多方混战。
首先要知道,在任何数组中,出现次数大于该数组长度1/3的值最多只有两个。
我们把这道题比作一场多方混战,战斗结果一定只有最多两个阵营幸存,其他阵营被歼灭。数组中的数字即代表某士兵所在的阵营。
我们维护两个潜在幸存阵营A和B。我们遍历数组,如果遇到了属于A或者属于B的士兵,则把士兵加入A或B队伍中,该队伍人数加一。继续遍历。
如果遇到了一个士兵既不属于A阵营,也不属于B阵营,这时有两种情况:
情况一:A阵营和B阵营都还有活着的士兵,那么进行一次厮杀,参与厮杀的三个士兵全部阵亡:A阵营的一个士兵阵亡,B阵营的一个士兵阵亡,这个不知道从哪个阵营来的士兵也阵亡。继续遍历。
情况二:A阵营或B阵营已经没有士兵了。没有士兵的阵营暂时从地球上消失了。那么把当前遍历到的新士兵算作新的潜在幸存阵营,这个新阵营只有他一个人。继续遍历。
大战结束,最后A和B阵营就是初始人数最多的阵营。判断一下A,B的人数是否超过所有人数的三分之一就行了。
229、求众数2#
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
|
class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> ans;
int element1 = 0;
int element2 = 0;
int vote1 = 0;
int vote2 = 0;
for(auto num:nums){
if(vote1>0&&num==element1){
vote1++;
}else if(vote2>0&&num==element2){
vote2++;
}else if(vote1==0){
vote1++;
element1=num;
}else if(vote2==0){
vote2++;
element2=num;
}else{
vote1--;
vote2--;
}
}
int cnt1 = 0;
int cnt2 = 0;
for (auto & num : nums) {
if (vote1 > 0 && num == element1) {
cnt1++;
}
if (vote2 > 0 && num == element2) {
cnt2++;
}
}
// 检测元素出现的次数是否满足要求
if (vote1 > 0 && cnt1 > nums.size() / 3) {
ans.push_back(element1);
}
if (vote2 > 0 && cnt2 > nums.size() / 3) {
ans.push_back(element2);
}
return ans;
}
};
|
206、反转链表#
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* cur = NULL, *pre = head;
while (pre != NULL) {
ListNode* t = pre->next;
pre->next = cur;
cur = pre;
pre = t;
}
return cur;
}
};
|
226、翻转二叉树#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(!root) return nullptr;
TreeNode* t =root->left;
root->left=root->right;
root->right=t;
if(root->left){
invertTree(root->left);
}
if(root->right){
invertTree(root->right);
}
return root;
}
};
|
234、回文链表#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
bool isPalindrome(ListNode* head) {
stack<int> st;
ListNode* p = head;
while(p){
st.push(p->val);
p=p->next;
}
while(head){
if(head->val!=st.top()) return false;
head=head->next;
st.pop();
}
return true;
}
};
|
283、移动零#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int len = nums.size();
int j=0;
for(int i=0;i<len;i++){
if(nums[i]!=0){
nums[j]=nums[i];
j++;
}
}
for(;j<len;j++){
nums[j]=0;
}
}
};
|
338、比特位计数#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
vector<int> countBits(int n) {
vector<int> res(n+1);
for(int i =0;i<=n;i++){
int cnt = 0;
int j =i;
while(j){
if(j&1) cnt++;
j=j>>1;
}
res[i]=cnt;
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
|
public class Solution {
public int[] CountBits(int n) {
//x = x&(x-1),清除最低位的1
int[] bits = new int[n+1];
for(int i=1;i<=n;i++)
{
bits[i] = bits[i&(i-1)]+1;
}
return bits;
}
}
|
key:x = x & (x-1)
448、找到所有数组中消失的元素#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> res;
set<int> st;
for(int i =0;i<nums.size();i++){
st.insert(nums[i]);
}
for(int i =1;i<=nums.size();i++){
if(!st.count(i)){
res.push_back(i);
}
}
return res;
}
};
|
461、汉明距离#
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution {
public:
int hammingDistance(int x, int y) {
int res=0;
while(x||y){
res+= (x&1)^(y&1);
x=x>>1;
y=y>>1;
}
return res;
}
};
|
543、二叉树的直径#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
int res = 0;
int dfs(TreeNode* root){
if(!root) return 0;
int l = 1+dfs(root->left);
int r = 1+dfs(root->right);
res = max(res,l+r-2);
return max(l,r);
}
int diameterOfBinaryTree(TreeNode* root) {
dfs(root);
return res;
}
};
|
617、合并二叉树#
1
2
3
4
5
6
7
8
9
10
11
|
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if(root1==nullptr){return root2;}
if(root2==nullptr){return root1;}
root2->val=root2->val+root1->val;
root2->left=mergeTrees(root1->left,root2->left);
root2->right=mergeTrees(root1->right,root2->right);
return root2;
}
};
|
中等模块#
2、两数相加#
3、无重复字符串的最长子串#
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 lengthOfLongestSubstring(string s) {
int n = s.length();
if(n==0) return 0;
int left=0;
int len = 0;
int res = 0;
unordered_map<char,int> st;
for(int i =0;i<n;i++){
if(!st.count(s[i])){
len++;
st[s[i]]=i;
}else{
left=st[s[i]]>=left?st[s[i]]+1:left; //注意
len = i-left+1;
st[s[i]]=i;
}
res=max(res,len);
}
return res;
}
};
|
5、最长回文子串#
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
|
class Solution {
public:
string longestPalindrome(string s) {
int n = s.length();
int maxLen = 0;
int maxLeft = 0;
int len = 1;
for(int i =0;i<n;i++){
int l = i-1;
int r = i+1;
while(l>=0&&s[l]==s[i]){
len++;
l--;
}
while(r<n&&s[r]==s[i]){
len++;
r++;
}
while(l>=0&&r<n&&s[l]==s[r]){
len=len+2;
l--;
r++;
}
if(len>maxLen){
maxLen=len;
maxLeft=l;
}
len = 1;
}
return s.substr(maxLeft+1,maxLen);
}
};
|
11、盛最多水的容器#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution {
public:
int maxArea(vector<int>& height) {
int r = height.size()-1;
int res = 0;
int l = 0;
int sum =0;
while(l<r){
int shorter = min(height[l],height[r]);
int len = r-l;
if(height[l]<height[r]){
l++;
}else{
r--;
}
sum=shorter*len;
res=max(res,sum);
}
return res;
}
};
|
15、三数之和#
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
|
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
if(nums.size()<3) return ans;
sort(nums.begin(), nums.end());
if(nums[0]>0) return ans;
int i = 0;
while(i<nums.size()){
if(nums[i]>0) break; // 1楼网友指正,将这个if语句放这里提前终止循环
int left = i+1, right = nums.size()-1;
while(left< right){
if(nums[i] + nums[left] +nums[right]>0)
right--;
else if(nums[i] + nums[left] +nums[right]<0)
left++;
else{
ans.push_back({nums[i], nums[left], nums[right]});
// 相同的left和right不应该再次出现,因此跳过
while(left<right&&nums[left]==nums[left+1])
left++;
while(left<right&&nums[right] == nums[right-1])
right--;
left++;
right--;
}
}
// 避免nums[i]作为第一个数重复出现
while(i+1<nums.size()&&nums[i] == nums[i+1])
i++;
i++;
}
return ans;
}
};
|
16、最接近的三数之和#
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
|
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
int res = 1e7;
int n = nums.size();
sort(nums.begin(),nums.end());
int i =0;
while(i<n){
int l = i+1;
int r = n-1;
while(l<r){
int sum=nums[i]+nums[l]+nums[r];
if(sum<target){
l++;
if(abs(res-target)>abs(sum-target)){
res=sum;
}
}else if(sum>target){
r--;
if(abs(res-target)>abs(sum-target)){
res=sum;
}
}
else{
return target;
}
}
i++;
}
return res;
}
};
|
17、电话号码的字母组合#
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
|
class Solution {
public:
//1. 用map记录每个数字按键对应的所有字母
unordered_map<char, string> m = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"},
{'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}
};
//2. 存储最终结果和临时结果的变量
vector<string> ans;
string current;
string cp;
int n;
void dfs(int len,char c){
if(current.length()==n){
ans.push_back(current);
return;
}
for(int i =0;i<m[c].length();i++){
current+=m[c][i];
dfs(len+1,cp[len+1]);
current.pop_back();
}
}
vector<string> letterCombinations(string digits) {
cp = digits;
n = digits.length();
if(n==0) return ans;
dfs(0,digits[0]);
return ans;
}
};
|
19、删除链表的倒数第N个结点#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* start = head;
ListNode* end = head;
while(n--){
end = end -> next;
}
if(end == nullptr) return head->next;
while(end -> next != nullptr){
end = end -> next;
start = start -> next;
}
start -> next = start -> next -> next;
return head;
}
};
|
22、括号生成#
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
|
class Solution {
public:
vector<string> res;
string cur="";
void dfs(int l,int r){
if(l==0&&r==0){
res.push_back(cur);
return;
}
if(l>0){
cur+='(';
dfs(l-1,r);
cur.pop_back();
}
if(r>l){
cur+=')';
dfs(l,r-1);
cur.pop_back();
}
}
vector<string> generateParenthesis(int n) {
dfs(n,n);
return res;
}
};
class Solution {
public:
int m;
vector<string> res;
string cur="";
void dfs(int l,int r){
if(l==r&&l+r==2*m){
res.push_back(cur);
return;
}
if(l<=m){
cur+='(';
dfs(l+1,r);
cur.pop_back();
}
if(l>r){
cur+=')';
dfs(l,r+1);
cur.pop_back();
}
}
vector<string> generateParenthesis(int n) {
m = n;
dfs(0,0);
return res;
}
};
|
31、下一个排列#
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:
void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(),nums.end());
}
};
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int i,j;
bool flag=false;
for(int k=n-1;k>=1;k--){
if(nums[k]>nums[k-1]){
i = k-1;
j = k;
flag=true;
break;
}
}
if(flag){
for(int k = n-1;k>=i;k--){
if(nums[k]>nums[i]){
swap(nums[k],nums[i]);
sort(nums.begin()+j,nums.end());
break;
}
}
}
else 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
24
25
26
27
28
29
30
|
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0,r=nums.size()-1;
if(target==nums[l]) return l;
if(target==nums[r]) return r;
if(target<nums[l]&&target>nums[r]) return -1;
if(target>nums[l]){
while(l<r){
int mid = (l+r) >> 1;
if(target==nums[mid]) return mid;
else if(target<nums[mid]||nums[mid]<nums[0]) r=mid;
else l=mid+1;
}
return -1;
}
l = 0;
r=nums.size()-1;
if(target<nums[r]){
while(l<r){
int mid = (l+r) >> 1;
if(target==nums[mid]) return mid;
else if(nums[mid]>nums[nums.size()-1]||nums[mid]<target) l=mid+1;
else r=mid;
}
return -1;
}
return -1;
}
};
|