Leetcode刷题记录

April 07, 2021 33349

（一）、每日一题

2021.04.07

点击进入题目
思路：

1.暴力for。
2.二分查找。

解析：
2.二分查找
思路：
1.左中右值相等又不等于target,缩小区间：l++,r–；

2.左区间有序:
(1)target在有序的区间内，范围变为：[l,mid-1]
(2)target不在这段有序的区间中，范围变为：[mid+1,r]

3.右区间有序:
(1)target在这段有序区间内，范围变为：[mid-1,r];
(2)target不再这段有序区间内，范围变为：[l,mid+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
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n=nums.size();
        if(n==0)return false;
        if(n==1){
            if(nums[0]==target)return true;
            else return false;
        }
        int l=0;
        int r=n-1;
        while(l<r){
            int mid=(l+r)/2; if(nums[mid]==target||nums[l]==target||nums[r]==target)return true;
            if(nums[l]==nums[mid]&&nums[r]==nums[mid]){
                l++;
                r--;
            }
            else if(nums[l]<=nums[mid]){
                if(nums[l]<target&&nums[mid]>target)
                    r=mid-1;
                else 
                    l=mid+1;
            }
            else {
                if(nums[r]>target&&nums[mid]<target)
                    l=mid+1;
                else
                    r=mid-1;
            }
        }
        return false;
    }
};

1.暴力for：(不是重点)

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int n=nums.size();
        for(int i=0;i<n;i++){
            if(nums[i]==target)
            return true;
        }
        return false;
    }
};

2021.04.08

点击进入题目
思路：

1.二分
2.暴力for

解析：
1.二分
(1)一旦nums[l]>=nums[mid]说明更小的一定在[l，mid-1]内
(2)要判断一下边界nums[l],nums[r]是不是更小的，这是用于处理有序的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n=nums.size();
        int l=0;
        int r=n-1;
        int min=nums[0];
        while(l<r){
            int mid=l+(r-l)/2;
            if(nums[mid]<min)min=nums[mid];
            if(nums[l]<min)min=nums[l];
            if(nums[r]<min)min=nums[r];
            if(nums[l]>=nums[mid]){
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        return min;
    }
};

2.暴力（懒得贴了）

2020.04.09

2020.04.10 263.丑数

点击进入题目
思路：
简单暴力。

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool isUgly(int n) {
        if(n<=0)return false;
        while(n%2==0){
            n=n/2;}
        while(n%3==0){
            n=n/3;}
        while(n%5==0){
            n=n/5;}
        if(n!=1)
            return false;
        else return true;
    }
};

2020.04.11 264.丑数Ⅱ

点击进入题目

思路：
1.DP，三指针
2.暴力打表

解析：
1.DP，三指针
三个指针：ptr1,ptr2,ptr3
ptr1负责*2操作，ptr2负责*3操作，ptr3负责*5操作
找到每次的最小值，找到了就让指针向前跑一格
（手动模拟一遍就懂了）

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 nthUglyNumber(int n) {
        int ans[n+2];
        ans[1]=1;
        int ptr1=1;
        int ptr2=1;
        int ptr3=1;
        for(int i=2;i<=n;i++){
            int minn=min(ans[ptr1]*2,min(ans[ptr2]*3,ans[ptr3]*5));
            ans[i]=minn;
            if(ans[ptr1]*2==minn)
                ptr1++;
            if(ans[ptr2]*3==minn)//不能用else if 因为其他的如果相同了 也该往前跑一步！！
                ptr2++;
            if(ans[ptr3]*5==minn)
                ptr3++;
        }
        return ans[n];
    }
};

2.打表
适合竞赛的时候用，这里主要是DP，不贴打表做法了。

2020.04.12 179.最大数

点击进入题目

思路：
修改sort方法，将合适的位置放好，再用to_string函数拼接成答案返回

解析：
1.没有用到C++精髓的cmp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    static bool cmp(int a,int b){
        long sx=10;//不开long要爆int
        long sy=10;
        while(a>=sx)
            sx*=10;
        while(b>=sy)
            sy*=10;
        return sx*b+a<sy*a+b; 
    }
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),cmp);
        string ans;
        for(auto num:nums)
            ans+=to_string(num);
        if(ans[0]=='0')return "0"; 
        return ans;
    }
};

2.用到了C++精髓的cmp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    static bool cmp(int a,int b){
        string x=to_string(a);
        string y=to_string(b);
        return x+y>y+x;
    }
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),cmp);
        string ans;
        for(auto num:nums)
            ans+=to_string(num);
        if(ans[0]=='0')return "0"; 
        return ans;
    }
};

2020.04.13 783.二叉搜索树节点最小距离

点击进入题目

思路：
1.BFS(非递归)，找每个节点，用vector存起来然后sort一下，再遍历一下两两之差（代码又臭又长）
(感觉需要写个stl的博客了，太不熟练)
2.官方题解①：中序遍历(递归)
3.官方题解②：莫里斯中序遍历

解析：
1.BFS：
queue实现遍历每个节点，vector来存放每个节点的value，所有节点遍历完之后，对vector排个序，循环看看哪两个数的差最小就是答案了。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        queue<TreeNode *> roots;
        vector<int >ans;
        roots.push(root);
        ans.push_back(root->val);
        int submin=900000;
        while(!roots.empty()){
                TreeNode * tmproot;
                tmproot=roots.front();
                roots.pop();
                if(tmproot->left){
                   roots.push(tmproot->left);
                   ans.push_back(tmproot->left->val);
               }
                if(tmproot->right){
                    roots.push(tmproot->right);
                    ans.push_back(tmproot->right->val);
                }
        }
        sort(ans.begin(),ans.end());
        int n=ans.size();
        for(int i=1;i<n;i++){
            if(submin>ans[i]-ans[i-1]){
                submin=ans[i]-ans[i-1];
            }
        }
        return submin;

    }
};

2.DFS(递归，中序遍历)：
全局定义最小值，然后每次递归的时候更新最小值，

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minn=900000;
    TreeNode* pre;
    int minDiffInBST(TreeNode* root) {
        dfs(root);
        return minn;
    }
    void dfs(TreeNode *root){
        if(root==nullptr)return;
        dfs(root->left);
        if(pre!=nullptr){
            minn=min(minn,abs(root->val-pre->val));
        }
        pre=root;
        dfs(root->right);
    }
};

2021.04.14 208.实现Trie(前缀树)

点击进入题目

思路：
1.无敌的STL法：string + unordered_set
2.乖乖建树

题解：
1.STL法

  • 学前缀树就知道了，可以用hash表存放串，找的时候直接通过函数找只要O(1)，这里直接用unordered_set来存放；
  • 然后用string的find函数，可以找到字串在母串哪个位置，直接字串是不是第一位就Ok
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 Trie {
public:
    unordered_set <string > mode;
    /** Initialize your data structure here. */
    Trie() {

    }
    
    /** Inserts a word into the trie. */
    void insert(string word) {
        mode.insert(word);
    }
    
    /** Returns if the word is in the trie. */
    bool search(string word) {
        if(mode.find(word)!=mode.end())return true;
        else return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        for(auto s:mode){
            if(s.find(prefix)==0)
                return true;
        }
        return false;
    }
};

2.建树

2021.04.15 213.打家劫舍Ⅱ

点击进入题目

思路：
头取或者尾取，那么我们就开两个数组，一个存取头之后的max，一个存取尾之后的max

题解：

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 rob(vector<int>& nums) {
        int n=nums.size();
        if(n==1)
            return nums[0];
        if(n==2)
            return max(nums[1],nums[0]);
        int dp1[110];
        dp1[0]=0;
        dp1[1]=nums[1];
        int dp2[110];
        dp2[n-1]=0;
        dp2[n-2]=nums[n-2];
        for(int i=2;i<n;i++){
            dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i]);
            dp2[n-i-1]=max(dp2[n-i],dp2[n-i+1]+nums[n-i-1]);
        }
        return max(dp1[n-1],dp2[0]);
    }
};

2021.04.16 87.扰乱字符串(困难)

点击进入题目

2021.04.17 220.存在重复元素Ⅲ

点击进入题目

思路：
set、滑动窗口
运用set内部排序的机制，滑动窗口主要就是要准确利用合适的数据结构；窗口就是边界的处理，内部所需要的东西，需要通过不同的数据结构来实现。

解析：

  1. eptr从小到大循环
  2. 窗口大小(即set.size())必须小于等于k，一旦比k大，左边界移一步（即从set里删除当前的sptr）
  3. 通过lower_bound()来找比nums[right]-t更大的数，如果找到了 就是true
  4. 如果循环完都没有找到，返回false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n=nums.size();
        if(n==0||n==1) return false;
        set<long >s1;
        int sptr=0;
        int eptr=0;
        while(eptr<n){
            if(eptr-sptr>k){
                s1.erase(nums[sptr]);
                sptr++;
            }
            if(s1.lower_bound((long long )nums[eptr]-t)!=s1.end()&&(*(s1.lower_bound((long long)nums[eptr]-t))-nums[eptr]<=t))
                return true;
            s1.insert(nums[eptr]);
            eptr++;
        } 
        return false;
    }
};

2021.04.18 26.删除有序数组中的重复项

点击进入题目

思路：
简单题

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        long n=nums.size();
        for(int i=1;i<n;i++){
            if(nums[i]==nums[i-1]){
                nums.erase(nums.begin()+i);
                i--;
                n--;
            }
        }
        return n;
    }
};

2021.04.19 27.移除元素

点击进入题目

思路：
vector的erase函数，简单死了，代码都懒得放了。

2021.04.20 28.实现strStr()

不知道是不是力扣看我最近太自闭了，全是STL简单题，分分钟写出来找自信

点击进入题目

思路：
string的find函数

解析：

1
2
3
4
5
6
7
class Solution {
public:
    int strStr(string haystack, string needle) {
        if(haystack.find(needle)==haystack.npos) return -1;
        else return haystack.find(needle);
    }
};

2021.04.21 91.解码方法

点击进入题目

思路：
明显DP，转移方程需要想好。
（转移方程五分钟，边界判断两小时= =）

  1. 当前单独：dp[i]=dp[i-1]
  2. 当前和前一个合并 dp[i]=dp[i-2]
  3. 选择单独或者合并 dp[i]=dp[i-1]+dp[i-2]

前导0特判：

  1. 硬判断
  2. string前添加其他前导，使其不满足任何条件

吐槽一下“00”这个例子，必须要我手动memset一下数组，不然自己跑出来是正确的0，但是提交上去跑出来是1，WA了；日了狗！！

解析：

1.O(n)空间

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 numDecodings(string s) {
        int dp[110]={0};//手动赋值或者memset一下，不然会出错。
        dp[0]=1;
        s=' '+s;
        int a,b;
        int n=s.size();
        for(int i=1;i<n;i++){
            a=s[i]-'0';
            b=10*(s[i-1]-'0')+s[i]-'0';
            if(a<=9&&a>=1)
                dp[i]=dp[i-1];
            if(b>=10&&b<=26)
                dp[i]=dp[i-2];
            if(a<=9&&a>=1&&b>=10&&b<=26)
                dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n-1];
    }
};

2.空间优化O(1)
因为只用到了三个数，可以只开三位空间
循环跑这三位，通过取余操作。
主要是因为这里只用到了n-1这一位，所以dp[n-1]之前的数都是无用的，可以被不断覆盖。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int numDecodings(string s) {
        int dp[3]={0};
        dp[0]=1;
        s=' '+s;
        int a,b;
        int n=s.size();
        for(int i=1;i<n;i++){
            a=s[i]-'0';
            b=10*(s[i-1]-'0')+s[i]-'0';
            dp[i%3]=0;
            if(a<=9&&a>=1)
                dp[i%3]=dp[(i-1)%3];
            if(b>=10&&b<=26)
                dp[i%3]=dp[(i-2)%3];
            if(a<=9&&a>=1&&b>=10&&b<=26)
                dp[i%3]=dp[(i-1)%3]+dp[(i-2)%3];
        }
        return dp[(n-1)%3];
    }
};

2021.04.22 363.矩形区域不超过 K 的最大数值和【待补】

点击进入题目

写疯了，暴力肯定过不了哈。

思路：
前缀和！！（以前学过，而且第一次去比赛就用上了的差分约束，当时只有11个人写出来了，东软去的九个人全写出来了，结果我现在忘得一干二净了，菜死了无语！我甚至想用滑动窗口来解决这一题= =。）
这里是二维前缀和（我记得当时是zzy讲的）

解析：

1

2021.04.23 【待补】

2021.04.24 377.组合总和IV

点击进入题目

思路：
首先想到了全排列，用dfs来全排列
但是这样会TLE，要用记忆化

解析：

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 ans=0;
    unordered_map <int ,int > tmp;
    int combinationSum4(vector<int>& nums, int target) {
        ans=dfs(target,nums);
        return ans;
    }
    int dfs(int target,vector<int>& nums){
        if(target==0) return 1;
        if(target < 0) return 0;
        if(tmp.count(target))return tmp[target];
        //直接用tmp[target]来看存不存在，会TLE，很神奇
        
        //看了一下官方文档！用operator[]的话，
        //如果k与容器中元素的键匹配，则该函数返回对其映射值的引用。
        //如果k与容器中任何元素的键都不匹配，则该函数将使用该键插入一个新元素，并返回对其映射值的引用。

        //find()不会有这个效果
        //但是unordered_map是hash表，讲道理就算新插入也应该是O(1)啊
        //又搞不懂了，以后查看有没有还是用count()函数吧

        int step=0;
        for(int i=0;i<nums.size();i++){
            target-=nums[i];
            step+=dfs(target,nums);
            target+=nums[i];
        }
        tmp[target]=step;
        return step;
    }
};

2021.04.25 897.递增顺序搜索树

最近写题太懒惰了，思维也不是很好，不在状态的感觉。

思路：
中序遍历，中间进行操作。
开一个tmp，一个ans，ans指向tmp的头，最后返回的就是ans（tmp的头）；

但是这里tmp开一位空的位置，空位置的right开始才是后续的答案，所以返回ans->right;

中序遍历过程中tmp的操作（已经dfs过node的left了）：
node的left标记为走过，不用再走了
tmp的right指向node；
tmp放到tmp的right位置

解析：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode * tmp;
    TreeNode * ans;
    TreeNode* increasingBST(TreeNode* root) {
        tmp=new TreeNode(-1);
        ans=tmp;
        dfs(root);
        return ans->right;
    }
    void dfs(TreeNode * node){
        if(node==nullptr) return ;
        dfs(node->left);

        node->left=nullptr;
        tmp->right=node;
        tmp=tmp->right;

        dfs(node->right);
    }
};

2021.04.26 1011.在D天内送达包裹的能力

点击进入题目

思路：
二分查找。
因为有序，能力一定是大于等于货物的最大值的。
那么就从最大值到货物总和，进行二分
看每种能力，需要的天数，
如果当前能力，送完货物的天数比D大，那么就在mid-right里，左区间可以不管了。
如果送完货物的天数比D小，那么就在left-mid，右区间不管了。

解析：
left=max(nums)
right=sum(nums)

需要天数直接暴力查看，然后对比D，来更新左右区间。

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 shipWithinDays(vector<int>& weights, int D) {
        int left=*max_element(weights.begin(), weights.end());
        int right=accumulate(weights.begin(),weights.end(),0);
        int mid;
        while(right>left){
            mid=left+(right-left)/2;
            int cur=0;
            int day=1;
            for(auto weight:weights){
                if(cur+weight>mid){
                    cur=0;
                    day++;
                }
                cur+=weight;
            }
            if(day<=D)
                right=mid;
            else
                left=mid+1;
        }
        return left;
    }
};

2021.04.27 938.二叉搜索树的范围和

点击进入题目

思路：
遍历二叉树。简单题。

解析：

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int ans=0;
    int rangeSumBST(TreeNode* root, int low, int high) {
        dfs(root,low,high);
        return ans;
    }
    void dfs(TreeNode* root,int low,int high){
        if(root==nullptr){
            return ;
        }
        if(root->val>=low&&root->val<=high)
        ans+=root->val;
        dfs(root->left,low,high);
        dfs(root->right,low,high);
    }
};

2021.04.28 633.平方数之和

点击进入题目

思路：
根据题意，很容易想到双指针，

解析：
主要是指针如何遍历：

此题的数，a、b范围一定在[0,sqrt(c)]之间。
所以指针1（ptr1）指向0，指针2（ptr2）指向sqrt(c);
范围一定是ptr1< ptr2;（决定了外层循环）
如果两数之和，大于C，ptr2左移
如果两数之和，小于C，ptr1右移
如果等于C，返回真；
找到最后都没找到，返回FALSE;

刚开始我的思路和2，3，5那个三指针的题一样，但是那样模拟，(sqrt(c))^2+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:
    bool judgeSquareSum(int c) {
        //unordered_map<int,bool> ans;
        long long  ptr1=0;
        long long  ptr2=sqrt(c);
        //ans[0]=true;
        //ans[1]=true;
        //int tt;
        while(ptr1<=ptr2){
            /*
            tt=min((ptr1+1)*(ptr1+1)+ptr2*ptr2,ptr1*ptr1+(ptr2+1)*(ptr2+1));
            if(tt==ptr1*ptr1+(ptr2+1)*(ptr2+1)){
                ptr2++;
            }
            if(tt==(ptr1+1)*(ptr1+1)+ptr2*ptr2){
                ptr1++;
            }
            ans[tt]=true;
            */
            long long tmp1=ptr1*ptr1+ptr2*ptr2;//夺笋呐！！
            if(tmp1<c)ptr1++;
            else if(tmp1>c)ptr2--;
            else return true;
        }
        return false;
    }
};

2021.04.29 403.青蛙过河

点击进入题目

思路：
状态转移DP

解析：

  1. map+set解决

    map嵌套一个set，一个点，对应几个跳过去的步数（可以用哪些步数跳到）
    那么可以在前面石头的时候就把后面石头的状态赋值了

  2. dp数组转移

1.map+set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool canCross(vector<int>& stones) {
        int len=stones.size();
        unordered_map<int,unordered_set<int > > ans;
        ans[stones[0]].insert(0);
        for(int i=0;i<len;i++){
            auto tmps=ans[stones[i]];
            for(auto tmp:tmps){//遍历到达当前点可以用的步数
                for(int step=tmp-1;step<=tmp+1;step++){//
                    ans[stones[i]+step].insert(step);
                }
            }
        }
        if(ans[stones[len-1]].empty()) return false;
        else return true; 
    }
};

2021.04.30 137.只出现一次的数字II

点击进入题目

思路：
map，很简单，写过的。

2021.05.01 690.员工的重要性【待补】

点击进入题目

2021.05.02 554.砖墙【待补】

点击进入题目

2021.05.03 7.整数反转

点击进入题目

评论区：面试官问了这道题 然后反问面试官32位整数最大值是多少 会是什么结果

思路：
这题主要是INT_MIN和INT_MAX
用Long long 来暂存，然后对比看是否超过int。
（第一遍WA在了负数，第二遍WA在了爆INT）

解析：
直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int reverse(int x) {
        string xx;
        xx=to_string(x);
        if(x<0){
            xx.erase(xx.begin());
        }
        int n=xx.size();
        long long ans;
        ans=0;
        long long tmp=1;
        for(int i=0;i<xx.size();i++){
            ans+=((xx[i]-'0')*tmp);
            tmp*=10;
        }
        if(ans>INT_MAX||ans<INT_MIN) return 0;
        if(x<0)
            ans*=(-1);
        return ans;
    }
};

2021.05.04 1473.粉刷房子III【待补】

点击进入题目

2021.05.05 740.删除并获得点数【待补】

点击进入题目

2021.05.06 1720.解码异或后的数组

点击进入题目

思路：
根据异或性质，很容易的出来，直接异或就好。

解析：
直接上代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    vector<int> decode(vector<int>& encoded, int first) {
        vector<int >ans;
        ans.push_back(first);
        for(int i=0;i<encoded.size();i++){
            ans.push_back(encoded[i] xor ans.back());
        }
        return ans;
    }
};

2021.05.07 1486.数组异或操作

点击进入题目

思路：
简单题。

解析：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int xorOperation(int n, int start) {
        int ans=start;
        for(int i=1;i<n;i++){
            ans^=(start+i*2);
        }
        return ans;
    }
};

（二）、剑指offer

58.左旋转字符串

点击进入题目

思路：
简单暴力。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        int a=s.length();
        string b=s;
        int i;
        for(i=0;i<a-n;i++){
            s[i]=b[i+n];
        }
        int j=0;
        for(;i<a;i++){
            s[i]=b[j++];
        }
        return s;
    }
};

27.二叉树的镜像

点击进入题目

思路：
左子节点和右子节点交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* mirrorTree(TreeNode* root) {
        if(root==NULL)return NULL;
        TreeNode * tmp=root->left;
        root->left=mirrorTree(root->right);
        root->right=mirrorTree(tmp);
        return root;
    }
};

55.二叉树的深度

点击进入题目

思路：

1.DFS
2.BFS

解析：
1.DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)return 0;
        return 1+max(maxDepth(root->left),maxDepth(root->right));
    }
};

2.BFS:

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL) return 0;
        int depth=0;
        queue<TreeNode *> Q;
        Q.push(root);
        while(!Q.empty()){
            int n=Q.size();
            depth++;
            for(int i=0;i<n;i++){
                TreeNode * tmp=Q.front();
                Q.pop();
                if(tmp->left)
                    Q.push(tmp->left);
                if(tmp->right)
                    Q.push(tmp->right);
            }
        }
        return depth;
    }
};

22.链表中倒数第K个节点

点击进入题目

思路：

1.暴力得到链表长度，然后用n-k来得到倒数
2.双指针

解析：
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k){
        if(k==1&& !head->next) return head;
        int n=1;
        ListNode * t=head;
        while(t&&t->next){
            n++;
            t=t->next;
        }
        int i;
        for(i=0;i<n;i++){
            if(n-i==k)
                break;
            else 
                head=head->next;
        }
        return head;
    }
};

2.双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* first=head;
        ListNode* later=head; 
        while(k--){
            first=first->next;
        }
        while(first){
            later=later->next;
            first=first->next;
        }
        return later;
    }
};

17.打印从1到最大的n位数

点击进入题目

思路：
暴力

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> printNumbers(int n) {
        vector <int >ans;
        int i=1;
        ans.push_back(i);
        while(i++){
            int num=1;
            int tmp=i;
            while(tmp/10){
                num++;
                tmp/=10;
            }
            if(num>n) break;
            ans.push_back(i);
        }
        return ans;
    }
};

29.顺时针打印矩阵

点击进入题目

思路：
注意边界，循环跑

解析：

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
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
         if(matrix.size() == 0)
            return {};
        vector<int> ans;
        if(matrix[0].size()==0)
            return ans;
        int left=0;
        int right=matrix[0].size()-1;
        int top=0;
        int bottom=matrix.size()-1;
        while(left<=right&&top<=bottom){
            for(int i=left;i<=right;i++){
                ans.push_back(matrix[top][i]);
            }
            for(int i=top+1;i<=bottom;i++){
                ans.push_back(matrix[i][right]);
            }
            if(left<right&&top<bottom){
                for(int i=right-1;i>=left;i--){
                    ans.push_back(matrix[bottom][i]);
                }
                for(int i=bottom-1;i>top;i--){
                    ans.push_back(matrix[i][left]);
                }
            }
            right--;
            left++;
            bottom--;
            top++;
        }
        return ans;
    }
};

05.替换空格

点击进入题目

思路：
知识点就是正确使用string，string直接拼接就完事，很简单

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    string replaceSpace(string s) {
        string ans;
        int n=s.size();
        for(int i=0;i<n;i++){
            if(s[i]!=' '){
                ans+=s[i];
            }
            else{
                ans+="%20";
            }
        }
        return ans;
    }
};

06.从头到尾打印链表

点击进入题目

思路：
很傻一道题，把链表的数用vector存下来，用个reverse函数翻转一下就ok。

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int >ans;
        if(head==NULL)
            return ans;
        int i=0;
        while(head){
            ans.push_back(head->val);
            head=head->next;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

54.二叉搜索树的第K大节点

点击进入题目

思路：
set能排序，就很舒服，直接用dfs把所有数存在set里，然后返回set。

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    set<int > tmp;
    int kthLargest(TreeNode* root, int k) {
        dfs(root);
        int n=tmp.size();
        return *tmp.begin()+(n-k);
    }
    void dfs(TreeNode *root){
        if(root==NULL)return ;
        tmp.insert(root->val);
        dfs(root->left);
        dfs(root->right);
    }
};

24.反转链表

深刻认识到链表相关的知识掌握得太薄弱了。

15.二进制中1的个数

点击进入题目

思路：
注意虽然给的是一串数字，但是是二进制，所以除的时候不是除以十，是右移1位，所以是除以二。

解析：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        long long  ans=0;
        while(n){
            if(n%2==1)
                ans++;
            n>>=1;
        }
        return ans;
    }
};

25.合并两个排序的链表

思路：

解析：

1
2


49.丑数

二刷丑数Ⅱ
点击进入题目

思路：
三指针、DP

解析：

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 nthUglyNumber(int n) {
        long long uglys[2000];
        int ptr1=1;
        int ptr2=1;
        int ptr3=1;
        uglys[1]=1;
        for(int i=2;i<=n;i++){
            uglys[i]=min(uglys[ptr1]*2,min(uglys[ptr2]*3,uglys[ptr3]*5));
            if(uglys[ptr1]*2==uglys[i]){
                ptr1++;
            }
            if(uglys[ptr2]*3==uglys[i]){
                ptr2++;
            }
            if(uglys[ptr3]*5==uglys[i]){
                ptr3++;
            }
        }
        return uglys[n];
    }
};

59-I.滑动窗口的最大值

点击进入题目

第一个没有看题解写出来的困难题，嘎嘎嘎无敌！！
（看了评论区，好吧，我是废物）

思路：
滑动窗口+multiset
用set有坑，因为窗口内会有重复的元素！！
用set的话，如果窗口的left是重复元素之一，erase(nums[left])的时候会擦掉窗口内的元素！
咱用mutiset（再夸一下，STL无敌！！），然而！multiset的erase也有误用情况！因为erase都是擦除全部，得用迭代器来找（不用多说，很好理解吧！），然后erase掉迭代器的位置。

解析：

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<int> maxSlidingWindow(vector<int>& nums, int k) {
        multiset <int > tmp;
        vector <int > ans;
        int left=0;
        int right=0;
        int n=nums.size();
        if(nums.size()==0) return ans;
        while(right<n){
            if(right-left>k){
                multiset <int>::iterator pos = tmp.find(nums[left]);  
                tmp.erase(pos);
                left++;
            }
            if(right-left==k){
                int nn=tmp.size();
                ans.push_back(*tmp.rbegin());
            }
            tmp.insert(nums[right]);
            right++;
        }
        tmp.insert(nums[right-1]);
        if(right-left>k){
                multiset <int>::iterator pos = tmp.find(nums[left]);  
                tmp.erase(pos);
                left++;
            }
            if(right-left==k){
                int nn=tmp.size();
                ans.push_back(*tmp.rbegin());
        }
        return ans;
    }
};

10-Ⅱ.青蛙跳台阶问题

点击进入题目

思路：
= =入门的，没啥好说的。

解析：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int numWays(int n) {
        int ans[110];
        ans[0]=1;
        ans[1]=1;
        ans[2]=2;
        for(int i=3;i<=n;i++)
            ans[i]=(ans[i-1]+ans[i-2])%1000000007;
        return ans[n];
    }
};

53-Ⅱ.0～n-1中缺失的数字

点击进入题目

简单题，O(n)和O(logn)都可过。

思路：
评论区一位大佬曰：“排序这个条件没用上的可以不用秀了。”搞得我都不好意思不用二分写一下了。

解析：

O(n)遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i;
        for(i=0;i<nums.size();i++){
            if(nums[i]!=i){
                break;
            }
        }
        
        return i;
    }
};

O(logn)二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l=0;
        int r=nums.size()-1;
        int mid=(l+r)/2;
        while(l<=r){
            mid=(l+r)/2;
            if(nums[mid]!=mid)
                r=mid-1;
            else l=mid+1;
        }
        return l;
    }
};

56-Ⅱ.数组中数字出现的次数Ⅱ

点击进入题目

思路：
1.用STL：MAP或者直接count()，美汁汁儿！
2.状态机：位运算；但是是数电的东西，没学过，先不慌写

解析：
1.Map:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int ,int > ans;
        int ansnum;
        for(int i=0;i<nums.size();i++){
            ans[nums[i]]++;
        }
        for(int i=0;i<nums.size();i++){
            if(ans[nums[i]]==1){
                ansnum=nums[i];
            }
        }
        return ansnum;
    }
};

2.状态机：位运算

61.扑克牌中的顺子

说实话，这题真的恶心人，不知道在干嘛。he tui！！真的是不想看得很，又害怕到时候我撞上了这sb题，大草，认怂。
之前cf开的一个打麻将的顺子筒子啥的题，比这好了不止10倍！我tm直接给这题出题人上香！！

1

16.数值的整数次方

点击进入题目

这题就该用pow，返回值是double，也没有取模，完全就是pow，有点委屈快速幂了。

思路：

  1. pow()
  2. 快速幂。

解析：

1.pow()

1
2
3
4
5
6
class Solution {
public:
    double myPow(double x, int n) {
        return pow(x,n);
    }
};

2.快速幂：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    double myPow(double x, int n) {
        //return pow(x,n);
        double ans=1.0;
        int tmp=abs(n);
        while(tmp){
            if(tmp&1){
                ans*=x;
            }
            x=x*x;
            tmp=tmp/2;
        }
        if(n<0)return 1/ans;
        return ans;
    }
};

（三）、题库

198.打家劫舍

点击进入题目

思路：
很easy的dp，偷还是不偷两种选择
公式：dp[n]=max(dp[n-1],dp[n-1]+nums[i]);

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int rob(vector<int>& nums){
        long dp[1010];
        if(nums.size()==1) return nums[0];
        dp[0]=nums[0];
        dp[1]=max(nums[1],nums[0]);
        for(int i=2;i<nums.size();i++){
            dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
        }
        return dp[nums.size()-1];
    }
};

3.无重复字符的最长字串

点击进入题目

思路：
入门级滑动窗口。

解析：

  1. 开个hashmap来存字母出现次数
  2. 左右指针中，右指针向右遍历
  3. 遍历过程中如果当前字母是之前出现过的，就找到之前出现的位置，把左值针指向找到的位置，缩小窗口
    在循环中不断更新ans。
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 ans=0;
        int n=s.size();
        if(n==0) return 0;
        if(n==1) return 1;
        unordered_map<char, int> ss;
        int sptr=0;
        int eptr=0;
        while(eptr<n){
            char c1=s[eptr++];
            ss[c1]++;
            while(ss[c1]>1){
                char c2=s[sptr];
                ss[c2]--;
                sptr++;
            }
            ans=max(ans,eptr-sptr);
        } 
        return ans;
    }
};

875.爱吃香蕉的珂珂

点击进入题目

思路：
二分查找，边界注意。

解析：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left=1;
        int right=*max_element(piles.begin(),piles.end());
        int mid;
        while(left<right){
            mid=left+(right-left)/2;
            int time=0;
            for(auto pile:piles){
                time=time+(pile)/mid;
                if(pile%mid!=0) time++;
            }
            if(time>h)left=mid+1;
            else right=mid;
        }
        return left;
    }
};
  • 本文作者：lybbor
  • 版权声明：本博客所有文章均采用 BY-NC-SA 许可协议，转载请注明出处！