Cinte's Leetcode Record
0%

Posted on Edited on In Disqus:
Symbols count in article: 253 Reading time ≈ 1 mins.

633. 平方数之和

是一个排序Two sum的变种，范围是0~sqrt(c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool judgeSquareSum(int c) {
        long l = 0, r = sqrt(c);
        while(l <= r)
        {
            auto sum = l * l + r * r;
            if(sum > c)
                --r;
            else if(sum < c)
                ++l;
            else
                return true;
        }
        return false;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

665. 非递减数列

所有纠正只在转折处出现

两种情况

1639223566766.jpg 这种情况下把nums[i-1]改成比nums[i-2]和nums[i]之前的值即可

1639223632869.jpg 这种情况下把nums[i]改成nums[i-1]和nums[i+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:
    bool checkPossibility(vector<int>& nums) {
        int n = nums.size();
        bool isCorrect = false;
        for(int i = 1; i < n; ++i)
        {
            if(nums[i] < nums[i - 1])
            {
                if(isCorrect)
                    return false;
                if(i == 1 || ( i >= 2 && nums[i] >= nums[i - 2]))
                    isCorrect = true;
                else if(i == n - 1 || (i < n - 1 && nums[i + 1] >= nums[i - 1]))
                    isCorrect = true;
                else
                    return false;
            }
        }
        return true;
    }
};
答案的方法，对原数组进行修改
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool checkPossibility(vector<int>& nums) {
        bool isC = false;
        for(int i = 0, n = nums.size(); i < n - 1; ++i)
        {
            if(nums[i] > nums[i + 1])
            {
                if(isC)
                    return false;
                // 当nums[i+1]>=nums[i-1]的时候，只需要让nums[i]=nums[i+1]或者nums[i+1]=nums[i],则无论如何都能成立,所以这里不动的话对后面没有影响
                // 但是nums[i+1]<nums[i-1],如果令nums[i]=nums[i+1],必然不成立，所以需要让nums[i+1]=nums[i]
                if(i != 0 && nums[i + 1] < nums[i - 1])
                    nums[i + 1] = nums[i];
                isC = true;
            }
        }
        return true;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 764 Reading time ≈ 1 mins.

911. 在线选举

times是严格递增的，所以只需要预处理记录每个时间段谁的票多，就可以得出每个时间点的获胜者，在搜索的时候，找到不大于t的最大时间点的胜者即可

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 TopVotedCandidate {
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) : times(times) {
        unordered_map<int, int> memo;
        int top = -1;
        int maxVote = -1;
        for(auto p : persons)
        {
            if(++memo[p] >= maxVote)
            {
                top = p;
                maxVote = memo[p];
            }
            tops.push_back(top);
        }
    }
    
    int q(int t) {
        // 寻找第一个大于t的时间点
        auto pos = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return tops[pos];
    }
private:
    vector<int> tops;
    vector<int> times;
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

452. 用最少数量的箭引爆气球

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:
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty())
            return 0;
        sort(points.begin(), points.end(), [](auto& v1, auto& v2)
        {
            return v1[0] < v2[0];
        });
        int l = points[0][0], r= points[0][1];
        int ret = 1;
        for(int i = 1, n = points.size(); i < n; ++i)
        {
            int cl = points[i][0], cr = points[i][1];
            if((cl >= l && cl <= r) || (cr >=l && cr <= r))
            {
                l = max(l, cl);
                r = min(r, cr);
            }else
            {
                l = cl;
                r = cr;
                ++ret;
            }
        }
        return ret;
    }
};

另一种

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 findMinArrowShots(vector<vector<int>>& points) {
        if(points.empty())
            return 0;
        sort(points.begin(), points.end(), [](auto& v1, auto& v2)
        {
            return v1[1] < v2[1]; // 这里与上面不同
        });
        int l = points[0][1];
        int ret = 1;
        for(int i = 1, n = points.size(); i < n; ++i)
        {
            if(points[i][0] > l) // 当弹出时候,假如后面还有能被他引爆的气球，他们这些气球必然可以被他的下一个箭引爆。
            // 例如[0, 5],[6, 7],[3, 8]
            {
                l = points[i][1];
                ++ret;
            }
        }
        return ret;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 773 Reading time ≈ 1 mins.

748. 最短补全词

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 shortestCompletingWord(string licensePlate, vector<string>& words) {
        int map[26]{ 0 };
        int mL = INT_MAX, ret = -1;
        int count = 0;
        for(auto ch : licensePlate)
            if(ch != ' ' && !(ch >= '0' && ch <= '9'))
                if(++map[lower(ch)] == 1)
                    ++count;
        for(int i = 0, n = words.size(); i < n; ++i)
        {
            int m[26]{0};
            copy(map, map + 25, m);
            auto tmp = count;
            for(auto& ch : words[i])
                if(--m[lower(ch)] == 0)
                    --tmp;
            if(tmp == 0 && words[i].size() < mL)
            {
                mL = words[i].size();
                ret = i;
            }
        }
        return words[ret];
    }
private:
    int lower(char ch)
    {
        if(ch >= 'A' && ch <= 'Z')
            return ch - 'A';
        return ch - 'a';
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 206 Reading time ≈ 1 mins.

面试题 05.01. 插入

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int insertBits(int N, int M, int i, int j) {
        // 把N的i~j置为0
        for(int k = i; k <= j; ++k)
            if((1 << k) & N)
                N ^= 1 << k;
        // M放到i开头上
        M <<= i;
        return M + N;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 717 Reading time ≈ 1 mins.

605. 种花问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int m = flowerbed.size();
        for(int i = 0; i < m; ++i)
        {
            if(flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] != 1) && (i == m - 1 || flowerbed[i + 1] != 1))
            {
                flowerbed[i] = 1;
                --n;
            }
        }
        return n <= 0;
    }
};

答案

通过2个1之间的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
class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int m = flowerbed.size();
        int prev{ -1};
        for(int i = 0; i < m; ++i)
        {
            if(flowerbed[i] == 1)
            {
                if(prev < 0)
                    n -= i / 2;
                else
                    n -= (i - prev - 2) / 2;
                if(n <= 0)
                    return true;
                prev = i;
            }
        }
        if(prev == -1)
            n -= (m + 1) / 2;
        else
            n -= (m - prev - 1) / 2;
        return n <= 0;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 1k Reading time ≈ 1 mins.

435. 无重叠区间

问题转换为求最多的不重合区间的数量

超时的解法

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:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int>& v1, vector<int>& v2)
        {
            return v1[0] < v2[0];
        });
        int n = intervals.size();
        vector<int> dp(n, 1);
        int ret = 1;
        for(int i = 1; i < n; ++i)
        {
            for(int j = 0; j < i; ++j)
            {
                if(intervals[i][0] >= intervals[j][1])
                {
                    dp[i] = max(dp[i], 1 + dp[j]);
                    ret = max(dp[i], ret);
                }
            }
        }
        return n - ret;
    }
};

优化

参考300. 最长递增子序列的贪心+二分解法

顺便看看题解

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 eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& v1, const auto& v2)
        {
            return v1[1] < v2[1];
        });
        int right = intervals[0][1];
        int ret = 1;
        int n = intervals.size();
        for(int i = 1; i < n; ++i)
        {
            if(intervals[i][0] >= right)
            {
                right = intervals[i][1];
                ++ret;
            }
        }
        return n - ret;
    }
};

如果右边那个可以的话，比右边那个右端点小的肯定也可以

Posted on Edited on In Disqus:
Symbols count in article: 295 Reading time ≈ 1 mins.

383. 赎金信

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int map[26]{ 0 };
        for(auto ch : magazine)
            ++map[ch - 'a'];
        for(auto ch : ransomNote)
            --map[ch - 'a'];
        for(int i = 0; i < 26; ++i)
            if(map[i] < 0)
                return false;
        return true;
    }
};

Posted on Edited on In Disqus:
Symbols count in article: 271 Reading time ≈ 1 mins.

1877. 数组中最大数对和的最小值

使得他们和起来的波动最小，所以排序后，两头加，大的加小的

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int minPairSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int ret = 0;
        for(int i = 0, n = nums.size(); i < n / 2; ++i) // 只需要遍历一半
            ret = max(nums[i] + nums[n - i - 1], ret);
        return ret;
    }
};