LeetCode Go · 数组与矩阵（3）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

1725. 可以形成最大正方形的矩形数目

简单1 种解法

标签：数组

题目、示例与约束

给你一个数组 rectangles ，其中 rectangles[i] = [li, wi] 表示第 i 个矩形的长度为 li 、宽度为 wi 。

如果存在 k 同时满足 k <= li 和 k <= wi ，就可以将第 i 个矩形切成边长为 k 的正方形。例如，矩形 [4,6] 可以切成边长最大为 4 的正方形。

设 maxLen 为可以从矩形数组 rectangles 切分得到的 最大正方形 的边长。

请你统计有多少个矩形能够切出边长为 maxLen 的正方形，并返回矩形 数目 。

 

示例 1：

输入：rectangles = [[5,8],[3,9],[5,12],[16,5]]
输出：3
解释：能从每个矩形中切出的最大正方形边长分别是 [5,3,5,5] 。
最大正方形的边长为 5 ，可以由 3 个矩形切分得到。

示例 2：

输入：rectangles = [[2,3],[3,7],[4,3],[3,7]]
输出：3

 

提示：

• 1 <= rectangles.length <= 1000
• rectangles[i].length == 2
• 1 <= li, wi <= 109
• li != wi

方法一：一次遍历 · Go 实现

思考

每个矩形能切出的最大正方形边长为 $min(l,w)$。要统计能达到全局最大边长的矩形个数。

一遍扫描维护当前最大边长 $mx$ 及其出现次数：发现更大边长则重置计数，相等则累加。不必单独再扫一遍。

我们定义一个变量 $ans$ 来记录当前最大边长的正方形的个数，定义另一个变量 $mx$ 来记录当前最大的边长。

遍历数组 $rectangles$，对于每个矩形 $[l,w]$，我们取 $x=min(l,w)$，如果 $mx<x$，说明我们找到了一个更大的边长，此时我们将 $mx$ 更新为 $x$，并将 $ans$ 更新为 $1$；如果 $mx=x$，说明我们找到了一个和当前最大边长相同的边长，此时我们将 $ans$ 增加 $1$。

最后返回 $ans$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $rectangles$ 的长度。空间复杂度 $O(1)$。

func countGoodRectangles(rectangles [][]int) (ans int) {
	mx := 0
	for _, e := range rectangles {
		x := min(e[0], e[1])
		if mx < x {
			mx = x
			ans = 1
		} else if mx == x {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1752. 检查数组是否经排序和轮转得到

简单1 种解法

标签：数组

题目、示例与约束

给你一个数组 nums 。nums 的源数组中，所有元素与 nums 相同，但按非递减顺序排列。

如果 nums 能够由源数组轮转若干位置（包括 0 个位置）得到，则返回 true ；否则，返回 false 。

源数组中可能存在 重复项 。

注意：数组 A 在轮转 x 个位置后得到长度相同的数组 B ，使得对于每一个有效的下标 i，满足 B[i] == A[(i+x) % A.length]。

 

示例 1：

输入：nums = [3,4,5,1,2]
输出：true
解释：[1,2,3,4,5] 为有序的源数组。
可以轮转 x = 2 个位置，使新数组从值为 3 的元素开始：[3,4,5,1,2] 。

示例 2：

输入：nums = [2,1,3,4]
输出：false
解释：源数组无法经轮转得到 nums 。

示例 3：

输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 为有序的源数组。
可以轮转 x = 0 个位置（即不轮转）得到 nums 。

 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

方法一：一次遍历 · Go 实现

思考

非降序数组至多轮转一次。环上下降点（ $nums[i-1]>nums[i]$，下标模 $n$）至多一个。

一次遍历统计这样的下降，个数不超过 $1$ 则合法。

要满足题目要求，那么数组 $\mathit{\text{nums}}$ 中最多只能存在一个元素，其值大于下一个元素，即 $nums[i]>nums[i+1]$。如果存在多个这样的元素，那么数组 $\mathit{\text{nums}}$ 无法通过轮转得到。

注意，数组 $\mathit{\text{nums}}$ 最后一个元素的下一个元素是数组 $\mathit{\text{nums}}$ 的第一个元素。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func check(nums []int) bool {
	cnt := 0
	for i, x := range nums {
		if x > nums[(i+1)%len(nums)] {
			cnt++
		}
	}
	return cnt <= 1
}

力扣原题 · Doocs 题解来源

1779. 找到最近的有相同 X 或 Y 坐标的点

简单1 种解法

标签：数组

题目、示例与约束

给你两个整数 x 和 y ，表示你在一个笛卡尔坐标系下的 (x, y) 处。同时，在同一个坐标系下给你一个数组 points ，其中 points[i] = [ai, bi] 表示在 (ai, bi) 处有一个点。当一个点与你所在的位置有相同的 x 坐标或者相同的 y 坐标时，我们称这个点是 有效的 。

请返回距离你当前位置 曼哈顿距离 最近的 有效 点的下标（下标从 0 开始）。如果有多个最近的有效点，请返回下标 最小 的一个。如果没有有效点，请返回 -1 。

两个点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 abs(x1 - x2) + abs(y1 - y2) 。

 

示例 1：

输入：x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]
输出：2
解释：所有点中，[3,1]，[2,4] 和 [4,4] 是有效点。有效点中，[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小，都为 1 。[2,4] 的下标最小，所以返回 2 。

示例 2：

输入：x = 3, y = 4, points = [[3,4]]
输出：0
提示：答案可以与你当前所在位置坐标相同。

示例 3：

输入：x = 3, y = 4, points = [[2,3]]
输出：-1
解释：没有 有效点。

 

提示：

• 1 <= points.length <= 104
• points[i].length == 2
• 1 <= x, y, ai, bi <= 104

方法一：直接遍历 · Go 实现

思考

有效点与给定点共享横坐标或纵坐标，要曼哈顿距离最小者的最小下标。 $n\le {10}^4$，扫一遍即可。

对每个有效点算 $|a-x|+|b-y|$，维护最小距离及其下标。

直接遍历 points 数组，对于 $points[i]$，如果 $points[i][0]=x$ 或者 $points[i][1]=y$，则说明 $points[i]$ 是有效点，计算曼哈顿距离，更新最小距离和最小距离的下标。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为 points 数组的长度。

func nearestValidPoint(x int, y int, points [][]int) int {
	ans, mi := -1, 1000000
	for i, p := range points {
		a, b := p[0], p[1]
		if a == x || b == y {
			d := abs(a-x) + abs(b-y)
			if d < mi {
				ans, mi = i, d
			}
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

1800. 最大升序子数组和

简单1 种解法

标签：数组

题目、示例与约束

给你一个正整数组成的数组 nums ，返回 nums 中一个 严格递增子数组 的最大可能元素和。

子数组是数组中的一个连续数字序列。

 

示例 1：

输入：nums = [10,20,30,5,10,50]
输出：65
解释：[5,10,50] 是元素和最大的升序子数组，最大元素和为 65 。

示例 2：

输入：nums = [10,20,30,40,50]
输出：150
解释：[10,20,30,40,50] 是元素和最大的升序子数组，最大元素和为 150 。 

示例 3：

输入：nums = [12,17,15,13,10,11,12]
输出：33
解释：[10,11,12] 是元素和最大的升序子数组，最大元素和为 33 。 

 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

方法一：直接模拟 · Go 实现

思考

题目要求的是连续且严格递增的子数组之和的最大值。若枚举全部子数组再检验是否升序，时间复杂度为 $O(n^2)$。 $n\le 100$，该做法可以通过，但会把大量不满足升序的区间一并检查。

升序一旦在某对相邻元素处断开，则跨越该处的任何区间都不再合法。因此只需从左到右维护当前这一段升序的和 $t$：能接上则累加并更新答案，否则从当前元素重新起段。一次遍历即可得到全局最大值。

我们用变量 $t$ 记录当前升序子数组的和，用变量 $ans$ 记录最大的升序子数组和。

遍历数组 $nums$：

如果当前元素是数组的第一个元素，或者当前元素大于前一个元素，那么将当前元素加入到当前升序子数组的和，即 $t=t+nums[i]$，并且更新最大升序子数组和 $ans=max(ans,t)$；否则，当前元素不满足升序子数组的条件，那么将当前升序子数组的和 $t$ 重置为当前元素，即 $t=nums[i]$。

遍历结束，返回最大升序子数组和 $ans$。

时间复杂度 $O(n)$，其中 $n$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$。

func maxAscendingSum(nums []int) int {
	ans, t := 0, 0
	for i, v := range nums {
		if i == 0 || v > nums[i-1] {
			t += v
			if ans < t {
				ans = t
			}
		} else {
			t = v
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1848. 到目标元素的最小距离

简单1 种解法

标签：数组

题目、示例与约束

给你一个整数数组 nums （下标 从 0 开始 计数）以及两个整数 target 和 start ，请你找出一个下标 i ，满足 nums[i] == target 且 abs(i - start) 最小化 。注意：abs(x) 表示 x 的绝对值。

返回 abs(i - start) 。

题目数据保证 target 存在于 nums 中。

 

示例 1：

输入：nums = [1,2,3,4,5], target = 5, start = 3
输出：1
解释：nums[4] = 5 是唯一一个等于 target 的值，所以答案是 abs(4 - 3) = 1 。

示例 2：

输入：nums = [1], target = 1, start = 0
输出：0
解释：nums[0] = 1 是唯一一个等于 target 的值，所以答案是 abs(0 - 0) = 0 。

示例 3：

输入：nums = [1,1,1,1,1,1,1,1,1,1], target = 1, start = 0
输出：0
解释：nums 中的每个值都是 1 ，但 nums[0] 使 abs(i - start) 的结果得以最小化，所以答案是 abs(0 - 0) = 0 。

 

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 104
• 0 <= start < nums.length
• target 存在于 nums 中

方法一：一次遍历 · Go 实现

思考

目标值保证出现，求与 $\mathit{\text{start}}$ 下标距离最小的出现位置。不必构造额外结构。

一次遍历所有等于 $\mathit{\text{target}}$ 的下标，取 $|i-\mathit{\text{start}}|$ 的最小值。

遍历数组，找到所有等于 $target$ 的下标，然后计算 $|i-start|$，取最小值即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$。

func getMinDistance(nums []int, target int, start int) int {
	ans := 1 << 30
	for i, x := range nums {
		if t := abs(i - start); x == target && t < ans {
			ans = t
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

1886. 判断矩阵经轮转后是否一致

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。

 

示例 1：

输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]]
输出：true
解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。

示例 2：

输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]]
输出：false
解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。

示例 3：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]]
输出：true
解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。

 

提示：

• n == mat.length == target.length
• n == mat[i].length == target[i].length
• 1 <= n <= 10
• mat[i][j] 和 target[i][j] 不是 0 就是 1

方法一：原地比较 · Go 实现

思考

判断 $mat$ 旋转 $0/90/180/270$ 度后是否能得到 $target$。可生成四份新矩阵再比较，但 $n\le 10$，原地对照即可。

四种旋转把 $(i,j)$ 分别映到 $(i,j)$、 $(j,n-1-i)$、 $(n-1-i,n-1-j)$、 $(n-1-j,i)$。用四位掩码同时检验，某格不匹配则关掉对应位，全部关掉即可提前失败。

我们观察矩阵的轮转规律，发现对于矩阵中的元素 $\text{mat}[i][j]$，它在轮转 90 度后会出现在 $\text{mat}[j][n-1-i]$ 的位置，在轮转 180 度后会出现在 $\text{mat}[n-1-i][n-1-j]$ 的位置，在轮转 270 度后会出现在 $\text{mat}[n-1-j][i]$ 的位置。

因此，我们可以用一个整数 $\mathit{\text{ok}}$ 来记录当前轮转的状态，初始值为 $0b1111$，表示四种轮转状态都可能。对于矩阵中的每个元素，我们比较它在不同轮转状态下的位置与目标矩阵中的对应位置的元素是否相等，如果不相等，则将对应的轮转状态从 $\mathit{\text{ok}}$ 中去掉。最后，如果 $\mathit{\text{ok}}$ 不为零，说明至少有一种轮转状态可以使矩阵与目标矩阵一致，返回 $\mathit{\text{true}}$；否则，返回 $\mathit{\text{false}}$。

时间复杂度 $O(n^2)$，其中 $n$ 是矩阵的大小。空间复杂度 $O(1)$。

func findRotation(mat [][]int, target [][]int) bool {
    n := len(mat)
    ok := 0b1111

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if mat[i][j] != target[i][j] {
                ok &= ^0b0001
            }
            if mat[j][n-1-i] != target[i][j] {
                ok &= ^0b0010
            }
            if mat[n-1-i][n-1-j] != target[i][j] {
                ok &= ^0b0100
            }
            if mat[n-1-j][i] != target[i][j] {
                ok &= ^0b1000
            }
            if ok == 0 {
                return false
            }
        }
    }

    return ok != 0
}

力扣原题 · Doocs 题解来源

1909. 删除一个元素使数组严格递增

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，如果 恰好 删除 一个 元素后，数组 严格递增 ，那么请你返回 true ，否则返回 false 。如果数组本身已经是严格递增的，请你也返回 true 。

数组 nums 是 严格递增 的定义为：对于任意下标的 1 <= i < nums.length 都满足 nums[i - 1] < nums[i] 。

 

示例 1：

输入：nums = [1,2,10,5,7]
输出：true
解释：从 nums 中删除下标 2 处的 10 ，得到 [1,2,5,7] 。
[1,2,5,7] 是严格递增的，所以返回 true 。

示例 2：

输入：nums = [2,3,1,2]
输出：false
解释：
[3,1,2] 是删除下标 0 处元素后得到的结果。
[2,1,2] 是删除下标 1 处元素后得到的结果。
[2,3,2] 是删除下标 2 处元素后得到的结果。
[2,3,1] 是删除下标 3 处元素后得到的结果。
没有任何结果数组是严格递增的，所以返回 false 。

示例 3：

输入：nums = [1,1,1]
输出：false
解释：删除任意元素后的结果都是 [1,1] 。
[1,1] 不是严格递增的，所以返回 false 。

示例 4：

输入：nums = [1,2,3]
输出：true
解释：[1,2,3] 已经是严格递增的，所以返回 true 。

 

提示：

• 2 <= nums.length <= 1000
• 1 <= nums[i] <= 1000

方法一：遍历 · Go 实现

思考

枚举删除位置再检查严格递增需要 $O(n^2)$。 $n$ 通常不超过 ${10}^3$ 量级时尚可，但只需删除至多一个元素，破坏点至多一处。

从左扫描第一个满足 $\mathit{\text{nums}}[i]\ge \mathit{\text{nums}}[i+1]$ 的下标 $i$，此后只需验证「删 $i$」或「删 $i+1$」之一能使全数组严格递增。

线性检查跳过被删下标即可，不必真的改写数组。若无破坏点，删除任一端点仍成立。

我们可以遍历数组，找到第一个不满足 $\mathit{\text{nums}}[i]<\mathit{\text{nums}}[i+1]$ 的位置 $i$，然后检查删除 $i$ 或者 $i+1$ 后的数组是否严格递增，如果是则返回 $\mathit{\text{true}}$，否则返回 $\mathit{\text{false}}$。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func canBeIncreasing(nums []int) bool {
	check := func(k int) bool {
		pre := 0
		for i, x := range nums {
			if i == k {
				continue
			}
			if pre >= x {
				return false
			}
			pre = x
		}
		return true
	}
	i := 0
	for i+1 < len(nums) && nums[i] < nums[i+1] {
		i++
	}
	return check(i) || check(i+1)
}

力扣原题 · Doocs 题解来源

1914. 循环轮转矩阵

中等1 种解法

标签：数组、矩阵、模拟

题目、示例与约束

给你一个大小为 m x n 的整数矩阵 grid​​​ ，其中 m 和 n 都是 偶数 ；另给你一个整数 k 。

矩阵由若干层组成，如下图所示，每种颜色代表一层：

矩阵的循环轮转是通过分别循环轮转矩阵中的每一层完成的。在对某一层进行一次循环旋转操作时，层中的每一个元素将会取代其 逆时针 方向的相邻元素。轮转示例如下：

返回执行 k 次循环轮转操作后的矩阵。

 

示例 1：

输入：grid = [[40,10],[30,20]], k = 1
输出：[[10,20],[40,30]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

示例 2：

输入：grid = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]], k = 2
输出：[[3,4,8,12],[2,11,10,16],[1,7,6,15],[5,9,13,14]]
解释：上图展示了矩阵在执行循环轮转操作时每一步的状态。

 

提示：

• m == grid.length
• n == grid[i].length
• 2 <= m, n <= 50
• m 和 n 都是 偶数
• 1 <= grid[i][j] <= 5000
• 1 <= k <= 109

方法一：逐层模拟 · Go 实现

思考

各层是互不相交的环， $k$ 可能大于环长，按格逐步旋转会重复劳动。应将一层顺时针展开成一维，对 $k$ 取模后再写回。

从上、右、下、左四条边依次收集，旋转后再按同一顺序放回，层与层独立，总时间为矩阵规模的线性。

我们先计算得到矩阵的层数 $p$，然后从外到内逐层模拟循环轮转的过程。

对于每一层，我们按照顺时针方向，将上、右、下、左四条边的元素依次放入数组 $nums$ 中。记数组 $nums$ 的长度为 $l$。接下来，我们将 $k$ 模 $l$。然后从数组的第 $k$ 个位置开始，将数组中的元素依次放回矩阵的上、右、下、左四条边。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func rotateGrid(grid [][]int, k int) [][]int {
	m, n := len(grid), len(grid[0])

	rotate := func(p, k int) {
		nums := []int{}
		for j := p; j < n-p-1; j++ {
			nums = append(nums, grid[p][j])
		}
		for i := p; i < m-p-1; i++ {
			nums = append(nums, grid[i][n-p-1])
		}
		for j := n - p - 1; j > p; j-- {
			nums = append(nums, grid[m-p-1][j])
		}
		for i := m - p - 1; i > p; i-- {
			nums = append(nums, grid[i][p])
		}
		l := len(nums)
		k %= l
		if k == 0 {
			return
		}
		for j := p; j < n-p-1; j++ {
			grid[p][j] = nums[k]
			k = (k + 1) % l
		}
		for i := p; i < m-p-1; i++ {
			grid[i][n-p-1] = nums[k]
			k = (k + 1) % l
		}
		for j := n - p - 1; j > p; j-- {
			grid[m-p-1][j] = nums[k]
			k = (k + 1) % l
		}
		for i := m - p - 1; i > p; i-- {
			grid[i][p] = nums[k]
			k = (k + 1) % l
		}
	}

	for i := 0; i < m/2 && i < n/2; i++ {
		rotate(i, k)
	}
	return grid
}

力扣原题 · Doocs 题解来源

1920. 基于排列构建数组

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个 从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个 同样长度 的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。

从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

 

示例 1：

输入：nums = [0,2,1,5,3,4]
输出：[0,1,2,4,5,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[0], nums[2], nums[1], nums[5], nums[3], nums[4]]
    = [0,1,2,4,5,3]

示例 2：

输入：nums = [5,0,1,2,3,4]
输出：[4,5,0,1,2,3]
解释：数组 ans 构建如下：
ans = [nums[nums[0]], nums[nums[1]], nums[nums[2]], nums[nums[3]], nums[nums[4]], nums[nums[5]]]
    = [nums[5], nums[0], nums[1], nums[2], nums[3], nums[4]]
    = [4,5,0,1,2,3]

 

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] < nums.length
• nums 中的元素 互不相同

 

进阶：你能在不使用额外空间的情况下解决此问题吗（即 O(1) 内存）？

方法一：模拟 · Go 实现

思考

$\mathit{\text{ans}}[i]=\mathit{\text{nums}}[\mathit{\text{nums}}[i]]$ 已由题面给出，且允许使用额外数组。直接按定义构造即可，不必原地编码。

一次遍历写下每个映射，时间为 $O(n)$。

我们可以直接模拟题目描述的过程，构建一个新的数组 $\mathit{\text{ans}}$，对于每个 $i$，令 $\mathit{\text{ans}}[i]=\mathit{\text{nums}}[\mathit{\text{nums}}[i]]$。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func buildArray(nums []int) []int {
	ans := make([]int, len(nums))
	for i, num := range nums {
		ans[i] = nums[num]
	}
	return ans
}

力扣原题 · Doocs 题解来源

1929. 数组串联

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，数组下标 从 0 开始计数 ，对于所有 0 <= i < n 的 i ，满足下述所有要求：

• ans[i] == nums[i]
• ans[i + n] == nums[i]

具体而言，ans 由两个 nums 数组 串联 形成。

返回数组 ans 。

 

示例 1：

输入：nums = [1,2,1]
输出：[1,2,1,1,2,1]
解释：数组 ans 按下述方式形成：
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]

示例 2：

输入：nums = [1,3,2,1]
输出：[1,3,2,1,1,3,2,1]
解释：数组 ans 按下述方式形成：
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]

 

提示：

• n == nums.length
• 1 <= n <= 1000
• 1 <= nums[i] <= 1000

方法一：模拟 · Go 实现

思考

答案定义为原数组首尾相接。直接拼接两份 $\mathit{\text{nums}}$ 即满足下标映射，无需逐格赋值循环。

我们直接根据题目描述模拟，将 $\mathit{\text{nums}}$ 中的元素依次添加到答案数组中，然后再将 $\mathit{\text{nums}}$ 中的元素再次添加到答案数组中。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

func getConcatenation(nums []int) []int {
	return append(nums, nums...)
}

力扣原题 · Doocs 题解来源

1958. 检查操作是否合法

中等1 种解法

标签：数组、枚举、矩阵

题目、示例与约束

给你一个下标从 0 开始的 8 x 8 网格 board ，其中 board[r][c] 表示游戏棋盘上的格子 (r, c) 。棋盘上空格用 '.' 表示，白色格子用 'W' 表示，黑色格子用 'B' 表示。

游戏中每次操作步骤为：选择一个空格子，将它变成你正在执行的颜色（要么白色，要么黑色）。但是，合法 操作必须满足：涂色后这个格子是 好线段的一个端点 （好线段可以是水平的，竖直的或者是对角线）。

好线段 指的是一个包含 三个或者更多格子（包含端点格子）的线段，线段两个端点格子为 同一种颜色 ，且中间剩余格子的颜色都为 另一种颜色 （线段上不能有任何空格子）。你可以在下图找到好线段的例子：

给你两个整数 rMove 和 cMove 以及一个字符 color ，表示你正在执行操作的颜色（白或者黑），如果将格子 (rMove, cMove) 变成颜色 color 后，是一个 合法 操作，那么返回 true ，如果不是合法操作返回 false 。

 

示例 1：

输入：board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
输出：true
解释：'.'，'W' 和 'B' 分别用颜色蓝色，白色和黑色表示。格子 (rMove, cMove) 用 'X' 标记。
以选中格子为端点的两个好线段在上图中用红色矩形标注出来了。

示例 2：

输入：board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W"
输出：false
解释：虽然选中格子涂色后，棋盘上产生了好线段，但选中格子是作为中间格子，没有产生以选中格子为端点的好线段。

 

提示：

• board.length == board[r].length == 8
• 0 <= rMove, cMove < 8
• board[rMove][cMove] == '.'
• color 要么是 'B' 要么是 'W' 。

方法一：枚举 · Go 实现

思考

合法落子需在某一方向上形成「本色—对方若干—本色」的好线段。棋盘 $8\times 8$，八个方向各走一遍即可。

自落点沿方向前进，统计步数；途中遇到空格或提前遇到本色则该方向失败，步数大于 $1$ 且碰到本色则成功。

无需真的翻转棋子。

我们枚举所有可能的方向，对于每个方向 $(a,b)$，我们从 $(\mathit{\text{rMove}},\mathit{\text{cMove}})$ 出发，用一个变量 $\mathit{\text{cnt}}$ 记录我们走过的格子数，如果我们在走的过程中遇到了颜色为 $\mathit{\text{color}}$ 的格子，且 $\mathit{\text{cnt}}>1$，那么我们就找到了一个好线段，返回 $\mathit{\text{true}}$。

枚举结束后，如果我们没有找到任何好线段，那么返回 $\mathit{\text{false}}$。

时间复杂度 $O(m+n)$，其中 $m$ 为 $\mathit{\text{board}}$ 的行数，而 $n$ 为 $\mathit{\text{board}}$ 的列数，本题中 $m=n=8$。空间复杂度 $O(1)$。

func checkMove(board [][]byte, rMove int, cMove int, color byte) bool {
	for a := -1; a <= 1; a++ {
		for b := -1; b <= 1; b++ {
			if a == 0 && b == 0 {
				continue
			}
			i, j := rMove, cMove
			cnt := 0
			for 0 <= i+a && i+a < 8 && 0 <= j+b && j+b < 8 {
				i += a
				j += b
				cnt++
				if cnt > 1 && board[i][j] == color {
					return true
				}
				if board[i][j] == color || board[i][j] == '.' {
					break
				}
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

2012. 数组美丽值求和

中等1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。对于每个下标 i（1 <= i <= nums.length - 2），nums[i] 的 美丽值 等于：

• 2，对于所有 0 <= j < i 且 i < k <= nums.length - 1 ，满足 nums[j] < nums[i] < nums[k]
• 1，如果满足 nums[i - 1] < nums[i] < nums[i + 1] ，且不满足前面的条件
• 0，如果上述条件全部不满足

返回符合 1 <= i <= nums.length - 2 的所有 nums[i] 的 美丽值的总和 。

 

示例 1：

输入：nums = [1,2,3]
输出：2
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 2

示例 2：

输入：nums = [2,4,6,4]
输出：1
解释：对于每个符合范围 1 <= i <= 2 的下标 i :
- nums[1] 的美丽值等于 1
- nums[2] 的美丽值等于 0

示例 3：

输入：nums = [3,2,1]
输出：0
解释：对于每个符合范围 1 <= i <= 1 的下标 i :
- nums[1] 的美丽值等于 0

 

提示：

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 105

方法一：预处理右侧最小值 + 遍历维护左侧最大值 · Go 实现

思考

$n\le {10}^5$，对每个 $i$ 再扫左右最值会达到平方。美丽度 $2$ 要求 $nums[i]$ 严格大于左侧全部、小于右侧全部；美丽度 $1$ 只看相邻。

右侧最小值可预处理： $right[i]$ 为后缀最小。左侧最大值在从左往右扫描时用变量 $l$ 维护。

对每个中间下标先用 $l$ 与 $right[i+1]$ 判定 $2$ 分，否则再看相邻三项是否严格递增。

我们可以预处理出右侧最小值数组 $right$，其中 $right[i]$ 表示 $nums[i..n-1]$ 中的最小值。

然后我们从左到右遍历数组 $nums$，同时维护左侧最大值 $l$。对于每个位置 $i$，我们判断 $l<nums[i]<right[i+1]$ 是否成立，如果成立则将 $2$ 累加至答案，否则判断 $nums[i-1]<nums[i]<nums[i+1]$ 是否成立，如果成立则将 $1$ 累加至答案。

遍历结束后即可得到答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $nums$ 的长度。

func sumOfBeauties(nums []int) (ans int) {
	n := len(nums)
	right := make([]int, n)
	right[n-1] = nums[n-1]
	for i := n - 2; i > 0; i-- {
		right[i] = min(right[i+1], nums[i])
	}
	for i, l := 1, nums[0]; i < n-1; i++ {
		r := right[i+1]
		if l < nums[i] && nums[i] < r {
			ans += 2
		} else if nums[i-1] < nums[i] && nums[i] < nums[i+1] {
			ans++
		}
		l = max(l, nums[i])
	}
	return
}

力扣原题 · Doocs 题解来源

2016. 增量元素之间的最大差值

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。

返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1 。

 

示例 1：

输入：nums = [7,1,5,4]
输出：4
解释：
最大差值出现在 i = 1 且 j = 2 时，nums[j] - nums[i] = 5 - 1 = 4 。
注意，尽管 i = 1 且 j = 0 时 ，nums[j] - nums[i] = 7 - 1 = 6 > 4 ，但 i > j 不满足题面要求，所以 6 不是有效的答案。

示例 2：

输入：nums = [9,4,3,2]
输出：-1
解释：
不存在同时满足 i < j 和 nums[i] < nums[j] 这两个条件的 i, j 组合。

示例 3：

输入：nums = [1,5,2,10]
输出：9
解释：
最大差值出现在 i = 0 且 j = 3 时，nums[j] - nums[i] = 10 - 1 = 9 。

 

提示：

• n == nums.length
• 2 <= n <= 1000
• 1 <= nums[i] <= 109

方法一：维护前缀最小值 · Go 实现

思考

$n\le 1000$，双重循环可行，但只需最大的 $nums[j]-nums[i]$（ $i<j$ 且递增）。对固定右端，最优左端就是此前的最小值。

维护前缀最小 $mi$：若当前 $x>mi$ 则更新差值，否则把 $mi$ 换成更小的 $x$。无递增对时保持 $-1$。

我们用一个变量 $\mathit{\text{mi}}$ 表示当前遍历到的元素中的最小值，用一个变量 $\mathit{\text{ans}}$ 表示最大差值，初始时 $\mathit{\text{mi}}$ 为 $+\mathrm{\infty }$，而 $\mathit{\text{ans}}$ 为 $-1$。

遍历数组，对于当前遍历到的元素 $x$，如果 $x>\mathit{\text{mi}}$，则更新 $\mathit{\text{ans}}$ 为 $max(\mathit{\text{ans}},x-\mathit{\text{mi}})$，否则更新 $\mathit{\text{mi}}=x$。

遍历结束后，返回 $\mathit{\text{ans}}$。

遍历结束后，返回 $ans$。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

func maximumDifference(nums []int) int {
	mi := 1 << 30
	ans := -1
	for _, x := range nums {
		if mi < x {
			ans = max(ans, x-mi)
		} else {
			mi = x
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2018. 判断单词是否能放入填字游戏内

中等1 种解法

标签：数组、枚举、矩阵

题目、示例与约束

给你一个 m x n 的矩阵 board ，它代表一个填字游戏 当前 的状态。填字游戏格子中包含小写英文字母（已填入的单词），表示 空 格的 ' ' 和表示 障碍 格子的 '#' 。

如果满足以下条件，那么我们可以 水平 （从左到右 或者 从右到左）或 竖直 （从上到下 或者 从下到上）填入一个单词：

• 该单词不占据任何 '#' 对应的格子。
• 每个字母对应的格子要么是 ' ' （空格）要么与 board 中已有字母 匹配 。
• 如果单词是 水平 放置的，那么该单词左边和右边 相邻 格子不能为 ' ' 或小写英文字母。
• 如果单词是 竖直 放置的，那么该单词上边和下边 相邻 格子不能为 ' ' 或小写英文字母。

给你一个字符串 word ，如果 word 可以被放入 board 中，请你返回 true ，否则请返回 false 。

 

示例 1：

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
输出：true
解释：单词 "abc" 可以如上图放置（从上往下）。

示例 2：

输入：board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
输出：false
解释：无法放置单词，因为放置该单词后上方或者下方相邻格会有空格。

示例 3：

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
输出：true
解释：单词 "ca" 可以如上图放置（从右到左）。

 

提示：

• m == board.length
• n == board[i].length
• 1 <= m * n <= 2 * 105
• board[i][j] 可能为 ' ' ，'#' 或者一个小写英文字母。
• 1 <= word.length <= max(m, n)
• word 只包含小写英文字母。

方法一：枚举 · Go 实现

思考

$mn\le 2\times {10}^5$，单词须放在被 '#' 隔开的整段空档，且可正向或反向。枚举每个格子作为起点，四个方向各试一次，总长度与格子数同阶。

起点须贴着边界或 '#'，否则不是一段的开端。check 还要求单词末端的下一格不在板内或为 '#'，并且途中字母匹配或为空格。

任一方向成功即返回。

我们可以枚举矩阵的每个位置 $(i,j)$，判断是否能以该位置为起点，从左到右或从右到左放置单词 word，或者从上到下或从下到上放置单词 word。

该位置能作为起点需要满足以下条件：

1. 如果要从从左到右放置单词 word，那么该位置必须是左边界，或者该位置左边的格子 board[i][j - 1] 是 '#'；
2. 如果要从从右到左放置单词 word，那么该位置必须是右边界，或者该位置右边的格子 board[i][j + 1] 是 '#'；
3. 如果要从从上到下放置单词 word，那么该位置必须是上边界，或者该位置上边的格子 board[i - 1][j] 是 '#'；
4. 如果要从从下到上放置单词 word，那么该位置必须是下边界，或者该位置下边的格子 board[i + 1][j] 是 '#'。

在满足上述条件的情况下，我们可以从该位置开始，判断是否能放置单词 word。我们设计一个函数 $check(i,j,a,b)$，表示从位置 $(i,j)$ 开始，沿着方向 $(a,b)$ 放置单词 word 是否合法。如果合法，返回 true，否则返回 false。

函数 $check(i,j,a,b)$ 的实现如下：

我们先获取当前方向的另一个边界位置 $(x,y)$，即 $(x,y)=(i+a\times k,j+b\times k)$，其中 $k$ 为单词 word 的长度。如果 $(x,y)$ 在矩阵内，并且 $(x,y)$ 的格子不是 '#'，则说明当前方向的另一个边界位置不是 '#'，因此不能放置单词 word，返回 false。

否则，我们从位置 $(i,j)$ 开始，沿着方向 $(a,b)$ 遍历单词 word，如果遇到格子 board[i][j] 不是空格或者不是单词 word 的当前字符，说明不能放置单词 word，返回 false。如果遍历完单词 word，说明能放置单词 word，返回 true。

时间复杂度 $O(m\times n)$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别为矩阵的行数和列数。

func placeWordInCrossword(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	k := len(word)
	check := func(i, j, a, b int) bool {
		x, y := i+a*k, j+b*k
		if x >= 0 && x < m && y >= 0 && y < n && board[x][y] != '#' {
			return false
		}
		for _, c := range word {
			if i < 0 || i >= m || j < 0 || j >= n || (board[i][j] != ' ' && board[i][j] != byte(c)) {
				return false
			}
			i, j = i+a, j+b
		}
		return true
	}
	for i := range board {
		for j := range board[i] {
			leftToRight := (j == 0 || board[i][j-1] == '#') && check(i, j, 0, 1)
			rightToLeft := (j == n-1 || board[i][j+1] == '#') && check(i, j, 0, -1)
			upToDown := (i == 0 || board[i-1][j] == '#') && check(i, j, 1, 0)
			downToUp := (i == m-1 || board[i+1][j] == '#') && check(i, j, -1, 0)
			if leftToRight || rightToLeft || upToDown || downToUp {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

2022. 将一维数组转变成二维数组

简单1 种解法

标签：数组、矩阵、模拟

题目、示例与约束

给你一个下标从 0 开始的一维整数数组 original 和两个整数 m 和  n 。你需要使用 original 中 所有 元素创建一个 m 行 n 列的二维数组。

original 中下标从 0 到 n - 1 （都 包含 ）的元素构成二维数组的第一行，下标从 n 到 2 * n - 1 （都 包含 ）的元素构成二维数组的第二行，依此类推。

请你根据上述过程返回一个 m x n 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。

 

示例 1：

输入：original = [1,2,3,4], m = 2, n = 2
输出：[[1,2],[3,4]]
解释：
构造出的二维数组应该包含 2 行 2 列。
original 中第一个 n=2 的部分为 [1,2] ，构成二维数组的第一行。
original 中第二个 n=2 的部分为 [3,4] ，构成二维数组的第二行。

示例 2：

输入：original = [1,2,3], m = 1, n = 3
输出：[[1,2,3]]
解释：
构造出的二维数组应该包含 1 行 3 列。
将 original 中所有三个元素放入第一行中，构成要求的二维数组。

示例 3：

输入：original = [1,2], m = 1, n = 1
输出：[]
解释：
original 中有 2 个元素。
无法将 2 个元素放入到一个 1x1 的二维数组中，所以返回一个空的二维数组。

示例 4：

输入：original = [3], m = 1, n = 2
输出：[]
解释：
original 中只有 1 个元素。
无法将 1 个元素放满一个 1x2 的二维数组，所以返回一个空的二维数组。

 

提示：

• 1 <= original.length <= 5 * 104
• 1 <= original[i] <= 105
• 1 <= m, n <= 4 * 104

方法一：模拟 · Go 实现

思考

能否整形仅取决于 $mn$ 是否等于原长度。长度至多 $5\times {10}^4$，按行切分即可。

不满足则返回空数组；否则步长 $n$ 切片得到各行。

根据题目描述，我们知道，要想构造出一个 $m$ 行 $n$ 列的二维数组，需要满足 $m\times n$ 等于原数组的长度。如果不满足，直接返回空数组即可。

如果满足，我们可以按照题目描述的过程，将原数组中的元素依次放入二维数组中即可。

时间复杂度 $O(m\times n)$，其中 $m$ 和 $n$ 分别为二维数组的行数和列数。忽略答案的空间消耗，空间复杂度 $O(1)$。

func construct2DArray(original []int, m int, n int) (ans [][]int) {
	if m*n != len(original) {
		return [][]int{}
	}
	for i := 0; i < m*n; i += n {
		ans = append(ans, original[i:i+n])
	}
	return
}

力扣原题 · Doocs 题解来源

2057. 值相等的最小索引

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；如果不存在这样的下标，返回 -1 。

x mod y 表示 x 除以 y 的 余数 。

 

示例 1：

输入：nums = [0,1,2]
输出：0
解释：
i=0: 0 mod 10 = 0 == nums[0].
i=1: 1 mod 10 = 1 == nums[1].
i=2: 2 mod 10 = 2 == nums[2].
所有下标都满足 i mod 10 == nums[i] ，所以返回最小下标 0

示例 2：

输入：nums = [4,3,2,1]
输出：2
解释：
i=0: 0 mod 10 = 0 != nums[0].
i=1: 1 mod 10 = 1 != nums[1].
i=2: 2 mod 10 = 2 == nums[2].
i=3: 3 mod 10 = 3 != nums[3].
2 唯一一个满足 i mod 10 == nums[i] 的下标

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9,0]
输出：-1
解释：不存在满足 i mod 10 == nums[i] 的下标

示例 4：

输入：nums = [2,1,3,5,2]
输出：1
解释：1 是唯一一个满足 i mod 10 == nums[i] 的下标

 

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 9

方法一：遍历 · Go 实现

思考

$n\le 100$，从左到右找最小 $i$ 满足 $imod10=nums[i]$。不存在则 $-1$。

一次遍历即可，无需预处理。

我们直接遍历数组，对于每个下标 $i$，我们判断是否满足 $imod10=\mathit{\text{nums}}[i]$，如果满足则返回当前下标 $i$。

如果遍历完数组都没有找到满足条件的下标，则返回 $-1$。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func smallestEqual(nums []int) int {
	for i, x := range nums {
		if i%10 == x {
			return i
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

2061. 扫地机器人清扫过的空间个数 🔒

中等2 种解法

标签：数组、矩阵、模拟

题目、示例与约束

一个房间用一个从 0 开始索引的二维二进制矩阵 room 表示，其中 0 表示空闲空间， 1 表示放有物体的空间。在每个测试用例中，房间左上角永远是空闲的。

一个扫地机器人面向右侧，从左上角开始清扫。机器人将一直前进，直到抵达房间边界或触碰到物体时，机器人将会顺时针旋转 90 度并重复以上步骤。初始位置和所有机器人走过的空间都会被它清扫干净。

若机器人持续运转下去，返回被清扫干净的空间数量。

 

示例 1：

输入: room = [[0,0,0],[1,1,0],[0,0,0]]
输出: 7
解释:
机器人清理了位于 (0, 0)、 (0, 1) 和 (0, 2) 的空间。
机器人位于房间边界，所以它顺时针旋转 90 度，现在面向下。
机器人清理了位于 (1, 2) 和 (2, 2) 的空间。
机器人位于房间边界，所以它顺时针旋转 90 度，现在面向左。
机器人清理了位于 (2, 1) 和 (2, 0) 的空间。
机器人已清理了所有 7 处空闲空间，所以返回 7。

示例 2：

输入: room = [[0,1,0],[1,0,0],[0,0,0]]
输出t: 1
解释:
机器人清理了位于 (0, 0) 的空间。
机器人触碰到了物体，所以它顺时针旋转 90 度，现在面向下。
机器人触碰到了物体，所以它顺时针旋转 90 度，现在面向左。
机器人位于房间边界，所以它顺时针旋转 90 度，现在面向上。
机器人位于房间边界，所以它顺时针旋转 90 度，现在面向右。
机器人回到了起始位置。
机器人清理了 1 处空间，所以返回 1。

 

提示：

• m == room.length
• n == room[r].length
• 1 <= m, n <= 300
• room[r][c] 只会是 0 或 1 。
• room[0][0] == 0

方法一：DFS 模拟 · Go 实现

思考

机器人遇障右转，房间 $\le 300\times 300$。会循环，终止条件是同一位置同一朝向再现。清扫过的空地标记后不再重复计数。

状态 $(i,j,k)$ 用集合记录。能前进则沿朝向 DFS，否则就地转向。空地首次访问时答案加一。

我们从起点 $(0,0)$ 开始模拟机器人的清扫过程，每次清扫当前位置，然后向前走一步，如果碰到墙壁或者已经清扫过的位置，就顺时针旋转 90 度，然后继续清扫。

过程中，我们用一个三元组 $(i,j,k)$ 表示机器人当前的位置 $(i,j)$ 和朝向 $k$，其中 $k$ 的取值范围为 $0,1,2,3$，分别表示朝右、朝下、朝左、朝上。我们用一个集合 vis 记录所有访问过的状态三元组。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为房间的行数和列数。

func numberOfCleanRooms(room [][]int) (ans int) {
	m, n := len(room), len(room[0])
	vis := make([][][4]bool, m)
	for i := range vis {
		vis[i] = make([][4]bool, n)
	}
	dirs := [5]int{0, 1, 0, -1, 0}
	var dfs func(i, j, k int)
	dfs = func(i, j, k int) {
		if vis[i][j][k] {
			return
		}
		if room[i][j] == 0 {
			ans++
			room[i][j] = -1
		}
		vis[i][j][k] = true
		x, y := i+dirs[k], j+dirs[k+1]
		if x >= 0 && x < m && y >= 0 && y < n && room[x][y] != 1 {
			dfs(x, y, k)
		} else {
			dfs(i, j, (k+1)%4)
		}
	}
	dfs(0, 0, 0)
	return
}

方法二 · Go 实现

思考

方法一用递归模拟，深度可达 $O(mn)$。同一转移写成循环即可去掉调用栈： vis 记录三元组，前进或转向直到状态重复。

计数规则不变。

func numberOfCleanRooms(room [][]int) (ans int) {
	m, n := len(room), len(room[0])
	vis := make([][][4]bool, m)
	for i := range vis {
		vis[i] = make([][4]bool, n)
	}
	dirs := [5]int{0, 1, 0, -1, 0}
	var i, j, k int
	for !vis[i][j][k] {
		vis[i][j][k] = true
		if room[i][j] == 0 {
			ans++
			room[i][j] = -1
		}
		x, y := i+dirs[k], j+dirs[k+1]
		if x >= 0 && x < m && y >= 0 && y < n && room[x][y] != 1 {
			i, j = x, y
		} else {
			k = (k + 1) % 4
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2079. 给植物浇水

中等1 种解法

标签：数组、模拟

题目、示例与约束

你打算用一个水罐给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。x = -1 处有一条河，你可以在那里重新灌满你的水罐。

每一株植物都需要浇特定量的水。你将会按下面描述的方式完成浇水：

• 按从左到右的顺序给植物浇水。
• 在给当前植物浇完水之后，如果你没有足够的水 完全 浇灌下一株植物，那么你就需要返回河边重新装满水罐。
• 你 不能 提前重新灌满水罐。

最初，你在河边（也就是，x = -1），在 x 轴上每移动 一个单位 都需要 一步 。

给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有一个整数 capacity 表示水罐的容量，返回浇灌所有植物需要的 步数 。

 

示例 1：

输入：plants = [2,2,3,3], capacity = 5
输出：14
解释：从河边开始，此时水罐是装满的：
- 走到植物 0 (1 步) ，浇水。水罐中还有 3 单位的水。
- 走到植物 1 (1 步) ，浇水。水罐中还有 1 单位的水。
- 由于不能完全浇灌植物 2 ，回到河边取水 (2 步)。
- 走到植物 2 (3 步) ，浇水。水罐中还有 2 单位的水。
- 由于不能完全浇灌植物 3 ，回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。
需要的步数是 = 1 + 1 + 2 + 3 + 3 + 4 = 14 。

示例 2：

输入：plants = [1,1,1,4,2,3], capacity = 4
输出：30
解释：从河边开始，此时水罐是装满的：
- 走到植物 0，1，2 (3 步) ，浇水。回到河边取水 (3 步)。
- 走到植物 3 (4 步) ，浇水。回到河边取水 (4 步)。
- 走到植物 4 (5 步) ，浇水。回到河边取水 (5 步)。
- 走到植物 5 (6 步) ，浇水。
需要的步数是 = 3 + 3 + 4 + 4 + 5 + 5 + 6 = 30 。

示例 3：

输入：plants = [7,7,7,7,7,7,7], capacity = 8
输出：49
解释：每次浇水都需要重新灌满水罐。
需要的步数是 = 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6 + 6 + 7 = 49 。

 

提示：

• n == plants.length
• 1 <= n <= 1000
• 1 <= plants[i] <= 106
• max(plants[i]) <= capacity <= 109

方法一：模拟 · Go 实现

思考

水罐容量不小于单株需求，从河出发顺序浇灌。水量不够时必须返回再装满，步数为 $2i+1$（来回至第 $i$ 株再前进一步）。

维护剩余水量，够则只走一步，不够则按上式加步并重置为 $capacity-p$。

我们可以模拟给植物浇水的过程，用一个变量 $\mathit{\text{water}}$ 表示当前水罐中的水量，初始时 $\mathit{\text{water}}=\mathit{\text{capacity}}$。

我们遍历植物，对于每一株植物：

• 如果当前水罐中的水量足够浇灌这株植物，我们就向前移动一步，浇灌这株植物，同时更新 $\mathit{\text{water}}=\mathit{\text{water}}-\mathit{\text{plants}}[i]$。
• 否则我们就需要返回河边重新装满水罐，再次走到当前位置，然后向前移动一步，此时我们需要的步数为 $i\times 2+1$，然后我们浇灌这株植物，更新 $\mathit{\text{water}}=\mathit{\text{capacity}}-\mathit{\text{plants}}[i]$。

最后返回总的步数即可。

时间复杂度 $O(n)$，其中 $n$ 为植物的数量。空间复杂度 $O(1)$。

func wateringPlants(plants []int, capacity int) (ans int) {
	water := capacity
	for i, p := range plants {
		if water >= p {
			water -= p
			ans++
		} else {
			water = capacity - p
			ans += i*2 + 1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2113. 查询删除和添加元素后的数组 🔒

中等1 种解法

标签：数组

题目、示例与约束

给你一个 下标从 0 开始 的数组 nums。一开始，在第 0 分钟，数组没有变化。此后每过一分钟，数组的 最左边 的元素将被移除，直到数组为空。然后，每过一分钟，数组的 尾部 将添加一个元素，添加的顺序和删除的顺序相同，直到数组被复原。此后上述操作无限循环进行。

• 举个例子，如果 nums = [0, 1, 2]，那么数组将按如下流程变化：[0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → [1,2] → [2] → [] → [0] → [0,1] → [0,1,2] → ...

然后给你一个长度为 n 的二维数组 queries，其中 queries[j] = [timej, indexj]，表示第 j 个查询。第 j 个查询的答案定义如下：

• 如果在时刻 timej，indexj < nums.length，那么答案是此时的 nums[indexj]；
• 如果在时刻 timej，indexj >= nums.length，那么答案是 -1。

请返回一个长度为 n 的整数数组 ans，其中 ans[j] 为第 j 个查询的答案。

 

示例 1:

输入: nums = [0,1,2], queries = [[0,2],[2,0],[3,2],[5,0]]
输出: [2,2,-1,0]
解释:
第 0 分钟: [0,1,2] - 数组和 nums 相同。
第 1 分钟: [1,2]   - 最左侧元素 0 被移除。
第 2 分钟: [2]     - 最左侧元素 1 被移除。
第 3 分钟: []      - 最左侧元素 0 被移除。
第 4 分钟: [0]     - 0 被添加到数组尾部。
第 5 分钟: [0,1]   - 1 被添加到数组尾部。

在第 0 分钟, nums[2] 是 2。
在第 2 分钟, nums[0] 是 2。
在第 3 分钟, nums[2] 不存在。
在第 5 分钟, nums[0] 是 0。

示例 2:

输入: nums = [2], queries = [[0,0],[1,0],[2,0],[3,0]]
输出: [2,-1,2,-1]
第 0 分钟: [2] - 数组和 nums 相同。
第 1 分钟: []  - 最左侧元素 2 被移除。
第 2 分钟: [2] - 2 被添加到数组尾部。
第 3 分钟: []  - 最左侧元素 2 被移除。

在第 0 分钟, nums[0] 是 2。
在第 1 分钟, nums[0] 不存在。
在第 2 分钟, nums[0] 是 2。
在第 3 分钟, nums[0] 不存在。

 

提示:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100
• n == queries.length
• 1 <= n <= 105
• queries[j].length == 2
• 0 <= timej <= 105
• 0 <= indexj < nums.length

方法一：直接计算 · Go 实现

思考

数组按周期 $2n$ 循环：前 $n$ 秒从左删除，后 $n$ 秒从左补回。查询可达 ${10}^5$，若对每个时刻真的改数组，总时间与空间都不可接受。

$tmod2n$ 后只需判断落在删除阶段还是补回阶段，再把询问下标映射回原数组。删除阶段剩余长度为 $n-t$，下标 $i$ 对应原位置 $i+t$；补回阶段长度为 $t-n$，下标 $i$ 对应 $\mathit{\text{nums}}[i]$。

对每个询问按上述规则 $O(1)$ 取值，越界则填 $-1$。

我们先初始化一个数组 $ans$，长度为 $m$，用于存储答案，初始化所有元素为 $-1$。

接下来遍历数组 $queries$，对于每个查询，我们先获取当前查询的时间 $t$ 和索引 $i$，先将 $t$ 对 $2n$ 取模，然后判断 $t$ 和 $n$ 的关系：

• 如果 $t<n$，那么 $t$ 时刻的数组元素个数为 $n-t$，并且数组元素是原数组元素整体向左移动 $t$ 个位置后的结果，因此如果 $i<n-t$，答案为 $nums[i+t]$；
• 如果 $t>n$，那么 $t$ 时刻的数组元素个数为 $t-n$，并且数组元素是原数组元素的前 $t-n$ 个元素，因此如果 $i<t-n$，答案为 $nums[i]$。

最后返回数组 $ans$ 即可。

时间复杂度 $O(m)$，其中 $m$ 为数组 $queries$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func elementInNums(nums []int, queries [][]int) []int {
	n, m := len(nums), len(queries)
	ans := make([]int, m)
	for j, q := range queries {
		t, i := q[0], q[1]
		t %= (n * 2)
		ans[j] = -1
		if t < n && i < n-t {
			ans[j] = nums[i+t]
		} else if t > n && i < t-n {
			ans[j] = nums[i]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2155. 分组得分最高的所有下标

中等1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的二进制数组 nums ，数组长度为 n 。nums 可以按下标 i（ 0 <= i <= n ）拆分成两个数组（可能为空）：numsleft 和 numsright 。

• numsleft 包含 nums 中从下标 0 到 i - 1 的所有元素（包括 0 和 i - 1 ），而 numsright 包含 nums 中从下标 i 到 n - 1 的所有元素（包括 i 和 n - 1 ）。
• 如果 i == 0 ，numsleft 为 空 ，而 numsright 将包含 nums 中的所有元素。
• 如果 i == n ，numsleft 将包含 nums 中的所有元素，而 numsright 为 空 。

下标 i 的 分组得分 为 numsleft 中 0 的个数和 numsright 中 1 的个数之 和 。

返回 分组得分 最高 的 所有不同下标 。你可以按 任意顺序 返回答案。

 

示例 1：

输入：nums = [0,0,1,0]
输出：[2,4]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [0,0,1,0] 。得分为 0 + 1 = 1 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,1,0] 。得分为 1 + 1 = 2 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [1,0] 。得分为 2 + 1 = 3 。
- 3 ：numsleft 为 [0,0,1] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 4 ：numsleft 为 [0,0,1,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
下标 2 和 4 都可以得到最高的分组得分 3 。
注意，答案 [4,2] 也被视为正确答案。

示例 2：

输入：nums = [0,0,0]
输出：[3]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [0,0,0] 。得分为 0 + 0 = 0 。
- 1 ：numsleft 为 [0] 。numsright 为 [0,0] 。得分为 1 + 0 = 1 。
- 2 ：numsleft 为 [0,0] 。numsright 为 [0] 。得分为 2 + 0 = 2 。
- 3 ：numsleft 为 [0,0,0] 。numsright 为 [] 。得分为 3 + 0 = 3 。
只有下标 3 可以得到最高的分组得分 3 。

示例 3：

输入：nums = [1,1]
输出：[0]
解释：按下标分组
- 0 ：numsleft 为 [] 。numsright 为 [1,1] 。得分为 0 + 2 = 2 。
- 1 ：numsleft 为 [1] 。numsright 为 [1] 。得分为 0 + 1 = 1 。
- 2 ：numsleft 为 [1,1] 。numsright 为 [] 。得分为 0 + 0 = 0 。
只有下标 0 可以得到最高的分组得分 2 。

 

提示：

• n == nums.length
• 1 <= n <= 105
• nums[i] 为 0 或 1

方法一：前缀和 · Go 实现

思考

下标 $i$ 的得分是左侧 $0$ 的个数加右侧 $1$ 的个数。若每个 $i$ 都重新扫描左右，时间为 $O(n^2)$。

从左到右移动分割点时，左侧 $0$ 与右侧 $1$ 各增减一个当前元素，可用两个计数器滚动。同时维护最高分及其下标列表。

$\mathit{\text{l0}}$ 累加 $x\oplus 1$， $\mathit{\text{r1}}$ 减去 $x$，比较 $t$ 与 $\mathit{\text{mx}}$ 以更新答案。

我们从 $i=0$ 开始，用两个变量 $\mathit{\text{l0}}$ 和 $\mathit{\text{r1}}$ 分别记录 $i$ 左侧和右侧的 $1$ 的个数，初始时 $\mathit{\text{l0}}=0$，而 $\mathit{\text{r1}}=\sum \mathit{\text{nums}}$。

我们遍历数组 $\mathit{\text{nums}}$，对于每个 $i$，更新 $\mathit{\text{l0}}$ 和 $\mathit{\text{r1}}$，计算当前分组得分 $t=\mathit{\text{l0}}+\mathit{\text{r1}}$，如果 $t$ 等于当前最大分组得分 $\mathit{\text{mx}}$，则将 $i$ 加入答案数组，如果 $t$ 大于 $\mathit{\text{mx}}$，则更新 $\mathit{\text{mx}}$ 为 $t$，并将答案数组清空，然后将 $i$ 加入答案数组。

遍历结束后，返回答案数组。

时间复杂度 $O(n)$，其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func maxScoreIndices(nums []int) []int {
	l0, r1 := 0, 0
	for _, x := range nums {
		r1 += x
	}
	mx := r1
	ans := []int{0}
	for i, x := range nums {
		l0 += x ^ 1
		r1 -= x
		t := l0 + r1
		if mx == t {
			ans = append(ans, i+1)
		} else if mx < t {
			mx = t
			ans = []int{i + 1}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2176. 统计数组中相等且可以被整除的数对

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k ，请你返回满足 0 <= i < j < n ，nums[i] == nums[j] 且 (i * j) 能被 k 整除的数对 (i, j) 的 数目 。

 

示例 1：

输入：nums = [3,1,2,2,2,1,3], k = 2
输出：4
解释：
总共有 4 对数符合所有要求：
- nums[0] == nums[6] 且 0 * 6 == 0 ，能被 2 整除。
- nums[2] == nums[3] 且 2 * 3 == 6 ，能被 2 整除。
- nums[2] == nums[4] 且 2 * 4 == 8 ，能被 2 整除。
- nums[3] == nums[4] 且 3 * 4 == 12 ，能被 2 整除。

示例 2：

输入：nums = [1,2,3,4], k = 1
输出：0
解释：由于数组中没有重复数值，所以没有数对 (i,j) 符合所有要求。

 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i], k <= 100

方法一：枚举 · Go 实现

思考

统计 $i<j$、 $\mathit{\text{nums}}[i]=\mathit{\text{nums}}[j]$ 且 $i\cdot j$ 能被 $k$ 整除的对数。 $n\le 100$，二重枚举即可。

固定 $j$ 再扫前面的 $i$，同时检查值相等与乘积取模。

无需额外下标结构。

我们先在 $[0,n)$ 的范围内枚举下标 $j$，然后在 $[0,j)$ 的范围内枚举下标 $i$，统计满足 $\mathit{\text{nums}}[i]=\mathit{\text{nums}}[j]$ 且 $(i\times j)modk=0$ 的数对个数。

时间复杂度 $O(n^2)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func countPairs(nums []int, k int) (ans int) {
	for j, y := range nums {
		for i, x := range nums[:j] {
			if x == y && (i*j%k) == 0 {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2198. 单因数三元组 🔒

中等1 种解法

标签：数组、计数、枚举

题目、示例与约束

给定一个下标从 0 开始的正整数数组 nums。由三个 不同 索引 (i, j, k) 组成的三元组，如果 nums[i] + nums[j] + nums[k] 能被 nums[i]、nums[j] 或 nums[k] 中的 一个 整除，则称为 nums 的 单因数三元组。

返回 nums 的单因数三元组。

 

示例 1:

输入: nums = [4,6,7,3,2]
输出: 12
解释:
三元组索引 (0, 3, 4), (0, 4, 3), (3, 0, 4), (3, 4, 0), (4, 0, 3), 和 (4, 3, 0) 的值为 [4, 3, 2] (或者说排列为 [4, 3, 2]).
4 + 3 + 2 = 9 只能被 3 整除，所以所有的三元组都是单因数三元组。
三元组索引 (0, 2, 3), (0, 3, 2), (2, 0, 3), (2, 3, 0), (3, 0, 2), 和 (3, 2, 0) 的值为 [4, 7, 3]  (或者说排列为 [4, 7, 3]).
4 + 7 + 3 = 14 只能被 7 整除，所以所有的三元组都是单因数三元组。
一共有 12 个单因数三元组。

示例 2:

输入: nums = [1,2,2]
输出: 6
提示:
三元组索引 (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), 和 (2, 1, 0) 的值为 [1, 2, 2] (或者说排列为 [1, 2, 2]).
1 + 2 + 2 = 5 只能被 1 整除，所以所有的三元组都是单因数三元组。
一共有6个单因数三元组。

示例 3:

输入: nums = [1,1,1]
输出: 0
提示:
没有单因数三元组。
注意 (0, 1, 2) 不是单因数三元组。 因为 nums[0] + nums[1] + nums[2] = 3，3 可以被 nums[0], nums[1], nums[2] 整除。

 

提示:

• 3 <= nums.length <= 105
• 1 <= nums[i] <= 100

方法一：计数 + 枚举 · Go 实现

思考

三元组值和只能被三个数中的恰好一个整除。下标有序的排列都算，但 $n\le {10}^5$ 不能枚举三元组。值域只有 $[1,100]$，可枚举值再按重数组合。

统计每个值的出现次数，三重循环 $a,b,c\in [1,100]$，若 $a+b+c$ 恰被其中一个整除，则按 $a,b,c$ 是否相等用排列数 $x(x-1)z$ 等公式计入。

复杂度与值域立方成正比，与 $n$ 无关。

我们注意到，数组 $\mathit{\text{nums}}$ 的元素的范围是 $[1,100]$，因此我们可以枚举三个数 $a,b,c$，其中 $a,b,c\in [1,100]$，然后判断 $a+b+c$ 是否只能被 $a,b,c$ 中的一个数整除。如果是，则我们可以计算出以 $a,b,c$ 为元素的单因数三元组的个数。具体计算方法如下：

• 如果 $a=b$，那么以 $a,b,c$ 为元素的单因数三元组的个数为 $x\times (x-1)\times z$，其中 $x$, $y$, $z$ 分别表示 $a$, $b$, $c$ 在数组 $\mathit{\text{nums}}$ 中出现的次数。
• 如果 $a=c$，那么以 $a,b,c$ 为元素的单因数三元组的个数为 $x\times (x-1)\times y$。
• 如果 $b=c$，那么以 $a,b,c$ 为元素的单因数三元组的个数为 $x\times y\times (y-1)$。
• 如果 $a,b,c$ 互不相等，那么以 $a,b,c$ 为元素的单因数三元组的个数为 $x\times y\times z$。

最后，我们将所有的单因数三元组的个数相加即可。

时间复杂度 $O(M^3)$，空间复杂度 $O(M)$。其中 $M$ 为数组 $\mathit{\text{nums}}$ 中元素的取值范围。

func singleDivisorTriplet(nums []int) (ans int64) {
	cnt := [101]int{}
	for _, x := range nums {
		cnt[x]++
	}
	f := func(a, b int) int {
		if a%b == 0 {
			return 1
		}
		return 0
	}
	for a := 1; a <= 100; a++ {
		for b := 1; b <= 100; b++ {
			for c := 1; c <= 100; c++ {
				s := a + b + c
				t := f(s, a) + f(s, b) + f(s, c)
				if t == 1 {
					if a == b {
						ans += int64(cnt[a] * (cnt[a] - 1) * cnt[c])
					} else if a == c {
						ans += int64(cnt[a] * (cnt[a] - 1) * cnt[b])
					} else if b == c {
						ans += int64(cnt[b] * (cnt[b] - 1) * cnt[a])
					} else {
						ans += int64(cnt[a] * cnt[b] * cnt[c])
					}
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2210. 统计数组中峰和谷的数量

简单1 种解法

标签：数组

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums 。如果两侧距 i 最近的不相等邻居的值均小于 nums[i] ，则下标 i 是 nums 中，某个峰的一部分。类似地，如果两侧距 i 最近的不相等邻居的值均大于 nums[i] ，则下标 i 是 nums 中某个谷的一部分。对于相邻下标 i 和 j ，如果 nums[i] == nums[j] ， 则认为这两下标属于 同一个 峰或谷。

注意，要使某个下标所做峰或谷的一部分，那么它左右两侧必须 都 存在不相等邻居。

返回 nums 中峰和谷的数量。

 

示例 1：

输入：nums = [2,4,1,1,6,5]
输出：3
解释：
在下标 0 ：由于 2 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。
在下标 1 ：4 的最近不相等邻居是 2 和 1 。由于 4 > 2 且 4 > 1 ，下标 1 是一个峰。
在下标 2 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 2 是一个谷。
在下标 3 ：1 的最近不相等邻居是 4 和 6 。由于 1 < 4 且 1 < 6 ，下标 3 符合谷的定义，但需要注意它和下标 2 是同一个谷的一部分。
在下标 4 ：6 的最近不相等邻居是 1 和 5 。由于 6 > 1 且 6 > 5 ，下标 4 是一个峰。
在下标 5 ：由于 5 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。
共有 3 个峰和谷，所以返回 3 。

示例 2：

输入：nums = [6,6,5,5,4,1]
输出：0
解释：
在下标 0 ：由于 6 的左侧不存在不相等邻居，所以下标 0 既不是峰也不是谷。
在下标 1 ：由于 6 的左侧不存在不相等邻居，所以下标 1 既不是峰也不是谷。
在下标 2 ：5 的最近不相等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 2 既不是峰也不是谷。
在下标 3 ：5 的最近不相等邻居是 6 和 4 。由于 5 < 6 且 5 > 4 ，下标 3 既不是峰也不是谷。
在下标 4 ：4 的最近不相等邻居是 5 和 1 。由于 4 < 5 且 4 > 1 ，下标 4 既不是峰也不是谷。
在下标 5 ：由于 1 的右侧不存在不相等邻居，所以下标 5 既不是峰也不是谷。
共有 0 个峰和谷，所以返回 0 。

 

提示：

• 3 <= nums.length <= 100
• 1 <= nums[i] <= 100

方法一：遍历 · Go 实现

思考

峰谷定义依赖「最近的不相等邻居」，连续相等段应视为同一高度。 $n\le 100$，即使对每个 $i$ 向两侧找最近不同值也能通过，但会重复扫描平台。

从左到右走时，上一个已经结算过的不同高度位置可以用指针 $j$ 记住。若 $nums[i]=nums[i+1]$，说明仍在平台内部，跳过；否则用 $nums[j]$ 与 $nums[i+1]$ 判断 $i$ 是否严格高于或低于两侧，再把 $j$ 更新为 $i$。一遍线性扫描即可数出峰谷。

我们初始化一个指针 $j$ 指向下标 $0$ 的位置，然后在 $[1,n-1]$ 的范围内遍历数组。对于每一个位置 $i$：

• 如果 $nums[i]=nums[i+1]$，则跳过。
• 否则，如果 $nums[i]$ 大于 $nums[j]$ 且 $nums[i]$ 大于 $nums[i+1]$，则 $i$ 是一个峰；如果 $nums[i]$ 小于 $nums[j]$ 且 $nums[i]$ 小于 $nums[i+1]$，则 $i$ 是一个谷。
• 然后，我们将 $j$ 更新为 $i$，继续遍历。

遍历结束后，我们就可以得到峰和谷的数量。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func countHillValley(nums []int) int {
	ans := 0
	for i, j := 1, 0; i < len(nums)-1; i++ {
		if nums[i] == nums[i+1] {
			continue
		}
		if nums[i] > nums[j] && nums[i] > nums[i+1] {
			ans++
		}
		if nums[i] < nums[j] && nums[i] < nums[i+1] {
			ans++
		}
		j = i
	}
	return ans
}

力扣原题 · Doocs 题解来源

2239. 找到最接近 0 的数字

简单1 种解法

标签：数组

题目、示例与约束

给你一个长度为 n 的整数数组 nums ，请你返回 nums 中最 接近 0 的数字。如果有多个答案，请你返回它们中的 最大值 。

 

示例 1：

输入：nums = [-4,-2,1,4,8]
输出：1
解释：
-4 到 0 的距离为 |-4| = 4 。
-2 到 0 的距离为 |-2| = 2 。
1 到 0 的距离为 |1| = 1 。
4 到 0 的距离为 |4| = 4 。
8 到 0 的距离为 |8| = 8 。
所以，数组中距离 0 最近的数字为 1 。

示例 2：

输入：nums = [2,-1,1]
输出：1
解释：1 和 -1 都是距离 0 最近的数字，所以返回较大值 1 。

 

提示：

• 1 <= n <= 1000
• -105 <= nums[i] <= 105

方法一：一次遍历 · Go 实现

思考

找绝对值最小的数；并列时取较大者。 $n\le {10}^3$，排序后取最靠近零的几个即可，但只需维护当前最优。

一遍扫描：若绝对值更小，或绝对值相同且数值更大，则更新答案。额外空间 $O(1)$。

我们定义一个变量 $\mathit{\text{d}}$ 来记录当前最小的距离，初始时 $\mathit{\text{d}}=\mathrm{\infty }$。然后我们遍历数组，对于每个元素 $x$，我们计算 $y=|x|$，如果 $y<d$ 或者 $y=d$ 且 $x>\mathit{\text{ans}}$，我们就更新答案 $\mathit{\text{ans}}=x$ 和 $\mathit{\text{d}}=y$。

遍历结束后返回答案即可。

时间复杂度 $O(n)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。

func findClosestNumber(nums []int) int {
	ans, d := 0, 1<<30
	for _, x := range nums {
		if y := abs(x); y < d || (y == d && x > ans) {
			ans, d = x, y
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

2257. 统计网格图中没有被保卫的格子数

中等1 种解法

标签：数组、矩阵、模拟

题目、示例与约束

给你两个整数 m 和 n 表示一个下标从 0 开始的 m x n 网格图。同时给你两个二维整数数组 guards 和 walls ，其中 guards[i] = [rowi, coli] 且 walls[j] = [rowj, colj] ，分别表示第 i 个警卫和第 j 座墙所在的位置。

一个警卫能看到 4 个坐标轴方向（即东、南、西、北）的 所有 格子，除非他们被一座墙或者另外一个警卫 挡住 了视线。如果一个格子能被 至少 一个警卫看到，那么我们说这个格子被 保卫 了。

请你返回空格子中，有多少个格子是 没被保卫 的。

 

示例 1：

输入：m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
输出：7
解释：上图中，被保卫和没有被保卫的格子分别用红色和绿色表示。
总共有 7 个没有被保卫的格子，所以我们返回 7 。

示例 2：

输入：m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
输出：4
解释：上图中，没有被保卫的格子用绿色表示。
总共有 4 个没有被保卫的格子，所以我们返回 4 。

 

提示：

• 1 <= m, n <= 105
• 2 <= m * n <= 105
• 1 <= guards.length, walls.length <= 5 * 104
• 2 <= guards.length + walls.length <= m * n
• guards[i].length == walls[j].length == 2
• 0 <= rowi, rowj < m
• 0 <= coli, colj < n
• guards 和 walls 中所有位置 互不相同 。

方法一：模拟 · Go 实现

思考

守卫沿行列直到撞墙，求未被注视的空格数。 $mn\le {10}^5$，不能对每个守卫重复扫完整行。同一方向上，后一个守卫看到的格子会被前面走过，因此从每个守卫向四向走到墙或边界即可，格子至多被覆盖常数次。

网格上墙壁与守卫标为 $2$，空格被看到标为 $1$。四向延伸时遇 $2$ 停止。最后统计仍为 $0$ 的格子。

我们创建一个 $m\times n$ 的二维数组 $g$，其中 $g[i][j]$ 表示第 $i$ 行第 $j$ 列的格子。初始时 $g[i][j]$ 的值为 $0$，表示该格子没有被保卫。

然后遍历所有的警卫和墙，将 $g[i][j]$ 的值置为 $2$，这些位置不能被访问。

接下来，我们遍历所有警卫的位置，从该位置出发，向四个方向进行模拟，直到遇到墙或警卫，或者越界。在模拟的过程中，将遇到的格子的值置为 $1$，表示该格子被保卫。

最后，我们遍历 $g$，统计值为 $0$ 的格子的个数，即为答案。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别为网格的行数和列数。

func countUnguarded(m int, n int, guards [][]int, walls [][]int) (ans int) {
	g := make([][]int, m)
	for i := range g {
		g[i] = make([]int, n)
	}
	for _, e := range guards {
		g[e[0]][e[1]] = 2
	}
	for _, e := range walls {
		g[e[0]][e[1]] = 2
	}
	dirs := [5]int{-1, 0, 1, 0, -1}
	for _, e := range guards {
		for k := 0; k < 4; k++ {
			x, y := e[0], e[1]
			a, b := dirs[k], dirs[k+1]
			for x+a >= 0 && x+a < m && y+b >= 0 && y+b < n && g[x+a][y+b] < 2 {
				x, y = x+a, y+b
				g[x][y] = 1
			}
		}
	}
	for _, row := range g {
		for _, v := range row {
			if v == 0 {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2293. 极大极小游戏

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。

对 nums 执行下述算法：

1. 设 n 等于 nums 的长度，如果 n == 1 ，终止 算法过程。否则，创建 一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。
2. 对于满足 0 <= i < n / 2 的每个 偶数 下标 i ，将 newNums[i] 赋值 为 min(nums[2 * i], nums[2 * i + 1]) 。
3. 对于满足 0 <= i < n / 2 的每个 奇数 下标 i ，将 newNums[i] 赋值 为 max(nums[2 * i], nums[2 * i + 1]) 。
4. 用 newNums 替换 nums 。
5. 从步骤 1 开始 重复 整个过程。

执行算法后，返回 nums 中剩下的那个数字。

 

示例 1：

输入：nums = [1,3,5,2,4,8,2,2]
输出：1
解释：重复执行算法会得到下述数组。
第一轮：nums = [1,5,4,2]
第二轮：nums = [1,4]
第三轮：nums = [1]
1 是最后剩下的那个数字，返回 1 。

示例 2：

输入：nums = [3]
输出：3
解释：3 就是最后剩下的数字，返回 3 。

 

提示：

• 1 <= nums.length <= 1024
• 1 <= nums[i] <= 109
• nums.length 是 2 的幂

方法一：模拟 · Go 实现

思考

每轮把相邻两数按奇偶下标取 $min$ 或 $max$，直到剩一个数。长度是 $2$ 的幂且不超过 $1024$，按题意模拟即可，不必闭式。

在原数组上把新一轮写到前半段： $n$ 每次折半，第 $i$ 个新值来自 $nums[2i]$ 与 $nums[2i+1]$。最后留下 $nums[0]$。

根据题意，我们可以模拟整个过程，最后剩下的数字即为答案。在实现上，我们不需要额外创建数组，直接在原数组上进行操作即可。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。空间复杂度 $O(1)$。

func minMaxGame(nums []int) int {
	for n := len(nums); n > 1; {
		n >>= 1
		for i := 0; i < n; i++ {
			a, b := nums[i<<1], nums[i<<1|1]
			if i%2 == 0 {
				nums[i] = min(a, b)
			} else {
				nums[i] = max(a, b)
			}
		}
	}
	return nums[0]
}

力扣原题 · Doocs 题解来源

2303. 计算应缴税款总额

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个下标从 0 开始的二维整数数组 brackets ，其中 brackets[i] = [upperi, percenti] ，表示第 i 个税级的上限是 upperi ，征收的税率为 percenti 。税级按上限 从低到高排序（在满足 0 < i < brackets.length 的前提下，upperi-1 < upperi）。

税款计算方式如下：

• 不超过 upper0 的收入按税率 percent0 缴纳
• 接着 upper1 - upper0 的部分按税率 percent1 缴纳
• 然后 upper2 - upper1 的部分按税率 percent2 缴纳
• 以此类推

给你一个整数 income 表示你的总收入。返回你需要缴纳的税款总额。与标准答案误差不超 10-5 的结果将被视作正确答案。

 

示例 1：

输入：brackets = [[3,50],[7,10],[12,25]], income = 10
输出：2.65000
解释：
前 $3 的税率为 50% 。需要支付税款 $3 * 50% = $1.50 。
接下来 $7 - $3 = $4 的税率为 10% 。需要支付税款 $4 * 10% = $0.40 。
最后 $10 - $7 = $3 的税率为 25% 。需要支付税款 $3 * 25% = $0.75 。
需要支付的税款总计 $1.50 + $0.40 + $0.75 = $2.65 。

示例 2：

输入：brackets = [[1,0],[4,25],[5,50]], income = 2
输出：0.25000
解释：
前 $1 的税率为 0% 。需要支付税款 $1 * 0% = $0 。
剩下 $1 的税率为 25% 。需要支付税款 $1 * 25% = $0.25 。
需要支付的税款总计 $0 + $0.25 = $0.25 。

示例 3：

输入：brackets = [[2,50]], income = 0
输出：0.00000
解释：
没有收入，无需纳税，需要支付的税款总计 $0 。

 

提示：

• 1 <= brackets.length <= 100
• 1 <= upperi <= 1000
• 0 <= percenti <= 100
• 0 <= income <= 1000
• upperi 按递增顺序排列
• upperi 中的所有值 互不相同
• 最后一个税级的上限大于等于 income

方法一：模拟 · Go 实现

思考

税级按上限递增且最后一级覆盖全部收入，因此税额由各档实际落入的金额唯一确定。 $brackets$ 至多 $100$ 档，按序扫描即可。

第 $i$ 档的应纳税基数是 $min(income,uppe{r}_i)$ 与上一档上限之差（若为负则该档未触及）。乘以税率并累加，最后除以 $100$ 得到实缴税款。无需回溯或预计算。

我们遍历 brackets，对于每个税级，计算该税级的税额，然后累加即可。

时间复杂度 $O(n)$，其中 $n$ 为 brackets 的长度。空间复杂度 $O(1)$。

func calculateTax(brackets [][]int, income int) float64 {
	var ans, prev int
	for _, e := range brackets {
		upper, percent := e[0], e[1]
		ans += max(0, min(income, upper)-prev) * percent
		prev = upper
	}
	return float64(ans) / 100.0
}

力扣原题 · Doocs 题解来源

2319. 判断矩阵是否是一个 X 矩阵

简单1 种解法

标签：数组、矩阵

题目、示例与约束

如果一个正方形矩阵满足下述 全部 条件，则称之为一个 X 矩阵 ：

1. 矩阵对角线上的所有元素都 不是 0
2. 矩阵中所有其他元素都是 0

给你一个大小为 n x n 的二维整数数组 grid ，表示一个正方形矩阵。如果 grid 是一个 X 矩阵 ，返回 true ；否则，返回 false 。

 

示例 1：

输入：grid = [[2,0,0,1],[0,3,1,0],[0,5,2,0],[4,0,0,2]]
输出：true
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 是一个 X 矩阵。

示例 2：

输入：grid = [[5,7,0],[0,3,1],[0,5,0]]
输出：false
解释：矩阵如上图所示。
X 矩阵应该满足：绿色元素（对角线上）都不是 0 ，红色元素都是 0 。
因此，grid 不是一个 X 矩阵。

 

提示：

• n == grid.length == grid[i].length
• 3 <= n <= 100
• 0 <= grid[i][j] <= 105

方法一：模拟 · Go 实现

思考

$X$ 矩阵要求两条对角线上非零、其余位置为零。 $n\le 100$，扫描每个格子即可判定。

下标满足 $i=j$ 或 $i+j=n-1$ 时拒绝 $0$，否则拒绝非零。中途失败立即返回，无需额外结构。

我们可以直接遍历矩阵，对于每个元素，判断其是否满足 $X$ 矩阵的条件。若不满足，直接返回 $\mathit{\text{false}}$；若遍历完所有元素都满足，返回 $\mathit{\text{true}}$。

时间复杂度 $O(n^2)$，其中 $n$ 为矩阵的行数或列数。空间复杂度 $O(1)$。

func checkXMatrix(grid [][]int) bool {
	for i, row := range grid {
		for j, v := range row {
			if i == j || i+j == len(row)-1 {
				if v == 0 {
					return false
				}
			} else if v != 0 {
				return false
			}
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

2373. 矩阵中的局部最大值

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个大小为 n x n 的整数矩阵 grid 。

生成一个大小为 (n - 2) x (n - 2) 的整数矩阵  maxLocal ，并满足：

• maxLocal[i][j] 等于 grid 中以 i + 1 行和 j + 1 列为中心的 3 x 3 矩阵中的 最大值 。

换句话说，我们希望找出 grid 中每个 3 x 3 矩阵中的最大值。

返回生成的矩阵。

 

示例 1：

输入：grid = [[9,9,8,1],[5,6,2,6],[8,2,6,4],[6,2,2,2]]
输出：[[9,9],[8,6]]
解释：原矩阵和生成的矩阵如上图所示。
注意，生成的矩阵中，每个值都对应 grid 中一个相接的 3 x 3 矩阵的最大值。

示例 2：

输入：grid = [[1,1,1,1,1],[1,1,1,1,1],[1,1,2,1,1],[1,1,1,1,1],[1,1,1,1,1]]
输出：[[2,2,2],[2,2,2],[2,2,2]]
解释：注意，2 包含在 grid 中每个 3 x 3 的矩阵中。

 

提示：

• n == grid.length == grid[i].length
• 3 <= n <= 100
• 1 <= grid[i][j] <= 100

方法一：枚举 · Go 实现

思考

每个位置填入以其为左上的 $3\times 3$ 的最大值。 $n\le 100$，直接枚举窗口即可。

对每个 $(i,j)$ 扫描九格取最大，写入 $(n-2)\times (n-2)$ 的答案矩阵。

我们可以枚举每个 $3\times 3$ 的矩阵，求出每个 $3\times 3$ 的矩阵中的最大值，然后将这些最大值放入答案矩阵中。

时间复杂度 $O(n^2)$，其中 $n$ 是矩阵的边长。忽略答案矩阵的空间消耗，空间复杂度 $O(1)$。

func largestLocal(grid [][]int) [][]int {
	n := len(grid)
	ans := make([][]int, n-2)
	for i := range ans {
		ans[i] = make([]int, n-2)
		for j := 0; j < n-2; j++ {
			for x := i; x <= i+2; x++ {
				for y := j; y <= j+2; y++ {
					ans[i][j] = max(ans[i][j], grid[x][y])
				}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2432. 处理用时最长的那个任务的员工

简单1 种解法

标签：数组

题目、示例与约束

共有 n 位员工，每位员工都有一个从 0 到 n - 1 的唯一 id 。

给你一个二维整数数组 logs ，其中 logs[i] = [idi, leaveTimei] ：

• idi 是处理第 i 个任务的员工的 id ，且
• leaveTimei 是员工完成第 i 个任务的时刻。所有 leaveTimei 的值都是 唯一 的。

注意，第 i 个任务在第 (i - 1) 个任务结束后立即开始，且第 0 个任务从时刻 0 开始。

返回处理用时最长的那个任务的员工的 id 。如果存在两个或多个员工同时满足，则返回几人中 最小 的 id 。

 

示例 1：

输入：n = 10, logs = [[0,3],[2,5],[0,9],[1,15]]
输出：1
解释：
任务 0 于时刻 0 开始，且在时刻 3 结束，共计 3 个单位时间。
任务 1 于时刻 3 开始，且在时刻 5 结束，共计 2 个单位时间。
任务 2 于时刻 5 开始，且在时刻 9 结束，共计 4 个单位时间。
任务 3 于时刻 9 开始，且在时刻 15 结束，共计 6 个单位时间。
时间最长的任务是任务 3 ，而 id 为 1 的员工是处理此任务的员工，所以返回 1 。

示例 2：

输入：n = 26, logs = [[1,1],[3,7],[2,12],[7,17]]
输出：3
解释：
任务 0 于时刻 0 开始，且在时刻 1 结束，共计 1 个单位时间。
任务 1 于时刻 1 开始，且在时刻 7 结束，共计 6 个单位时间。
任务 2 于时刻 7 开始，且在时刻 12 结束，共计 5 个单位时间。
任务 3 于时刻 12 开始，且在时刻 17 结束，共计 5 个单位时间。
时间最长的任务是任务 1 ，而 id 为 3 的员工是处理此任务的员工，所以返回 3 。

示例 3：

输入：n = 2, logs = [[0,10],[1,20]]
输出：0
解释：
任务 0 于时刻 0 开始，且在时刻 10 结束，共计 10 个单位时间。
任务 1 于时刻 10 开始，且在时刻 20 结束，共计 10 个单位时间。
时间最长的任务是任务 0 和 1 ，处理这两个任务的员工的 id 分别是 0 和 1 ，所以返回最小的 0 。

 

提示：

• 2 <= n <= 500
• 1 <= logs.length <= 500
• logs[i].length == 2
• 0 <= idi <= n - 1
• 1 <= leaveTimei <= 500
• idi != idi + 1
• leaveTimei 按严格递增顺序排列

方法一：直接遍历 · Go 实现

思考

$\mathit{\text{logs}}$ 按离开时间严格递增，第 $i$ 个任务的耗时即 $leaveTim{e}_i$ 减去上一任务离开时间。长度至多 $500$，一遍扫描即可同时维护最长耗时与对应最小 $id$。

我们用变量 $last$ 记录上一个任务的结束时间，用变量 $mx$ 记录最长的工作时间，用变量 $ans$ 记录工作时间最长且 $id$ 最小的员工。初始时，三个变量均为 $0$。

接下来，遍历数组 $logs$，对于每个员工，我们将员工完成任务的时间减去上一个任务的结束时间，即可得到该员工的工作时间 $t$。如果 $mx$ 小于 $t$，或者 $mx$ 等于 $t$ 且该员工的 $id$ 小于 $ans$，则更新 $mx$ 和 $ans$。然后我们将 $last$ 更新为上一个任务的结束时间加上 $t$。继续遍历，直到遍历完整个数组。

最后返回答案 $ans$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $logs$ 的长度。空间复杂度 $O(1)$。

func hardestWorker(n int, logs [][]int) (ans int) {
	var mx, last int
	for _, log := range logs {
		uid, t := log[0], log[1]
		t -= last
		if mx < t || (mx == t && uid < ans) {
			mx = t
			ans = uid
		}
		last += t
	}
	return
}

力扣原题 · Doocs 题解来源