leetcode-5

  1. 二叉树的最大深度

左子树最大深度为l 右子树最大深度为r，该二叉树的最大深度为max(l,r)+1

深度优先搜索

1
2
3
4
5
6
7

int maxDepth(TreeNode* root) {
    if(root==nullptr){
        return 0;
    }
    return max(maxDepth(root->left),maxDepth(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

int maxDepth(TreeNode* root) {
    if(root== nullptr){
        return 0;
    }
    queue<TreeNode*>Q;
    Q.push(root);
    int ans =0;
    while(!Q.empty()){
        int sz =Q.size();
        while(sz>0){
            TreeNode *node =Q.front();
            Q.pop();
            if(node->left){
                Q.push(node->left);
            }
            if(node->right){
                Q.push(node->right);
            }
            sz--;
        }
        ans++;
    }
    return ans;
}
  1. 爬楼梯

核心点在于最后一级台阶是怎么上的，是爬一级还是爬两级，从后往前递推

1
2
3
4
5
6
7
8
9
10
11
12
13

int climbStairs(int n) {
    if(n<2){
        return 1;
    }
    int fib[2]={1,1};
    for(int i=2;i<=n;i++){
        int next=fib[0]+fib[1];
        fib[0]=fib[1];
        fib[1]=next;
    }
    return fib[1];
}

思想是这样，但是有其他更快的方式实现

  1. 加一

记录数组尾部出现了多少个9

1
2
3
4
5
6
7
8
9
10
11
12
13
14

vector<int> plusOne(vector<int>& digits) {
    int n=digits.size();
    for(int i=n-1;i>=0;i--){
        if(digits[i]==9){
            digits[i]=0;
        }else{
            digits[i]+=1;
            return digits;
        }        
    }
    digits.insert(digits.begin(),1);
    return digits;
}
  1. 阶乘后的零

计算质因子5的个数和2的个数，取少得一个;又因为2的个数肯定比5的个数多 

1
2
3
4
5
6
7
8
9
10

int trailingZeroes(int n) {
    int count=0;
    while(n>=5){
        n=n/5;
        count +=n;
    }
        
    return count;
}
  1. 多数元素

hash表遍历最简单，复杂度比较高

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int majorityElement(vector<int>& nums) {
    unordered_map<int,int> counts;
    int major=0;
    int cnt =0;
    for(int num:nums){
        counts[num]++;
        if(counts[num]>cnt){
            major =num;
            cnt = counts[num];
        }
    }
    return major;
}

还可以用排序，直接去中间的数值（注意本身的条件）

1
2
3
4
5

int majorityElement(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    return nums[nums.size() / 2];
}

注意本身的条件