leetcode自练题目

1. 二叉树深度

int maxDepth(TreeNode* root) {
        if(root==NULL) return  0;
        int left=maxDepth(root->left);
        int right=maxDepth(root->right);
        return left>right?(left+1):(right+1);
    }

2. 左右子树互换

TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return NULL;
        TreeNode* left=invertTree(root->left);
        TreeNode* right=invertTree(root->right);
        root->right=left;
        root->left=right;
        return root;
    }

3. 对称二叉树

bool check(TreeNode* p,TreeNode* q){
        if(!p&&!q) return true;
        if(!p||!q) return false;
        return p->val==q->val && check(p->left,q->right) && check(p->right,q->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root,root);
    }

4. 二叉树的直径

class Solution {
    int ans=0;
public:
    int diameterOfBinaryTree(TreeNode* root) {
        maxdepth(root);
        return ans;
    }
    int maxdepth(TreeNode* root){
        if(root==NULL){
            return 0;
        }
        int left=maxdepth(root->left);
        int right=maxdepth(root->right);
        int now=left+right;
        ans=max(now,ans);
        return max(left,right)+1;
    }
};

5. 二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> res;
        if (root != nullptr) que.push(root);
        while (!que.empty()) {
            vector<int> tmp;
            for(int i = que.size(); i > 0; --i) {
                root = que.front();
                que.pop();
                tmp.push_back(root->val);
                if (root->left != nullptr) que.push(root->left);
                if (root->right != nullptr) que.push(root->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

作者：Krahets
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/2361604/102-er-cha-shu-de-ceng-xu-bian-li-yan-du-dyf7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

6. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

int longestConsecutive(vector<int>& nums) {
        if(nums.size()==0) return 0;
        int ans=1;
        int max1=1;
        sort(nums.begin(),nums.end());
        for(int i=1;i<nums.size();i++){
            if(nums[i]==nums[i-1]+1){
                ans++;
            }
            else if(nums[i]==nums[i-1]){
                continue;
            }
            else{
                max1=max(ans,max1);
                ans=1;
            }
        }
        return max(ans,max1);
    }

7.移动0

void moveZeroes(vector<int>& nums) {
        int i=0,j=0;
        while(j<nums.size()){
            if(nums[j]!=0){
                swap(nums[i],nums[j]);
                i++;
            }
            j++;
        }
    }

8. 盛最多水的容器

int maxArea(vector<int>& height) {
        int l=0;
        int r=height.size()-1;
        int ans=0;
        while(l<r){
            int area=min(height[l],height[r]) * (r-l);
            ans=max(ans,area);
            if(height[l]<=height[r]){
                ++l;
            } 
            else{
                --r;
            }
        }
        return ans;
    }

9. 无重复字符的最长字串

int lengthOfLongestSubstring(string s) {
    unordered_map<char,int> hash;
    int res=0;
    for(int i=0,j=0;j<s.size();j++){
        hash[s[j]]++;
        while(hash[s[j]]>1){
            hash[s[i++]]--;}
        res = max(res,j-i+1);
        }
     return res;

10. 和为k的子数组

int subarraySum(vector<int>& nums, int k) {
        int cout=0;
        for(int i=0;i<nums.size();++i){
            int sum=0;
            for(int j=i;j>=0;--j){
                sum+=nums[j];
                if(sum==k){
                    cout++;
                }
            }
        }
        return cout;
    }