1 介绍

本博客用来记录代码随想录leetcode200题之额外题目相关题目。

2 训练

题目1：1365. 有多少小于当前数字的数字

解题思路：二分查找。

C++代码如下，

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& a) {
        vector<int> b = a;
        sort(b.begin(), b.end());
        vector<int> res;
        for (auto x : a) {
            auto iter = lower_bound(b.begin(), b.end(), x);
            int i = distance(b.begin(), iter);
            res.emplace_back(i);
        }
        return res;
    }
};

python3代码如下，

class Solution:
    def smallerNumbersThanCurrent(self, a: List[int]) -> List[int]:
        b = copy.deepcopy(a)
        b.sort()
        res = []
        for x in a:
            i = bisect.bisect_left(b, x)
            res.append(i)
        return res 

题目2：941. 有效的山脉数组

解题思路：模拟。

C++代码如下，

class Solution {
public:
    bool validMountainArray(vector<int>& a) {
        int n = a.size();
        if (n < 3) return false;
        if (!(a[0] < a[1])) return false;
        if (!(a[n-2] > a[n-1])) return false;
        int i = 0;
        while (i+1 < n && a[i] < a[i+1]) i += 1;
        int j = i;
        while (j+1 < n && a[j] > a[j+1]) j += 1;
        if (j != n-1) return false;
        return true;
    }
};

python3代码如下，

class Solution:
    def validMountainArray(self, a: List[int]) -> bool:
        n = len(a)
        if n < 3:
            return False 
        if not (a[0] < a[1]):
            return False
        if not (a[-2] > a[-1]):
            return False 
        i = 0 
        while i + 1 < n and a[i] < a[i+1]:
            i += 1 
        j = i 
        while j + 1 < n and a[j] > a[j+1]:
            j += 1 
        if j != n-1:
            return False 
        return True 

题目3：1207. 独一无二的出现次数

解题思路：模拟。

C++代码如下，

class Solution {
public:
    bool uniqueOccurrences(vector<int>& a) {
        unordered_map<int, int> cnt1;
        for (auto x : a) cnt1[x]++;
        unordered_map<int, int> cnt2;
        for (auto [k, v] : cnt1) {
            cnt2[v]++;
            if (cnt2[v] > 1) return false;
        }
        return true;
    }
};

python3代码如下，

class Solution:
    def uniqueOccurrences(self, a: List[int]) -> bool:
        cnt = collections.Counter(a)
        res = collections.Counter(cnt.values())
        for k in res:
            if res[k] > 1:
                return False 
        return True 

题目4：283. 移动零

解题思路：双指针。

C++代码如下，

python3代码如下，

3 参考

代码随想录