我是靠谱客的博主 粗暴草丛,最近开发中收集的这篇文章主要介绍leetcode每天5题-Day101.矩阵置零2.合并区间3.求数列的和4.水仙花数5.蓄水,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

目录

  • 1.矩阵置零
  • 2.合并区间
  • 3.求数列的和
  • 4.水仙花数
  • 5.蓄水

落下了day07、day08、day09…
完了…过了12点了…到day11了

1.矩阵置零

leetcode73. 矩阵置零-中等
题目:给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。
请使用原地算法。
了解原地算法。
①使用标记数组
用两个标记数组分别记录每一行和每一列是否有零出现
(1).首先遍历该数组一次,如果某个元素0,那么就将该元素所在的行和列所对应标记数组的位置置为 true
(2).最后再次遍历该数组,用标记数组更新原数组

var setZeroes = function(matrix) {
    const m = matrix.length,n = matrix[0].length;
    const clo=new Array(n).fill(false);
    const row=new Array(m).fill(false);
    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(matrix[i][j]==0){
                clo[j]=true;
                row[i]=true;
            }
        }
    }

    for(let i=0;i<m;i++){
        for(let j=0;j<n;j++){
            if(row[i]||clo[j]){
                matrix[i][j]=0;
            }
        }
    }
};

注:标记数组标记的是整行/整列,若某一行/列为0,则标记数组的整行/整列都被标记为true
时间复杂度:O(mn),其中 m是矩阵的行数,n是矩阵的列数。我们至多只需要遍历该矩阵两次。

空间复杂度:O(m+n),其中m是矩阵的行数,n是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。
②使用两个标记变量

var setZeroes = function(matrix) {
    const m = matrix.length,n = matrix[0].length;
    let col=false;
    let row=false;

    // 若第一列有0  把clo置true
    for(let i=0;i<m;i++){
        if(matrix[i][0]==0){
            col=true;
        }
    }

    // 若第一行有0  把row置true
    for(let j=0;j<n;j++){
        if(matrix[0][j]==0){
            row=true;
        }
    }

    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            if(matrix[i][j]==0){
                matrix[i][0]=matrix[0][j]=0;
            }
        }
    }

    // 对于除去第一行和第一列的剩余矩阵  若对应的第一行/列有0 则把其对应的某行/列置0
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            if(matrix[i][0]==0||matrix[0][j]==0){
                matrix[i][j]=0;
            }
        }
    }

    if(col){
        for(let i=0;i<m;i++){
            matrix[i][0]=0;
        }
    }

    if(row){
        for(let j=0;j<n;j++){
            matrix[0][j]=0;
        }
    }
};

个人感觉这个方法好难理解啊,下面????这个双重for循环想好一会儿才恍然大明白....

for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            if(matrix[i][0]==0||matrix[0][j]==0){
                matrix[i][j]=0;
            }
        }
    }

时间复杂度:O(mn),其中m是矩阵的行数,n是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度:O(1),我们只需要常数空间存储若干变量。
③使用一个标记变量

2.合并区间

leetcode56. 合并区间-中等
题目:以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。
①排序
将列表中的区间按照左端点升序排序

var merge = function(intervals) {
    // 按区间的左端点排序
    intervals.sort((a,b)=>a[0]-b[0]);

    const ans=[];
    for(let i=0;i<intervals.length;i++){
        let l=intervals[i][0],r=intervals[i][1];
        //  区间段中的区间左端点大于ans中右端点
        if(ans.length==0||l>ans[ans.length-1][1]){
            ans.push([l,r]);
        }else{
            // 更新ans中右端点的值
            ans[ans.length-1][1]=Math.max(ans[ans.length-1][1],r);
        }
    }
    return ans;
};

3.求数列的和

数列定义: 数列的第一项为n,以后各项为前一项的平方根,求数列的前m项的和
输入描述: 输入数据有多组,每组占一行,由两个整数n(n<10000)m(m<1000)组成。
n和m的含义如前所述
输出描述: 对于每组输入数据,输出该数列的和,每个测试实例占一行,要求精度保留2位小数

var m;
var sum,n;
var sc

while(sc = read_line()){
	var arr = sc.split(' ');
  n=parseInt(arr[0]);
  m=parseInt(arr[1]);
  sum=0;
  for(var i=0;i<m;i++){
      sum=sum+n;
      n=Math.sqrt(n);
  }
  print(sum.toFixed(2));
}

4.水仙花数

定义: 指一个三位数,它的各位数字的立方和等于其本身。现在要求输出所有在m和n范围内的水仙花数
输入描述: 输入数据有多组,每组占一行,包括两个整数m和n(100<=m<=n<=999)
输出描述: 对于每个测试实例,要求输出所有在给定范围内的水仙花数,如果给定范围内不存在水仙花数,则输出no;每个测试实例的输出占一行

var sc;
while(sc = read_line()){
    var arr = sc.split(' ');
    n=parseInt(arr[1]);
    m=parseInt(arr[0]);
    if(100<=m&&m<=n&&n<=999){
        var out = [];
        var j=0;
        for(var i=m;i<=n;i++)
        {
            var geWei,shiWei,baiWei;
            baiWei=parseInt(i/100);
            shiWei=parseInt((i-baiWei*100)/10);
            geWei=i-baiWei*100-shiWei*10;
            if(i==geWei*geWei*geWei+shiWei*shiWei*shiWei+baiWei*baiWei*baiWei)
            {
                j=j+1;
                if(j>1){
                    out.push(" "+i);
                }
                else{
                    out.push(i);
                }
            }
        }
        if(j==0){
            out.push("no");
        }
        print(out.join(''));
    }
}

5.蓄水

leetcode-LCP 33. 蓄水-简单
题目:

刚看完题的我:这是简单题???
①贪心+堆排序
②枚举+贪心
③枚举+计数

最后

以上就是粗暴草丛为你收集整理的leetcode每天5题-Day101.矩阵置零2.合并区间3.求数列的和4.水仙花数5.蓄水的全部内容,希望文章能够帮你解决leetcode每天5题-Day101.矩阵置零2.合并区间3.求数列的和4.水仙花数5.蓄水所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(44)

评论列表共有 0 条评论

立即
投稿
返回
顶部