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 题 · 点击题目展开，先独立思考，再查看解法。

557. 反转字符串中的单词 III

简单1 种解法

标签：双指针、字符串

题目、示例与约束

给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

 

示例 1：

输入：s = "Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"

示例 2:

输入： s = "Mr Ding"
输出："rM gniD"

 

提示：

• 1 <= s.length <= 5 * 104
• s 包含可打印的 ASCII 字符。
• s 不包含任何开头或结尾空格。
• s 里 至少 有一个词。
• s 中的所有单词都用一个空格隔开。

方法一：模拟 · Go 实现

思考

要反转每个单词，单词之间的空格保留。按空格切开、逐词反转再拼回即可。

split 得到单词数组，每个单词 [::-1] 后用空格连接。不必自己维护双指针，除非题目禁止库函数。

我们可以将字符串 $\mathit{\text{s}}$ 按照空格分割成单词数组 $\mathit{\text{words}}$，然后将每个单词反转后再拼接成字符串。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串 $\mathit{\text{s}}$ 的长度。

func reverseWords(s string) string {
	words := strings.Fields(s)
	for i, w := range words {
		t := []byte(w)
		slices.Reverse(t)
		words[i] = string(t)
	}
	return strings.Join(words, " ")
}

力扣原题 · Doocs 题解来源

696. 计数二进制子串

简单1 种解法

标签：双指针、字符串

题目、示例与约束

给定一个字符串 s，统计并返回具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是成组连续的。

重复出现（不同位置）的子串也要统计它们出现的次数。

 

示例 1：

输入：s = "00110011"
输出：6
解释：6 个子串满足具有相同数量的连续 1 和 0 ："0011"、"01"、"1100"、"10"、"0011" 和 "01" 。
注意，一些重复出现的子串（不同位置）要统计它们出现的次数。
另外，"00110011" 不是有效的子串，因为所有的 0（还有 1 ）没有组合在一起。

示例 2：

输入：s = "10101"
输出：4
解释：有 4 个子串："10"、"01"、"10"、"01" ，具有相同数量的连续 1 和 0 。

 

提示：

• 1 <= s.length <= 105
• s[i] 为 '0' 或 '1'

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

思考

统计由连续相同 $0$ 与连续相同 $1$ 组成、且两段长度相等的子串。枚举所有子串是平方级。

按连续段切分，相邻两段能贡献 $min(\mathit{\text{pre}},\mathit{\text{cur}})$ 个合法子串。扫完所有段即可。

我们可以遍历字符串 $s$，用一个变量 $\mathit{\text{pre}}$ 记录上一个连续字符的数量，另一个变量 $\mathit{\text{cur}}$ 记录当前连续字符的数量。那么以当前字符结尾的满足条件的子串数量为 $min(\mathit{\text{pre}},\mathit{\text{cur}})$。我们将 $min(\mathit{\text{pre}},\mathit{\text{cur}})$ 累加到答案中，并将 $\mathit{\text{cur}}$ 的值赋给 $\mathit{\text{pre}}$，继续遍历字符串 $s$ 直到结束。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。

func countBinarySubstrings(s string) (ans int) {
	n := len(s)
	i := 0
	pre := 0
	for i < n {
		j := i + 1
		for j < n && s[j] == s[i] {
			j++
		}
		cur := j - i
		ans += min(pre, cur)
		pre = cur
		i = j
	}
	return
}

力扣原题 · Doocs 题解来源

723. 粉碎糖果 🔒

中等1 种解法

标签：数组、双指针、矩阵、模拟

题目、示例与约束

这个问题是实现一个简单的消除算法。

给定一个 m x n 的二维整数数组 board 代表糖果所在的方格，不同的正整数 board[i][j] 代表不同种类的糖果，如果 board[i][j] == 0 代表 (i, j) 这个位置是空的。

给定的方格是玩家移动后的游戏状态，现在需要你根据以下规则粉碎糖果，使得整个方格处于稳定状态并最终输出：

• 如果有三个及以上水平或者垂直相连的同种糖果，同一时间将它们粉碎，即将这些位置变成空的。
• 在同时粉碎掉这些糖果之后，如果有一个空的位置上方还有糖果，那么上方的糖果就会下落直到碰到下方的糖果或者底部，这些糖果都是同时下落，也不会有新的糖果从顶部出现并落下来。
• 通过前两步的操作，可能又会出现可以粉碎的糖果，请继续重复前面的操作。
• 当不存在可以粉碎的糖果，也就是状态稳定之后，请输出最终的状态。

你需要模拟上述规则并使整个方格达到稳定状态，并输出。

 

示例 1 :

输入: board = [[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]
输出: [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]

示例 2:

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

 

提示:

• m == board.length
• n == board[i].length
• 3 <= m, n <= 50
• 1 <= board[i][j] <= 2000

 

方法一：模拟 · Go 实现

思考

要反复消除横竖连续三个及以上的相同糖果并下落，直到稳定。棋盘不大，直接按规则模拟是可行的。

若边消边落，后一次消除可能破坏前一次尚未结算的连通，题目要求同一时刻所有稳定的三连一起消去。因此先整盘标记，再统一下落。

用负数标记待消格（比较时取绝对值），一行一列扫长度为 $3$ 的窗口；若本轮有标记，则每列自底向上把正数落下、上空填零，并继续下一轮。

我们可以逐行和逐列遍历矩阵，找到连续三个相同的元素，将它们标记为负数。如果成功标记，我们需要将矩阵中的元素下移，直到没有元素可以下移为止。

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

func candyCrush(board [][]int) [][]int {
	m := len(board)
	n := len(board[0])
	run := true

	for run {
		run = false
		for i := 0; i < m; i++ {
			for j := 2; j < n; j++ {
				if board[i][j] != 0 && abs(board[i][j]) == abs(board[i][j-1]) && abs(board[i][j]) == abs(board[i][j-2]) {
					run = true
					val := abs(board[i][j])
					board[i][j] = -val
					board[i][j-1] = -val
					board[i][j-2] = -val
				}
			}
		}
		for j := 0; j < n; j++ {
			for i := 2; i < m; i++ {
				if board[i][j] != 0 && abs(board[i][j]) == abs(board[i-1][j]) && abs(board[i][j]) == abs(board[i-2][j]) {
					run = true
					val := abs(board[i][j])
					board[i][j] = -val
					board[i-1][j] = -val
					board[i-2][j] = -val
				}
			}
		}
		if run {
			for j := 0; j < n; j++ {
				k := m - 1
				for i := m - 1; i >= 0; i-- {
					if board[i][j] > 0 {
						board[k][j] = board[i][j]
						k--
					}
				}
				for k >= 0 {
					board[k][j] = 0
					k--
				}
			}
		}
	}

	return board
}

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

力扣原题 · Doocs 题解来源

777. 在 LR 字符串中交换相邻字符

中等1 种解法

标签：双指针、字符串

题目、示例与约束

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL"，或者用一个 "XR" 替换一个 "RX"。现给定起始字符串 start 和结束字符串 result，请编写代码，当且仅当存在一系列移动操作使得 start 可以转换成 result 时， 返回 True。

 

示例 1：

输入：start = "RXXLRXRXL", result = "XRLXXRRLX"
输出：true
解释：通过以下步骤我们可以将 start 转化为 result：
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

示例 2：

输入：start = "X", result = "L"
输出：false

 

提示：

• 1 <= start.length <= 104
• start.length == result.length
• start 和 result 都只包含 'L', 'R' 或 'X'。

方法一：双指针 · Go 实现

思考

XL→LX、RX→XR 相当于 L 左移、R 右移，且二者不能穿过对方。 $n\le {10}^4$，去掉 X 后字母序列必须相同。

对齐非 X 字符后，每个 L 在 $\mathit{\text{start}}$ 中的下标不能小于目标（不能右移），每个 R 不能大于目标（不能左移）。

双指针跳过 X 后逐对检验。

替换操作实际上是将 L 往左移动（L 左边为 X 时才能移动），R 往右移动（R 右边是 X 时才能移动），但 L 无法穿过 R。所以，如果去掉 start 和 end 中的所有 X，剩下的字符应该是相同的，否则返回 false。

双指针遍历 start 和 end：

• 如果当前字符为 L 且 $i<j$，那么这个 L 无法向右移动，返回 false；
• 如果当前字符为 R 且 $i>j$，那么这个 R 无法向左移动，返回 false。

如果双指针均遍历到末尾，返回 true。

时间复杂度 $O(n)$，其中 $n$ 表示字符串 start 或 end 的长度。

相似题目：

• 2337. 移动片段得到字符串

func canTransform(start string, end string) bool {
	n := len(start)
	i, j := 0, 0
	for {
		for i < n && start[i] == 'X' {
			i++
		}
		for j < n && end[j] == 'X' {
			j++
		}
		if i == n && j == n {
			return true
		}
		if i == n || j == n || start[i] != end[j] {
			return false
		}
		if start[i] == 'L' && i < j {
			return false
		}
		if start[i] == 'R' && i > j {
			return false
		}
		i, j = i+1, j+1
	}
}

力扣原题 · Doocs 题解来源

795. 区间子数组个数

中等2 种解法

标签：数组、双指针

题目、示例与约束

给你一个整数数组 nums 和两个整数：left 及 right 。找出 nums 中连续、非空且其中最大元素在范围 [left, right] 内的子数组，并返回满足条件的子数组的个数。

生成的测试用例保证结果符合 32-bit 整数范围。

 

示例 1：

输入：nums = [2,1,4,3], left = 2, right = 3
输出：3
解释：满足条件的三个子数组：[2], [2, 1], [3]

示例 2：

输入：nums = [2,9,2,5,6], left = 2, right = 8
输出：7

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= left <= right <= 109

方法一：区间计数 · Go 实现

思考

统计最大值落在 $[left,right]$ 的子数组。 $n\le {10}^5$，枚举两端再求最大过慢。最大值 $\le R$ 的子数组减去最大值 $\le L-1$ 的，即所求。

$f(x)$ 扫一遍：当前值 $\le x$ 则延长合法后缀，个数加其长度，否则清零。

题目要我们统计数组 nums 中，最大值在区间 $[left,right]$ 范围内的子数组个数。

对于区间 $[left,..right]$ 问题，我们可以考虑将其转换为 $[0,..right]$ 然后再减去 $[0,..left-1]$ 的问题。也就是说，所有最大元素不超过 $right$ 的子数组个数，减去所有最大元素不超过 $left-1$ 的子数组个数，剩下的就是最大元素在区间 $[left,..right]$ 范围内的子数组个数，即题目要求的结果。

$$ans=\sum _{i=0}^{right}an{s}_i-\sum _{i=0}^{left-1}an{s}_i$$

对于本题，我们设计一个函数 $f(x)$，表示数组 nums 中，最大值不超过 $x$ 的子数组个数。那么答案为 $f(right)-f(left-1)$。函数 $f(x)$ 的执行逻辑如下：

• 用变量 $cnt$ 记录最大值不超过 $x$ 的子数组的个数，用 $t$ 记录当前子数组的长度。
• 遍历数组 nums，对于每个元素 $nums[i]$，如果 $nums[i]\le x$，则当前子数组的长度加一，即 $t=t+1$，否则当前子数组的长度重置为 0，即 $t=0$。然后将当前子数组的长度加到 $cnt$ 中，即 $cnt=cnt+t$。
• 遍历结束，将 $cnt$ 返回即可。

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

func numSubarrayBoundedMax(nums []int, left int, right int) int {
	f := func(x int) (cnt int) {
		t := 0
		for _, v := range nums {
			t++
			if v > x {
				t = 0
			}
			cnt += t
		}
		return
	}
	return f(right) - f(left-1)
}

方法二：单调栈 + 枚举元素计算贡献 · Go 实现

思考

差分把「落在区间」拆开。也可枚举谁当最大值：用单调栈找左严格更大、右非严格更大，贡献 $(i-l)(r-i)$，仅当该值在 $[left,right]$ 内计入。

左右边界不对等是为了每个子数组只算一个最大元（相同时取最左）。

我们还可以枚举数组中每个元素 $nums[i]$ 作为子数组的最大值，然后统计以该元素为最大值的子数组的个数。问题转化为求出每个元素 $nums[i]$ 左侧第一个大于该元素的下标 $l[i]$，右侧第一个大于等于该元素的下标 $r[i]$，则以该元素为最大值的子数组的个数为 $(i-l[i])\times (r[i]-i)$。

我们可以使用单调栈方便地求出 $l[i]$ 和 $r[i]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

相似题目：

• 907. 子数组的最小值之和

func numSubarrayBoundedMax(nums []int, left int, right int) (ans int) {
	n := len(nums)
	l := make([]int, n)
	r := make([]int, n)
	for i := range l {
		l[i], r[i] = -1, n
	}
	stk := []int{}
	for i, v := range nums {
		for len(stk) > 0 && nums[stk[len(stk)-1]] <= v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			l[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	stk = []int{}
	for i := n - 1; i >= 0; i-- {
		v := nums[i]
		for len(stk) > 0 && nums[stk[len(stk)-1]] < v {
			stk = stk[:len(stk)-1]
		}
		if len(stk) > 0 {
			r[i] = stk[len(stk)-1]
		}
		stk = append(stk, i)
	}
	for i, v := range nums {
		if left <= v && v <= right {
			ans += (i - l[i]) * (r[i] - i)
		}
	}
	return
}

力扣原题 · Doocs 题解来源

809. 情感丰富的文字

中等1 种解法

标签：数组、双指针、字符串

题目、示例与约束

有时候人们会用重复写一些字母来表示额外的感受，比如 "hello" -> "heeellooo", "hi" -> "hiii"。我们将相邻字母都相同的一串字符定义为相同字母组，例如："h", "eee", "ll", "ooo"。

对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母 c ），然后往其中添加相同的字母 c 使其长度达到 3 或以上。

例如，以 "hello" 为例，我们可以对字母组 "o" 扩张得到 "hellooo"，但是无法以同样的方法得到 "helloo" 因为字母组 "oo" 长度小于 3。此外，我们可以进行另一种扩张 "ll" -> "lllll" 以获得 "helllllooo"。如果 s = "helllllooo"，那么查询词 "hello" 是可扩张的，因为可以对它执行这两种扩张操作使得 query = "hello" -> "hellooo" -> "helllllooo" = s。

输入一组查询单词，输出其中可扩张的单词数量。

 

示例：

输入： 
s = "heeellooo"
words = ["hello", "hi", "helo"]
输出：1
解释：
我们能通过扩张 "hello" 的 "e" 和 "o" 来得到 "heeellooo"。
我们不能通过扩张 "helo" 来得到 "heeellooo" 因为 "ll" 的长度小于 3 。

 

提示：

• 1 <= s.length, words.length <= 100
• 1 <= words[i].length <= 100
• s 和所有在 words 中的单词都只由小写字母组成。

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

思考

伸展要求查询串的连续段只能拉长、且拉长后该段长度至少为 $3$，不能改字母或缩短。 $s$ 与单词都很短，对每个单词做一次双指针对齐即可。

同步扫描两串的连续段，字母必须相同；若原段更长，或目标段短于 $3$ 却与原段长度不等，则不能伸展。两串同时扫完才算匹配。

我们可以遍历数组 $\mathit{\text{words}}$，对于数组中的每个单词 $t$，判断 $t$ 是否可以通过扩张得到 $s$，如果可以，那么答案加一。

因此，问题的关键在于判断单词 $t$ 是否可以通过扩张得到 $s$。这里我们通过一个 $\mathit{\text{check}}(s,t)$ 函数来判断。函数的具体实现逻辑如下：

首先判断 $s$ 和 $t$ 的长度关系，如果 $t$ 的长度大于 $s$，直接返回 $\mathit{\text{false}}$；否则，我们用双指针 $i$ 和 $j$ 分别指向 $s$ 和 $t$，初始时 $i$ 和 $j$ 的值均为 $0$。

如果 $i$ 和 $j$ 指向的字符不同，那么 $t$ 无法通过扩张得到 $s$，直接返回 $\mathit{\text{false}}$；否则，我们需要判断 $i$ 指向的字符的连续出现次数 $c_1$ 和 $j$ 指向的字符的连续出现次数 $c_2$ 的关系。如果 $c_1<c_2$ 或者 $c_1<3$ 并且 $c_1\ne c_2$，那么 $t$ 无法通过扩张得到 $s$，直接返回 $\mathit{\text{false}}$；否则，将 $i$ 和 $j$ 分别右移 $c_1$ 和 $c_2$ 次。继续判断。

如果 $i$ 和 $j$ 都到达了字符串的末尾，那么 $t$ 可以通过扩张得到 $s$，返回 $\mathit{\text{true}}$，否则返回 $\mathit{\text{false}}$。

时间复杂度 $O(n\times m+\sum _{i=0}^{m-1}{w}_i)$，其中 $n$ 和 $m$ 分别为字符串 $s$ 和数组 $\mathit{\text{words}}$ 的长度，而 $w_i$ 为数组 $\mathit{\text{words}}$ 中第 $i$ 个单词的长度。

func expressiveWords(s string, words []string) (ans int) {
	check := func(s, t string) bool {
		m, n := len(s), len(t)
		if n > m {
			return false
		}
		i, j := 0, 0
		for i < m && j < n {
			if s[i] != t[j] {
				return false
			}
			k := i
			for k < m && s[k] == s[i] {
				k++
			}
			c1 := k - i
			i, k = k, j
			for k < n && t[k] == t[j] {
				k++
			}
			c2 := k - j
			j = k
			if c1 < c2 || (c1 != c2 && c1 < 3) {
				return false
			}
		}
		return i == m && j == n
	}
	for _, t := range words {
		if check(s, t) {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

821. 字符的最短距离

简单1 种解法

标签：数组、双指针、字符串

题目、示例与约束

给你一个字符串 s 和一个字符 c ，且 c 是 s 中出现过的字符。

返回一个整数数组 answer ，其中 answer.length == s.length 且 answer[i] 是 s 中从下标 i 到离它 最近 的字符 c 的 距离 。

两个下标 i 和 j 之间的 距离 为 abs(i - j) ，其中 abs 是绝对值函数。

 

示例 1：

输入：s = "loveleetcode", c = "e"
输出：[3,2,1,0,1,0,0,1,2,2,1,0]
解释：字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。
距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。
距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。
对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。
距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。

示例 2：

输入：s = "aaab", c = "b"
输出：[3,2,1,0]

 

提示：

• 1 <= s.length <= 104
• s[i] 和 c 均为小写英文字母
• 题目数据保证 c 在 s 中至少出现一次

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

思考

对每个位置求到最近字符 $c$ 的距离。若对每个下标向两侧扫描， $n\le {10}^4$ 时平方级偏慢。注意到最近的 $c$ 只可能来自左侧或右侧。

从左向右记录最近的 $c$ 下标，再从右向左扫一遍取更近者。两遍线性扫描即可填满答案数组。

我们先创建一个长度为 $n$ 的答案数组 $ans$。

接下来，我们从左到右遍历字符串 $s$，记录最近出现的字符 $c$ 的位置 $pre$，那么对于位置 $i$，答案就是 $i-pre$，即 $ans[i]=i-pre$。

然后，我们从右到左遍历字符串 $s$，记录最近出现的字符 $c$ 的位置 $suf$，那么对于位置 $i$，答案就是 $suf-i$，即 $ans[i]=min(ans[i],suf-i)$。

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

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func shortestToChar(s string, c byte) []int {
	n := len(s)
	ans := make([]int, n)
	const inf int = 1 << 30
	pre := -inf
	for i := range s {
		if s[i] == c {
			pre = i
		}
		ans[i] = i - pre
	}
	suf := inf
	for i := n - 1; i >= 0; i-- {
		if s[i] == c {
			suf = i
		}
		ans[i] = min(ans[i], suf-i)
	}
	return ans
}

力扣原题 · Doocs 题解来源

832. 翻转图像

简单1 种解法

标签：位运算、数组、双指针、矩阵、模拟

题目、示例与约束

给定一个 n x n 的二进制矩阵 image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。

• 例如，水平翻转 [1,1,0] 的结果是 [0,1,1]。

反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。

• 例如，反转 [0,1,1] 的结果是 [1,0,0]。

 

示例 1：

输入：image = [[1,1,0],[1,0,1],[0,0,0]]
输出：[[1,0,0],[0,1,0],[1,1,1]]
解释：首先翻转每一行: [[0,1,1],[1,0,1],[0,0,0]]；
     然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]

示例 2：

输入：image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出：[[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释：首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
     然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

 

提示：

• n == image.length
• n == image[i].length
• 1 <= n <= 20
• images[i][j] == 0 或 1.

方法一：双指针 · Go 实现

思考

每行先水平翻转再取反。 $n\le 20$，可在原数组上用首尾双指针同时完成两步。

若两端相等，翻转后仍相等，取反使它们同时变号；若两端不等，翻转加取反恰好互换，无需改值。中间单独一格只取反。

我们可以遍历矩阵，对于遍历到的每一行 $\mathit{\text{row}}$，我们使用双指针 $i$ 和 $j$ 分别指向该行的首尾元素，如果 $\mathit{\text{row}}[i]=\mathit{\text{row}}[j]$，交换后两者的值仍然保持不变，因此，我们只需要对 $\mathit{\text{row}}[i]$ 和 $\mathit{\text{row}}[j]$ 进行异或反转即可，然后将 $i$ 和 $j$ 分别向中间移动一位，直到 $i\ge j$。如果 $\mathit{\text{row}}[i]\ne \mathit{\text{row}}[j]$，此时交换后再反转两者的值，仍然保持不变，因此，可以不进行任何操作。

最后，如果 $i=j$，我们直接对 $\mathit{\text{row}}[i]$ 进行反转即可。

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

func flipAndInvertImage(image [][]int) [][]int {
	for _, row := range image {
		i, j := 0, len(row)-1
		for ; i < j; i, j = i+1, j-1 {
			if row[i] == row[j] {
				row[i] ^= 1
				row[j] ^= 1
			}
		}
		if i == j {
			row[i] ^= 1
		}
	}
	return image
}

力扣原题 · Doocs 题解来源

844. 比较含退格的字符串

简单1 种解法

标签：栈、双指针、字符串、模拟

题目、示例与约束

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

 

示例 1：

输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

示例 2：

输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 ""。

示例 3：

输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 "c"，但 t 仍然是 "b"。

 

提示：

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 '#'

 

进阶：

• 你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

方法一：双指针 · Go 实现

思考

退格后两串是否相等。若先构造退格后的新串，额外线性空间即可；题目更希望在原串上比较。

从右向左扫，用计数器消化 # 及其左侧应删字符，再比较当前有效字符。一侧先结束而另一侧仍有字符则不等。

我们用双指针 $i$ 和 $j$ 分别指向字符串 $s$ 和 $t$ 的末尾。

每次向前移动一个字符，如果当前字符是退格符，则跳过当前字符，同时退格符的数量加一，如果当前字符不是退格符，则判断退格符的数量，如果退格符的数量大于 $0$，则跳过当前字符，同时退格符的数量减一，如果退格符的数量等于 $0$，那么该字符需要进行比较。

我们每次找到两个字符串中需要比较的字符，然后进行比较，如果两个字符不相等，则返回 $false$，如果遍历完两个字符串，都没有发现不相等的字符，则返回 $true$。

时间复杂度 $O(m+n)$，空间复杂度 $O(1)$。其中 $m$ 和 $n$ 分别是字符串 $s$ 和 $t$ 的长度。

func backspaceCompare(s string, t string) bool {
	i, j := len(s)-1, len(t)-1
	skip1, skip2 := 0, 0
	for ; i >= 0 || j >= 0; i, j = i-1, j-1 {
		for i >= 0 {
			if s[i] == '#' {
				skip1++
				i--
			} else if skip1 > 0 {
				skip1--
				i--
			} else {
				break
			}
		}
		for j >= 0 {
			if t[j] == '#' {
				skip2++
				j--
			} else if skip2 > 0 {
				skip2--
				j--
			} else {
				break
			}
		}
		if i >= 0 && j >= 0 {
			if s[i] != t[j] {
				return false
			}
		} else if i >= 0 || j >= 0 {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

905. 按奇偶排序数组

简单1 种解法

标签：数组、双指针、排序

题目、示例与约束

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

 

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例 2：

输入：nums = [0]
输出：[0]

 

提示：

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

方法一：双指针 · Go 实现

思考

要求偶数在前、奇数在后，相对顺序无要求。另开数组按奇偶分发即可，但可以原地完成。左右指针相向：左遇偶数、右遇奇数则各自收缩；否则交换。每个位置至多被访问常数次。

我们用两个指针 $i$ 和 $j$ 分别指向数组的首尾，当 $i<j$ 时，执行以下操作。

• 如果 $nums[i]$ 为偶数，则 $i$ 自增 $1$。
• 如果 $nums[j]$ 为奇数，则 $j$ 自减 $1$。
• 如果 $nums[i]$ 为奇数，且 $nums[j]$ 为偶数，则交换 $nums[i]$ 和 $nums[j]$。然后 $i$ 自增 $1$，而 $j$ 自减 $1$。

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

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

func sortArrayByParity(nums []int) []int {
	for i, j := 0, len(nums)-1; i < j; {
		if nums[i]%2 == 0 {
			i++
		} else if nums[j]%2 == 1 {
			j--
		} else {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	return nums
}

力扣原题 · Doocs 题解来源

917. 仅仅反转字母

简单1 种解法

标签：双指针、字符串

题目、示例与约束

给你一个字符串 s ，根据下述规则反转字符串：

• 所有非英文字母保留在原有位置。
• 所有英文字母（小写或大写）位置反转。

返回反转后的 s 。

 

示例 1：

输入：s = "ab-cd"
输出："dc-ba"

示例 2：

输入：s = "a-bC-dEf-ghIj"
输出："j-Ih-gfE-dCba"

示例 3：

输入：s = "Test1ng-Leet=code-Q!"
输出："Qedo1ct-eeLg=ntse-T!"

 

提示

• 1 <= s.length <= 100
• s 仅由 ASCII 值在范围 [33, 122] 的字符组成
• s 不含 '\"' 或 '\\'

方法一：双指针 · Go 实现

思考

只反转字母，其他字符留在原位。另开数组收集字母再倒填可行，双指针可一次完成。首尾相向跳过非字母后交换，字符串不可变故先转为数组。

我们用两个指针 $i$ 和 $j$ 分别指向字符串的头部和尾部。当 $i<j$ 时，我们不断地移动 $i$ 和 $j$，直到 $i$ 指向一个英文字母，并且 $j$ 指向一个英文字母，然后交换 $s[i]$ 和 $s[j]$。最后返回字符串即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串的长度。

func reverseOnlyLetters(s string) string {
	cs := []rune(s)
	i, j := 0, len(s)-1
	for i < j {
		for i < j && !unicode.IsLetter(cs[i]) {
			i++
		}
		for i < j && !unicode.IsLetter(cs[j]) {
			j--
		}
		if i < j {
			cs[i], cs[j] = cs[j], cs[i]
			i++
			j--
		}
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

922. 按奇偶排序数组 II

简单1 种解法

标签：数组、双指针、排序

题目、示例与约束

给定一个非负整数数组 nums，  nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

 

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。

示例 2：

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

 

提示：

• 2 <= nums.length <= 2 * 104
• nums.length 是偶数
• nums 中一半是偶数
• 0 <= nums[i] <= 1000

 

进阶：可以不使用额外空间解决问题吗？

方法一：双指针 · Go 实现

思考

偶数下标放偶数、奇数下标放奇数，且两种数各占一半。另开数组按奇偶分发即可，但可原地完成。 $i$ 只扫偶数下标，若该位为奇，则 $j$ 在奇数下标找一个偶数交换； $j$ 只增不减，线性完成。

我们用两个指针 $i$ 和 $j$ 分别指向偶数下标和奇数下标，初始时 $i=0$, $j=1$。

当 $i$ 指向偶数下标时，如果 $\mathit{\text{nums}}[i]$ 是奇数，那么我们需要找到一个奇数下标 $j$，使得 $\mathit{\text{nums}}[j]$ 是偶数，然后交换 $\mathit{\text{nums}}[i]$ 和 $\mathit{\text{nums}}[j]$。继续遍历，直到 $i$ 指向数组末尾。

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

func sortArrayByParityII(nums []int) []int {
	for i, j := 0, 1; i < len(nums); i += 2 {
		if nums[i]%2 == 1 {
			for nums[j]%2 == 1 {
				j += 2
			}
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	return nums
}

力扣原题 · Doocs 题解来源

923. 三数之和的多种可能

中等1 种解法

标签：数组、哈希表、双指针、计数、排序

题目、示例与约束

给定一个整数数组 arr ，以及一个整数 target 作为目标值，返回满足 i < j < k 且 arr[i] + arr[j] + arr[k] == target 的元组 i, j, k 的数量。

由于结果会非常大，请返回 109 + 7 的模。

 

示例 1：

输入：arr = [1,1,2,2,3,3,4,4,5,5], target = 8
输出：20
解释：
按值枚举(arr[i], arr[j], arr[k])：
(1, 2, 5) 出现 8 次；
(1, 3, 4) 出现 8 次；
(2, 2, 4) 出现 2 次；
(2, 3, 3) 出现 2 次。

示例 2：

输入：arr = [1,1,2,2,2,2], target = 5
输出：12
解释：
arr[i] = 1, arr[j] = arr[k] = 2 出现 12 次：
我们从 [1,1] 中选择一个 1，有 2 种情况，
从 [2,2,2,2] 中选出两个 2，有 6 种情况。

 

提示：

• 3 <= arr.length <= 3000
• 0 <= arr[i] <= 100
• 0 <= target <= 300

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

思考

求三元组之和等于 $target$ 的方案数，值域 $[0,100]$， $n\le 3000$。枚举三个下标为立方级，偏紧。先计数，再枚举 $i<j$，第三个数 $c=target-a-b$ 必须在 $j$ 之后。

枚举 $j$ 时先把当前 $b$ 从计数中减掉，再用表 $O(1)$ 取右侧 $c$ 的个数。

我们可以用一个哈希表或者一个长度为 $101$ 的数组 $cnt$ 统计数组 $arr$ 中每个元素的出现次数。

然后，我们枚举数组 $arr$ 中的每个元素 $arr[j]$，先将 $cnt[arr[j]]$ 减一，然后再枚举 $arr[j]$ 之前的元素 $arr[i]$，计算 $c=target-arr[i]-arr[j]$，如果 $c$ 在 $[0,100]$ 的范围内，那么答案就加上 $cnt[c]$，最后返回答案。

注意，这里的答案可能会超过 ${10}^9+7$，所以在每次加法操作后都要取模。

时间复杂度 $O(n^2)$，其中 $n$ 为数组 $arr$ 的长度。空间复杂度 $O(C)$，其中 $C$ 为数组 $arr$ 中元素的最大值，本题中 $C=100$。

func threeSumMulti(arr []int, target int) (ans int) {
	const mod int = 1e9 + 7
	cnt := [101]int{}
	for _, x := range arr {
		cnt[x]++
	}
	for j, b := range arr {
		cnt[b]--
		for _, a := range arr[:j] {
			if c := target - a - b; c >= 0 && c < len(cnt) {
				ans = (ans + cnt[c]) % mod
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

925. 长按键入

简单1 种解法

标签：双指针、字符串

题目、示例与约束

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

 

示例 1：

输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。

示例 2：

输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。

 

提示：

• 1 <= name.length, typed.length <= 1000
• name 和 typed 的字符都是小写字母

方法一：双指针 · Go 实现

思考

判断 $\mathit{\text{typed}}$ 是否由 $\mathit{\text{name}}$ 经长按得到，即每一段连续相同字符只能变长、不能变短或换字母。长度至多 $1000$，按段比较即可。

双指针同时扫两串：当前字符必须相同，再各自数完这一段；若 $\mathit{\text{name}}$ 该段更长则失败。两串都恰好走完才合法。

我们利用两个指针 $i$ 和 $j$ 分别指向字符串 $\mathit{\text{typed}}$ 和 $\mathit{\text{name}}$ 的第一个字符，然后开始遍历，如果 $\mathit{\text{typed}}[j]\ne \mathit{\text{name}}[i]$，说明两个字符串不匹配，直接返回 $\mathit{\text{False}}$。否则，我们找到连续相同的字符的下一个位置，分别记为 $x$ 和 $y$，如果 $x-i>y-j$，说明 $\mathit{\text{typed}}$ 中的字符个数小于 $\mathit{\text{name}}$ 中的字符个数，直接返回 $\mathit{\text{False}}$。否则，我们将 $i$ 和 $j$ 更新为 $x$ 和 $y$，继续遍历，直到 $i$ 和 $j$ 分别遍历完 $\mathit{\text{name}}$ 和 $\mathit{\text{typed}}$，返回 $\mathit{\text{True}}$。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是字符串 $\mathit{\text{name}}$ 和 $\mathit{\text{typed}}$ 的长度。空间复杂度 $O(1)$。

func isLongPressedName(name string, typed string) bool {
	m, n := len(name), len(typed)
	i, j := 0, 0

	for i < m && j < n {
		if name[i] != typed[j] {
			return false
		}
		x, y := i+1, j+1

		for x < m && name[x] == name[i] {
			x++
		}

		for y < n && typed[y] == typed[j] {
			y++
		}

		if x-i > y-j {
			return false
		}

		i, j = x, y
	}

	return i == m && j == n
}

力扣原题 · Doocs 题解来源

962. 最大宽度坡

中等1 种解法

标签：栈、数组、双指针、单调栈

题目、示例与约束

给定一个整数数组 A，坡是元组 (i, j)，其中  i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。

找出 A 中的坡的最大宽度，如果不存在，返回 0 。

 

示例 1：

输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

示例 2：

输入：[9,8,1,0,1,9,4,0,4,1]
输出：7
解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.

 

提示：

1. 2 <= A.length <= 50000
2. 0 <= A[i] <= 50000

 

方法一：单调栈 · Go 实现

思考

求最宽的 $i<j$ 且 $nums[i]\le nums[j]$。枚举所有对为平方级。可作为左端的下标必须构成从左开始的严格递减序列，否则更左且更小的值更优。单调栈记下这些候选，再从右往左用 $j$ 弹出能构成坡的栈顶，宽度取最大。

根据题意，我们可以发现，所有可能的 $\mathit{\text{nums}}[i]$ 所构成的子序列一定是单调递减的。为什么呢？我们不妨用反证法证明一下。

假设存在 $i_1<i_2$，并且 $\mathit{\text{nums}}[i_1]\le \mathit{\text{nums}}[i_2]$，那么实际上 $\mathit{\text{nums}}[i_2]$ 一定不可能是一个候选值，因为 $\mathit{\text{nums}}[i_1]$ 更靠左，会是一个更优的值。因此 $\mathit{\text{nums}}[i]$ 所构成的子序列一定单调递减，并且 $i$ 一定是从 0 开始。

我们用一个从栈底到栈顶单调递减的栈 $\mathit{\text{stk}}$ 来存储所有可能的 $\mathit{\text{nums}}[i]$，然后我们从右边界开始遍历 $j$，若遇到 $\mathit{\text{nums}}[\mathit{\text{stk.top()}}]\le \mathit{\text{nums}}[j]$，说明此时构成一个坡，循环弹出栈顶元素，更新 $\mathit{\text{ans}}$。

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

func maxWidthRamp(nums []int) int {
	n := len(nums)
	stk := []int{}
	for i, v := range nums {
		if len(stk) == 0 || nums[stk[len(stk)-1]] > v {
			stk = append(stk, i)
		}
	}
	ans := 0
	for i := n - 1; i >= 0; i-- {
		for len(stk) > 0 && nums[stk[len(stk)-1]] <= nums[i] {
			ans = max(ans, i-stk[len(stk)-1])
			stk = stk[:len(stk)-1]
		}
		if len(stk) == 0 {
			break
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

977. 有序数组的平方

简单1 种解法

标签：数组、双指针、排序

题目、示例与约束

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

 

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

 

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 已按 非递减顺序 排序

 

进阶：

• 请你设计时间复杂度为 O(n) 的算法解决本问题

方法一：双指针 · Go 实现

思考

有序数组含负数，平方后应重新有序。逐个平方再排序为 $O(n\log n)$。平方后两端较大、中间较小，左右指针取平方较大者从后往前填（或先写入再反转），线性完成。

由于数组 $nums$ 已经按照非递减顺序排好序，所以数组中负数的平方值是递减的，正数的平方值是递增的。我们可以使用双指针，分别指向数组的两端，每次比较两个指针指向的元素的平方值，将较大的平方值放入结果数组的末尾。

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

func sortedSquares(nums []int) []int {
	n := len(nums)
	ans := make([]int, n)
	for i, j, k := 0, n-1, n-1; i <= j; k-- {
		a := nums[i] * nums[i]
		b := nums[j] * nums[j]
		if a > b {
			ans[k] = a
			i++
		} else {
			ans[k] = b
			j--
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

986. 区间列表的交集

中等1 种解法

标签：数组、双指针、扫描线

题目、示例与约束

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

 

示例 1：

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

示例 2：

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

示例 3：

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

示例 4：

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]

 

提示：

• 0 <= firstList.length, secondList.length <= 1000
• firstList.length + secondList.length >= 1
• 0 <= starti < endi <= 109
• endi < starti+1
• 0 <= startj < endj <= 109
• endj < startj+1

方法一：双指针 · Go 实现

思考

两份闭区间列表各自已按端点排序且内部不相交，求所有交集。双指针指向当前区间，交集为 $[max(s_1,s_2),min(e_1,e_2)]$，若左端不超过右端则记录。结束较早的那条指针前进。

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
	m, n := len(firstList), len(secondList)
	var ans [][]int
	for i, j := 0, 0; i < m && j < n; {
		l := max(firstList[i][0], secondList[j][0])
		r := min(firstList[i][1], secondList[j][1])
		if l <= r {
			ans = append(ans, []int{l, r})
		}
		if firstList[i][1] < secondList[j][1] {
			i++
		} else {
			j++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

1089. 复写零

简单1 种解法

标签：数组、双指针

题目、示例与约束

给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。

注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。

 

示例 1：

输入：arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]

示例 2：

输入：arr = [1,2,3]
输出：[1,2,3]
解释：调用函数后，输入的数组将被修改为：[1,2,3]

 

提示：

• 1 <= arr.length <= 104
• 0 <= arr[i] <= 9

方法一：双指针 · Go 实现

思考

要求原地把每个 $0$ 复写成两个，超出原长度的部分丢弃。 $n\le {10}^4$，另开数组再拷回不符合原地。从左写入会覆盖尚未处理的元素，应先算能留下的最右原下标，再从右回填。

指针 $i$ 与虚拟长度 $k$ 同步前进：非零 $k$ 加 $1$，零加 $2$，直到 $k\ge n$。若最后一次因零使 $k=n+1$，该零只能写一次，先放在末尾。

然后 $j$ 从 $n-1$ 回写：零连续写两格，非零写一格。

先从左往右扫一遍，统计复写零之后会占到的长度。指针 $i$ 指向原数组中还能留下的最后一个位置， $k$ 是复写后的虚拟长度：非零元素 $k$ 加 $1$，零则加 $2$。当 $k\ge n$ 时停止。

再设写入位置 $j=n-1$。如果最后一个留下的是零且刚好超出数组末尾（ $k=n+1$），这个零只能写一次，先把它放到 $arr[j]$，再把 $i$ 和 $j$ 各减 $1$。

然后从右往左回填。若 $arr[i]\ne 0$，直接写入 $arr[j]$；若为 $0$，连续写入两个 $0$。

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

func duplicateZeros(arr []int) {
	n := len(arr)
	i, k := -1, 0
	for k < n {
		i, k = i+1, k+1
		if arr[i] == 0 {
			k++
		}
	}
	j := n - 1
	if k == n+1 {
		arr[j] = 0
		i, j = i-1, j-1
	}
	for j >= 0 {
		arr[j] = arr[i]
		if arr[i] == 0 {
			j--
			arr[j] = arr[i]
		}
		i, j = i-1, j-1
	}
}

力扣原题 · Doocs 题解来源

1163. 按字典序排在最后的子串

困难1 种解法

标签：双指针、字符串、Lyndon 分解

题目、示例与约束

给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

 

示例 1：

输入：s = "abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2：

输入：s = "leetcode"
输出："tcode"

 

提示：

• 1 <= s.length <= 4 * 105
• s 仅含有小写英文字符。

方法一：双指针 · Go 实现

思考

字典序最大的子串必是某个后缀，枚举全部后缀再比较为平方级。双指针 $i$、 $j$ 分别指向当前最优后缀与候选后缀，用 $k$ 比较对应字符：相等则延伸；候选更大则把 $i$ 跳过已比较的一段；最优更大则同样跳过 $j$。被跳过的起点不可能更优，从而线性找到最大后缀。

我们注意到，如果一个子串从位置 $i$ 开始，那么字典序最大的子串一定是 $s[i,..n-1]$，即从位置 $i$ 开始的最长后缀。因此，我们只需要找出字典序最大的后缀子串即可。

我们使用双指针 $i$ 和 $j$，其中指针 $i$ 指向当前字典序最大的子串的起始位置，指针 $j$ 指向当前考虑的子串的起始位置。另外，用一个变量 $k$ 记录当前比较到的位置。初始时 $i=0$, $j=1$, $k=0$。

每一次，我们比较 $s[i+k]$ 和 $s[j+k]$：

如果 $s[i+k]=s[j+k]$，说明 $s[i,..i+k]$ 和 $s[j,..j+k]$ 相同，我们将 $k$ 加 $1$，继续比较 $s[i+k]$ 和 $s[j+k]$；

如果 $s[i+k]<s[j+k]$，说明 $s[j,..j+k]$ 的字典序更大。此时，我们更新 $i=i+k+1$，并将 $k$ 重置为 $0$。如果此时 $i\ge j$，那么我们将指针 $j$ 更新为 $i+1$，即 $j=i+1$。这里我们跳过了以 $s[i,..,i+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[j,..,j+k]$ 为起始位置的后缀子串。

同理，如果 $s[i+k]>s[j+k]$，说明 $s[i,..,i+k]$ 的字典序更大。此时，我们更新 $j=j+k+1$，并将 $k$ 重置为 $0$。这里我们跳过了以 $s[j,..,j+k]$ 为起始位置的所有后缀子串，因为它们的字典序一定小于对应的 $s[i,..,i+k]$ 为起始位置的后缀子串。

最后，我们返回以 $i$ 为起始位置的后缀子串即可，即 $s[i,..,n-1]$。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。

func lastSubstring(s string) string {
	i, n := 0, len(s)
	for j, k := 1, 0; j+k < n; {
		if s[i+k] == s[j+k] {
			k++
		} else if s[i+k] < s[j+k] {
			i += k + 1
			k = 0
			if i >= j {
				j = i + 1
			}
		} else {
			j += k + 1
			k = 0
		}
	}
	return s[i:]
}

力扣原题 · Doocs 题解来源

1229. 安排会议日程 🔒

中等1 种解法

标签：数组、双指针、排序

题目、示例与约束

给定两个人的空闲时间表：slots1 和 slots2，以及会议的预计持续时间 duration，请你为他们安排 时间段最早 且合适的会议时间。

如果没有满足要求的会议时间，就请返回一个 空数组。

「空闲时间」的格式是 [start, end]，由开始时间 start 和结束时间 end 组成，表示从 start 开始，到 end 结束。 

题目保证数据有效：同一个人的空闲时间不会出现交叠的情况，也就是说，对于同一个人的两个空闲时间 [start1, end1] 和 [start2, end2]，要么 start1 > end2，要么 start2 > end1。

 

示例 1：

输入：slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
输出：[60,68]

示例 2：

输入：slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
输出：[]

 

提示：

• 1 <= slots1.length, slots2.length <= 104
• slots1[i].length, slots2[i].length == 2
• slots1[i][0] < slots1[i][1]
• slots2[i][0] < slots2[i][1]
• 0 <= slots1[i][j], slots2[i][j] <= 109
• 1 <= duration <= 106

方法一：排序 + 双指针 · Go 实现

思考

两人各有最多 ${10}^4$ 段空闲，两两求交为 $O(mn)$。各自按起点排序后，交集只可能发生在当前两段之间：交区间为起点取大、终点取小。

若长度达到 $duration$，取最早的一段即可。否则结束较早的一段不可能再与对方更靠后的段产生更早的可行交，对应指针前进。

排序保证候选按时间推进，双指针每次丢弃已无前途的一段，总比较次数线性。

我们可以将两个人的空闲时间分别排序，然后使用双指针遍历两个数组，找到两个人的空闲时间段的交集，如果交集的长度大于等于 duration，则返回交集的起始时间和起始时间加上 duration。否则，如果第一个人的空闲时间段的结束时间小于第二个人的空闲时间段的结束时间，我们就移动第一个人的指针，否则移动第二个人的指针。继续遍历，直到找到满足条件的时间段或者遍历结束。

时间复杂度 $O(m\times \log m+n\times \log n)$，空间复杂度 $O(\log m+\log n)$。其中 $m$ 和 $n$ 分别为两个数组的长度。

func minAvailableDuration(slots1 [][]int, slots2 [][]int, duration int) []int {
	sort.Slice(slots1, func(i, j int) bool { return slots1[i][0] < slots1[j][0] })
	sort.Slice(slots2, func(i, j int) bool { return slots2[i][0] < slots2[j][0] })
	i, j, m, n := 0, 0, len(slots1), len(slots2)
	for i < m && j < n {
		start := max(slots1[i][0], slots2[j][0])
		end := min(slots1[i][1], slots2[j][1])
		if end-start >= duration {
			return []int{start, start + duration}
		}
		if slots1[i][1] < slots2[j][1] {
			i++
		} else {
			j++
		}
	}
	return []int{}
}

力扣原题 · Doocs 题解来源

1332. 删除回文子序列

简单1 种解法

标签：双指针、字符串

题目、示例与约束

给你一个字符串 s，它仅由字母 'a' 和 'b' 组成。每一次删除操作都可以从 s 中删除一个回文 子序列。

返回删除给定字符串中所有字符（字符串为空）的最小删除次数。

「子序列」定义：如果一个字符串可以通过删除原字符串某些字符而不改变原字符顺序得到，那么这个字符串就是原字符串的一个子序列。

「回文」定义：如果一个字符串向后和向前读是一致的，那么这个字符串就是一个回文。

 

示例 1：

输入：s = "ababa"
输出：1
解释：字符串本身就是回文序列，只需要删除一次。

示例 2：

输入：s = "abb"
输出：2
解释："abb" -> "bb" -> "". 
先删除回文子序列 "a"，然后再删除 "bb"。

示例 3：

输入：s = "baabb"
输出：2
解释："baabb" -> "b" -> "". 
先删除回文子序列 "baab"，然后再删除 "b"。

 

提示：

• 1 <= s.length <= 1000
• s 仅包含字母 'a'  和 'b'

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

思考

每次删除一个回文子序列，字符只有 'a'、'b'。任意同字母子序列都是回文，故至多两次（先删完 'a' 再删完 'b'）。若 $s$ 本身已是回文，一次即可。判断 $s$ 是否等于其反转即可在两者之间抉择。

如果字符串 $s$ 本身是个回文串，那么只需要删除 $1$ 次。

如果字符串 $s$ 不是个回文串，那么先删除所有的 'a'，再删除所有的 'b'，总共需要删除 $2$ 次。

时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(1)$。

func removePalindromeSub(s string) int {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		if s[i] != s[j] {
			return 2
		}
	}
	return 1
}

力扣原题 · Doocs 题解来源

1455. 检查单词是否为句中其他单词的前缀

简单1 种解法

标签：双指针、字符串、字符串匹配

题目、示例与约束

给你一个字符串 sentence 作为句子并指定检索词为 searchWord ，其中句子由若干用 单个空格 分隔的单词组成。请你检查检索词 searchWord 是否为句子 sentence 中任意单词的前缀。

如果 searchWord 是某一个单词的前缀，则返回句子 sentence 中该单词所对应的下标（下标从 1 开始）。如果 searchWord 是多个单词的前缀，则返回匹配的第一个单词的下标（最小下标）。如果 searchWord 不是任何单词的前缀，则返回 -1 。

字符串 s 的 前缀 是 s 的任何前导连续子字符串。

 

示例 1：

输入：sentence = "i love eating burger", searchWord = "burg"
输出：4
解释："burg" 是 "burger" 的前缀，而 "burger" 是句子中第 4 个单词。

示例 2：

输入：sentence = "this problem is an easy problem", searchWord = "pro"
输出：2
解释："pro" 是 "problem" 的前缀，而 "problem" 是句子中第 2 个也是第 6 个单词，但是应该返回最小下标 2 。

示例 3：

输入：sentence = "i am tired", searchWord = "you"
输出：-1
解释："you" 不是句子中任何单词的前缀。

 

提示：

• 1 <= sentence.length <= 100
• 1 <= searchWord.length <= 10
• sentence 由小写英文字母和空格组成。
• searchWord 由小写英文字母组成。

方法一：字符串分割 · Go 实现

思考

句子很短。按空格拆成单词后，检查 $\mathit{\text{searchWord}}$ 是否为某个词的前缀，返回 $1$ 起始下标。

我们将 $\mathit{\text{sentence}}$ 按空格分割为 $\mathit{\text{words}}$，然后遍历 $\mathit{\text{words}}$，检查 $\mathit{\text{words}}[i]$ 是否是 $\mathit{\text{searchWord}}$ 的前缀，是则返回 $i+1$。若遍历结束，所有单词都不满足，返回 $-1$。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m)$。其中 $m$ 和 $n$ 分别是 $\mathit{\text{sentence}}$ 和 $\mathit{\text{searchWord}}$ 的长度。

func isPrefixOfWord(sentence string, searchWord string) int {
	for i, s := range strings.Split(sentence, " ") {
		if strings.HasPrefix(s, searchWord) {
			return i + 1
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源

1471. 数组中的 k 个最强值

中等1 种解法

标签：数组、双指针、排序

题目、示例与约束

给你一个整数数组 arr 和一个整数 k 。

设 m 为数组的中位数，只要满足下述两个前提之一，就可以判定 arr[i] 的值比 arr[j] 的值更强：

•  |arr[i] - m| > |arr[j] - m|
•  |arr[i] - m| == |arr[j] - m|，且 arr[i] > arr[j]

请返回由数组中最强的 k 个值组成的列表。答案可以以 任意顺序 返回。

中位数 是一个有序整数列表中处于中间位置的值。形式上，如果列表的长度为 n ，那么中位数就是该有序列表（下标从 0 开始）中位于 ((n - 1) / 2) 的元素。

• 例如 arr = [6, -3, 7, 2, 11]，n = 5：数组排序后得到 arr = [-3, 2, 6, 7, 11] ，数组的中间位置为 m = ((5 - 1) / 2) = 2 ，中位数 arr[m] 的值为 6 。
• 例如 arr = [-7, 22, 17, 3]，n = 4：数组排序后得到 arr = [-7, 3, 17, 22] ，数组的中间位置为 m = ((4 - 1) / 2) = 1 ，中位数 arr[m] 的值为 3 。

 

示例 1：

输入：arr = [1,2,3,4,5], k = 2
输出：[5,1]
解释：中位数为 3，按从强到弱顺序排序后，数组变为 [5,1,4,2,3]。最强的两个元素是 [5, 1]。[1, 5] 也是正确答案。
注意，尽管 |5 - 3| == |1 - 3| ，但是 5 比 1 更强，因为 5 > 1 。

示例 2：

输入：arr = [1,1,3,5,5], k = 2
输出：[5,5]
解释：中位数为 3, 按从强到弱顺序排序后，数组变为 [5,5,1,1,3]。最强的两个元素是 [5, 5]。

示例 3：

输入：arr = [6,7,11,7,6,8], k = 5
输出：[11,8,6,6,7]
解释：中位数为 7, 按从强到弱顺序排序后，数组变为 [11,8,6,6,7,7]。
[11,8,6,6,7] 的任何排列都是正确答案。

 

提示：

• 1 <= arr.length <= 105
• -105 <= arr[i] <= 105
• 1 <= k <= arr.length

方法一：排序 · Go 实现

思考

强度由与中位数的距离决定，并列取较大值。 $n\le {10}^5$，先排序得到中位数 $m=arr[(n-1)//2]$，再按 $(-|x-m|,-x)$ 排序取前 $k$ 个。

我们首先对数组 $\mathit{\text{arr}}$ 进行排序，然后找到数组的中位数 $m$。

接下来，我们按照题目描述的规则对数组进行排序，最后返回数组的前 $k$ 个元素即可。

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

func getStrongest(arr []int, k int) []int {
	sort.Ints(arr)
	m := arr[(len(arr)-1)>>1]
	sort.Slice(arr, func(i, j int) bool {
		x, y := abs(arr[i]-m), abs(arr[j]-m)
		if x == y {
			return arr[i] > arr[j]
		}
		return x > y
	})
	return arr[:k]
}

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

力扣原题 · Doocs 题解来源

1577. 数的平方等于两数乘积的方法数

中等2 种解法

标签：数组、哈希表、数学、双指针

题目、示例与约束

给你两个整数数组 nums1 和 nums2 ，请你返回根据以下规则形成的三元组的数目（类型 1 和类型 2 ）：

• 类型 1：三元组 (i, j, k) ，如果 nums1[i]2 == nums2[j] * nums2[k] 其中 0 <= i < nums1.length 且 0 <= j < k < nums2.length
• 类型 2：三元组 (i, j, k) ，如果 nums2[i]2 == nums1[j] * nums1[k] 其中 0 <= i < nums2.length 且 0 <= j < k < nums1.length

 

示例 1：

输入：nums1 = [7,4], nums2 = [5,2,8,9]
输出：1
解释：类型 1：(1,1,2), nums1[1]^2 = nums2[1] * nums2[2] (4^2 = 2 * 8)

示例 2：

输入：nums1 = [1,1], nums2 = [1,1,1]
输出：9
解释：所有三元组都符合题目要求，因为 1^2 = 1 * 1
类型 1：(0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2), nums1[i]^2 = nums2[j] * nums2[k]
类型 2：(0,0,1), (1,0,1), (2,0,1), nums2[i]^2 = nums1[j] * nums1[k]

示例 3：

输入：nums1 = [7,7,8,3], nums2 = [1,2,9,7]
输出：2
解释：有两个符合题目要求的三元组
类型 1：(3,0,2), nums1[3]^2 = nums2[0] * nums2[2]
类型 2：(3,0,1), nums2[3]^2 = nums1[0] * nums1[1]

示例 4：

输入：nums1 = [4,7,9,11,23], nums2 = [3,5,1024,12,18]
输出：0
解释：不存在符合题目要求的三元组

 

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 1 <= nums1[i], nums2[i] <= 10^5

方法一：哈希表 + 枚举 · Go 实现

思考

统计满足 $nums1[i{]}^2=nums2[j]\cdot nums2[k]$（及对称情形）的三元组。数组长度通常百级，枚举全部三下标可行，但同一乘积会被反复计算。

先用哈希表统计一侧所有无序对的乘积出现次数，再枚举另一侧每个 $x$ 查询 $x^2$ 的次数。两类角色对调各做一次后相加。

我们用哈希表 $\mathit{\text{cnt1}}$ 统计 $\mathit{\text{nums1}}$ 中每个数对 $(\mathit{\text{nums}}[j],\mathit{\text{nums}}[k])$ 出现的次数，其中 $0\le j<k<m$，其中 $m$ 为数组 $\mathit{\text{nums1}}$ 的长度。用哈希表 $\mathit{\text{cnt2}}$ 统计 $\mathit{\text{nums2}}$ 中每个数对 $(\mathit{\text{nums}}[j],\mathit{\text{nums}}[k])$ 出现的次数，其中 $0\le j<k<n$，其中 $n$ 为数组 $\mathit{\text{nums2}}$ 的长度。

接下来，我们枚举数组 $\mathit{\text{nums1}}$ 中的每个数 $x$，计算 $\mathit{\text{cnt2}}[x^2]$ 的值，即 $\mathit{\text{nums2}}$ 中有多少对数 $(\mathit{\text{nums}}[j],\mathit{\text{nums}}[k])$ 满足 $\mathit{\text{nums}}[j]\times \mathit{\text{nums}}[k]=x^2$。同理，我们枚举数组 $\mathit{\text{nums2}}$ 中的每个数 $x$，计算 $\mathit{\text{cnt1}}[x^2]$ 的值，即 $\mathit{\text{nums1}}$ 中有多少对数 $(\mathit{\text{nums}}[j],\mathit{\text{nums}}[k])$ 满足 $\mathit{\text{nums}}[j]\times \mathit{\text{nums}}[k]=x^2$，最后将两者相加返回即可。

时间复杂度 $O(m^2+n^2+m+n)$，空间复杂度 $O(m^2+n^2)$。其中 $m$ 和 $n$ 分别为数组 $\mathit{\text{nums1}}$ 和 $\mathit{\text{nums2}}$ 的长度。

func numTriplets(nums1 []int, nums2 []int) int {
	cnt1 := count(nums1)
	cnt2 := count(nums2)
	return cal(cnt1, nums2) + cal(cnt2, nums1)
}

func count(nums []int) map[int]int {
	cnt := map[int]int{}
	for j, x := range nums {
		for _, y := range nums[j+1:] {
			cnt[x*y]++
		}
	}
	return cnt
}

func cal(cnt map[int]int, nums []int) (ans int) {
	for _, x := range nums {
		ans += cnt[x*x]
	}
	return
}

方法二：哈希表 + 枚举优化 · Go 实现

思考

方法一把全部数对乘积存进表，空间达 $O(n^2)$。改为只存每个值的频次，枚举 $x$ 与一侧的 $y$，令 $z=x^2/y$（须整除），方案为 $v_y(v_z-[y=z])$，最后除以 $2$ 消去 $(y,z)$ 与 $(z,y)$ 的重复。时间变为 $O(mn)$，空间线性。

我们用哈希表 $\mathit{\text{cnt1}}$ 统计 $\mathit{\text{nums1}}$ 中每个数出现的次数，用哈希表 $\mathit{\text{cnt2}}$ 统计 $\mathit{\text{nums2}}$ 中每个数出现的次数。

接下来，我们枚举数组 $\mathit{\text{nums1}}$ 中的每个数 $x$，然后枚举 $\mathit{\text{cnt2}}$ 中的每个数对 $(y,v1)$，其中 $y$ 为 $\mathit{\text{cnt2}}$ 的键， $v1$ 为 $\mathit{\text{cnt2}}$ 的值。我们计算 $z=x^2/y$，如果 $y\times z=x^2$，此时如果 $y=z$，说明 $y$ 和 $z$ 是同一个数，那么 $v1=v2$，从 $v1$ 个数中任选两个数的方案数为 $v1\times (v1-1)=v1\times (v2-1)$；如果 $y\ne z$，那么 $v1$ 个数中任选两个数的方案数为 $v1\times v2$。最后将所有方案数相加并除以 $2$ 即可。这里除以 $2$ 是因为我们统计的是对数对 $(j,k)$ 的方案数，而实际上 $(j,k)$ 和 $(k,j)$ 是同一种方案。

时间复杂度 $O(m\times n)$，空间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为数组 $\mathit{\text{nums1}}$ 和 $\mathit{\text{nums2}}$ 的长度。

func numTriplets(nums1 []int, nums2 []int) int {
	cnt1 := count(nums1)
	cnt2 := count(nums2)
	return cal(cnt1, nums2) + cal(cnt2, nums1)
}

func count(nums []int) map[int]int {
	cnt := map[int]int{}
	for _, x := range nums {
		cnt[x]++
	}
	return cnt
}

func cal(cnt map[int]int, nums []int) (ans int) {
	for _, x := range nums {
		for y, v1 := range cnt {
			z := x * x / y
			if y*z == x*x {
				if v2, ok := cnt[z]; ok {
					if y == z {
						v2--
					}
					ans += v1 * v2
				}
			}
		}
	}
	ans /= 2
	return
}

力扣原题 · Doocs 题解来源

1616. 分割两个字符串得到回文串

中等1 种解法

标签：双指针、字符串

题目、示例与约束

给你两个字符串 a 和 b ，它们长度相同。请你选择一个下标，将两个字符串都在 相同的下标 分割开。由 a 可以得到两个字符串： aprefix 和 asuffix ，满足 a = aprefix + asuffix ，同理，由 b 可以得到两个字符串 bprefix 和 bsuffix ，满足 b = bprefix + bsuffix 。请你判断 aprefix + bsuffix 或者 bprefix + asuffix 能否构成回文串。

当你将一个字符串 s 分割成 sprefix 和 ssuffix 时， ssuffix 或者 sprefix 可以为空。比方说， s = "abc" 那么 "" + "abc" ， "a" + "bc" ， "ab" + "c" 和 "abc" + "" 都是合法分割。

如果 能构成回文字符串 ，那么请返回 true，否则返回 false 。

注意， x + y 表示连接字符串 x 和 y 。

 

示例 1：

输入：a = "x", b = "y"
输出：true
解释：如果 a 或者 b 是回文串，那么答案一定为 true ，因为你可以如下分割：
aprefix = "", asuffix = "x"
bprefix = "", bsuffix = "y"
那么 aprefix + bsuffix = "" + "y" = "y" 是回文串。

示例 2：

输入：a = "xbdef", b = "xecab"
输出：false

示例 3：

输入：a = "ulacfd", b = "jizalu"
输出：true
解释：在下标为 3 处分割：
aprefix = "ula", asuffix = "cfd"
bprefix = "jiz", bsuffix = "alu"
那么 aprefix + bsuffix = "ula" + "alu" = "ulaalu" 是回文串。

 

提示：

• 1 <= a.length, b.length <= 105
• a.length == b.length
• a 和 b 都只包含小写英文字母

方法一：双指针 · Go 实现

思考

分割点可以有 $n$ 种， $n$ 达 ${10}^5$，不能对每个分割点再花线性时间验回文。

若 $a$ 的前缀与 $b$ 的后缀尽量配对，剩余中间段必须本身是回文，且该中间段只能完全来自 $a$ 或完全来自 $b$。对称地交换 $a,b$ 再做一次。

双指针从两端向内，相等则收缩；停下后检查 $a[i..j]$ 或 $b[i..j]$ 是否回文，两方向任一成功即可。

我们可以使用双指针，其中一个指针 $i$ 从字符串 $a$ 的头部开始，另一个指针 $j$ 从字符串 $b$ 的尾部开始，如果两个指针指向的字符相等，那么两个指针同时往中间移动，直到遇到不同的字符或两指针交叉。

如果两指针交叉，即 $i\ge j$，说明 $prefix$ 和 $suffix$ 已经可以得到回文串，返回 true；否则，我们还需要判断 $a[i,...j]$ 或者 $b[i,...j]$ 是否是回文串，若是，返回 true。

否则，我们尝试交换两个字符串 $a$ 和 $b$，重复上述同样的过程。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 是字符串 $a$ 或 $b$ 的长度。

func checkPalindromeFormation(a string, b string) bool {
	return check1(a, b) || check1(b, a)
}

func check1(a, b string) bool {
	i, j := 0, len(b)-1
	for i < j && a[i] == b[j] {
		i++
		j--
	}
	return i >= j || check2(a, i, j) || check2(b, i, j)
}

func check2(a string, i, j int) bool {
	for i < j && a[i] == a[j] {
		i++
		j--
	}
	return i >= j
}

力扣原题 · Doocs 题解来源

1679. K 和数对的最大数目

中等2 种解法

标签：数组、哈希表、双指针、排序

题目、示例与约束

给你一个整数数组 nums 和一个整数 k 。

每一步操作中，你需要从数组中选出和为 k 的两个整数，并将它们移出数组。

返回你可以对数组执行的最大操作数。

 

示例 1：

输入：nums = [1,2,3,4], k = 5
输出：2
解释：开始时 nums = [1,2,3,4]：
- 移出 1 和 4 ，之后 nums = [2,3]
- 移出 2 和 3 ，之后 nums = []
不再有和为 5 的数对，因此最多执行 2 次操作。

示例 2：

输入：nums = [3,1,3,4,3], k = 6
输出：1
解释：开始时 nums = [3,1,3,4,3]：
- 移出前两个 3 ，之后nums = [1,4,3]
不再有和为 6 的数对，因此最多执行 1 次操作。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

方法一：排序 · Go 实现

思考

每对数字之和为 $k$ 且每个数只用一次，求最多对数。 $n$ 达 ${10}^5$，排序后两指针：和等于 $k$ 则配一对，偏大收右，偏小抬左。

我们对 $nums$ 进行排序。然后 $l$, $r$ 分别指向 $nums$ 首尾元素，判断两整数之和 $s$ 与 $k$ 的大小关系。

• 若 $s=k$，说明找到了两个整数，满足和为 $k$，答案加一，然后 $l$, $r$ 向中间移动；
• 若 $s>k$，则 $r$ 指针向左移动；
• 若 $s<k$，则 $l$ 指针向右移动；
• 继续循环判断，直至 $l\ge r$。

循环结束，返回答案。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为 $nums$ 的长度。

func maxOperations(nums []int, k int) int {
	sort.Ints(nums)
	l, r, ans := 0, len(nums)-1, 0
	for l < r {
		s := nums[l] + nums[r]
		if s == k {
			ans++
			l++
			r--
		} else if s > k {
			r--
		} else {
			l++
		}
	}
	return ans
}

方法二：哈希表 · Go 实现

思考

方法一需要排序。哈希表记录尚未配对的频次：遇到 $x$ 若 $k-x$ 仍有剩余则配掉，否则把 $x$ 入库，线性时间。

我们使用哈希表 $cnt$ 记录当前剩余整数及其出现的次数。

遍历 $nums$，对于当前整数 $x$，判断 $k-x$ 是否在 $cnt$ 中，若存在，则说明找到了两个整数，满足和为 $k$，答案加一，然后将 $k-x$ 的出现次数减一；否则，将 $x$ 的出现次数加一。

遍历结束，返回答案。

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

func maxOperations(nums []int, k int) (ans int) {
	cnt := map[int]int{}
	for _, x := range nums {
		if cnt[k-x] > 0 {
			cnt[k-x]--
			ans++
		} else {
			cnt[x]++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1750. 删除字符串两端相同字符后的最短长度

中等1 种解法

标签：双指针、字符串

题目、示例与约束

给你一个只包含字符 'a'，'b' 和 'c' 的字符串 s ，你可以执行下面这个操作（5 个步骤）任意次：

1. 选择字符串 s 一个 非空 的前缀，这个前缀的所有字符都相同。
2. 选择字符串 s 一个 非空 的后缀，这个后缀的所有字符都相同。
3. 前缀和后缀在字符串中任意位置都不能有交集。
4. 前缀和后缀包含的所有字符都要相同。
5. 同时删除前缀和后缀。

请你返回对字符串 s 执行上面操作任意次以后（可能 0 次），能得到的 最短长度 。

 

示例 1：

输入：s = "ca"
输出：2
解释：你没法删除任何一个字符，所以字符串长度仍然保持不变。

示例 2：

输入：s = "cabaabac"
输出：0
解释：最优操作序列为：
- 选择前缀 "c" 和后缀 "c" 并删除它们，得到 s = "abaaba" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "baab" 。
- 选择前缀 "b" 和后缀 "b" 并删除它们，得到 s = "aa" 。
- 选择前缀 "a" 和后缀 "a" 并删除它们，得到 s = "" 。

示例 3：

输入：s = "aabccabba"
输出：3
解释：最优操作序列为：
- 选择前缀 "aa" 和后缀 "a" 并删除它们，得到 s = "bccabb" 。
- 选择前缀 "b" 和后缀 "bb" 并删除它们，得到 s = "cca" 。

 

提示：

• 1 <= s.length <= 105
• s 只包含字符 'a'，'b' 和 'c' 。

方法一：双指针 · Go 实现

思考

每次从两端删除相同字符组成的非空前缀与后缀。删除后新的两端若仍相同可继续。双指针向内收即可模拟全过程。

当两端字符相同且指针尚未交错，把该字符在两侧的整段跳过，再缩进一格。剩余长度 $max(0,j-i+1)$。

我们定义两个指针 $i$ 和 $j$ 分别指向字符串 $s$ 的头部和尾部，然后向中间移动，直到 $i$ 和 $j$ 指向的字符不相等，此时 $max(0,j-i+1)$ 即为答案。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为字符串 $s$ 的长度。

func minimumLength(s string) int {
	i, j := 0, len(s)-1
	for i < j && s[i] == s[j] {
		for i+1 < j && s[i] == s[i+1] {
			i++
		}
		for i < j-1 && s[j] == s[j-1] {
			j--
		}
		i, j = i+1, j-1
	}
	return max(0, j-i+1)
}

力扣原题 · Doocs 题解来源

1768. 交替合并字符串

简单1 种解法

标签：双指针、字符串

题目、示例与约束

给你两个字符串 word1 和 word2 。请你从 word1 开始，通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。

返回 合并后的字符串 。

 

示例 1：

输入：word1 = "abc", word2 = "pqr"
输出："apbqcr"
解释：字符串合并情况如下所示：
word1：  a   b   c
word2：    p   q   r
合并后：  a p b q c r

示例 2：

输入：word1 = "ab", word2 = "pqrs"
输出："apbqrs"
解释：注意，word2 比 word1 长，"rs" 需要追加到合并后字符串的末尾。
word1：  a   b 
word2：    p   q   r   s
合并后：  a p b q   r   s

示例 3：

输入：word1 = "abcd", word2 = "pq"
输出："apbqcd"
解释：注意，word1 比 word2 长，"cd" 需要追加到合并后字符串的末尾。
word1：  a   b   c   d
word2：    p   q 
合并后：  a p b q c   d

 

提示：

• 1 <= word1.length, word2.length <= 100
• word1 和 word2 由小写英文字母组成

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

思考

按交替顺序拼接两串，较短的一方用尽后接上另一串剩余。一次配对遍历即可。

$\mathit{\text{zip\_longest}}$ 按位取出字符（缺省为空串）再连接，得到交替合并结果。

我们遍历 word1, word2 两个字符串，依次取出字符，拼接到结果字符串中。Python 代码可以简化为一行。

时间复杂度 $O(m+n)$，其中 $m$ 和 $n$ 分别是两个字符串的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

func mergeAlternately(word1 string, word2 string) string {
	m, n := len(word1), len(word2)
	ans := make([]byte, 0, m+n)
	for i := 0; i < m || i < n; i++ {
		if i < m {
			ans = append(ans, word1[i])
		}
		if i < n {
			ans = append(ans, word2[i])
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1813. 句子相似性 III

中等1 种解法

标签：数组、双指针、字符串

题目、示例与约束

给定两个字符串 sentence1 和 sentence2，每个表示由一些单词组成的一个句子。句子是一系列由 单个 空格分隔的 单词，且开头和结尾没有多余空格。每个单词都只包含大写和小写英文字母。

如果两个句子 s1 和 s2 ，可以通过往其中一个句子插入一个任意的句子（可以是空句子）而得到另一个句子，那么我们称这两个句子是 相似的 。注意，插入的句子必须与现有单词用空白隔开。 

比方说，

• s1 = "Hello Jane" 与 s2 = "Hello my name is Jane"，我们可以往 s1 中 "Hello" 和 "Jane" 之间插入 "my name is" 得到 s2 。
• s1 = "Frog cool" 与 s2 = "Frogs are cool" 不是相似的，因为尽管往 s1 中插入 "s are"，它没有与 "Frog" 用空格隔开。

给你两个句子 sentence1 和 sentence2 ，如果 sentence1 和 sentence2 是 相似 的，请你返回 true ，否则返回 false 。

 

示例 1：

输入：sentence1 = "My name is Haley", sentence2 = "My Haley"

输出：true

解释：可以往 sentence2 中 "My" 和 "Haley" 之间插入 "name is" ，得到 sentence1 。

 

示例 2：

输入：sentence1 = "of", sentence2 = "A lot of words"

输出：false

解释：没法往这两个句子中的一个句子只插入一个句子就得到另一个句子。

 

示例 3：

输入：sentence1 = "Eating right now", sentence2 = "Eating"

输出：true

解释：可以往 sentence2 的结尾插入 "right now" 得到 sentence1 。

 

提示：

• 1 <= sentence1.length, sentence2.length <= 100
• sentence1 和 sentence2 都只包含大小写英文字母和空格。
• sentence1 和 sentence2 中的单词都只由单个空格隔开。

方法一：双指针 · Go 实现

思考

较短句须能通过在某一处插入一段连续单词变成较长句，即较短句是较长句的一个「前缀加后缀」拼接。若枚举插入位置并逐词比较，单词数虽不大，但逻辑易与「可在多处插入」混淆。

将两句按空格拆成词数组并保证第一句不短于第二句。从左对齐统计公共前缀，从右对齐统计公共后缀；若二者长度之和覆盖较短句的全部单词，则中间缺口至多一段，恰为一次插入。

我们将两个句子按照空格分割成两个单词数组 words1 和 words2，假设 words1 和 words2 的长度分别为 $m$ 和 $n$，不妨设 $m\ge n$。

我们使用双指针 $i$ 和 $j$，初始时 $i=j=0$。接下来，我们循环判断 words1[i] 是否等于 words2[i]，是则指针 $i$ 继续右移；然后我们循环判断 words1[m - 1 - j] 是否等于 words2[n - 1 - j]，是则指针 $j$ 继续右移。

循环结束后，如果 $i+j\ge n$，说明两个句子相似，返回 true，否则返回 false。

时间复杂度 $O(L)$，空间复杂度 $O(L)$。其中 $L$ 为两个句子的长度之和。

func areSentencesSimilar(sentence1 string, sentence2 string) bool {
	words1, words2 := strings.Fields(sentence1), strings.Fields(sentence2)
	if len(words1) < len(words2) {
		words1, words2 = words2, words1
	}
	m, n := len(words1), len(words2)
	i, j := 0, 0
	for i < n && words1[i] == words2[i] {
		i++
	}
	for j < n && words1[m-1-j] == words2[n-1-j] {
		j++
	}
	return i+j >= n
}

力扣原题 · Doocs 题解来源

1826. 有缺陷的传感器 🔒

简单1 种解法

标签：数组、双指针

题目、示例与约束

实验室里正在进行一项实验。为了确保数据的准确性，同时使用 两个 传感器来采集数据。您将获得2个数组 sensor1 and sensor2，其中 sensor1[i] 和 sensor2[i] 分别是两个传感器对第 i 个数据点采集到的数据。

但是，这种类型的传感器有可能存在缺陷，它会导致 某一个 数据点采集的数据（掉落值）被丢弃。

数据被丢弃后，所有在其右侧的数据点采集的数据，都会被向左移动一个位置，最后一个数据点采集的数据会被一些随机值替换。可以保证此随机值不等于掉落值。

• 举个例子, 如果正确的数据是 [1,2,3,4,5] ， 此时 3 被丢弃了, 传感器会返回 [1,2,4,5,7] (最后的位置可以是任何值, 不仅仅是 7).

可以确定的是，最多有一个 传感器有缺陷。请返回这个有缺陷的传感器的编号 （1 或 2）。如果任一传感器 没有缺陷 ，或者 无法 确定有缺陷的传感器，则返回 -1 。

 

示例 1：

输入：sensor1 = [2,3,4,5], sensor2 = [2,1,3,4]
输出：1
解释：传感器 2 返回了所有正确的数据.
传感器2对第二个数据点采集的数据，被传感器1丢弃了，传感器1返回的最后一个数据被替换为 5 。

示例 2：

输入：sensor1 = [2,2,2,2,2], sensor2 = [2,2,2,2,5]
输出：-1
解释：无法判定哪个传感器是有缺陷的。
假设任一传感器丢弃的数据是最后一位，那么，另一个传感器就能给出与之对应的输出。

示例 3：

输入：sensor1 = [2,3,2,2,3,2], sensor2 = [2,3,2,3,2,7]
输出：2
解释：传感器 1 返回了所有正确的数据.
传感器 1 对第四个数据点的采集数据，被传感器2丢失了, 传感器 2 返回的最后一个数据被替换为 7 。

 

提示：

• sensor1.length == sensor2.length
• 1 <= sensor1.length <= 100
• 1 <= sensor1[i], sensor2[i] <= 100

方法一：遍历 · Go 实现

思考

一个传感器会丢掉某个值并把后续数据前移，另一个保持正确。需要判断哪一个损坏，或无法区分。两数组只在错位后不同，暴力对齐所有丢弃位置为 $O(n^2)$，而 $n$ 虽不大，结构上只需一次错位比较。

先找到第一个不同下标 $i$，此后把 $sensor1[i+1:]$ 与 $sensor2[i:]$、以及反过来的一对比较。哪一侧无法对齐，即对应传感器丢失了数据；两边都能对齐则无法判定。

遍历两个数组，找到第一个不相等的位置 $i$。如果 $i<n-1$，循环比较 $sensor1[i+1]$ 和 $sensor2[i]$，如果不相等，说明传感器 $1$ 有缺陷，返回 $1$；否则比较 $sensor1[i]$ 和 $sensor2[i+1]$，如果不相等，说明传感器 $2$ 有缺陷，返回 $2$。

遍历结束，说明无法确定有缺陷的传感器 🔒，返回 $-1$。

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

func badSensor(sensor1 []int, sensor2 []int) int {
	i, n := 0, len(sensor1)
	for ; i < n-1 && sensor1[i] == sensor2[i]; i++ {
	}
	for ; i < n-1; i++ {
		if sensor1[i+1] != sensor2[i] {
			return 1
		}
		if sensor1[i] != sensor2[i+1] {
			return 2
		}
	}
	return -1
}

力扣原题 · Doocs 题解来源