Cinte's Leetcode Record
0%

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

347. Top K Frequent Elements

Quick Select

快速排序，每次只排一半

T(n) : (1) Explore - LeetCode

b = 2, d=1,a=1

T(n) = T(n/2) + f(n)=T(n/2)+T(n)

1626147961860.png

那么T(n) 为 O(n)

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
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(auto& num : nums)
            map[num] += 1;
        for(auto& it : map)
            unique.push_back(it.first);
        sort(0, unique.size() - 1, unique.size() - k);
        vector<int> ret;
        // for(int i = unique.size() - 1; i >= unique.size() - k; --i) // 注意这种情况是错误的，当unique.siez() - k为0时，因为unique.size()是无符号数，而i是有符号数，i与unique.size() - k比较时将会自动转换为无符号数比较，这时的i是一个极大的无符号数，将导致i为负数时仍旧成立，解决方法可以先将unique.size()转为int
        //     ret.push_back(unique[i]);
        for(auto i = unique.end() - 1; i != unique.end() - 1 - k; --i)
            ret.push_back(*i);
        return ret;
    }
private:
    vector<int> unique;
    unordered_map<int, int> map;
private:
    int patition(int lo, int hi, int pivot)
    {
        swap(unique[pivot], unique[lo]);
        int i = lo, j = hi + 1;
        int c = map[unique[lo]];
        while(i < j)
        {
            while(i < hi && map[unique[++i]] < c) {}
            while(j > lo && map[unique[--j]] > c) {}
            if(i >= j)
                break;
            swap(unique[i], unique[j]);
        }
        swap(unique[j], unique[lo]);
        return j;
    }
    void sort(int lo, int hi, const int& k)
    {
        if(lo >= hi)
            return;
        auto pivot = lo + (rand() % (hi - lo + 1));
        auto j = patition(lo, hi, pivot);
        if(j == k)
            return;
        else if(j > k)
            sort(lo, j - 1, k);
        else
            sort(j + 1, hi, k);
    }
};

review

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
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        for(auto num : nums)
            ++map[num];
        vector<int> r;
        for(auto [num, _] : map)
            r.push_back(num);
        sort(r, 0, r.size() - 1, k);
        return vector<int>(r.begin(), r.begin() + k);
    }
private:
    unordered_map<int, int> map;
    int partition(vector<int>& nums, int lo, int hi)
    {
        auto pivot = lo + (rand() % (hi - lo + 1));
        int i = lo, j = hi + 1;
        int c = map[nums[pivot]];
        swap(nums[pivot], nums[lo]);
        while(i < j)
        {
            while(i < hi && map[nums[++i]] > c) {}
            while(j > lo && map[nums[--j]] < c) {}
            if(i >= j)
                break;
            swap(nums[i], nums[j]);
        }
        swap(nums[lo], nums[j]);
        return j;
    }
    void sort(vector<int>& nums, int lo, int hi, int k)
    {
        if(lo >= hi)
            return;
        auto j = partition(nums, lo, hi);
        if(j == k - 1)
            return;
        if(j < k - 1)
            sort(nums, j + 1, hi, k);
        else
            sort(nums, lo, j - 1, k);
    }
};

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

275. H 指数 II

二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int sz = citations.size();
        int lo = 0, hi = sz;
        while(lo < hi)
        {
            auto mid = (lo + hi) >> 1;
            if(citations[mid] < sz - mid)
                lo = mid + 1;
            else
                hi = mid;
        }
        return sz - hi;
    }
};

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

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

参考236. Lowest Common Ancestor of a Binary Tree

但因为这题是BST，所以有别的方法

以下情况:

  1. 当p，q都在root左侧，那么p，q都在root左子树。
  2. 当p，q都在root右侧，那么p，q都在root右子树。
  3. 当第一次产生没在同一个子树时，这时候的root就是解
    1. p或q为root，剩下的在一边的树
    2. p，q在root两侧
迭代
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:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root)
        {
            if(root->val > p->val && root->val > q->val)
                root = root->left;
            else if(root->val < p->val && root->val < q->val)
                root = root->right;
            else
                return root;
        }
        return nullptr;
    }
};
递归
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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
            if(root->val > p->val && root->val > q->val)
                return lowestCommonAncestor(root->left, p, q);
            else if(root->val < p->val && root->val < q->val)
                return lowestCommonAncestor(root->right, p, q);
            return root;
    }
};

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

剑指 Offer 64. 求1+2+…+n

shuai
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int sumNums(int n) {
        bool x = n > 1 && sumNums(n - 1); // n == 1时候终止递归，递归栈返回，从ret从n=1开始加上去。 此处使用逻辑符短路，代替了原本if(n <= 1) return 1;
        ret += n;
        return ret;
    }
private:
    int ret = 0;
};

写法二

1
2
3
4
5
6
7
class Solution {
public:
    int sumNums(int n) {
        n && (n += sumNums(n - 1));
        return n;
    }
};

如果没题目限制使用递归

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int sumNums(int n) {
        if(n == 1)
            return 1;
        n += sumNums(n - 1);
        return n;
    }
};

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

剑指 Offer 55 - II. 平衡二叉树

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
/**
 * 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:
    bool isBalanced(TreeNode* root) {
        if(!root)
            return true;
        auto left = dfs(root->left);
        auto right = dfs(root->right);
        if(abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right))
            return true;
        return false;
    }
private:
    int dfs(TreeNode* root)
    {
        if(!root)
            return 0;
        return max(dfs(root->left), dfs(root->right)) + 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
/**
 * 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:
    bool isBalanced(TreeNode* root) {
        return dfs(root) != -1;
    }
private:
    int dfs(TreeNode* root)
    {
        if(!root)
            return 0;
        auto left = dfs(root->left);
        if(left == -1)
            return -1;
        auto right = dfs(root->right);
        if(right == -1)
            return -1;
        if(abs(left - right) > 1)
            return - 1;
        return max(left, right) + 1;
    }
};

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

剑指 Offer 61. 扑克牌中的顺子

两个条件

  1. 最大值减去最小值<5

  2. 没有重复的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        int ma = 0, mi = 14;
        unordered_set<int> set;
        for(auto& num : nums)
        {
            if(num == 0)
                continue;
            if(!set.emplace(num).second)
                return false;
            ma = max(ma, num);
            mi = min(mi, num);
        }
        return ma - mi < 5;
    }
};

法2

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isStraight(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int nz = 0;
        while(nums[nz] == 0)
            ++nz;
        for(int i = nz + 1; i < nums.size(); ++i)
            if(nums[i] == nums[i - 1])
                return false;
        return nums.back() - nums[nz] < 5;
    }
};

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

剑指 Offer 67. 把字符串转换成整数

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
class Solution {
public:
    int strToInt(string str) {
        int start = 0;
        while(str[start] == ' ')
            ++start;
        bool positive = true;
        if(str[start] == '+' || str[start] == '-')
            positive = str[start++] == '+' ? true : false;
        int ret = 0;;
        for(int i = start; i < str.size(); ++i)
        {
            int num = str[i] - '0';
            if(isValid(str[i]))
            {
                if(positive)
                {
                    if(ret > INT_MAX / 10 || (ret == INT_MAX / 10 && num >= INT_MAX % 10))
                        return INT_MAX;
                }else
                {
                    if(-ret < INT_MIN / 10 || (-ret == INT_MIN / 10 && -num <= INT_MIN % 10))
                        return INT_MIN;
                }
                ret = ret * 10 + num;
            }
            else
                break; 
        }
        return positive ? ret : -ret;
    }
private:
    bool isValid(char ch)
    {
        return ch >= '0' && ch <= '9';
    }
};

稍微优化一下 

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 strToInt(string str) {
        int start = 0;
        while(str[start] == ' ')
            ++start;
        bool positive = true;
        if(str[start] == '+' || str[start] == '-')
            positive = str[start++] == '+' ? true : false;
        int ret = 0;;
        for(int i = start; i < str.size(); ++i)
        {
            int num = str[i] - '0';
            if(isValid(str[i]))
            {
                if(ret > 214748364 || (ret == 214748364 && num > 7)) // 即使当num == 8时,如果是负数，虽然没越界，但是假设他越界了，依旧可以返回正确的值
                    return positive ? INT_MAX : INT_MIN;
                ret = ret * 10 + num;
            }
            else
                break; 
        }
        return positive ? ret : -ret;
    }
private:
    bool isValid(char ch)
    {
        return ch >= '0' && ch <= '9';
    }
};