LeetCode Go · 数组与矩阵（2）

来源与许可

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

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

1184. 公交站间的距离

简单1 种解法

标签：数组

题目、示例与约束

环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。

环线上的公交车都可以按顺时针和逆时针的方向行驶。

返回乘客从出发点 start 到目的地 destination 之间的最短距离。

示例 1：

输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。

示例 2：

输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。

示例 3：

输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。

提示：

1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

方法一：模拟 · Go 实现

思考

车站成环，两点间只有顺时针与逆时针两条弧。累加总长 $s$ ，再沿一侧从 $s t a r t$ 走到 $d e s t i n a t i o n$ 得 $t$ ，另一侧为 $s - t$ ，取较小者。不必建图。

我们可以先统计出公交车的总行驶距离 $s$ ，然后模拟公交车的行驶过程，从出发点开始，每次向右移动一站，直到到达目的地为止，记录下这个过程中的行驶距离 $t$ ，最后返回 $t$ 和 $s - t$ 中的最小值即可。

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

func distanceBetweenBusStops(distance []int, start int, destination int) int {
	s, t := 0, 0
	for _, x := range distance {
		s += x
	}
	for start != destination {
		t += distance[start]
		start = (start + 1) % len(distance)
	}
	return min(t, s-t)
}

力扣原题 · Doocs 题解来源

1222. 可以攻击国王的皇后

中等1 种解法

标签：数组、矩阵、模拟

题目、示例与约束

在一个 下标从 0 开始 的 8 x 8 棋盘上，可能有多个黑皇后和一个白国王。

给你一个二维整数数组 queens，其中 queens[i] = [xQueeni, yQueeni] 表示第 i 个黑皇后在棋盘上的位置。还给你一个长度为 2 的整数数组 king，其中 king = [xKing, yKing] 表示白国王的位置。

返回 能够直接攻击国王的黑皇后的坐标。你可以以 任何顺序 返回答案。

示例 1：

输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出：[[0,1],[1,0],[3,3]]
解释：上面的图示显示了三个可以直接攻击国王的皇后和三个不能攻击国王的皇后（用红色虚线标记）。

示例 2：

输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
输出：[[2,2],[3,4],[4,4]]
解释：上面的图示显示了三个能够直接攻击国王的黑皇后和三个不能攻击国王的黑皇后（用红色虚线标记）。

提示：

1 <= queens.length < 64
queens[i].length == king.length == 2
0 <= xQueen_i, yQueen_i, xKing, yKing < 8
所有给定的位置都是唯一的。

方法一：直接搜索 · Go 实现

思考

棋盘仅 $8 \times 8$ ，皇后不足 $64$ 个。能攻击国王的皇后必须与国王同行、列或斜线，且中间无其他皇后。从国王沿八个方向外走，每个方向遇到的第一枚皇后即该方向唯一攻击者。

先把皇后坐标放入集合以便 $O (1)$ 查询，再从国王位置沿八个单位向量延伸，命中则记录并停止该方向。方向搜索保证遮挡关系，集合保证每步判定为常数。

我们先将所有皇后的位置存入哈希表或者二维数组 $s$ 中。

接下来，我们从国王的位置开始，依次向上、下、左、右、左上、右上、左下、右下八个方向搜索，如果某个方向上存在皇后，那么就将其位置加入答案中，并且停止继续搜索该方向。

搜索结束后，返回答案即可。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n^{2})$ 。本题中 $n = 8$ 。

func queensAttacktheKing(queens [][]int, king []int) (ans [][]int) {
	n := 8
	s := [8][8]bool{}
	for _, q := range queens {
		s[q[0]][q[1]] = true
	}
	for a := -1; a <= 1; a++ {
		for b := -1; b <= 1; b++ {
			if a != 0 || b != 0 {
				x, y := king[0]+a, king[1]+b
				for 0 <= x && x < n && 0 <= y && y < n {
					if s[x][y] {
						ans = append(ans, []int{x, y})
						break
					}
					x += a
					y += b
				}
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1243. 数组变换 🔒

简单1 种解法

标签：数组、模拟

题目、示例与约束

首先，给你一个初始数组 arr。然后，每天你都要根据前一天的数组生成一个新的数组。

第 i 天所生成的数组，是由你对第 i-1 天的数组进行如下操作所得的：

假如一个元素小于它的左右邻居，那么该元素自增 1。
假如一个元素大于它的左右邻居，那么该元素自减 1。
首、尾元素永不改变。

过些时日，你会发现数组将会不再发生变化，请返回最终所得到的数组。

示例 1：

输入：[6,2,3,4]
输出：[6,3,3,4]
解释：
第一天，数组从 [6,2,3,4] 变为 [6,3,3,4]。
无法再对该数组进行更多操作。

示例 2：

输入：[1,6,3,4,3,5]
输出：[1,4,4,4,4,5]
解释：
第一天，数组从 [1,6,3,4,3,5] 变为 [1,5,4,3,4,5]。
第二天，数组从 [1,5,4,3,4,5] 变为 [1,4,4,4,4,5]。
无法再对该数组进行更多操作。

提示：

1 <= arr.length <= 100
1 <= arr[i] <= 100

方法一：模拟 · Go 实现

思考

规则只看左右邻居，且两端永不改。 $n$ 与值均不超过 $100$ ，直接模拟直到稳定即可。同一天的增减必须基于旧数组，否则右侧尚未更新的值会污染左侧判定。

每轮复制出快照 $t$ ，按 $t$ 的邻接关系改 $a r r$ ，若有变动则继续。模拟忠实于「同时更新」的定义。

每次模拟一天，对于每个元素，如果它大于左右邻居，则自减 1，否则自增 1。如果数组在某一天不再发生变化，则返回该数组。

时间复杂度 $O (n \times m)$ ，空间复杂度 $O (n)$ 。其中 $n$ 和 $m$ 分别为数组长度和数组元素的最大值。

func transformArray(arr []int) []int {
	f := true
	for f {
		f = false
		t := make([]int, len(arr))
		copy(t, arr)
		for i := 1; i < len(arr)-1; i++ {
			if t[i] > t[i-1] && t[i] > t[i+1] {
				arr[i]--
				f = true
			}
			if t[i] < t[i-1] && t[i] < t[i+1] {
				arr[i]++
				f = true
			}
		}
	}
	return arr
}

力扣原题 · Doocs 题解来源

1260. 二维网格迁移

简单1 种解法

标签：数组、矩阵、模拟

题目、示例与约束

给你一个 m 行 n 列的二维网格 grid 和一个整数 k。你需要将 grid 迁移 k 次。

每次「迁移」操作将会引发下述活动：

位于 grid[i][j]（j < n - 1）的元素将会移动到 grid[i][j + 1]。
位于 grid[i][n - 1] 的元素将会移动到 grid[i + 1][0]。
位于 grid[m - 1][n - 1] 的元素将会移动到 grid[0][0]。

请你返回 k 次迁移操作后最终得到的 二维网格。

示例 1：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[9,1,2],[3,4,5],[6,7,8]]

示例 2：

输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]

示例 3：

输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
输出：[[1,2,3],[4,5,6],[7,8,9]]

提示：

m == grid.length
n == grid[i].length
1 <= m <= 50
1 <= n <= 50
-1000 <= grid[i][j] <= 1000
0 <= k <= 100

方法一：二维数组展开 · Go 实现

思考

每次把末格挪到开头并把其余右移一格，等价于把二维数组按行展平后整体右旋 $k$ 位。 $m, n \leq 50$ ，可直接计算每个元素的终态下标，而不必真的旋转 $k$ 次。

展平坐标为 $i \cdot n + j$ ，加上 $k$ 再对 $m n$ 取模，还原行、列写入新矩阵。一次遍历完成映射。

根据题目描述，如果我们将二维数组展开成一维数组，那么每次迁移操作就是将数组中的元素向右移动一个位置，最后一个元素移动到数组的首位。

因此，我们可以将二维数组展开成一维数组，然后计算每个元素在最后的位置 $i d x = (x, y)$ ，更新答案数组 ans[x][y] = grid[i][j] 即可。

时间复杂度 $O (m \times n)$ ，其中 $m$ 和 $n$ 分别是二维数组 grid 的行数和列数。需要遍历二维数组 grid 一次，计算每个元素在最后的位置。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

func shiftGrid(grid [][]int, k int) [][]int {
	m, n := len(grid), len(grid[0])
	ans := make([][]int, m)
	for i := range ans {
		ans[i] = make([]int, n)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			idx := (i*n + j + k) % (m * n)
			x, y := idx/n, idx%n
			ans[x][y] = grid[i][j]
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1272. 删除区间 🔒

中等1 种解法

标签：数组

题目、示例与约束

实数集合可以表示为若干不相交区间的并集，其中每个区间的形式为 [a, b)（左闭右开），表示满足 a <= x < b 的所有实数 x 的集合。如果某个区间 [a, b) 中包含实数 x ，则称实数 x 在集合中。

给你一个 有序的 不相交区间列表 intervals 。intervals 表示一个实数集合，其中每一项 intervals[i] = [a_i, b_i] 都表示一个区间 [a_i, b_i) 。再给你一个要删除的区间 toBeRemoved 。

返回 一组实数，该实数表示intervals 中删除了 toBeRemoved 的部分 。换句话说，返回实数集合，并满足集合中的每个实数 x 都在 intervals 中，但不在 toBeRemoved 中。你的答案应该是一个如上所述的 有序的 不相连的间隔列表。

示例 1：

输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
输出：[[0,1],[6,7]]

示例 2：

输入：intervals = [[0,5]], toBeRemoved = [2,3]
输出：[[0,2],[3,5]]

示例 3：

输入：intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
输出：[[-5,-4],[-3,-2],[4,5],[8,9]]

提示：

1 <= intervals.length <= 10⁴
-10⁹ <= a_i < b_i <= 10⁹

方法一：分类讨论 · Go 实现

思考

从已排序且互不重叠的区间中挖掉 $[x, y)$ 。每个区间与删除段的关系只有相离、被完全覆盖、或被切成左右两段。从左到右分类：不相交则原样保留，相交则可能写下 $[a, x)$ 与 $[y, b)$ 。线性一遍，无需再排序。

我们记要删除的区间为 $[x, y)$ ，遍历区间列表，对于每个区间 $[a, b)$ ，有以下三种情况：

$a \geq y$ 或 $b \leq x$ ，表示该区间与要删除的区间没有交集，直接将该区间加入答案；
$a < x$ , $b > y$ ，表示该区间与要删除的区间有交集，将该区间分成两个区间加入答案；
$a \geq x$ , $b \leq y$ ，表示该区间被要删除的区间完全覆盖，不加入答案。

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

func removeInterval(intervals [][]int, toBeRemoved []int) (ans [][]int) {
	x, y := toBeRemoved[0], toBeRemoved[1]
	for _, e := range intervals {
		a, b := e[0], e[1]
		if a >= y || b <= x {
			ans = append(ans, e)
		} else {
			if a < x {
				ans = append(ans, []int{a, x})
			}
			if b > y {
				ans = append(ans, []int{y, b})
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1287. 有序数组中出现次数超过25%的元素

简单1 种解法

标签：数组

题目、示例与约束

给你一个非递减的有序整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

示例：

输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

提示：

1 <= arr.length <= 10^4
0 <= arr[i] <= 10^5

方法一：遍历 · Go 实现

思考

有序数组中必有元素出现超过 $25 %$ ，即跨度至少 $⌊ n / 4 ⌋$ 。若 $a r r [i] = a r r [i + ⌊ n / 4 ⌋]$ ，该值已覆盖足够长度。从左扫描第一次命中即可，利用有序把计数变成下标比较。

我们从头开始遍历数组 $arr$ ，对于每个元素 $arr [i]$ ，我们检查 $arr [i]$ 是否等于 $arr [i + ⌊ \frac{n}{4} ⌋]$ ，其中 $n$ 是数组的长度。如果等于，那么 $arr [i]$ 就是我们要找的元素，直接返回即可。

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

func findSpecialInteger(arr []int) int {
	for i := 0; ; i++ {
		if arr[i] == arr[i+len(arr)/4] {
			return arr[i]
		}
	}
}

力扣原题 · Doocs 题解来源

1299. 将每个元素替换为右侧最大元素

简单1 种解法

标签：数组

题目、示例与约束

给你一个数组 arr ，请你将每个元素用它右边最大的元素替换，如果是最后一个元素，用 -1 替换。

完成所有替换操作后，请你返回这个数组。

示例 1：

输入：arr = [17,18,5,4,6,1]
输出：[18,6,6,6,1,-1]
解释：
- 下标 0 的元素 --> 右侧最大元素是下标 1 的元素 (18)
- 下标 1 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 2 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 3 的元素 --> 右侧最大元素是下标 4 的元素 (6)
- 下标 4 的元素 --> 右侧最大元素是下标 5 的元素 (1)
- 下标 5 的元素 --> 右侧没有其他元素，替换为 -1

示例 2：

输入：arr = [400]
输出：[-1]
解释：下标 0 的元素右侧没有其他元素。

提示：

1 <= arr.length <= 10⁴
1 <= arr[i] <= 10⁵

方法一：逆序遍历 · Go 实现

思考

每位要换成右侧最大值，末位为 $- 1$ 。从左再扫右侧会重复工作。自右向左维护后缀最大值 $m x$ ，先把当前位置写成旧的 $m x$ ，再用当前原值更新 $m x$ 。一遍逆序， $O (1)$ 额外空间。

我们用一个变量 $m x$ 记录当前位置右侧的最大值，初始时 $m x = - 1$ 。

然后我们从右向左遍历数组，对于每个位置 $i$ ，我们记当前位置的值为 $x$ ，将当前位置的值更新为 $m x$ ，然后更新 $m x = max (m x, x)$ 。

最后返回原数组即可。

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

func replaceElements(arr []int) []int {
	for i, mx := len(arr)-1, -1; i >= 0; i-- {
		x := arr[i]
		arr[i] = mx
		mx = max(mx, x)
	}
	return arr
}

力扣原题 · Doocs 题解来源

1313. 解压缩编码列表

简单1 种解法

标签：数组

题目、示例与约束

给你一个以行程长度编码压缩的整数列表 nums 。

考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。

请你返回解压后的列表。

示例 1：

输入：nums = [1,2,3,4]
输出：[2,4,4,4]
解释：第一对 [1,2] 代表着 2 的出现频次为 1，所以生成数组 [2]。
第二对 [3,4] 代表着 4 的出现频次为 3，所以生成数组 [4,4,4]。
最后将它们串联到一起 [2] + [4,4,4] = [2,4,4,4]。

示例 2：

输入：nums = [1,1,2,3]
输出：[1,3,3]

提示：

2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100

方法一：模拟 · Go 实现

思考

编码以 $(freq, val)$ 成对给出，按题意展开即可。没有重叠或依赖，从左到右每次取出一对，把 $val$ 重复 $freq$ 次写入答案。

我们可以直接模拟题目描述的过程，从左到右遍历数组 $nums$ ，每次取出两个数 $freq$ 和 $val$ ，然后将 $val$ 重复 $freq$ 次，将这 $freq$ 个 $val$ 加入答案数组即可。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $nums$ 的长度。我们只需要遍历一次数组 $nums$ 即可。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

func decompressRLElist(nums []int) (ans []int) {
	for i := 1; i < len(nums); i += 2 {
		for j := 0; j < nums[i-1]; j++ {
			ans = append(ans, nums[i])
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1375. 二进制字符串前缀一致的次数

中等1 种解法

标签：数组

题目、示例与约束

给你一个长度为 n 、下标从 1 开始的二进制字符串，所有位最开始都是 0 。我们会按步翻转该二进制字符串的所有位（即，将 0 变为 1）。

给你一个下标从 1 开始的整数数组 flips ，其中 flips[i] 表示对应下标 i 的位将会在第 i 步翻转。

二进制字符串 前缀一致 需满足：在第 i 步之后，在闭区间 [1, i] 内的所有位都是 1 ，而其他位都是 0 。

返回二进制字符串在翻转过程中 前缀一致 的次数。

示例 1：

输入：flips = [3,2,4,1,5]
输出：2
解释：二进制字符串最开始是 "00000" 。
执行第 1 步：字符串变为 "00100" ，不属于前缀一致的情况。
执行第 2 步：字符串变为 "01100" ，不属于前缀一致的情况。
执行第 3 步：字符串变为 "01110" ，不属于前缀一致的情况。
执行第 4 步：字符串变为 "11110" ，属于前缀一致的情况。
执行第 5 步：字符串变为 "11111" ，属于前缀一致的情况。
在翻转过程中，前缀一致的次数为 2 ，所以返回 2 。

示例 2：

输入：flips = [4,1,2,3]
输出：1
解释：二进制字符串最开始是 "0000" 。
执行第 1 步：字符串变为 "0001" ，不属于前缀一致的情况。
执行第 2 步：字符串变为 "1001" ，不属于前缀一致的情况。
执行第 3 步：字符串变为 "1101" ，不属于前缀一致的情况。
执行第 4 步：字符串变为 "1111" ，属于前缀一致的情况。
在翻转过程中，前缀一致的次数为 1 ，所以返回 1 。

提示：

n == flips.length
1 <= n <= 5 * 10⁴
flips 是范围 [1, n] 中所有整数构成的一个排列

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

思考

$f l i p s$ 是 $1. . n$ 的排列，第 $i$ 步把第 $f l i p s [i]$ 位翻成 $1$ ，问有多少时刻前缀 $[1. . i]$ 全为 $1$ 。这等价于前 $i$ 次翻转的最大值恰好为 $i$ 。维护扫描过的最大值 $m x$ ，当 $m x = i$ 时计入一次。

我们可以遍历数组 $f l i p s$ ，记录当前遍历过的元素的最大值 $m x$ ，若 $m x$ 等于当前遍历到的下标 $i$ ，则说明前 $i$ 个元素都被翻转过了，即前缀一致，答案累加。

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

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

func numTimesAllBlue(flips []int) (ans int) {
	mx := 0
	for i, x := range flips {
		mx = max(mx, x)
		if mx == i+1 {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1380. 矩阵中的幸运数

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个 m x n 的矩阵，矩阵中的数字 各不相同 。请你按任意顺序返回矩阵中的所有幸运数。

幸运数 是指矩阵中满足同时下列两个条件的元素：

在同一行的所有元素中最小
在同一列的所有元素中最大

示例 1：

输入：matrix = [[3,7,8],[9,11,13],[15,16,17]]
输出：[15]
解释：15 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

示例 2：

输入：matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
输出：[12]
解释：12 是唯一的幸运数，因为它是其所在行中的最小值，也是所在列中的最大值。

示例 3：

输入：matrix = [[7,8],[1,2]]
输出：[7]
解释：7 是唯一的幸运数字，因为它是行中的最小值，列中的最大值。

提示：

m == mat.length
n == mat[i].length
1 <= n, m <= 50
1 <= matrix[i][j] <= 10⁵
矩阵中的所有元素都是不同的

方法一：维护行最小值和列最大值 · Go 实现

思考

幸运数是所在行之最小、所在列之最大。元素互异，故行最小集合与列最大集合的交集即为全部幸运数。先求出每行最小值、每列最大值，再取交。

我们可以使用两个数组 $r o w s$ 和 $c o l s$ 记录矩阵中每一行的最小值和每一列的最大值，然后遍历矩阵中的每一个元素，检查该元素是否为所在行的最小值且为所在列的最大值，如果是则该元素为幸运数，我们将其加入答案数组。

遍历结束后，我们返回答案数组即可。

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

func luckyNumbers(matrix [][]int) (ans []int) {
	m, n := len(matrix), len(matrix[0])
	rows, cols := make([]int, m), make([]int, n)
	for i := range rows {
		rows[i] = 1 << 30
	}
	for i, row := range matrix {
		for j, x := range row {
			rows[i] = min(rows[i], x)
			cols[j] = max(cols[j], x)
		}
	}
	for i, row := range matrix {
		for j, x := range row {
			if rows[i] == cols[j] {
				ans = append(ans, x)
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1389. 按既定顺序创建目标数组

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：

目标数组 target 最初为空。
按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
重复上一步，直到在 nums 和 index 中都没有要读取的元素。

请你返回目标数组。

题目保证数字插入位置总是存在。

示例 1：

输入：nums = [0,1,2,3,4], index = [0,1,2,2,1]
输出：[0,4,1,3,2]
解释：
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

示例 2：

输入：nums = [1,2,3,4,0], index = [0,1,2,3,0]
输出：[0,1,2,3,4]
解释：
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

示例 3：

输入：nums = [1], index = [0]
输出：[1]

提示：

1 <= nums.length, index.length <= 100
nums.length == index.length
0 <= nums[i] <= 100
0 <= index[i] <= i

方法一：模拟 · Go 实现

思考

按 $index [i]$ 把 $nums [i]$ 插入目标数组，题面保证下标合法。 $n \leq 100$ ，直接 $insert$ 即可，每次插入把后续元素右移。

我们创建一个列表 $t a r g e t$ ，用于存储目标数组。由于题目保证数字插入位置总是存在，因此我们可以直接按照给定的顺序插入到对应的位置。

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

func createTargetArray(nums []int, index []int) []int {
	target := make([]int, len(nums))
	for i, x := range nums {
		copy(target[index[i]+1:], target[index[i]:])
		target[index[i]] = x
	}
	return target
}

力扣原题 · Doocs 题解来源

1431. 拥有最多糖果的孩子

简单1 种解法

标签：数组

题目、示例与约束

有 n 个有糖果的孩子。给你一个数组 candies，其中 candies[i] 代表第 i 个孩子拥有的糖果数目，和一个整数 extraCandies 表示你所有的额外糖果的数量。

返回一个长度为 n 的布尔数组 result，如果把所有的 extraCandies 给第 i 个孩子之后，他会拥有所有孩子中最多的糖果，那么 result[i] 为 true，否则为 false。

注意，允许有多个孩子同时拥有最多的糖果数目。

示例 1：

输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true] 
解释：如果你把额外的糖果全部给：
孩子 1，将有 2 + 3 = 5 个糖果，是孩子中最多的。
孩子 2，将有 3 + 3 = 6 个糖果，是孩子中最多的。
孩子 3，将有 5 + 3 = 8 个糖果，是孩子中最多的。
孩子 4，将有 1 + 3 = 4 个糖果，不是孩子中最多的。
孩子 5，将有 3 + 3 = 6 个糖果，是孩子中最多的。

示例 2：

输入：candies = [4,2,1,1,2], extraCandies = 1
输出：[true,false,false,false,false] 
解释：只有 1 个额外糖果，所以不管额外糖果给谁，只有孩子 1 可以成为拥有糖果最多的孩子。

示例 3：

输入：candies = [12,1,12], extraCandies = 10
输出：[true,false,true]

提示：

n == candies.length
2 <= n <= 100
1 <= candies[i] <= 100
1 <= extraCandies <= 50

方法一 · Go 实现

思考

$n \leq 100$ ，先求出当前最大值 $m x$ ，再判断每个孩子加上额外糖果后是否不小于 $m x$ 。不必模拟真正分配。

func kidsWithCandies(candies []int, extraCandies int) (ans []bool) {
	mx := slices.Max(candies)
	for _, candy := range candies {
		ans = append(ans, candy+extraCandies >= mx)
	}
	return
}

力扣原题 · Doocs 题解来源

1437. 是否所有 1 都至少相隔 k 个元素

简单1 种解法

标签：数组

题目、示例与约束

给你一个由若干 0 和 1 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素，则返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,0,0,0,1,0,0,1], k = 2
输出：true
解释：每个 1 都至少相隔 2 个元素。

示例 2：

输入：nums = [1,0,0,1,0,1], k = 2
输出：false
解释：第二个 1 和第三个 1 之间只隔了 1 个元素。

提示：

1 <= nums.length <= 10⁵
0 <= k <= nums.length
nums[i] 的值为 0 或 1

方法一：模拟 · Go 实现

思考

$n \leq 10^{5}$ ，记录上一个 $1$ 的下标 $j$ ，遇到新的 $1$ 时检查中间 $0$ 的个数 $i - j - 1$ 是否小于 $k$ 。一遍扫描即可。

我们可以遍历数组 $nums$ ，用变量 $j$ 记录上一个 $1$ 的下标，那么当前位置 $i$ 的元素为 $1$ 时，只需要判断 $i - j - 1$ 是否小于 $k$ 即可。如果小于 $k$ ，则说明存在两个 $1$ 之间的 $0$ 的个数小于 $k$ ，返回 $false$ ；否则，将 $j$ 更新为 $i$ ，继续遍历数组。

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

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

func kLengthApart(nums []int, k int) bool {
	j := -(k + 1)
	for i, x := range nums {
		if x == 1 {
			if i-j-1 < k {
				return false
			}
			j = i
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1450. 在既定时间做作业的学生人数

简单1 种解法

标签：数组

题目、示例与约束

给你两个整数数组 startTime（开始时间）和 endTime（结束时间），并指定一个整数 queryTime 作为查询时间。

已知，第 i 名学生在 startTime[i] 时开始写作业并于 endTime[i] 时完成作业。

请返回在查询时间 queryTime 时正在做作业的学生人数。形式上，返回能够使 queryTime 处于区间 [startTime[i], endTime[i]]（含）的学生人数。

示例 1：

输入：startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
输出：1
解释：一共有 3 名学生。
第一名学生在时间 1 开始写作业，并于时间 3 完成作业，在时间 4 没有处于做作业的状态。
第二名学生在时间 2 开始写作业，并于时间 2 完成作业，在时间 4 没有处于做作业的状态。
第三名学生在时间 3 开始写作业，预计于时间 7 完成作业，这是是唯一一名在时间 4 时正在做作业的学生。

示例 2：

输入：startTime = [4], endTime = [4], queryTime = 4
输出：1
解释：在查询时间只有一名学生在做作业。

示例 3：

输入：startTime = [4], endTime = [4], queryTime = 5
输出：0

示例 4：

输入：startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
输出：0

示例 5：

输入：startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
输出：5

提示：

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

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

思考

$n \leq 100$ ，对每个学生判断 $queryTime$ 是否落在 $[start, end]$ 内并计数。

我们可以直接遍历两个数组，对于每个学生，判断 $queryTime$ 是否在他们的作业时间区间内，若是，答案加一。

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

时间复杂度 $O (n)$ ，其中 $n$ 为学生数量。空间复杂度 $O (1)$ 。

func busyStudent(startTime []int, endTime []int, queryTime int) (ans int) {
	for i, x := range startTime {
		if x <= queryTime && queryTime <= endTime[i] {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1470. 重新排列数组

简单1 种解法

标签：数组

题目、示例与约束

给你一个数组 nums ，数组中有 2n 个元素，按 [x₁,x₂,...,x_n,y₁,y₂,...,y_n] 的格式排列。

请你将数组按 [x₁,y₁,x₂,y₂,...,x_n,y_n] 格式重新排列，返回重排后的数组。

示例 1：

输入：nums = [2,5,1,3,4,7], n = 3
输出：[2,3,5,4,1,7] 
解释：由于 x₁=2, x₂=5, x₃=1, y₁=3, y₂=4, y₃=7 ，所以答案为 [2,3,5,4,1,7]

示例 2：

输入：nums = [1,2,3,4,4,3,2,1], n = 4
输出：[1,4,2,3,3,2,4,1]

示例 3：

输入：nums = [1,1,2,2], n = 2
输出：[1,2,1,2]

提示：

1 <= n <= 500
nums.length == 2n
1 <= nums[i] <= 10^3

方法一：模拟 · Go 实现

思考

要把 $[x_{1}, \dots, x_{n}, y_{1}, \dots, y_{n}]$ 交错。zip 前半与后半后展平即可。

我们在 $[0, n)$ 的范围内遍历下标 $i$ ，每次取出 $nums [i]$ 和 $nums [i + n]$ ，并将它们依次放入答案数组中。

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

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

func shuffle(nums []int, n int) (ans []int) {
	for i := 0; i < n; i++ {
		ans = append(ans, nums[i])
		ans = append(ans, nums[i+n])
	}
	return
}

力扣原题 · Doocs 题解来源

1503. 所有蚂蚁掉下来前的最后一刻

中等1 种解法

标签：脑筋急转弯、数组、模拟

题目、示例与约束

有一块木板，长度为 n 个单位。一些蚂蚁在木板上移动，每只蚂蚁都以 每秒一个单位 的速度移动。其中，一部分蚂蚁向左移动，其他蚂蚁向右移动。

当两只向不同方向移动的蚂蚁在某个点相遇时，它们会同时改变移动方向并继续移动。假设更改方向不会花费任何额外时间。

而当蚂蚁在某一时刻 t 到达木板的一端时，它立即从木板上掉下来。

给你一个整数 n 和两个整数数组 left 以及 right 。两个数组分别标识向左或者向右移动的蚂蚁在 t = 0 时的位置。请你返回最后一只蚂蚁从木板上掉下来的时刻。

示例 1：

输入：n = 4, left = [4,3], right = [0,1]
输出：4
解释：如上图所示：
-下标 0 处的蚂蚁命名为 A 并向右移动。
-下标 1 处的蚂蚁命名为 B 并向右移动。
-下标 3 处的蚂蚁命名为 C 并向左移动。
-下标 4 处的蚂蚁命名为 D 并向左移动。
请注意，蚂蚁在木板上的最后时刻是 t = 4 秒，之后蚂蚁立即从木板上掉下来。（也就是说在 t = 4.0000000001 时，木板上没有蚂蚁）。

示例 2：

输入：n = 7, left = [], right = [0,1,2,3,4,5,6,7]
输出：7
解释：所有蚂蚁都向右移动，下标为 0 的蚂蚁需要 7 秒才能从木板上掉落。

示例 3：

输入：n = 7, left = [0,1,2,3,4,5,6,7], right = []
输出：7
解释：所有蚂蚁都向左移动，下标为 7 的蚂蚁需要 7 秒才能从木板上掉落。

提示：

1 <= n <= 10^4
0 <= left.length <= n + 1
0 <= left[i] <= n
0 <= right.length <= n + 1
0 <= right[i] <= n
1 <= left.length + right.length <= n + 1
left 和 right 中的所有值都是唯一的，并且每个值 只能出现在二者之一 中。

方法一：脑筋急转弯 · Go 实现

思考

若按秒模拟每只蚂蚁的位置，并在相遇时改向，时间可达到木板长度与蚂蚁数的乘积，在 $n \leq 10^{4}$ 时尚可，但实现烦琐且没有必要。

两蚁相遇后各自掉头，其后续轨迹与彼此穿过、继续沿原方向前进完全相同。因此碰撞可以忽略，答案就是向左蚂蚁走到 $0$ 、向右蚂蚁走到 $n$ 所需时间的最大值。

题目关键点在于两只蚂蚁相遇，然后分别调转方向的情况，实际上相当于两只蚂蚁继续往原来的方向移动。因此，我们只需要求出所有蚂蚁中最远的那只蚂蚁的移动距离即可。

注意 $left$ 和 $right$ 数组的长度可能为 $0$ 。

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

func getLastMoment(n int, left []int, right []int) (ans int) {
	for _, x := range left {
		ans = max(ans, x)
	}
	for _, x := range right {
		ans = max(ans, n-x)
	}
	return
}

力扣原题 · Doocs 题解来源

1534. 统计好三元组

简单1 种解法

标签：数组、枚举

题目、示例与约束

给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量。

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组 。

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值。

返回 好三元组的数量 。

示例 1：

输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)] 。

示例 2：

输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1
输出：0
解释：不存在满足所有条件的三元组。

提示：

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

方法一：枚举 · Go 实现

思考

统计满足三组绝对值约束的下标三元组。 $n \leq 100$ ，三重循环约 $10^{6}$ 次比较，足以通过。

按 $i < j < k$ 枚举即可直接套用三个不等式，不必预处理。约束彼此独立，没有值得再换数据结构的单调性。

枚举结束后，即可得到答案。

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

func countGoodTriplets(arr []int, a int, b int, c int) (ans int) {
	n := len(arr)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for k := j + 1; k < n; k++ {
				if abs(arr[i]-arr[j]) <= a && abs(arr[j]-arr[k]) <= b && abs(arr[i]-arr[k]) <= c {
					ans++
				}
			}
		}
	}
	return
}

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

力扣原题 · Doocs 题解来源

1535. 找出数组游戏的赢家

中等1 种解法

标签：数组、模拟

题目、示例与约束

给你一个由不同整数组成的整数数组 arr 和一个整数 k 。

每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的赢家。

返回赢得比赛的整数。

题目数据保证游戏存在赢家。

示例 1：

输入：arr = [2,1,3,5,4,6,7], k = 2
输出：5
解释：一起看一下本场游戏每回合的情况：

因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。

示例 2：

输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜。

示例 3：

输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9

示例 4：

输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
输出：99

提示：

2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr 所含的整数 各不相同 。
1 <= k <= 10^9

方法一：脑筋急转弯 · Go 实现

思考

每轮比较队首两个数，大者赢得一场并回到队首， $k$ 可达 $10^{9}$ ，不能真的模拟那么多轮。

无论谁赢，下一轮都是「当前胜者」对阵尚未出场的下一个元素。连续获胜 $k$ 场者即为答案；若扫完整列仍无人达到 $k$ ，胜者只能是全局最大值，因为它之后再不会输。

我们注意到，每次会比较数组的前两个元素，不管结果怎么样，下一次的比较，一定是轮到了数组中的下一个元素和当前的胜者进行比较。因此，如果循环了 $n - 1$ 次，那么最后的胜者一定是数组中的最大元素。否则，如果某个元素连续胜出了 $k$ 次，那么这个元素就是最后的胜者。

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

相似题目：

3175. 找到连续赢 K 场比赛的第一位玩家

func getWinner(arr []int, k int) int {
	mx, cnt := arr[0], 0
	for _, x := range arr[1:] {
		if mx < x {
			mx = x
			cnt = 1
		} else {
			cnt++
		}
		if cnt == k {
			break
		}
	}
	return mx
}

力扣原题 · Doocs 题解来源

1550. 存在连续三个奇数的数组

简单2 种解法

标签：数组

题目、示例与约束

给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。

示例 1：

输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。

示例 2：

输入：arr = [1,2,34,3,4,5,7,23,12]
输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。

提示：

1 <= arr.length <= 1000
1 <= arr[i] <= 1000

方法一：遍历 + 计数 · Go 实现

思考

判断是否存在连续三个奇数。 $n$ 不大，一次扫描即可，无需额外下标结构。

用计数器累加当前奇数游程：遇到奇数加一，到 $3$ 便成功；遇到偶数清零。这样只依赖相邻关系，额外空间为常数。

我们用一个变量 $cnt$ 记录当前连续奇数的个数。

接下来，我们遍历数组，如果当前元素是奇数，则 $cnt$ 加一，如果 $cnt$ 等于 3，则返回 $True$ 。如果当前元素是偶数，则 $cnt$ 置零。

遍历结束后，如果没有找到连续三个奇数，则返回 $False$ 。

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

func threeConsecutiveOdds(arr []int) bool {
	cnt := 0
	for _, x := range arr {
		if x&1 == 1 {
			cnt++
			if cnt == 3 {
				return true
			}
		} else {
			cnt = 0
		}
	}
	return false
}

方法二：遍历 + 位运算 · Go 实现

思考

方法一单独判断每个数的奇偶，实现清晰但分支稍多。三个数均为奇数，当且仅当它们按位与的最低位为 $1$ 。对每个三元组做一次与运算即可，省去显式计数。

根据位运算的性质，两个数进行按位与运算是奇数，当且仅当两个数都是奇数。如果有连续三个数按位与运算的结果是奇数，那么这三个数都是奇数。

因此，我们只需要遍历数组，判断是否存在连续三个数的按位与结果是否是奇数即可，如果存在则返回 $True$ ，否则返回 $False$ 。

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

func threeConsecutiveOdds(arr []int) bool {
	for i, n := 2, len(arr); i < n; i++ {
		if arr[i-2]&arr[i-1]&arr[i]&1 == 1 {
			return true
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

1560. 圆形赛道上经过次数最多的扇区

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。

请你以数组形式返回经过次数最多的那几个扇区，按扇区编号升序排列。

注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。

示例 1：

输入：n = 4, rounds = [1,3,1,2]
输出：[1,2]
解释：本场马拉松比赛从扇区 1 开始。经过各个扇区的次序如下所示：
1 --> 2 --> 3（阶段 1 结束）--> 4 --> 1（阶段 2 结束）--> 2（阶段 3 结束，即本场马拉松结束）
其中，扇区 1 和 2 都经过了两次，它们是经过次数最多的两个扇区。扇区 3 和 4 都只经过了一次。

示例 2：

输入：n = 2, rounds = [2,1,2,1,2,1,2,1,2]
输出：[2]

示例 3：

输入：n = 7, rounds = [1,3,5,7]
输出：[1,2,3,4,5,6,7]

提示：

2 <= n <= 100
1 <= m <= 100
rounds.length == m + 1
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] ，其中 0 <= i < m

方法一：考虑开始、结束的位置关系 · Go 实现

思考

圆环上按给定路段连续走过，求经过次数最多的扇区。完整圈对每个扇区贡献相同，真正拉开差距的只有第一起点到最后终点之间多走的那一段。

若起点编号不超过终点，多走的是闭区间 $[r o u n d s [0], r o u n d s [- 1]]$ ；否则这段跨过 $n$ ，等于 $[1, r o u n d s [- 1]]$ 与 $[r o u n d s [0], n]$ 的并。列出该并集即可，不必模拟每一圈。

由于每个阶段的结束位置是下一个阶段的开始位置，并且每个阶段都是逆时针方向的，所以我们可以根据开始和结束的位置关系来确定每个扇区的经过次数。

如果 $rounds [0] \leq rounds [m]$ ，那么从 $rounds [0]$ 开始，到 $rounds [m]$ 结束的所有扇区经过的次数是最多的，我们可以直接返回这个区间内的所有扇区。

否则，从 $1$ 开始，到 $rounds [m]$ 结束的所有扇区和从 $rounds [0]$ 开始，到 $n$ 结束的所有扇区的并集是经过次数最多的，我们可以返回这两个区间的并集。

时间复杂度 $O (n)$ ，其中 $n$ 是扇区的个数。忽略答案数组的空间消耗，空间复杂度 $O (1)$ 。

func mostVisited(n int, rounds []int) []int {
	m := len(rounds) - 1
	var ans []int
	if rounds[0] <= rounds[m] {
		for i := rounds[0]; i <= rounds[m]; i++ {
			ans = append(ans, i)
		}
	} else {
		for i := 1; i <= rounds[m]; i++ {
			ans = append(ans, i)
		}
		for i := rounds[0]; i <= n; i++ {
			ans = append(ans, i)
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1566. 重复至少 K 次且长度为 M 的模式

简单1 种解法

标签：数组、枚举

题目、示例与约束

给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。

模式是由一个或多个值组成的子数组（连续的子序列），连续重复多次但 不重叠 。模式由其长度和重复次数定义。

如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true ，否则返回 false 。

示例 1：

输入：arr = [1,2,4,4,4,4], m = 1, k = 3
输出：true
解释：模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。

示例 2：

输入：arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
输出：true
解释：模式 (1,2) 长度为 2 ，且连续重复 2 次。另一个符合题意的模式是 (2,1) ，同样重复 2 次。

示例 3：

输入：arr = [1,2,1,2,1,3], m = 2, k = 3
输出：false
解释：模式 (1,2) 长度为 2 ，但是只连续重复 2 次。不存在长度为 2 且至少重复 3 次的模式。

示例 4：

输入：arr = [1,2,3,1,2], m = 2, k = 2
输出：false
解释：模式 (1,2) 出现 2 次但并不连续，所以不能算作连续重复 2 次。

示例 5：

输入：arr = [2,2,2,2], m = 2, k = 3
输出：false
解释：长度为 2 的模式只有 (2,2) ，但是只连续重复 2 次。注意，不能计算重叠的重复次数。

提示：

2 <= arr.length <= 100
1 <= arr[i] <= 100
1 <= m <= 100
2 <= k <= 100

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

思考

判断是否存在长度为 $m$ 且至少重复 $k$ 次的模式。 $n$ 很小，枚举起点再核对也可以，但可用一次扫描。

模式重复 $k$ 次，等价于存在连续 $(k - 1) m$ 个位置满足 $a_{i} = a_{i - m}$ 。从下标 $m$ 起累计该相等关系，一旦达到目标长度即成功；不相等则清零。

首先，如果数组的长度小于 $m \times k$ ，那么肯定不存在长度为 $m$ 且至少重复 $k$ 次的模式，直接返回 $false$ 。

接下来，我们定义一个变量 $cnt$ 来记录当前连续重复的次数，如果数组存在连续的 $(k - 1) \times m$ 个元素 $a_{i}$ ，使得 $a_{i} = a_{i - m}$ ，那么我们就找到了一个长度为 $m$ 且至少重复 $k$ 次的模式，返回 $true$ 。否则，我们将 $cnt$ 置为 $0$ ，继续遍历数组。

最后，如果遍历完数组都没有找到符合条件的模式，返回 $false$ 。

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

func containsPattern(arr []int, m int, k int) bool {
	cnt, target := 0, (k-1)*m
	for i := m; i < len(arr); i++ {
		if arr[i] == arr[i-m] {
			cnt++
			if cnt == target {
				return true
			}
		} else {
			cnt = 0
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

1572. 矩阵对角线元素的和

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。

请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

示例 1：

输入：mat = [[1,2,3],
            [4,5,6],
            [7,8,9]]
输出：25
解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25
请注意，元素 mat[1][1] = 5 只会被计算一次。

示例 2：

输入：mat = [[1,1,1,1],
            [1,1,1,1],
            [1,1,1,1],
            [1,1,1,1]]
输出：8

示例 3：

输入：mat = [[5]]
输出：5

提示：

n == mat.length == mat[i].length
1 <= n <= 100
1 <= mat[i][j] <= 100

方法一：逐行遍历 · Go 实现

思考

求方阵主副对角线之和，中心在奇数阶时会被加两次。 $n$ 不大，按行各取两个对角元即可，注意中心只加一次。

第 $i$ 行主对角为 $r o w [i]$ ，副对角为 $r o w [n - i - 1]$ 。当 $j = i$ 时只累加一个；否则两个都加。一遍行扫描完成。

我们可以遍历矩阵的每一行 $row [i]$ ，对于每一行，我们可以计算出两个对角线上的元素，即 $row [i] [i]$ 和 $row [i] [n - i - 1]$ ，其中 $n$ 是矩阵的行数。如果 $i = n - i - 1$ ，则说明当前行的对角线上只有一个元素，否则有两个元素。我们将其加到答案中即可。遍历完所有行后，即可得到答案。

时间复杂度 $O (n)$ ，其中 $n$ 是矩阵的行数。空间复杂度 $O (1)$ 。

func diagonalSum(mat [][]int) (ans int) {
	n := len(mat)
	for i, row := range mat {
		ans += row[i]
		if j := n - i - 1; j != i {
			ans += row[j]
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1582. 二进制矩阵中的特殊位置

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给定一个 m x n 的二进制矩阵 mat，返回矩阵 mat 中特殊位置的数量。

如果位置 (i, j) 满足 mat[i][j] == 1 并且行 i 与列 j 中的所有其他元素都是 0（行和列的下标从 0 开始计数），那么它被称为特殊位置。

示例 1：

输入：mat = [[1,0,0],[0,0,1],[1,0,0]]
输出：1
解释：位置 (1, 2) 是一个特殊位置，因为 mat[1][2] == 1 且第 1 行和第 2 列的其他所有元素都是 0。

示例 2：

输入：mat = [[1,0,0],[0,1,0],[0,0,1]]
输出：3
解释：位置 (0, 0)，(1, 1) 和 (2, 2) 都是特殊位置。

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 100
mat[i][j] 是 0 或 1。

方法一：计数 · Go 实现

思考

统计值为 $1$ 且其所在行、列再无其它 $1$ 的位置。对每个 $1$ 再扫整行整列会达到 $O (m n (m + n))$ ，矩阵较大时偏慢。

先用两个数组记下每行、每列的 $1$ 的个数，再扫一遍：格子为 $1$ 且对应行列计数都为 $1$ 时计入答案。

我们可以用两个数组 $rows$ 和 $cols$ 分别记录每一行和每一列的 $1$ 的个数。

然后遍历矩阵，对于每一个 $1$ ，检查其所在的行和列是否只有一个 $1$ ，如果是则答案加一。

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

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

func numSpecial(mat [][]int) (ans int) {
	rows := make([]int, len(mat))
	cols := make([]int, len(mat[0]))
	for i, row := range mat {
		for j, x := range row {
			rows[i] += x
			cols[j] += x
		}
	}
	for i, row := range mat {
		for j, x := range row {
			if x == 1 && rows[i] == 1 && cols[j] == 1 {
				ans++
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1583. 统计不开心的朋友

中等1 种解法

标签：数组、模拟

题目、示例与约束

给你一份 n 位朋友的亲近程度列表，其中 n 总是偶数。

对每位朋友 i，preferences[i] 包含一份 按亲近程度从高到低排列 的朋友列表。换句话说，排在列表前面的朋友与 i 的亲近程度比排在列表后面的朋友更高。每个列表中的朋友均以 0 到 n-1 之间的整数表示。

所有的朋友被分成几对，配对情况以列表 pairs 给出，其中 pairs[i] = [x_i, y_i] 表示 x_i 与 y_i 配对，且 y_i 与 x_i 配对。

但是，这样的配对情况可能会使其中部分朋友感到不开心。在 x 与 y 配对且 u 与 v 配对的情况下，如果同时满足下述两个条件，x 就会不开心：

x 与 u 的亲近程度胜过 x 与 y，且
u 与 x 的亲近程度胜过 u 与 v

返回 不开心的朋友的数目 。

示例 1：

输入：n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
输出：2
解释：
朋友 1 不开心，因为：
- 1 与 0 配对，但 1 与 3 的亲近程度比 1 与 0 高，且
- 3 与 1 的亲近程度比 3 与 2 高。
朋友 3 不开心，因为：
- 3 与 2 配对，但 3 与 1 的亲近程度比 3 与 2 高，且
- 1 与 3 的亲近程度比 1 与 0 高。
朋友 0 和 2 都是开心的。

示例 2：

输入：n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
输出：0
解释：朋友 0 和 1 都开心。

示例 3：

输入：n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
输出：4

提示：

2 <= n <= 500
n 是偶数
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] 不包含 i
preferences[i] 中的所有值都是独一无二的
pairs.length == n/2
pairs[i].length == 2
x_i != y_i
0 <= x_i, y_i <= n - 1
每位朋友都恰好被包含在一对中

方法一：枚举 · Go 实现

思考

配对完成后，若 $x$ 更喜欢 $u$ ，且 $u$ 也更喜欢 $x$ 而非自己的搭档，则 $x$ 不开心。 $n \leq 500$ ，枚举每个 $x$ 及其更偏好的对象即可。

预处理亲近度字典与配对表。对每个 $x$ ，只检查排在搭档 $y$ 之前的 $u$ ：一旦某个 $u$ 把 $x$ 排在自己的搭档之前， $x$ 便不开心，可立即停止内层循环。

我们用数组 $d$ 记录每个朋友与其它朋友的亲近程度，其中 $d [i] [j]$ 表示朋友 $i$ 对 $j$ 的亲近程度（值越小，越亲近），另外，用数组 $p$ 记录每个朋友的配对朋友。

我们枚举每个朋友 $x$ ，对于 $x$ 的配对朋友 $y$ ，我们找到 $x$ 对 $y$ 的亲近程度 $d [x] [y]$ ，然后枚举比 $d [x] [y]$ 更亲近的其它朋友 $u$ ，如果存在 $u$ 对 $x$ 的亲近程度 $d [u] [x]$ 比 $d [u] [y]$ 更高，那么 $x$ 就是不开心的朋友，将结果加一即可。

枚举结束后，即可得到不开心的朋友的数目。

时间复杂度 $O (n^{2})$ ，空间复杂度 $O (n^{2})$ 。其中 $n$ 为朋友的数目。

func unhappyFriends(n int, preferences [][]int, pairs [][]int) (ans int) {
	d := make([][]int, n)
	for i := range d {
		d[i] = make([]int, n)
	}

	for i := 0; i < n; i++ {
		for j := 0; j < n-1; j++ {
			d[i][preferences[i][j]] = j
		}
	}

	p := make([]int, n)
	for _, e := range pairs {
		x, y := e[0], e[1]
		p[x] = y
		p[y] = x
	}

	for x := 0; x < n; x++ {
		y := p[x]
		for i := 0; i < d[x][y]; i++ {
			u := preferences[x][i]
			v := p[u]
			if d[u][x] < d[u][v] {
				ans++
				break
			}
		}
	}

	return
}

力扣原题 · Doocs 题解来源

1599. 经营摩天轮的最大利润

中等1 种解法

标签：数组、模拟

题目、示例与约束

你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。

给你一个长度为 n 的数组 customers ， customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i 次。如果有座舱空闲就不能让游客等待。每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。

你可以随时停下摩天轮，即便是 在服务所有游客之前 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。

返回最大化利润所需执行的 最小轮转次数 。如果不存在利润为正的方案，则返回 -1 。

示例 1：

输入：customers = [8,3], boardingCost = 5, runningCost = 6
输出：3
解释：座舱上标注的数字是该座舱的当前游客数。
1. 8 位游客抵达，4 位登舱，4 位等待下一舱，摩天轮轮转。当前利润为 4 * $5 - 1 * $6 = $14 。
2. 3 位游客抵达，4 位在等待的游客登舱，其他 3 位等待，摩天轮轮转。当前利润为 8 * $5 - 2 * $6 = $28 。
3. 最后 3 位游客登舱，摩天轮轮转。当前利润为 11 * $5 - 3 * $6 = $37 。
轮转 3 次得到最大利润，最大利润为 $37 。

示例 2：

输入：customers = [10,9,6], boardingCost = 6, runningCost = 4
输出：7
解释：
1. 10 位游客抵达，4 位登舱，6 位等待下一舱，摩天轮轮转。当前利润为 4 * $6 - 1 * $4 = $20 。
2. 9 位游客抵达，4 位登舱，11 位等待（2 位是先前就在等待的，9 位新加入等待的），摩天轮轮转。当前利润为 8 * $6 - 2 * $4 = $40 。
3. 最后 6 位游客抵达，4 位登舱，13 位等待，摩天轮轮转。当前利润为 12 * $6 - 3 * $4 = $60 。
4. 4 位登舱，9 位等待，摩天轮轮转。当前利润为 * $6 - 4 * $4 = $80 。
5. 4 位登舱，5 位等待，摩天轮轮转。当前利润为 20 * $6 - 5 * $4 = $100 。
6. 4 位登舱，1 位等待，摩天轮轮转。当前利润为 24 * $6 - 6 * $4 = $120 。
7. 1 位登舱，摩天轮轮转。当前利润为 25 * $6 - 7 * $4 = $122 。
轮转 7 次得到最大利润，最大利润为$122 。

示例 3：

输入：customers = [3,4,0,5,1], boardingCost = 1, runningCost = 92
输出：-1
解释：
1. 3 位游客抵达，3 位登舱，0 位等待，摩天轮轮转。当前利润为 3 * $1 - 1 * $92 = -$89 。
2. 4 位游客抵达，4 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 2 * $92 = -$177 。
3. 0 位游客抵达，0 位登舱，0 位等待，摩天轮轮转。当前利润为 7 * $1 - 3 * $92 = -$269 。
4. 5 位游客抵达，4 位登舱，1 位等待，摩天轮轮转。当前利润为 11 * $1 - 4 * $92 = -$357 。
5. 1 位游客抵达，2 位登舱，0 位等待，摩天轮轮转。当前利润为 13 * $1 - 5 * $92 = -$447 。
利润永不为正，所以返回 -1 。

提示：

n == customers.length
1 <= n <= 10⁵
0 <= customers[i] <= 50
1 <= boardingCost, runningCost <= 100

方法一：模拟 · Go 实现

思考

摩天轮每转一圈最多上 $4$ 人并扣除运转成本，求利润首次达到最大时的圈数。顾客分批到达，人数达 $10^{5}$ ，必须按圈模拟，不能跳过等待队列。

维护等待人数与累计利润：每圈并入新到达的人，上船 $min (4, w a i t)$ 人，利润加上票价减去运转费。若当前利润严格更大则更新最佳圈数；队列与后续批次都空时停止。利润始终非正则返回 $- 1$ 。

我们直接模拟摩天轮的轮转过程，每次轮转时，累加等待的游客以及新到达的游客，然后最多 $4$ 个人上船，更新等待的游客数和利润，记录最大利润与其对应的轮转次数。

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

func minOperationsMaxProfit(customers []int, boardingCost int, runningCost int) int {
	ans := -1
	t, mx := 0, 0
	wait, i := 0, 0
	for wait > 0 || i < len(customers) {
		if i < len(customers) {
			wait += customers[i]
		}
		up := min(4, wait)
		wait -= up
		t += up*boardingCost - runningCost
		i++
		if t > mx {
			mx = t
			ans = i
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1620. 网络信号最好的坐标

中等1 种解法

标签：数组、枚举

题目、示例与约束

给你一个数组 towers 和一个整数 radius 。

数组 towers 中包含一些网络信号塔，其中 towers[i] = [x_i, y_i, q_i] 表示第 i 个网络信号塔的坐标是 (x_i, y_i) 且信号强度参数为 q_i。所有坐标都是在 X-Y 坐标系内的整数坐标。两个坐标之间的距离用 欧几里得距离 计算。

整数 radius 表示一个塔 能到达 的 最远距离 。如果一个坐标跟塔的距离在 radius 以内，那么该塔的信号可以到达该坐标。在这个范围以外信号会很微弱，所以 radius 以外的距离该塔是 不能到达的 。

如果第 i 个塔能到达 (x, y) ，那么该塔在此处的信号为 ⌊q_i / (1 + d)⌋ ，其中 d 是塔跟此坐标的距离。一个坐标的 信号强度 是所有 能到达 该坐标的塔的信号强度之和。

请你返回数组 [c_x, c_y] ，表示 信号强度 最大的整数坐标点 (c_x, c_y) 。如果有多个坐标网络信号一样大，请你返回字典序最小的非负坐标。

注意：

坐标 (x1, y1) 字典序比另一个坐标 (x2, y2) 小，需满足以下条件之一：
- 要么 x1 < x2 ，
- 要么 x1 == x2 且 y1 < y2 。
⌊val⌋ 表示小于等于 val 的最大整数（向下取整函数）。

示例 1：

输入：towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
输出：[2,1]
解释：
坐标 (2, 1) 信号强度之和为 13
- 塔 (2, 1) 强度参数为 7 ，在该点强度为 ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- 塔 (1, 2) 强度参数为 5 ，在该点强度为 ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- 塔 (3, 1) 强度参数为 9 ，在该点强度为 ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
没有别的坐标有更大的信号强度。

示例 2：

输入：towers = [[23,11,21]], radius = 9
输出：[23,11]
解释：由于仅存在一座信号塔，所以塔的位置信号强度最大。

示例 3：

输入：towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
输出：[1,2]
解释：坐标 (1, 2) 的信号强度最大。

提示：

1 <= towers.length <= 50
towers[i].length == 3
0 <= x_i, y_i, q_i <= 50
1 <= radius <= 50

方法一：暴力枚举 · Go 实现

思考

塔数不超过 $50$ ，坐标与半径均在 $[0, 50]$ ，候选接收点只有 $51 \times 51$ 个，三重循环计算信号强度完全可行。

信号公式对距离超出半径的塔贡献为零，否则为 $⌊ q / (1 + d) ⌋$ 。

枚举每个整点累加各塔贡献，记录强度最大且字典序最小的坐标；初值 $(0, 0)$ 保证全零时的题定答案。

由于坐标点的范围是 $[0, . . 50]$ ，因此我们可以直接暴力枚举所有的坐标点 $(i, j)$ ，计算每个坐标点的信号强度，然后找出信号强度最大的坐标点。

时间复杂度 $O (n \times C^{2})$ ，其中 $n$ 是信号塔的数量，而 $C$ 是坐标点的范围大小。

func bestCoordinate(towers [][]int, radius int) []int {
	ans := []int{0, 0}
	mx := 0
	for i := 0; i < 51; i++ {
		for j := 0; j < 51; j++ {
			t := 0
			for _, e := range towers {
				d := math.Sqrt(float64((i-e[0])*(i-e[0]) + (j-e[1])*(j-e[1])))
				if d <= float64(radius) {
					t += int(float64(e[2]) / (1 + d))
				}
			}
			if mx < t {
				mx = t
				ans = []int{i, j}
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1646. 获取生成数组中的最大值

简单1 种解法

标签：数组、模拟

题目、示例与约束

给你一个整数 n 。按下述规则生成一个长度为 n + 1 的数组 nums ：

nums[0] = 0
nums[1] = 1
当 2 <= 2 * i <= n 时，nums[2 * i] = nums[i]
当 2 <= 2 * i + 1 <= n 时，nums[2 * i + 1] = nums[i] + nums[i + 1]

返回生成数组 nums 中的最大值。

示例 1：

输入：n = 7
输出：3
解释：根据规则：
  nums[0] = 0
  nums[1] = 1
  nums[(1 * 2) = 2] = nums[1] = 1
  nums[(1 * 2) + 1 = 3] = nums[1] + nums[2] = 1 + 1 = 2
  nums[(2 * 2) = 4] = nums[2] = 1
  nums[(2 * 2) + 1 = 5] = nums[2] + nums[3] = 1 + 2 = 3
  nums[(3 * 2) = 6] = nums[3] = 2
  nums[(3 * 2) + 1 = 7] = nums[3] + nums[4] = 2 + 1 = 3
因此，nums = [0,1,1,2,1,3,2,3]，最大值 3

示例 2：

输入：n = 2
输出：1
解释：根据规则，nums[0]、nums[1] 和 nums[2] 之中的最大值是 1

示例 3：

输入：n = 3
输出：2
解释：根据规则，nums[0]、nums[1]、nums[2] 和 nums[3] 之中的最大值是 2

提示：

0 <= n <= 100

方法一：模拟 · Go 实现

思考

数组由下标奇偶的递推定义， $n$ 不超过百级，按定义填表后取最大值即可。

$n < 2$ 时答案就是 $n$ ；否则令 $nums [0] = 0, nums [1] = 1$ ，偶数下标抄一半处，奇数下标取相邻两项之和。

我们先判断 $n$ 的值，如果 $n < 2$ ，则直接返回 $n$ 。

否则，我们创建一个长度为 $n + 1$ 的数组 $n u m s$ ，并初始化 $n u m s [0] = 0$ 以及 $n u m s [1] = 1$ 。

然后从下标 $2$ 开始遍历，如果当前下标 $i$ 为偶数，则 $n u m s [i] = n u m s [i / 2]$ ，否则 $n u m s [i] = n u m s [i / 2] + n u m s [i / 2 + 1]$ 。

最后返回数组 $n u m s$ 中的最大值即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为给定的整数。

func getMaximumGenerated(n int) int {
	if n < 2 {
		return n
	}
	nums := make([]int, n+1)
	nums[1] = 1
	for i := 2; i <= n; i++ {
		if i%2 == 0 {
			nums[i] = nums[i/2]
		} else {
			nums[i] = nums[i/2] + nums[i/2+1]
		}
	}
	return slices.Max(nums)
}

力扣原题 · Doocs 题解来源

1672. 最富有客户的资产总量

简单1 种解法

标签：数组、矩阵

题目、示例与约束

给你一个 m x n 的整数网格 accounts ，其中 accounts[i][j] 是第 i 位客户在第 j 家银行托管的资产数量。返回最富有客户所拥有的 资产总量 。

客户的 资产总量 就是他们在各家银行托管的资产数量之和。最富有客户就是 资产总量 最大的客户。

示例 1：

输入：accounts = [[1,2,3],[3,2,1]]
输出：6
解释：
第 1 位客户的资产总量 = 1 + 2 + 3 = 6
第 2 位客户的资产总量 = 3 + 2 + 1 = 6
两位客户都是最富有的，资产总量都是 6 ，所以返回 6 。

示例 2：

输入：accounts = [[1,5],[7,3],[3,5]]
输出：10
解释：
第 1 位客户的资产总量 = 6
第 2 位客户的资产总量 = 10 
第 3 位客户的资产总量 = 8
第 2 位客户是最富有的，资产总量是 10

示例 3：

输入：accounts = [[2,8,7],[7,1,3],[1,9,5]]
输出：17

提示：

m == accounts.length
n == accounts[i].length
1 <= m, n <= 50
1 <= accounts[i][j] <= 100

方法一：求和 · Go 实现

思考

财富是一行之和，矩阵不超过 $50 \times 50$ ，对每行求和再取最大。

我们遍历 accounts，求出每一行的和的最大值即可。

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

func maximumWealth(accounts [][]int) int {
	ans := 0
	for _, e := range accounts {
		s := 0
		for _, v := range e {
			s += v
		}
		if ans < s {
			ans = s
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1701. 平均等待时间

中等1 种解法

标签：数组、模拟

题目、示例与约束

有一个餐厅，只有一位厨师。你有一个顾客数组 customers ，其中 customers[i] = [arrival_i, time_i] ：

arrival_i 是第 i 位顾客到达的时间，到达时间按 非递减 顺序排列。
time_i 是给第 i 位顾客做菜需要的时间。

当一位顾客到达时，他将他的订单给厨师，厨师一旦空闲的时候就开始做这位顾客的菜。每位顾客会一直等待到厨师完成他的订单。厨师同时只能做一个人的订单。厨师会严格按照 订单给他的顺序 做菜。

请你返回所有顾客需要等待的平均时间。与标准答案误差在 10^-5 范围以内，都视为正确结果。

示例 1：

输入：customers = [[1,2],[2,5],[4,3]]
输出：5.00000
解释：
1) 第一位顾客在时刻 1 到达，厨师拿到他的订单并在时刻 1 立马开始做菜，并在时刻 3 完成，第一位顾客等待时间为 3 - 1 = 2 。
2) 第二位顾客在时刻 2 到达，厨师在时刻 3 开始为他做菜，并在时刻 8 完成，第二位顾客等待时间为 8 - 2 = 6 。
3) 第三位顾客在时刻 4 到达，厨师在时刻 8 开始为他做菜，并在时刻 11 完成，第三位顾客等待时间为 11 - 4 = 7 。
平均等待时间为 (2 + 6 + 7) / 3 = 5 。

示例 2：

输入：customers = [[5,2],[5,4],[10,3],[20,1]]
输出：3.25000
解释：
1) 第一位顾客在时刻 5 到达，厨师拿到他的订单并在时刻 5 立马开始做菜，并在时刻 7 完成，第一位顾客等待时间为 7 - 5 = 2 。
2) 第二位顾客在时刻 5 到达，厨师在时刻 7 开始为他做菜，并在时刻 11 完成，第二位顾客等待时间为 11 - 5 = 6 。
3) 第三位顾客在时刻 10 到达，厨师在时刻 11 开始为他做菜，并在时刻 14 完成，第三位顾客等待时间为 14 - 10 = 4 。
4) 第四位顾客在时刻 20 到达，厨师拿到他的订单并在时刻 20 立马开始做菜，并在时刻 21 完成，第四位顾客等待时间为 21 - 20 = 1 。
平均等待时间为 (2 + 6 + 4 + 1) / 4 = 3.25 。

提示：

1 <= customers.length <= 10⁵
1 <= arrival_i, time_i <= 10⁴
arrival_i<= arrival_i+1

方法一：模拟 · Go 实现

思考

每位顾客的等待时间由厨师何时空闲与到达时刻共同决定。顾客按到达时间给出，且厨师严格按订单顺序做菜，因此不必重排，按序模拟即可。

维护厨师完成上一单的时刻 $t$ 。下一位到达时刻为 $a$ 、做菜时间为 $b$ 时，开工时刻为 $max (t, a)$ ，完成时刻为 $max (t, a) + b$ ，等待为完成时刻减去 $a$ 。

累加全部等待再除以人数，得到平均等待时间。

我们用变量 tot 记录顾客的总等待时间，用变量 t 记录做完每个顾客的订单的时间，初始值均为 $0$ 。

遍历顾客数组 customers，对于每个顾客：

如果当前时间 t 小于等于顾客的到达时间 customers[i][0]，说明厨师没有在做菜，那么厨师可以立即开始做菜，做完这道菜的时间为 $t = c u s t o m e r s [i] [0] + c u s t o m e r s [i] [1]$ ，顾客的等待时间为 customers[i][1]。

否则，说明厨师正在做菜，那么顾客需要等待厨师做完此前的菜，才能开始做自己的菜，做完这道菜的时间为 $t = t + c u s t o m e r s [i] [1]$ ，顾客的等待时间为 $t - c u s t o m e r s [i] [0]$ 。

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

func averageWaitingTime(customers [][]int) float64 {
	tot, t := 0, 0
	for _, e := range customers {
		a, b := e[0], e[1]
		t = max(t, a) + b
		tot += t - a
	}
	return float64(tot) / float64(len(customers))
}

力扣原题 · Doocs 题解来源

1706. 球会落何处

中等1 种解法

标签：数组、矩阵、模拟

题目、示例与约束

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

示例 1：

输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

示例 2：

输入：grid = [[-1]]
输出：[-1]
解释：球被卡在箱子左侧边上。

示例 3：

输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 为 1 或 -1

方法一：分情况讨论 + DFS · Go 实现

思考

每列顶端放一球，挡板将球导向左或右。网格规模有限，可对每颗球独立模拟下落。

卡住的情形只有四类：贴边且挡板把球推出网格，或相邻两格形成 $V$ 形。除此以外，球沿挡板斜向进入下一行。

用 $dfs (i, j)$ 表示从 $(i, j)$ 出发的出口列：先判卡住返回 $- 1$ ，否则递归到 $(i + 1, j \pm 1)$ ；到达第 $m$ 行则返回当前列。

我们可以使用 DFS 来模拟球的运动过程，设计一个函数 $dfs (i, j)$ ，表示球从第 $i$ 行第 $j$ 列出发，最终会落在第几列。对于以下情况，球会卡住：

球位于最左一列，并且球所在的单元格单元格挡板将球导向左侧
球位于最右一列，并且此单元格挡板将球导向右侧
球所在的单元格挡板将球导向右侧，并且球右侧相邻单元格挡板将球导向左侧
球所在的单元格挡板将球导向左侧，并且球左侧相邻单元格挡板将球导向右侧

如果满足以上任意一种情况，我们就可以判断球会卡住，返回 $- 1$ 。否则，我们就可以继续递归地寻找球的下一个位置。最后，如果球到了最后一行，我们就可以返回当前列的编号。

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

func findBall(grid [][]int) (ans []int) {
	m, n := len(grid), len(grid[0])
	var dfs func(i, j int) int
	dfs = func(i, j int) int {
		if i == m {
			return j
		}
		if j == 0 && grid[i][j] == -1 {
			return -1
		}
		if j == n-1 && grid[i][j] == 1 {
			return -1
		}
		if grid[i][j] == 1 && grid[i][j+1] == -1 {
			return -1
		}
		if grid[i][j] == -1 && grid[i][j-1] == 1 {
			return -1
		}
		if grid[i][j] == 1 {
			return dfs(i+1, j+1)
		}
		return dfs(i+1, j-1)
	}
	for j := 0; j < n; j++ {
		ans = append(ans, dfs(0, j))
	}
	return
}

力扣原题 · Doocs 题解来源

LeetCode Go · 数组与矩阵（2） ​

1184. 公交站间的距离 ​

1222. 可以攻击国王的皇后 ​

1243. 数组变换 🔒 ​

1260. 二维网格迁移 ​

1272. 删除区间 🔒 ​

1287. 有序数组中出现次数超过25%的元素 ​

1299. 将每个元素替换为右侧最大元素 ​

1313. 解压缩编码列表 ​

1375. 二进制字符串前缀一致的次数 ​

1380. 矩阵中的幸运数 ​

1389. 按既定顺序创建目标数组 ​

1431. 拥有最多糖果的孩子 ​

1437. 是否所有 1 都至少相隔 k 个元素 ​

1450. 在既定时间做作业的学生人数 ​

1470. 重新排列数组 ​

1503. 所有蚂蚁掉下来前的最后一刻 ​

1534. 统计好三元组 ​

1535. 找出数组游戏的赢家 ​

1550. 存在连续三个奇数的数组 ​

1560. 圆形赛道上经过次数最多的扇区 ​

1566. 重复至少 K 次且长度为 M 的模式 ​

1572. 矩阵对角线元素的和 ​

1582. 二进制矩阵中的特殊位置 ​

1583. 统计不开心的朋友 ​

1599. 经营摩天轮的最大利润 ​

1620. 网络信号最好的坐标 ​

1646. 获取生成数组中的最大值 ​

1672. 最富有客户的资产总量 ​

1701. 平均等待时间 ​

1706. 球会落何处 ​

继续阅读

LeetCode Go · 数组与矩阵（2）

1184. 公交站间的距离

1222. 可以攻击国王的皇后

1243. 数组变换 🔒

1260. 二维网格迁移

1272. 删除区间 🔒

1287. 有序数组中出现次数超过25%的元素

1299. 将每个元素替换为右侧最大元素

1313. 解压缩编码列表

1375. 二进制字符串前缀一致的次数

1380. 矩阵中的幸运数

1389. 按既定顺序创建目标数组

1431. 拥有最多糖果的孩子

1437. 是否所有 1 都至少相隔 k 个元素

1450. 在既定时间做作业的学生人数

1470. 重新排列数组

1503. 所有蚂蚁掉下来前的最后一刻

1534. 统计好三元组

1535. 找出数组游戏的赢家

1550. 存在连续三个奇数的数组

1560. 圆形赛道上经过次数最多的扇区

1566. 重复至少 K 次且长度为 M 的模式

1572. 矩阵对角线元素的和

1582. 二进制矩阵中的特殊位置

1583. 统计不开心的朋友

1599. 经营摩天轮的最大利润

1620. 网络信号最好的坐标

1646. 获取生成数组中的最大值

1672. 最富有客户的资产总量

1701. 平均等待时间

1706. 球会落何处