leetcode每天5题-Day01

1.接雨水

leetcode42.接雨水-困难

①动态规划
创建两个长度都为 n 的数组 leftMax 和rightMax。对于0≤i<n，leftMax[i] 表示下标 i及其左边的位置中，height 的最大高度，rightMax[i] 表示下标 i及其右边的位置中，height 的最大高度。

对于0≤i<n，下标 i 处能接的雨水量等于min(leftMax[i],rightMax[i])−height[i]。
遍历每个下标位置即可得到能接的雨水总量。
时：O(n)，其中 n 是数组height的长度。计算数组leftMax 和 rightMax 的元素值各需要遍历数组height 一次，计算能接的雨水总量还需要遍历一次。
空：O(n)，其中 n 是数组height 的长度。需要创建两个长度为 n 的数组 leftMax 和rightMax。
②单调栈(还未理解)
时：O(n)
空：O(n)
③双指针
空间优化：O(n)–>O(1)，使用双指针和两个变量代替两个数组（leftMax 和rightMax）
时：O(n)，其中 n 是数组height 的长度。两个指针的移动总次数不超过 n
空：O(1)，只需要使用常数的额外空间。

2.两数之和

leetcode1.两数之和-简单
给定一个整数数组 nums 和一个整数目标值target，请你在该数组中找出 和为目标值target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
①暴力枚举
双重循环：找target-x
时：O(n²)
空：O(1)
②一遍遍历+哈希查找

var twoSum = function(nums, target) {
    
    // 一遍遍历+哈希查找
    const map=new Map();
    for(let i=0;i<nums.length;i++){
    
        const x=nums[i];
        if(map.has(target-x)){
    
            const index=map.get(target-x);
            return [i,index];
        }
        map.set(x,i);
    }
    return [];
};

时：O(n)，其中 n 是数组中的元素数量。对于每一个元素 x，我们可以 O(1)地寻找 target - x。
空：O(n)，其中 n 是数组中的元素数量。主要为哈希表的开销。

3.翻转二叉树

leetcode226.翻转二叉树-简单
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

①递归

var invertTree = function(root) {
    
    if(root==null) return null;
    // if(root.left)
    let temp=root.left;
    root.left=root.right;
    root.right=temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
};

时：O(n)
空：O(n)
②DFS（深度优先搜索）
③BFS（广度优先遍历）

4.最长公共前缀

leetcode14.最长公共前缀-简单
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。
①横向扫描
依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
时：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空：O(1)，使用的额外空间复杂度为常数。
②纵向扫描
纵向扫描时，从前往后遍历所有字符串的每一列，比较相同列上的字符是否相同，如果相同则继续对下一列进行比较，如果不相同则当前列不再属于公共前缀，当前列之前的部分为最长公共前缀。

	var longestCommonPrefix = function(strs) {
    
    // 纵向扫描
    if(!strs) return "";
    let len=strs[0].length;
    for(let i=0;i<len;i++){
    
        for(let j=1;j<strs.length;j++){
    
            if(i==strs[j].length||strs[0][i]!==strs[j][i]){
    
                return strs[0].substring(0,i);
            }
        }
    }
    return strs[0];
};

时：O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。
空：O(1)，使用的额外空间复杂度为常数。
③分治
④二分查找

5.无序数组中最大的两个数

参考：无序数组中找出最大的两个（K）数

补上昨天的…进度太慢了…