leetcode_数组
目录：
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。 你不需要考虑数组中超出新长度后面的元素。
思路
解答
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,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ]示例 2:
输入: [ [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的位置
再遍历两个数组，对矩阵的行或列进行置零
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)
解法二
题目要求常数级别的空间复杂度，这就要求在矩阵本身做标记
思路：
[
[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]
]
代码：
// 在测试用例为 [[-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置记录第一行或第一例是否需要置零
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：
输入：[2,1,4,7,3,2,5] 输出：5 解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。示例 2：
输入：[2,2,2] 输出：0 解释：不含 “山脉”。提示：
0 <= A.length <= 10000 0 <= A[i] <= 10000
解答
遍历整个数组，维护三个状态
- 不上升和下降
- asc、desc置0
- 直接往后
- 上升：asc++
- 若desc不为0➛证明是从新的山脚开始up➛asc初始化为1
- 置desc为0[先升后降才算山脉]
- 下降：desc++
- 若asc不为0➛证明之前上升过➛取历史宽度最大
// 执行用时：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 。
例如:
输入: 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内的相反数，即代表得到结果
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
}
