当前位置：网站首页>leetcode 5 questions a day-Day01

leetcode 5 questions a day-Day01

2022-07-30 02:50:00 【Qilixiang 777】

1.接雨水

leetcode42.接雨水-困难
在这里插入图片描述
①动态规划
Create both lengths 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].
Traverse each subscript position to get the total amount of rainwater that can be received.
时：O(n),其中 n 是数组height的长度.计算数组leftMax 和 rightMax 的元素值各需要遍历数组height 一次,计算能接的雨水总量还需要遍历一次.
空：O(n),其中 n 是数组height 的长度.需要创建两个长度为 n 的数组 leftMax 和rightMax.
②单调栈(not yet understood)
时：O(n)
空：O(n)
③双指针
空间优化：O(n)–>O(1),Use double pointers and two variables instead of two arrays（leftMax 和rightMax）
时：O(n),其中 n 是数组height 的长度.The total number of movements of the two pointers does not exceed 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.最长公共前缀-简单
Write a function to find the longest common in an array of strings前缀.
如果不存在公共前缀,返回空字符串 “”.
①横向扫描
依次遍历字符串数组中的每个字符串,对于每个遍历到的字符串,更新最长公共前缀,当遍历完所有的字符串以后,即可得到字符串数组中的最长公共前缀.
时：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];
};