26. 删除排序数组中的重复项

描述

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。 你不需要考虑数组中超出新长度后面的元素。

思路

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    var t int
    for k, v := range nums {
        if k == 0 || v != nums[k-1] {
            nums[t] = v
            t++
        }
    }
    return t
}

73. 矩阵置零

题目

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

示例 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/set-matrix-zeroes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

最优解为解法三

解法一

使用两个数组，分别存储行和列对应为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

func setZeroes(matrix [][]int) {
    if len(matrix) < 1 {
        return
    }
    
    // 默认为false表示非0
    row, line := make([]bool, len(matrix)), make([]bool, len(matrix[0]))
    
    // 标记
    for kr, vr := range matrix {
        for kl, vl := range vr {
            if vl == 0 {
                row[kr] = true
                line[kl] = true
            }
        }
    }
    
    // 置零行
    for kr, vr := range row {
        // 这一行为0
        if vr {
            // 遍历当前行的所有列
            for k, _ := range matrix[0] {
                // matrix[为0的行][每一列] = 0
                matrix[kr][k] = 0
            }
        }
    }
    
    // 置零列
    for kl, vl := range line {
        // 这一列为零
        if vl {
            // 遍历当前列所有行
            for k, _ := range matrix {
                // matrix[每一行][为0的列] = 0
                matrix[k][kl] = 0
            }
        }
    }
}
// 执行用时 :16 ms, 在所有 Go 提交中击败了82.33%的用户
// 内存消耗 :5.0 MB, 在所有 Go 提交中击败了100.00%的用户
// 时间复杂度：O(mn)
// 空间复杂度：O(m+n)

解法二

题目要求常数级别的空间复杂度，这就要求在矩阵本身做标记

思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
// 遍历
// 将本行不为0的置m
[
  [0,m,m,0],
  [3,4,5,2],
  [1,3,1,5]
]
// 将本列不为0的置m
[
  [0,m,m,0],
  [m,4,5,m],
  [m,3,1,m]
]
// 遍历行列，将max置0
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

// 在测试用例为 [[-2147483648],[2],[3]] 时没过
func setZeroes(matrix [][]int) {
    for kr, vr := range matrix {
        for kl, vl := range vr {
            if vl == 0 {
                for s:=0; s < len(matrix[kr]); s++ {
                    if matrix[kr][s] != 0 {
                        matrix[kr][s] = math.MinInt32
                    }
                }
                
                for s:=0; s < len(matrix); s++ {
                    if matrix[s][kl] != 0 {
                        matrix[s][kl] = math.MinInt32
                    }
                }
            }
        }
    }
    
    for kr, vr := range matrix {
        for kl, vl := range vr {
            if vl == math.MinInt32 {
                matrix[kr][kl] = 0
            }
        }
    }
}

// 所以不能单纯用 min 来做标记
// 当元素为min的时候用max，当元素为max的时候用min
// 实际上输入含max的时候，依然过不了，再加上判断的话逻辑就太复杂了，建议寻求别的办法
func setZeroes(matrix [][]int) {
	for r := 0; r < len(matrix); r++ {
		for c := 0; c < len(matrix[r]); c++ {
			v := matrix[r][c]

			// 出现 0 或 被标记为min
			if v == 0 || v == math.MinInt64 {
				matrix[r][c] = math.MaxInt64

				// 行做标记
				for s := 0; s < len(matrix[r]); s++ {
					if matrix[r][s] != 0 && matrix[r][s] != math.MinInt64 {
						matrix[r][s] = math.MaxInt64
					} else if matrix[r][s] == 0 {
						matrix[r][s] = math.MinInt64
					}
				}

				// 列做标记
				for s := 0; s < len(matrix); s++ {
					if matrix[s][c] != 0 && matrix[s][c] != math.MinInt64 {
						matrix[s][c] = math.MaxInt64
					} else if matrix[s][c] == 0 {
						matrix[s][c] = math.MinInt64
					}
				}
			}
		}
	}

	// 所有max替换为0
	for r := 0; r < len(matrix); r++ {
		for c := 0; c < len(matrix[r]); c++ {
			v := matrix[r][c]
			if v == math.MaxInt64 {
				matrix[r][c] = 0
			}
		}
	}
}

思路三

不利用额外的空间来存储，将矩阵所在的行或列的第一个元素来记录本行或列是否需要置零

不过需要两个bool置记录第一行或第一例是否需要置零

 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

func setZeroes(matrix [][]int) {
    // 第一行 或 第一列 是否需要清0
    var brow, bcol bool
    
    for kr, vr := range matrix {
        for kc, vc := range vr {
            if vc == 0 {
                // 第0行
                if kr == 0 {
                    brow = true
                }
                
                // 第0列
                if kc == 0 {
                    bcol = true
                }
                
                // 做标记
                // 左边的5和上边的3需要标记 kr=1, kc=2 -> m[1][0], m[0][2] = 0, 0
                // 1, 2, 3, 4
                // 5, 7, 0, 8 
                // 9, 2, 3, 6
                matrix[kr][0], matrix[0][kc] = 0, 0
            }
        }
    }
    
    // 按照第一行第一列标记置0
    for i:=1; i<len(matrix); i++ {
        for j:=1; j<len(matrix[i]); j++ {
            if matrix[i][0]==0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    
    // 第一行第一列置0
    if brow {
        for j:=0; j<len(matrix[0]); j++ {
            matrix[0][j] = 0
        }
    }
    // 第一列置0
    if bcol {
        for i:=0; i<len(matrix); i++ {
            matrix[i][0] = 0
        }
    }
}

// 执行用时 :16 ms, 在所有 Go 提交中击败了82.33%的用户
// 内存消耗 :5.0 MB, 在所有 Go 提交中击败了100.00%的用户
// 时间复杂度：O(mn)
// 空间复杂度：O(1)

845. 数组中的最长山脉

题目

我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：

  • B.length >= 3
  • 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1] （注意：B 可以是 A 的任意子数组，包括整个数组 A。）

给出一个整数数组 A，返回最长 “山脉” 的长度。

如果不含有 “山脉” 则返回 0。

示例 1：

1
2
3

输入：[2,1,4,7,3,2,5]
输出：5
解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。

示例 2：

1
2
3

输入：[2,2,2]
输出：0
解释：不含 “山脉”。

提示：

1
2

0 <= A.length <= 10000
0 <= A[i] <= 10000

解答

遍历整个数组，维护三个状态

  • 不上升和下降
    • asc、desc置0
    • 直接往后
  • 上升：asc++
    • 若desc不为0➛证明是从新的山脚开始up➛asc初始化为1
    • 置desc为0[先升后降才算山脉]
  • 下降：desc++
    • 若asc不为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

// 执行用时：20 ms, 在所有 Go 提交中击败了95.71%的用户
// 内存消耗：6.2 MB, 在所有 Go 提交中击败了46.07%的用户
func longestMountain(arr []int) int {
	l := len(arr)
	if l < 3 {
		return 0
	}

	var asc, desc, max int
	for i := 1; i < l; i++ {
		switch {
		case arr[i] == arr[i-1]:
			asc, desc = 0, 0
		case arr[i] > arr[i-1]:
			// part1: 记录上升下降值
			asc++
			// part2: 上升下降后的逻辑
			// 上升的过程中，若desc还存在，证明是“从新的山底开始”，初始化本轮的desc为1
			if desc != 0 {
				asc = 1
			}
			// 上升过程 desc 要重置
			desc = 0
		case arr[i] < arr[i-1]:
			// part1: 记录上升下降值
			desc++
			// part2: 上升下降后的逻辑
			// 下降的过程，asc不为0，可以统计山脉[asc+desc表示宽度]
			if asc != 0 {
				max = maxInt(max, asc+desc)
			}
		}
	}

	// 如果有山顶，需要加进去
	if max != 0 {
		max++
	}
	return max
}

func maxInt(a, b int) int {
	if a > b {
		return a
	}
	return b
}

454. 四数相加 II

题目

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。

例如:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

输入:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
输出:
2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/4sum-ii 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

由于是四个组合，将它们分为两等份

对一组遍历求和后，记录到map内。

另外一组遍历求和，只要存在map内的相反数，即代表得到结果

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func fourSumCount(A []int, B []int, C []int, D []int) int {
    var (
        mp = make(map[int]int, 0)
        ret int
    )
    for _, a := range A {
        for _, b := range B {
            mp[a+b]++
        }
    }

    for _, c := range C {
        for _, d := range D {
            ret += mp[-c-d]
        }
    }
    return ret
}