13. 最大子数组和（普通数组/53）

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
假设：1 <= nums.length <= $(10)^5$；$(-10)^4$ <= nums[i] <= $(10)^4$。

【分析】
Kadane算法：时间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution{
	public int MaxSubArray(int[] nums){
		int maxGlobal=nums[0];
		int maxHere=nums[0];
		for(int i=1;i<nums.Length;i++){//循环从第二个元素开始
			// 如果当前子数组的和加上当前元素大于当前元素本身，说明继续使用当前子数组更优（下面一行代码的第二项）
			// 否则，从当前元素开始新的子数组（下面一行代码的第一项）
			maxHere=Math.Max(nums[i],maxHere+nums[i]);
			// 更新全局最大子数组和
			maxGlobal=Math.Max(maxHere,maxGlobal);
		}
		return maxGlobal;
	}
}

18. 矩阵置零（矩阵/73）

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
假设：m == matrix.length；n == matrix[0].length；1 <= m, n <= 200；$(-2)^(31)$ <= matrix[i][j] <= $2^(31)$ - 1。

【分析】
原地算法，又称环形矩阵算法，输入的资料通常会被要输出的部分覆盖掉。
题解过程中就是，利用矩阵的第一行和第一列来记录这些信息，而不是额外使用数组，以便减少空间复杂度。
先记录首行首列是否本身含0；把有0的行或列标记在首行和首列；再遍历整个矩阵，通过首行首列的0，置零整行整列；最后再根据标记置零第一行第一列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public class Solution {
    public void SetZeroes(int[][] matrix) {
		//int[][] x=...，左项是行数，右项是列数
		//二维数组的表示：[[2,3],[1,2,3],[6],[5,0]]
		//上述数组有4行，第一行有2列……
		//x[0]=[2,3]; x[0]表示第一行
		int m=matrix.Length;
		int n=matrix[0].Length;
		bool firstRowHasZero=false;
		bool firstColHasZero=false;
		// for(int j=0;j<n;j++){
		// 	if(matrix[0][j]==0){
		// 		firstRowHasZero=true;
		// 		break;
		// 	}
		// }
		// for(int i=0;i<m;i++){
		// 	if(matrix[i][0]==0){
		// 		firstColHasZero=true;
		// 		break;
		// 	}
		// }
		//for循环写法和Any的LINQ语法时间空间复杂度一致，时间复杂度=O(n)，空间复杂度=O(1)。（但是LINQ看起来更简洁）
		firstRowHasZero=matrix[0].Any(c=>c==0);//检查第一行是否存在0
		firstColHasZero=matrix.Any(r=>r[0]==0);//检查第一行是否存在0
		
		for(int i=1;i<m;i++){
			for(int j=1;j<n;j++){
				if(matrix[i][j]==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[i][0]==0 || matrix[0][j]==0){
					matrix[i][j]=0;
				}
			}
		}
		
		if(firstRowHasZero){
			for(int j=0;j<n;j++){
				matrix[0][j]=0;
			}
		}
		if(firstColHasZero){
			for(int i=0;i<m;i++){
				matrix[i][0]=0;
			}
		}
    }
}