Day6–HOT100–238. 除自身以外数组的乘积，41. 缺失的第一个正数，73. 矩阵置零
每日刷题系列。今天的题目是力扣HOT100题单。
题目类型：普通数组，矩阵。（方法：前缀，置换，哈希）
238. 除自身以外数组的乘积
思路【@灵艾山茶府】：
对于i位置除自身以外的数组乘积，等于前缀积乘后缀积。
注意构建前缀积的时候，是除自身外的，所以第一个数要赋值为1，然后从第二个数来时累乘。
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
// 前缀积
int[] preProd = new int[n];
preProd[0] = 1;
for (int i = 1; i < n; i++) {
preProd[i] = preProd[i - 1] * nums[i - 1];
}
// 后缀积
int[] postProd = new int[n];
postProd[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
postProd[i] = postProd[i + 1] * nums[i + 1];
}
// 对于i位置除自身以外的数组乘积，等于前缀积乘后缀积
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = preProd[i] * postProd[i];
}
return res;
}
}
思路【@灵艾山茶府】：
使用O(1)额外空间的办法。实际上是使用了O(n)，但是题目说返回值不算。
先求后缀积，然后直接把结果乘到里面。前缀积就用单一变量累乘就行了。
（注意乘的时机，先求完结果，再累乘pre）
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] postProd = new int[n];
postProd[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
postProd[i] = postProd[i + 1] * nums[i + 1];
}
int pre = 1;
for (int i = 0; i < n; i++) {
// 此时 pre 为 nums[0] 到 nums[i-1] 的乘积，直接乘到 suf[i] 中
postProd[i] *= pre;
pre *= nums[i];
}
return postProd;
}
}
41. 缺失的第一个正数
思路【@灵艾山茶府】：
换座位的思路。
假设索引从1开始。第i个学生应该坐在i位置的椅子上。如果不是则换回去对的位置。换完之后，第一个没坐在合适位置上的人，就是答案。如果全部都坐在对的位置上了，返回n+1.
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
// 如果当前学生的学号在 [1,n] 中，但（真身）没有坐在正确的座位上
while (nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
// 那么就交换 nums[i] 和 nums[j]，其中 j 是 i 的学号
// 减一是因为数组下标从 0 开始
int j = nums[i] - 1;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
// 找第一个学号与座位编号不匹配的学生
for (int i = 0; i < n; i++) {
if (nums[i] != i + 1) {
return i + 1;
}
}
// 所有学生都坐在正确的座位上
return n + 1;
}
}
看了答案都看不懂的系列。太笨了唉。
能用
i = nums[i]判断吗？不能，因为会死循环。可以把
i=nums[i]套一层nums，用nums[i]=nums[nums[i]]判断。! 这时候是我的脑子死循环了……………………
直接抄吧，下次再做。
73. 矩阵置零
思路【我】：
使用两个set记录要置零的行索引和列索引。
class Solution {
public void setZeroes(int[][] matrix) {
// 横向，可以用Arrays.fill(matrix[i],0);
int n = matrix.length;
int m = matrix[0].length;
Set<Integer> seti = new HashSet<>();
Set<Integer> setj = new HashSet<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
seti.add(i);
setj.add(j);
}
}
}
for (int i : seti) {
Arrays.fill(matrix[i], 0);
}
for (int j : setj) {
for (int i = 0; i < n; i++) {
matrix[i][j] = 0;
}
}
return;
}
}
也有优化空间的版本，但是我觉得没必要，写起来太麻烦，那一丁点空间又没什么意义。
思路【@powcai】：
关键思想: 用matrix第一行和第一列记录该行该列是否有0,作为标志位
但是对于第一行,和第一列要设置一个标志位,为了防止自己这一行(一列)也有0的情况.注释写在代码里,直接看代码很好理解!
代码【@powcai】：
class Solution {
public void setZeroes(int[][] matrix) {
int row = matrix.length;
int col = matrix[0].length;
boolean row0_flag = false;
boolean col0_flag = false;
// 第一行是否有零
for (int j = 0; j < col; j++) {
if (matrix[0][j] == 0) {
row0_flag = true;
break;
}
}
// 第一列是否有零
for (int i = 0; i < row; i++) {
if (matrix[i][0] == 0) {
col0_flag = true;
break;
}
}
// 把第一行第一列作为标志位
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
// 置0
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if (row0_flag) {
for (int j = 0; j < col; j++) {
matrix[0][j] = 0;
}
}
if (col0_flag) {
for (int i = 0; i < row; i++) {
matrix[i][0] = 0;
}
}
}
}