lc-day7

发表于

397. 整数替换

每日一题

简单的递归，注意值的边界问题

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int res = 0x3f3f3f3f;
    int integerReplacement(long long n) {
        if(n == 1) return 0;
        if(n & 1) {
            return 1 + min(integerReplacement(n - 1), integerReplacement(n + 1));
        }
        return 1 + integerReplacement(n / 2);
    }
};

530.⼆叉搜索树的最⼩绝对差

题目

很简单的题目,把握好中序遍历就行了,都是些小细节

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int ans = INT_MAX;
    TreeNode* node = NULL;
    int getMinimumDifference(TreeNode* root) {
        if(root->left) ans = getMinimumDifference(root->left);
        if(node != nullptr) ans = min(ans, root->val - node->val);
        node = root;
        if(root->right) ans = getMinimumDifference(root->right);
        return ans;
    }
};

501.⼆叉搜索树中的众数

题目

水题，先上自己的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    unordered_map<int, int> p;
    int mi = -1;
    vector<int> vec;
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        for(auto &[a, b] : p){
            if(mi == b) vec.push_back(a);
        }
        return vec;
    }

    void dfs(TreeNode* root){
        if(root == nullptr) return ;
        dfs(root->left);
        p[root->val]++;
        mi = max(p[root->val], mi);
        dfs(root->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
//没啥说的,随便改改就好了
class Solution {
public:
    int mi = 1;
    vector<int> vec;
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return vec;
    }
    TreeNode* pre = NULL;
    int count = 1;
    void dfs(TreeNode* root){
        if(root == nullptr) return ;
        dfs(root->left);
        if(pre != NULL && pre->val == root->val) {
            count++;
            if(count > mi) {
                mi = count;
                vec.clear();
                vec.push_back(root->val);
            }
            else if(count == mi) vec.push_back(root->val);
        }
        else if(pre == nullptr || pre->val != root->val) {
            count = 1;
            if(count == mi) vec.push_back(root->val);
        }
        pre = root;
        dfs(root->right);
    }
};

二叉树所有的迭代法周目二再说！