概述
目录
- 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.蓄水所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复