leetcode每天5题-Day04

蔚来的笔试题…不是原题，在力扣的基础上有改进

1.比较版本号

leetcode165. 比较版本号-中等
①字符串分割
将版本号按照点号分割成修订号

var compareVersion = function(version1, version2) {
    
    const v1=version1.split('.');
    const v2=version2.split('.');
    for(let i=0;i<v1.length||i<v2.length;++i){
    
        let x=0,y=0;
        if(i<v1.length){
    
            x=parseInt(v1[i]);
        }
        if(i<v2.length){
    
            y=parseInt(v2[i]);
        }
        if(x>y) return 1;
        if(x<y) return -1;
    }
    return 0;
};

时间复杂度：O(n+m)或O(max(n,m))，这是等价的，其中 n是字符串 version1 的长度，m 是字符串version2的长度。
空间复杂度：O(n+m)，我们需要 O(n+m) 的空间存储分割后的修订号列表。
②双指针
方法①需要存储分割后的修订号，为了优化空间复杂度，我们可以在分割版本号的同时解析出修订号进行比较。

var compareVersion = function(version1, version2) {
    
    const len1=version1.length,len2=version2.length;
    let i=0,j=0;
    while(i<len1||j<len2){
    
        let x=0;
        for(;i<len1&&version1[i]!=='.';++i){
    
            // charCodeAt()方法可返回指定位置的字符的Unicode编码。这个返回值是 0 - 65535 之间的整数
            x=x*10+version1[i].charCodeAt()-'0'.charCodeAt();
        }
        ++i;  // 跳过点号

        let y=0;
        for(;j<len2&&version2[j]!=='.';++j){
    
            y=y*10+version2[j].charCodeAt()-'0'.charCodeAt();
        }
        ++j;

        if(x!==y){
    
            return x>y?1:-1;
        }
    }
    return 0;
};

空：O(1)，只需要常数的空间保存若干变量。

2.机器人回家

leetcode-1654.到家的最少跳跃次数-中等
最短路+证明
BFS
在题解里看到的js解法，怎么感觉不像BFS呢，也可能是我不懂BFS吧..

var minimumJumps = function(forbidden, a, b, x) {
    
    forbidden=new Set(forbidden);
    // 分别是当前的位置，步数，上一次是否向左跳过
    const nodes=[[0,0,false]];
    while(nodes.length){
    
        const [node,level,jumpLeft]=nodes.shift();
        // 剪枝
        // 1.不在forbidden(也可能是访问过的位置)
        // 2.位置是负数时
        // 3.位置大于等于(x的最大值+a的最大值+b的最大值)
        if(forbidden.has(node)||node<0||node>5999) continue;

        // 把访问过的位置加进forbidden 防止a===b 且x到达不了时造成死循环 
        forbidden.add(node);

        if(node===x){
    
            return level;
        }

        if(!jumpLeft){
    
            nodes.push([node-b,level+1,true]);
        }
        nodes.push([node+a,level+1,false]);
    }
    return -1;
};

看到的另一种js解法，BFS，还没提交，有时间再提交一下看看

/* 限制最大6000 dfs 每次可以尝试： 向前 向后（上次是向后的话，这次不可尝试向后） 记录如果是向右跳过的点就不要在尝试了，放到 forbidden 中 把 forbidden 转换为 object 来判断是否不可跳，数组判断太慢了 */
var minimumJumps = function(forbidden, a, b, x) {
    
  let ans = Infinity;
  let map = {
    };
  forbidden.forEach(v => {
    
    map[v] = true;
  })
  const dfs = (posi, step, right) => {
    
    if (posi < 0 || posi > 6000) return ;
    if (map[posi]) return ;
    if (right) map[posi] = true;
    if (posi === x) {
    
      return ans = Math.min(ans, step);
    }
    dfs(posi+a, step+1, true);
    if (right) {
    
      dfs(posi-b, step+1, false);
    }
  }
  dfs(0, 0, true);
  return ans === Infinity ? -1 : ans;
};

3.不使用加减乘除符号的四则运算

不直接使用+ - * /等运算符号来实现字符串数字的addition(strA,atrB)，subtraction(strA,atrB)，multiplication(strA,atrB)，division(strA,atrB)

不使用加减乘除符号的四则运算
不使用+ - * /，来进行加法运算;判断一个字符串是不是合法的数字

4.连续子数组最大和

leetcode53.最大子数组和-中等
剑指 Offer 42. 连续子数组的最大和-简单
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)
一个长度为n的数组，总共有n(n+1)/2个子数组。若用枚举法计算所有子数组的和，最快也需要O(n²)时间。
①分析数组的规律

var maxSubArray = function(nums) {
    
    if(nums==null||nums.length==0) return;
    let sum=nums[0],n=nums[0];
    for(let i=1;i<nums.length;i++){
    
        if(n>0){
    
            n+=nums[i];
        }else{
    
            n=nums[i];
        }   
        if(sum<n) sum=n;
    }
    return sum;
};

②动态规划

var maxSubArray = function(nums) {
    
    const len=nums.length;
    if(len==1) return nums[0];
    let ans=nums[0];
    const dp=new Array(len).fill(0);
    dp[0]=nums[0];
    for(let i=1;i<len;++i){
    
        dp[i]=Math.max(dp[i-1],0)+nums[i];
        ans=Math.max(dp[i],ans);
    }
    return ans;
};

力扣官方更简洁版：

var maxSubArray = function(nums) {
    
    let pre = 0, maxAns = nums[0];
    nums.forEach((x) => {
    
        pre = Math.max(pre + x, x);
        maxAns = Math.max(maxAns, pre);
    });
    return maxAns;
};

时间复杂度：O(n)，其中 n为 nums数组的长度。我们只需要遍历一遍数组即可求得答案。
空间复杂度：O(1)，我们只需要常数空间存放若干变量。
③分治

5.二叉树中的最大路径和

leetcode124. 二叉树中的最大路径和-困难
DFS题…
①dfs+递归

var maxPathSum = function(root) {
    
    var ans=-9999;
    dfs(root);
    return ans;
    function dfs(root){
    
        if(!root) return 0;
        let left=dfs(root.left);
        let right=dfs(root.right);
        ans=Math.max(ans,root.val+left+right);
        return Math.max(0,Math.max(left,right)+root.val);
    }
};

②递归
maxGain()：计算二叉树中的一个节点的最大贡献值，

var maxPathSum = function(root) {
    
    let maxSum=Number.NEGATIVE_INFINITY;
    maxGain(root);
    return maxSum;
    function maxGain(root){
    
        if(root==null) return 0;

        // 递归计算左右节点的最大贡献值
        // 只有最大贡献值大于0时 才会选取对应子节点
        let leftGain=Math.max(maxGain(root.left),0);
        let rightGain=Math.max(maxGain(root.right),0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        let priceNewpath=root.val+leftGain+rightGain;

        //更新
        maxSum=Math.max(maxSum,priceNewpath);

        return root.val+Math.max(leftGain,rightGain);
    }
};

6.矩阵中的最小路径和

leetcode64. 最小路径和-中等
剑指 Offer II 099. 最小路径之和-中等
题目： 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。(每次只能向下或者向右移动一步。)

动态规划

特殊情况：第一列与第一行的元素
普通情况：元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值
根据写出状态转移方程(略)

var minPathSum = function(grid) {
    
    if(grid.length==0||grid[0].length==0||grid==null) return 0;
    // m行 n列
    let m=grid.length,n=grid[0].length;
    const dp = new Array(m).fill(0).map(() => new Array(n).fill(0));

dp[0][0]=grid[0][0];
// 因为dp[0][0]已经初始化了 所以i从1开始
for(let i=1;i<m;i++){
    
    dp[i][0]=dp[i-1][0]+grid[i][0];
}
for(let j=1;j<n;j++){
    
    dp[0][j]=dp[0][j-1]+grid[0][j];
}
for(let i=1;i<m;i++){
    
    for(let j=1;j<n;j++){
    
        dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
    }
}
return dp[m-1][n-1];
};

不知道这道题能不能用bfs解决？

关于JS中用Array.fill()初始化 二维数组
宫水三叶的题解中提到的不同路径问题：

动态规划入门

今天Day05了，而我刚写完Day04…