正文 

当前位置： 首页 > 程序 > java教程

力扣刷题：矩阵置零（java实现）(代码片段)

谦谦均 谦谦均     2023-01-29     376

关键词：

题目：给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶：

  • 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

实例1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

实例2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -2^31 <= matrix[i][j] <= 2^31 - 1

标签：数组、哈希表、矩阵

简单解法：只需要两个数组分别存储该行或者该列有没有0值，比如第二列（4，2）位置是0，那么把4，2存到定义的数组中，具体代码如下所示：

public void setZeroes(int[][] matrix) 
        int m = matrix.length;//行
        int n =matrix[0].length;//列
        int[] arrm = new int[m];//记录每行是否有0
        int[] arrn = new int[n];//记录每列是否有0
        //查询是0的行列值
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
                if(matrix[i][j] == 0)
                    arrm[i] = 1;
                    arrn[j] = 1;
                
            
        

        //再次遍历，将矩阵置零
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
                if(arrm[i] ==1 || arrn[j] ==1)
                    matrix[i][j] = 0;

上面这种方法需要额外的n+m的空间，在原矩阵的基础上进行操作，可以把这m+n的空间省下来。大概思路如下：

  • 判断第一行和第一列是否有0值，并用一个参数记录下来
  • 遍历矩阵，使用第一行和第一列存储该行或者该列有没有0值
  • 根据第一行和第一列的值，修改第一行和第一列以外的所有元素
  • 根据标记修改第一行和第一列的值

具体代码如下：

public static void setZeroes(int[][] matrix) 
        int m = matrix.length;
        int n = matrix[0].length;
        //将0的行列值赋值给第一行和第一列
        //判断第一行和第一列有没有0
        int zerom = -1;
        int zeron = -1;
        for (int i = 0; i < m; i++) 
            for (int j = 0; j < n; j++) 
                if(matrix[i][j] == 0)
                    if(i == 0)
                        zeron = 0;//第一行有0
                    
                    if(j == 0)
                        zerom = 0;//第一列有0
                    
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                
            
        
        //循环矩阵，置零
        for (int i = 1; i < m; i++) 
            for (int j = 1; j < n; j++) 
                if(matrix[0][j] == 0 || matrix[i][0] == 0)
                    matrix[i][j] = 0;
                
            
        
        if(zerom == 0)
            for (int i = 0; i < m; i++) 
                matrix[i][0] = 0;
            
        
        if(zeron == 0)
            for (int i = 0; i < n; i++) 
                matrix[0][i] = 0;

力扣刷题：合并区间（java实现）(代码片段)

题目描述：以数组intervals表示若干个区间的集合，其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。示例1：输入：in... 查看详情

力扣刷题：寻找峰值（java实现）(代码片段)

题目：峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设nums[-1]=nums[n]=... 查看详情

力扣刷题：岛屿数量（java实现）(代码片段)

给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以... 查看详情

力扣刷题：全排列（java实现）(代码片段)

题目：给定一个不含重复数字的数组nums，返回其所有可能的全排列。你可以按任意顺序返回答案。示例1：输入：nums=[1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例2：输入：nums=[0,1]输出&#x... 查看详情

力扣刷题：字母异位词分组（java实现）(代码片段)

题目：给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母都恰好只用一次。示例1:输入:strs=["eat... 查看详情

力扣刷题：单词搜索（java实现）(代码片段)

题目：给定一个mxn二维字符网格board和一个字符串单词word。如果word存在于网格中，返回true；否则，返回false。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相... 查看详情

力扣刷题：快乐数（java实现）(代码片段)

题目描述：编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为1，也可能是无限循环但始终变... 查看详情

力扣刷题：最长回文子串（java实现）(代码片段)

题目：给你一个字符串s，找到s中最长的回文子串。示例1：输入：s="babad"输出："bab"解释："aba"同样是符合题意的答案。【个人建议最好取第一个】示例2：输入：s="cbbd"... 查看详情

力扣刷题：前k个高频元素（java实现）(代码片段)

题目：给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按任意顺序返回答案。示例1:输入:nums=[1,1,1,2,2,3],k=2输出:[1,2]示例2:输入:nums=[1],k=1输出:[1]提示：1<=nums.length<=... 查看详情

力扣刷题：电话号码的字母组合（java实现）(代码片段)

题目：给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。示例1：输入：digits="23"... 查看详情

力扣刷题：三数之和（java实现）(代码片段)

题目：给你一个包含n个整数的数组nums，判断nums中是否存在三个元素a，b，c，使得a+b+c=0？请你找出所有和为0且不重复的三元组。标签：数组，双指针，排序注意：答案中不可以包... 查看详情

力扣刷题：无重复字符的最长子串（java实现）(代码片段)

题目：给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。示例1:输入:s="abcabcbb"输出:3解释:因为无重复字符的最长子串是“abc”，所以其长度为3。示例2:输入:s="bbbbb"输出:1解释:因为... 查看详情

力扣刷题笔记--304二维区域和检索-矩阵不可变前缀和(代码片段)

304二维区域和检索-矩阵不可变作者：AC_OIer链接：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/xia-ci-ru-he-zai-30-miao-nei-zuo-chu-lai-ptlo/来源：力扣（LeetCode）著作权归 查看详情

力扣刷题：从前序与中序遍历序列构造二叉树（java实现）(代码片段)

题目：给定一棵树的前序遍历preorder与中序遍历inorder。请构造二叉树并返回其根节点。示例1:Input:preorder=[3,9,20,15,7],inorder=[9,3,15,20,7]Output:[3,9,20,null,null,15,7]示例2:Input:preorder=[-1],inorder=[-1]Output:[- 查看详情

力扣刷题：填充每个节点的下一个右侧节点指针（java实现）(代码片段)

题目：给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：structNodeintval;Node*left;Node*right;Node*next;填充它的每个next指针，让这个指针指向其下一个右侧节点。如果... 查看详情

力扣刷题详解(含代码动态展示)(代码片段)

(文章目录)一、448.找到所有数组中消失的数字1.完整过程动态展示2.代码实现int*findDisappearedNumbers(int*nums,intnumsSize,int*returnSize)int*ptr=(int*)malloc(sizeof(int)*numsSize);intindex=0;intnoindex=0;while(index<numsSize)if(num 查看详情

力扣刷题每日打卡(代码片段)

​力扣刷题：重新排列数组：/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情

力扣刷题每日打卡(代码片段)

​力扣刷题：重新排列数组：/***Note:Thereturnedarraymustbemalloced,assumecallercallsfree().*/int*shuffle(int*nums,intnumsSize,intn,int*returnSize)if(numsSize==1)*returnSize=1;returnnums;in 查看详情