1 如何高效寻找素数

统计 n 以内的素数个数。

素数：只能被 1 和自身整除的自然数，0、1 除外

例如：

输入：100，输出：25

暴力算法：

fun bf(n: Int): Int {
	if (n == 0 || n == 1) return 0

    var count = 0

    for (i in 2..n) {
        count += if (isPrime(i)) 1 else 0
    }
    return count
}

fun isPrime(n: Int): Boolean {
    var i = 2
    // while (i * 2 <= n) {
    // while (i * i <= n) {
    while (i < n) {
        if (n % i == 0) return false
        i++
    }
    return true
}

埃筛法：

fun eratosthenes(n: Int): Int {
    if (n == 0 || n == 1) return 0

    var count = 0

    var isMarked = BooleanArray(n + 1)
    for (i in 2..n) {
        if (isMarked[i]) continue
        count++

        var j = i * 2
        while (j <= n) {
            isMarked[j] = true
            j += i
        }
    }
    return count
}

2 如何高效的进行模幂运算

要求我们的算法返回幂运算 a^b 的计算结果与 1337 取模（mod，也就是余数）后的结果。

就是我们要先计算幂 a^b，但是这个 b 会非常大，所以 b 是用数组的形式来表示的。

这道题有三个难点：

1. 如何处理用数组表示的指数？现在 b 是一个数组，也就是说 b 可以非常大，没办法直接转为整型，否则可能会溢出。那么怎么把这个数组作为指数，进行运算呢？
2. 二是如何取得求模之后的结果？按道理，起码应该先把幂运算结果算出来，然后做 %1337 这个运算。但是，指数运算的结果肯定大的吓人，也就是说，算出来真实结果也没有办法表示，也会溢出；
3. 三是如何高效进行幂运算？进行幂运算也是有技巧的。

第一步，如何处理数组指数

首先明确问题，现在 b 是一个数组，不能表示成整型，而且数组的特点是随机访问，删除最后一个元素比较高效。

暂时先不考虑模的要求，以 b = [1, 5, 6, 4] 来举例，结合指数运算的法则，我们可以发现：

a^{[1, 5, 6, 4]} = a ⁴ x a^{[1, 5, 6, 0]} = a ⁴ x ( a^{[1, 5, 6]})¹⁰

这里已经有明显的递归属性了。

到这里，首先写出代码框架：

private const val MOD = 1337

fun superPow(a: Int, b: IntArray): Int {
    if (b.isEmpty()) return 1 % MOD

    val last = b.last()
    val rest = b.dropLast(1).toIntArray()

    val part1 = myPow(a, last)  // a^last mod MOD
    val part2 = myPow(superPow(a, rest), 10)  // (superPow(...))^10 mod MOD

    return (part1 * part2) % MOD
}

// 计算 a^k mod MOD 的快速幂实现
fun myPow(a: Int, k: Int): Int {
  
}

到这里，已经解决了 b 是一个数组的问题，下面继续处理 mod，避免结果太大而导致整型溢出。

第二步，如何处理 mod 运算

首先明确问题，由于计算机的编码方式，如 (a * b) % m 这样的运算，乘法的结果可能会导致溢出，我们希望找到一种技巧，能够简化这种表达式，避免溢出同时得到结果。

比如在二分查找中，我们求中点索引时用 (l + r) / 2 转化成 l + (r - l) / 2，避免溢出的同时得到正确的结果。

下面是一个关于模运算的技巧：(a * b) % m = (a % m)(b % m) % m

证明，假设： a = Am +B; b = Cm + D，其中 A、B、C、D 是任意常数，那么，a * b = ACm² + ADm + BCm + BD，因此，(a * b) % m = (B * D) % m，又因为 a % m = B，b % m = D，所以，(a % k)(b % k) % k = BD % k

综上，就可以得到我们化简求模的等式了。

换句话说，对乘法的结果求模，等价于先对每个因子求模，然后对因子相乘的结果再求模。

由此扩展到本题，求一个数的幂其实就是对这个数进行连乘：

// 计算 a^k mod MOD 的快速幂实现
fun myPow(a: Int, k: Int): Int {
    var res = 1
    
    for (i in 0 until k) {
        res = res * a  // 先乘法
    }
    
    return res % MOD  // 最后统一取模
}

这样做的优点是：逻辑清晰；缺点是：如果 res 增长太快，可能会溢出。

证明：((a % m) * b) % m = (a * b) % m

对于整数 a 和正整数 m，存在唯一的整数 q（商）和 r（余数），满足 a = q * m + r，且 0 ≤ r < m，此时，a % m = r。

证明步骤：

1. 设 a % m = r，根据定义，a = k * m + r（k 是整数，0 ≤ r < m）；
2. 计算 a * b：a * b = (k * m + r) * b = k * m * b + r * b；
3. 对于 (a * b) % m：(a * b) % m = (k * m * b + r * b) % m = (r * b) % m；
4. 由于 r = a % m，代入得：(a * b) % m = (r * b) % m = ((a % m) * b) % m；

继续优化：根据 (a * b) % m = (a % m)(b % m) % m，我们计算 a^k % m

当 k = 1 时，a^k % m = a % m；

当 k = 2 时，a² % m = (a * a) % m = (a % m) * (a % m) % m = (a % m)² % m；

当 k = 3 时，

a³ % m = (a * a * a) % m = ((a * a) * a) % m = (a² * a) % m = ((a² % m) * (a % m)) % m

= ((a % m)² % m * (a % m)) % m （注意：这里相当于 ((A % M）* B) % M）

= (a % m)³ % m

当 k = 4 时，

a⁴ % m = (a * a * a * a) % m = ((a * a * a) * a) % m = (a³ * a) % m = ((a³ % m) * (a % m)) % m

= ((a % m)³ % m * (a % m)) % m

= (a % m)⁴ % m

归纳总结为：a^k % m = (a % m)^k % m

继续优化代码：

fun myPow(a: Int, k: Int): Int {
    val aa = a % MOD
    var res = 1
    
    for (i in 0 until k) {
        res = res * aa  // 先乘法
    }
    
    return res % MOD  // 最后统一取模
}

优化之后，虽然可以降低 res 增长的速度，但是还是存在溢出的风险。可不可以对 res 每次都取模呢？

// 计算 a 的 k 次方，然后与 base 求模的结果
fun myPow(a: Int, k: Int): Int {
  	if (k == 0) return 1 % MOD
    // 对因子求模
    val aa = a % MOD

    var res = 1
    for (i in 0 until k) {
        res = res * aa % MOD
    }
    return res
}

对比（aa = a % m）：

	最后取模（res）	每次取模（res）
k = 0	1 % m	1 % m
k = 1	a1 % m = aa % m	a1 % m = aa % m
k = 2	a2 % m = aa2 % m	a2 % m = ((aa % m) * aa) % m = aa2 % m
k = 3	a3 % m = aa3 % m	a3 % m = ((aa2 % m) * aa) % m = aa3 % m
k = 4	a4 % m = aa4 % m	a4 % m = ((aa3 % m) * aa) % m = aa4 % m

我们知道，最终的返回结果一定是在 [0, MOD-1] 范围内。

第三步，如何高效求幂

如果 k 为奇数，a^k % m = (a x a^k-1) % m = (a % m) * (a^k-1 % m) % m

如果 k 为偶数，a^k % m = (a^k/2)² % m

使用这种思路比直接用 for 循环求幂要高效，因为可以直接把问题的规模（k 的大小）直接减少一半。

// 计算 a^k mod MOD 的快速幂实现
fun pow(a: Int, k: Int): Int {
    if (k == 0) return 1 % MOD

    return if (k % 2 == 0) {
      	// 偶数：a^k = (a^(k/2))^2
        val sub = pow(a, k / 2)
        sub * sub % MOD
    } else {
      	// 奇数：a^k = a * a^(k-1)
        (a % MOD) * pow(a, k - 1) % MOD
    }
}

4 如何高效解决接雨水问题

给定 n 给非负整数，表示每个宽度为 1 的柱子的高度图，计算按照此排列的柱子，下雨之后能能接到多少雨水。

输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

输出：6

解释：上面是由数组 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] 表示的高度图，在这种情况袭，可以接住 6 个单位雨水（蓝色部分表示雨水）。

就是用一个数组表示一个条形图，问这个条形图最多能接多少水。

1 暴力解法

具体来讲，对于位置 i 能装下多少水呢？

能装下 2 格。为什么呢？因为位置 i 处能达到的水柱的高度和其左边的最高柱子、右边的最高柱子有关。其左边最高柱子的高度是 2，其右边最高柱子的高度是 3，因为 height[i] 的高度是 0，所以位置 i 处能装下 2 格的水。

这里我们假设左右两个最高柱子的高度分别为 leftMax 和 rightMax，位置 i 处的水柱高度就是 min(leftMax, rightMax) - height[i]。

根据以上的思路：

fun trap(height: Array<Int>): Int {
    val n = height.size
    var res = 0

    // 位置 0 和位置 n - 1 处无法存储水
    for (i in 1 until n - 1) {
        var leftMax = 0 // 位置 i 处左边最高的柱子
        var rightMax = 0 // 位置 i 处右边最高的柱子

        // 寻找左边最高的柱子，这里到 i 是因为后面要 -height[i]
        for (j in 0..i) {
            leftMax = leftMax.coerceAtLeast(height[j])
        }
        // 寻找右边最高的柱子，这里从 i 开始是因为后面要 -height[i]
        for (j in i until n) {
            rightMax = rightMax.coerceAtLeast(height[j])
        }

        res += leftMax.coerceAtMost(rightMax) - height[i]
    }

    return res
}

2 备忘录优化

在暴力算法中，需要计算每个位置的 leftMax 和 rightMax，我们可以直接先把结果计算出来，不需要每次都遍历。

定义两个数组 leftMax 和 rightMax 充当备忘录，leftMax[i] 表示位置 i 左边最高的柱子高度，rightMax[i] 表示位置 i 右边最高的柱子高度。预先把这两个数组准备好，避免重复计算：

fun trap(height: Array<Int>): Int {
    val n = height.size
    var res = 0

    // 数组备忘录
    val leftMax = IntArray(n)
    val rightMax = IntArray(n)

    // 初始化
    leftMax[0] = height[0]
    rightMax[n - 1] = height[n - 1]

    for (i in 1 until n) {
        leftMax[i] = height[i].coerceAtLeast(leftMax[i - 1])
    }

    for (i in n - 2 downTo 0) {
        rightMax[i] = height[i].coerceAtLeast(rightMax[i + 1])
    }

    for (i in 1 until n - 1) {
        res += leftMax[i].coerceAtMost(rightMax[i]) - height[i]
    }

    return res
}

备忘录算法和暴力算法的思路差不多，就是避免了重复计算。

3 双指针解法

fun trap(height: Array<Int>): Int {
    val n = height.size
    var res = 0

    var left = 0
    var right = n - 1

    // 左边最高柱子的高度和右边最高柱子的高度
    var leftMax = height[0]
    var rightMax = height[n - 1]

    while (left < right) {
        leftMax = leftMax.coerceAtLeast(height[left])
        rightMax = rightMax.coerceAtLeast(height[right])

        if (leftMax < rightMax) { // 左边的柱子低于右边柱子的高度，水的高度只和较低的柱子有关
            res += leftMax - height[left]
            left++
        } else { // 右边的柱子低于左边柱子的高度，水的高度只和较低的柱子有关
            res += rightMax - height[right]
            right--
        }
    }

    return res
}

需要说明的是：为什么要比较 leftMax 和 rightMax 的大小

• leftMax ：left 往左，所有“柱子”的最大值；
• rightMax：right 往右，所有“柱子”的最大值；
• 只要 leftMax < rightMax，右侧就一定有比 leftMax 更高的“柱子”。比如，leftMax = 3, rightMax = 5，意味着右侧一定存在一根 ≥5 的“柱子”。但是，水位是由较短的“柱子”来决定的；
• 所以，积水 = 3 - height[left]，完全不需要知道中间的“柱子”是什么样子的；
• 右侧，同理

虽然，leftMax 和 rightMax 并不相关，但可以用来判断，当前哪一侧是整段的短板：左短，左侧蓄水；右短，右侧蓄水；赵昂见区域不需要管，总有高柱子兜底。

5. 如何去除有序数组的重复元素

给你一个非严格递增排列的数组（即数组中允许有重复元素，但整体趋势是递增的），请你原地删除重复出现的元素，使得每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。然后返回 nums 中唯一元素的个数。

例如：

输入：[0, 1, 2, 2, 3, 3, 4]

输出：5

思路：我们已知数组是有序的，而且，我们只能在原地修改数组，不能创建新的数组来存放删除重复元素后的数组。因此需要一边遍历数组查找相同的元素，一边在对比发现不同元素时修改数组元素，这个时候就需要考虑快慢指针了。

快慢指针法：

• i：慢指针 → 指向数组中最后一个不重复的元素；
• j：快指针 → 遍历数组，找到新的不重复数字

val arr = arrayOf(0, 1, 2, 2, 3, 3, 4)

fun removeDuplicates(arr: Array<Int>): Int {
    if (arr.isEmpty()) return 0
    val n = arr.size

    var i = 0 // 慢指针：指向最后一个不重复的位置元素
    // j 快指针：从 1 开始遍历所有的元素
    for (j in 1 until n) {
    	// 发现不重复的元素
        if (arr[j] != arr[i]) {
            i++ 				// 慢指针前进一位
            arr[i] = arr[j]		// 覆盖新的不重复元素
        }
    }

    return i + 1 // 有效元素个数 = 最后下标 + 1
}

6 如何寻找最长回文子串

回文串就是正着读和反着读的结果都是一样的字符串。

比如：a，aba，abccba 都是回文串。

寻找回文串的核心思想是：从中间开始向两边扩散来判断回文串。

回文串的长度可能是奇数也可能是偶数。如果是 aba 这种情况，中心字符是 b，如果是 abba 这种情况，中心字符串是 bb。也就是说可以是 s[i] 为中心的回文串，也可以是 s[i] 和 s[i+1] 为中心的回文串。

/**
 * 截取最长回文子串
 * @param s 原始输入字符串
 * @return 字符串中最长的回文子串
 */
fun longestPalindrome(s: String): String? {
    if (s.isEmpty()) return ""

    val n = s.length

    var start = 0 // 回文字符串的起始位置
    var maxLength = 0 // 回文字符串的长度

    for (i in 0 until n) {
        // 奇数回文：以 s[i] 为中心，向左右两边扩展，处理奇数长度的回文字符串，aba
        val len1 = expandAroundCenter(s, i, i)
        // 偶数回文：以 s[i] 和 s[i+1] 为中心，向左右两边扩展，处理偶数长度的回文字符串 abccba
        val len2 = expandAroundCenter(s, i, i + 1)
        val len = len1.coerceAtLeast(len2)

        if (len > maxLength) {
            maxLength = len
            start = i - (len - 1) / 2
        }
    }

    return s.substring(start, start + maxLength)
}

/**
 *  从中心向两侧扩展，获取当前中心最长的回文长度
 *  @param s 原始字符串
 *  @param l 左边界
 *  @param r 右边界
 *  @return 合法回文串长度
 */
fun expandAroundCenter(s: String, l: Int, r: Int): Int {
    var left = l
    var right = r

    while (left >= 0 && right < s.length && s[left] == s[right]) {
        left--
        right++
    }
	
	// left 和 right 已经多走了一步，真正的回文区间是 [left + 1, right - 1]
	// 长度 = (right - 1) - (left + 1) + 1 = right - left + 1
    return right - left - 1 // 回文子串的长度
}

// longestPalindrome("abbacdeedc")

7 如何运用贪心思想广域玩跳跃游戏

7.1 跳跃游戏

给定义个非负整数数组 nums，你最初位于数组的第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

示例 1：

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

输出：true

解释：可以先跳 1 步，从下标 0 到达下标 1，然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

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

输出：false

解释：无论怎么样，总会到达下标为 3 的位置。但该下标最大跳跃长度为 0，所以永远不可能到达最后一个下标。

fun canJump(nums: Array<Int>): Boolean {
    val n = nums.size
    var farthest = 0

  	// 最后一个元素不用处理
    for (i in 0 until n - 1) {
        // 不断计算能跳跃的最远下标/位置，当前位置 = i + 能跳的步数 nums[i]
        farthest = farthest.coerceAtLeast(i + nums[i])

        // 碰到了 0，跳不动了，卡住
        if (farthest <= i) return false
    }
	
	// 最远位置 >= 最后一个下标，就能到达
    return farthest >= n - 1
}

val arr = arrayOf(2, 3, 1, 1, 4) // true
val arr = arrayOf(3, 2, 1, 0, 4) // false

7.2 跳跃游戏 II

给你一个非负整数数组 nums，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数达到数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例：

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

输出：2

解释：跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

fun jump(nums: Array<Int>): Int {
    val n = nums.size

    var jumps = 0 		// 记录跳跃了几次
    var end = 0 		// 当前跳跃范围的边界
    var farthest = 0 	// 能跳到的最远位置/下标

	// 最后一个不用跳
    for (i in 0 until n - 1) {
    	// 更新当前能到达的最远位置
        farthest = Math.max(farthest, i + nums[i])

        if (i == end) { 	// 到达当前能到达的最远位置，需要进行一次跳跃
            jumps++			// 步数 +1
            end = farthest	// 新边界 = 刚刚更新的最远位置
        }
    }

    return jumps // 返回最少步数
}

val arr = arrayOf(2, 3, 1, 1, 4)

i 和 end 标记了可以选择的跳跃步数，farthest 标记了所有选择 [i … end] 中能够跳到的最远距离，jumps 记录跳跃的次数。

为什么一定要 i == end 才跳？因为：只要你还没有走到当前这一跳的边界 end，就说明你还在这一跳的覆盖范围内，不需要开一次跳跃，只有当你走到了边界 i == end，才说明这一跳能走的路已经走完了，必须跳一次才能继续往前走。

8 如何 k 个一组，反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

• k 是一个正整数，它的值小于或等于链表的长度；
• 如果节点总数不是 k 的整倍数，那么，请将最后剩余的节点保持原有顺序；

输入：head = [1, 2, 3, 4, 5]，k = 2

输出：[2, 1, 4, 3, 5]

输入：head = [1, 2, 3, 4, 5]，k = 3

输出：[3, 2, 1, 4, 5]

输入：head = [1, 2, 3, 4, 5]，k = 1

输出：[1, 2, 3, 4, 5]

输入：head = [1]，k = 1

输出：[1]

反转 k 个节点后再挂回原来的节点（假设 k = 3）：

算法实现：

class ListNode(val value: Int) {
    var next: ListNode? = null
}

/**
 * 反转 [head, tail) 区间的节点
 */
fun reverse(head: ListNode?, tail: ListNode?): ListNode? {
    var pre: ListNode? = null
    var cur = head

    while (cur != tail) {
        val next = cur?.next
        cur?.next = pre
        pre = cur
        cur = next
    }

    return pre
}

/**
 * k 个一组反转链表
 */
fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
    // 1. 找到当前组的尾节点（即下一组的头节点）
    var tail = head

    repeat(k) {
        // 剩余节点不足 k 个，直接返回当前头节点
        if (tail == null) return head
        tail = tail?.next
    }

    // 2. 反转当前组（head 到 tail 前一个节点）
    val newHead = reverse(head, tail)

    // 3. 递归处理剩余链表，并连接当前组的尾节点（原 head）
    head?.next = reverseKGroup(tail, k)

    // 4. 返回当前组反转后的新头节点
    return newHead
}

fun main() {
    val head = ListNode(1).apply {
        next = ListNode(2).apply {
            next = ListNode(3).apply {
                next = ListNode(4).apply {
                    next = ListNode(5).apply {
                        next = ListNode(6).apply {
                            next = ListNode(7).apply {
                                next = ListNode(8).apply {
                                    next = ListNode(9)
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    val result = reverseKGroup(head, 3)

    var curr = result
    while (curr != null) {
        print("${curr.value} ")
        curr = curr.next
    }


}

递归过程（入栈）

• 第一步：初始调用 reversKGroup(1, 3)

  • 栈状态：[reversKGroup(1, 3)]

  • 执行：

    • 通过迭代 tail 指向 4；

    • 反转 1 —> 2 —> 3 得到 3 —> 2 —> 1，newHead = 3；

    • 递归调用 reverseKGroup(4, 3)；

• 第二步：递归调用（第一次）reverseKGroup(4, 3)

  • 栈状态：[reverseKGroup(1, 3), reverseKGroup(4, 3)]

  • 执行：

    • 通过迭代 tail 指向 7

    • 反转 4 —> 5 —> 6 得到 6 —> 5 —> 4，newHead = 6；

    • 递归调用 reverseKGroup(7, 3)

• 第三步：递归调用（第二次）reverseKGroup(7, 3)

  • 栈状态：[reverseKGroup(1, 3), reverseKGroup(4, 3),reverseKGroup(7, 3)]

  • 执行：

    • 通过迭代 tail 指向 null

    • 反转 7 —> 8 —> 9 得到 9 —> 8 —> 7，newHead = 9；

    • 递归调用 reverseKGroup(null, 3)

• 第四步：递归调用（第三次）reverseKGroup(null, 3)

  • 栈状态：[reverseKGroup(1, 3), reverseKGroup(4, 3),reverseKGroup(7, 3)]

  • 执行：

    • tail == null 成立，return null

递归返回过程（出栈）

• 第五步：递归返回/出栈（第一次）reverseKGroup(7, 3)

  • 接收返回值：null

  • 设置连接：head = 7，head.next = 7，即 9 —> 8 —> 7 —> null

  • 返回结果：newHead = 9

  • 栈状态：[reverseKGroup(1, 3), reverseKGroup(4, 3)]

• 第六步：递归返回/出栈（第二次）reverseKGroup(4, 3)

  • 接收返回值：9

  • 设置连接：head = 4，head.next = 4，即 6 —> 5 —> 4 —> 9

  • 返回结果：newHead = 6

  • 栈状态：[reverseKGroup(1, 3)]

• 第七步：递归返回/出栈（第三次）reverseKGroup(1, 3)

  • 接收返回值：6

  • 设置连接：head = 1，head.next = 6，即 3 —> 2 —> 1 —> 6

  • 返回结果：newHead = 3

  • 栈状态：[]

递归完成。

9 如何判定括号的合法性

我们要判断一个字符串中的括号是否合法。合法意味着：

1. 左边的括号必须用相同类型的右括号闭合；
2. 左括号必须以正确的顺序闭合；
3. 每个右括号都有一个对应的相同类型的左括号；

常见的括号包括：(、)、[、]、{、}。

我们可以使用栈来解决这个问题：

• 如果是左括号（(、[、{），则将其压入栈中；
• 如果是右括号（)、]、}），则检查栈顶元素是否是对应的左括号；
  • 如果栈为空，或者栈顶元素不是对应的左括号，则返回 false；
  • 如果匹配，则将栈顶元素弹出；

遍历结束后，如果栈为空，则说明所有括号都匹配，返回 true；否则返回 false。

注意：字符串中可能包含非括号字符，我们可以忽略这些字符，只处理括号。

9.1 算法思路

1. 遍历字符串：逐个检查每个字符；
2. 左括号入栈，遇到左括号（(、[、{）时，将其压入栈中；
3. 右括号匹配：遇到右括号（)、]、}）时：
   • 若栈为空，说明没有匹配的左括号，返回 false；
   • 若栈顶元素不匹配当前右括号，返回 false；
   • 若匹配，则弹出栈顶元素（表示匹配成功）；
4. 最终校验：遍历完成后，若栈为空，说明所有括号均匹配；否则有未闭合的括号，返回 false。

9.2 代码实现

fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>() // 1
    val mapping = mapOf(')' to '(', '}' to '{', ']' to '[') // 2 )=(, ]=[, }={

    for (char in s) {
        when (char) {
            '(', '{', '[' -> stack.addLast(char) // 左括号入栈
            ')', '}', ']' -> {
                if (stack.isEmpty() || stack.removeLast() != mapping[char]) { // 3
                    return false // 栈空或栈顶不匹配
                }
            }
            // 非括号字符串直接跳过
        }
    }
    return stack.isEmpty() // 栈空表示全部匹配
}

fun main() {
    println(isValid("()"))          // true
    println(isValid("()[]{}"))      // true
    println(isValid("(]"))          // false
    println(isValid("([)]"))        // false
    println(isValid("{[]}}"))       // false
    println(isValid(""))            // true 空字符串视为合法
}

关键点说明：

• 注释 1：栈的选择，使用 ArrayDeque 作为栈（高效双端队列），通过 addLast() 入栈，removeLast() 出栈；
• 注释 2：映射关系，通过 Map 存储右括号到左括号，方便快速匹配；
• 注释 3：边界处理，
  • 遇到右括号时，栈为空，直接返回 false；
  • 遍历结束后栈非空：有未闭合的括号，返回 false；

10 如何寻找消失的元素

10.1 寻找单个缺失的元素

题目描述： 给定一个包含 0, 1, 2, … , n 中 n 个数的数组，找到缺失的那个数。

示例： 输入 [3, 0, 1]，输出 2。

方法一：数学法（推荐）

思路： 计算 0 到 n 的和，减去数组元素的和，差值即为缺失的数。

fun findDisappearNumber(nums: IntArray): Int {
    val n = nums.size
    val sum = n * (n + 1) / 2
    val actualNum = nums.sum()

    return sum - actualNum
}

方法二：数学法，分阶段累加，避免溢出

方法一 中存在整型溢出风险。当数组的长度 n 很大时，n * (n + 1) /2 可能超过 Int 或 Long 的最大值。

fun findDisappearNumber(nums: IntArray): Int {
    var n = nums.size // 初始值为 n
    for (i in nums.indices) {
        n += i - nums[i]  // 累加差值，避免大数乘法
    }
    return n
}

测试：

val arr = intArrayOf(3, 0, 1)
println(findDisappearNumber(arr)) // 2

10.2 寻找所有消失的元素

题目描述： 给定一个长度为 n 的数组，其中每个元素都在 1 到 n 之间（包含），有些元素出现两次，有些出现一次，找出所有消失的元素。

**示例：**输入 [4, 3, 2, 7, 8, 2, 3, 1]，输出 [5, 6]

方法：原地标记法（推荐）

思路： 遍历数组，将元素对应的索引位置标记为负数，未被标记的索引即为消失的元素。

fun findDisappearNumber(nums: IntArray): List<Int> {
    // 标记出现过的元素
    for (num in nums) {
        val index = Math.abs(num) - 1
        if (nums[index] > 0) {
            nums[index] = -nums[index]
        }
    }

    // 收集未被标记的索引
    val result = mutableListOf<Int>()
    for (i in nums.indices) {
        if (nums[i] > 0) {
            result.add(i + 1) // 索引 +1 转换为元素值
        }
    }

    return result
}

11 如何寻找缺失和重复的元素

**题目：**给定一个长度为 n 的数组 nums，其中包含了从 1 到 n 的整数，但其中的一个数字重复出现了两次，同时有一个数字缺失。请找出重复的数字和缺失的数字。

**示例：**输入 [1, 2, 2, 4]，输出 [2, 3]

**思路：**遍历数组，将每个元素对应的索引位置标记为负数。若遇到已为负数的位置，则当前的元素为重复元素；最后未被标记的位置即为缺失元素。

方法：原地标记法

fun findErrorNums(nums: IntArray): IntArray {
    var duplicate = 0
    var missing = 0

    // 标记出现过的元素
    for (num in nums) {
        val index = Math.abs(num) - 1
        if (nums[index] < 0) {
            duplicate = Math.abs(num)  // 当前元素重复
        } else {
            nums[index] = -nums[index]  // 标记为负数
        }
    }

    for (i in nums.indices) {
        if (nums[i] > 0) {
            missing = i + 1
            break
        }
    }

    return intArrayOf(duplicate, missing)
}

12 如何高效的判断回文链表

回文链表： 一个链表从前往后读或从后往前读得到的序列是相同的。换句话说，量表的节点值序列是中心对称的。

示例：

• 奇数长度： 1 —> 2 —> 3 —> 2 —> 1 是回文链表
  • 正向：1，2，3，2，1
  • 反向：1，2，3，2，1
• 偶数长度： 1 —> 2 —> 2 —> 1 是回文链表
  • 正向：1，2，2，1
  • 反向：1，2，2，1
• 非回文示例：1 —> 2 —> 3
  • 正向：1，2，3
  • 反向：3，2，1

回文链表的特征：

• 对称性：链表的第一个节点和最后一个节点的值相同，第二个节点和倒数第二个节点的值相同，以此类推；
• 中心点：如果链表长度为奇数，则中心点只有一个节点；如果长度为偶数，则中心点在两个节点之间；

要高效的判断一个链表是否为回文链表，可以采用以下步骤：

1. 使用快慢指针找到链表的中点（慢指针一次一步，快指针一次两步，当快指针到达末尾时，慢指针在中点）；
2. 反转链表的后半部分；
3. 比较前半部分和反转后的后半部部分是否相同；
4. 恢复链表（如果需要保持原链表的结构，则再次反转后半部分并重新连接）；

图解：

链表的长度为奇数，快慢指针：

链表长度为偶数时，快慢指针

反转链表：

class ListNode(var value: Int) {
    var next: ListNode? = null
}

// 辅助函数，从数组中创建链表
fun createLinkedList(values: IntArray): ListNode? {
    if (values.isEmpty()) return null

    val head = ListNode(values[0])
    var curr = head
    for (i in 1 until values.size) {
        curr.next = ListNode(values[i])
        curr = curr.next!!
    }

    return head
}

fun reverseList(head: ListNode?): ListNode? {
    var prev: ListNode? = null
    var cur = head
    while (cur != null) { // 返回的是 prev，prev 要到最后一个非空节点，此时 cur == null
        val next = cur.next
        cur.next = prev
        prev = cur
        cur = next
    }
    return prev
}

fun isPalindrome(head: ListNode?): Boolean {
    // 空链表或单节点链表是回文
    if (head?.next == null) return true

    // 1. 快慢指针找中点
    var slow = head
    var fast = head
    while (fast?.next != null) { // fast 要到最后一个节点
        slow = slow?.next
        fast = fast.next?.next
    }

    // 2. 反转链表的后半部分
    var secondHalf = reverseList(slow)

    // 3 比较前半部分和反转后半部分
    var first = head
    var second = secondHalf
    var result = true

    while (first != null && second != null) {
        if (first.value != second.value) {
            result = false
            break
        }
        first = first.next
        second = second.next
    }

    // 4. 恢复链表的结构(可选)
    reverseList(secondHalf)

    return result
}

fun main() {
    val test1 = createLinkedList(intArrayOf(1, 2, 2, 1))
    println("测试用例1：${if (isPalindrome(test1)) "是回文" else "不是回文"}")

    val test2 = createLinkedList(intArrayOf(1, 2, 3))
    println("测试用例2：${if (isPalindrome(test2)) "是回文" else "不是回文"}")

    val test3: ListNode? = null
    println("测试用例3：${if (isPalindrome(test3)) "是回文" else "不是回文"}")

    val test4 = createLinkedList(intArrayOf(5))
    println(intArrayOf(5).contentToString())
    println("测试用例4：${if (isPalindrome(test4)) "是回文" else "不是回文"}")

    val test5 = createLinkedList(intArrayOf(1, 2, 3, 2, 1))
    println("测试用例5：${if (isPalindrome(test5)) "是回文" else "不是回文"}")

    val test6 = createLinkedList(intArrayOf(1, 2, 3, 4))
    println("测试用例6：${if (isPalindrome(test6)) "是回文" else "不是回文"}")
}

13 随机算法之水塘抽样算法

题目： 给你一个未知长度的链表，请你设计一个算法，只能遍历一次，随机地返回链表中的一个节点。这里说的随机是均匀随机（uniform random），也就是说，如果有 n 个元素，每个元素被选中的概率都是 1/n，不可以有统计意义上的偏差。

一般的想法是，我先遍历一遍链表，得到链表的总长度为 n，再生成一个 [1, n] 之间的随机数为索引，然后找到索引的节点，不就是一个随机的节点了吗？

但题目说了，只能遍历一遍链表，意味着这种思路不可行。题目还可以再泛化，给一个未知长度的序列，如何在其中随机的选择 k 个元素呢？

算法实现： 先解决抽取一个元素的问题，这个问题的难度在于，随机选择是「动态」的，比如，现在有 5 个元素，你已经随机选择了其中的某个元素 a 作为结果，但是现在再给一个新元素 b，你应该留着 a 还是将 b 作为结果呢，以什么逻辑选择 a 和 b 呢，怎么证明你的选择方法在概率上是公平的呢？

证明： 每个节点被选中的概率都是 1/n （n 是链表的长度）

• 对于第一个节点：它被选中的概率是 1（初始化），然后在遍历后续节点时，它被保留的概率是：1 - 1/2 = 1/2（当第二个节点时），然后乘以不被第三个节点替换的概率（1 - 1/3 = 2/3），以此类推，直到第 n 个节点。所以第一个节点最终被保留的概率为：1 * (1/2) * (2/3) * …* ((n-1)/n) = 1/n；
• 对于第 i 个节点：它被选中的条件是，在遍历它的时候，我们以 1/i 的概率选择了它（此时它成为候选），然后它不被后续的节点替代。不被后续节点替换的概率为：1/ i * (1 - 1/(i + 1)) * (1 - 1/(i + 2)) * …* (1 - 1/n) = 1/n；

class ListNode(val value: Int) {
    var next: ListNode? = null
}

/**
 * 从链表中随机返回一个节点的值，每个节点被选中的概率相等
 * @param head 链表头节点
 * @return 随机节点的值
 */
fun getRandom(head: ListNode): Int {
    var i = 0 // 用于记录当前遍历到第几个节点（从 1 开始）
    var res = 0 // 存在最终选中的节点值
    var p: ListNode? = head // 作为指针遍历链表

    while (p != null) {
        // 生成 [0, i) 范围内的随机数，等于 0 的概率为 1/i
        if (Random.nextInt(++i) == 0) {
            res = p.value
        }
        p = p.next
    }

    return res
}

// 测试示例
fun main() {
    // 构建测试链表：1 -> 2 -> 3 -> 4 -> 5
    val head = ListNode(1).apply {
        next = ListNode(2).apply {
            next = ListNode(3).apply {
                next = ListNode(4).apply {
                    next = ListNode(5)
                }
            }
        }
    }

    // 多次抽样验证均匀性
    val counts = IntArray(6) // [0, 0, 0, 0, 0, 0]，创建长度为 6 的数组，默认值为 0
    repeat(100000) {
        val value = getRandom(head)
        counts[value]++
    }

    // 打印概率分布
    // 打印概率分布
    println("节点\t出现次数\t概率")
    for (i in 1..5) {
        val probability = counts[i] / 10000.0
        System.out.printf("%d\t%d\t%.4f\n", i, counts[i], probability)
    }

}

同理，如果随机选择 k 个数，只要在第 i 个元素处以 k / i 的概率选择该元素，以 1 - k / i 的概率保持原有选择即可。

算法步骤：

• 初始化，将前 k 个元素放入水塘中；
• 对于第 i 个元素（i 从 k + 1 开始），以 k / i 的概率决定是否将其放入到水塘中（替换到水塘中的某个元素）；
  • 具体操作：生成一个 [0, i) 之间的随机数 r，如果 r < k，则用当前元素替换掉水塘中的第 r 个元素（注意水塘下标从 0 开始）；

算法证明：

• 对于前 k 个元素，在遍历到第 k + 1 个元素时，每个前 k 个元素被保留的概率 = 1 - (第 k + 1 个元素被选中且替换该元素的概率) = 1 - (k / (k + 1) * 1 / k) = k / k + 1；
• 因此，每个元素被选中的概率都是 k / n；

class ListNode(val value: Int) {
    var next: ListNode? = null
}


/**
 * 从链表中返回 k 个随机节点的值
 */
fun getRandom(head: ListNode?, k: Int): IntArray? {
    if (head == null || k <= 0) return null

    val res = IntArray(k)
    var p = head

    // 前 k 个元素先默认选上
    var j = 0
    while (p != null && j < k) {
        res[j] = p.value
        p = p.next
        j++
    }

    // 如果链表长度小于等于 k，直接返回
    if (j < k) {
        return res
    }


    var i = k
    while (p != null) {
        // 生成一个 [0, i) 之间的整数
        val randomIndex = Random.nextInt(++i)
        // 这个整数小于 k 的概率就是 k/i
        if (randomIndex < k) {
            res[randomIndex] = p.value
        }
        p = p.next
    }
    return res
}

// 测试示例
fun main() {
    val head = ListNode(1).apply {
        next = ListNode(2).apply {
            next = ListNode(3).apply {
                next = ListNode(4).apply {
                    next = ListNode(5)
                }
            }
        }
    }

    // 测试抽样 k=2 的情况
    val counts = IntArray(6)
    repeat(100000) {
        getRandom(head, 2)?.forEach { value ->
            counts[value] = counts[value] + 1
        }
    }

    // 理论上每个元素被选中次数约为 100000 * 2 / 5 = 40000
    // 打印概率分布
    println("节点\t出现次数\t概率")
    for (i in 1..5) {
        val probability = counts[i] / 100000.0
        System.out.printf("%d\t%d\t%.4f\n", i, counts[i], probability)
    }

}

14 如何调度考生的座位

问题描述

在考场里，一排有 N 个座位，编号分别为 0, 1, 2, …, N - 1。当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上（另外，如果考场里没有人，那么学生就坐在 0 号座位上）。

请实现 ExamRoom 类：

• ExamRoom(int N) 初始化考场，其中 N 是作为的数量；
• int seat() 让一个学生进入考场并坐下，返回该学生的座位编号；
• void leave(int p) 让坐在座位 p 上的学生离开考场。如果作为 p 上没有学生，什么也不做；

代码实现

class ExamRoom(num: Int) {

    private val n: Int = num // 座位总数
  	// 用于存储已被占用的座位号，初始化时，seats 为空
    private val seats: TreeSet<Int> = TreeSet() 

    /**
     * 获取新学生就坐的座位号
     *
     * @return 学生就坐的座位号
     */
    fun seat(): Int {
        var student = 0 // 用于存储新学生的座位号。如果考场中没有其他的学生，新学生的座位号为 0
      	// 如果 seats 集合不为空，说明考场中已经有学生就座，需要进一步计算新学生的座位
        if (seats.isNotEmpty()) { 
            // dist 用于存储当前找到的最大间隔
          	// 这里将第 1 个座位到 0 号座位的距离作为最初的最大间隔
            var dist = seats.first()
            var prev: Int? = null // 用于存储上一个已占用座位的座位号
            for (seat in seats) { // 遍历 seats 集合中的每个已占用座位
                if (prev != null) { // prev 不为空，即是否已经处理过至少一个座位
                    // // 计算当前位置和上一个位置之间的最大可插入位置的距离
                    val d = (seat - prev) / 2 
                    if (d > dist) {
                        // 如果当前间隔的距离大于之前记录的最大间隔 dist
                        // 则更新 dist 为当前间隔的距离
                        // 并更新 student 为上一个座位号加上间隔距离，即新学生应该坐在这个间隔的中间位置
                        dist = d
                        student = prev + d
                    }
                }
                prev = seat // 将当前座位号赋值给 prev，以便在下一次循环中使用
            }
            // 检查最后一个座位到最后一个已占用座位的距离是否是否大于之前记录的最大间隔 dist。
            // 如果是，则将新学生安排在最后一个座位
            if (n - 1 - seats.last() > dist) {
                student = n - 1
            }
        }
        seats.add(student)
        return student
    }

    fun leave(p: Int) {
        seats.remove(p)
    }

}

fun main() {
    val examRoom = ExamRoom(10)
    println(examRoom.seat()) // 0
    println(examRoom.seat()) // 9
    println(examRoom.seat()) // 4
    println(examRoom.seat()) // 2

    examRoom.leave(4)

    println(examRoom.seat()) // 5
}

初始化，val examRoom = ExamRoom(10)，此时：

n = 10
seats.size = 0

第 1 次执行 examRoom.seat()，此时：

student = 0
seats.isNotEmpty 不成立
seats.add(0)
seats.size = 1

第 2 次执行 examRoom.seat()，此时：

student = 0
seats.isNotEmpty 成立
dist = 0
prev = null
for(seat in seats){
  	seat = 0
  	prev != null 不成立
  	prev = 0
}
n = 10, seats.last = 0, 10 - 1 - 0 > 0 成立
student = 9
seats.add(9)
seats.size = 2

第 3 次执行 examRoom.seat()，此时：

student = 0
seats.isNotEmpty 成立
dist = 0
prev = null
// for 循环
for(seat in seats) {
  	seat = 0
  	prev != null 不成立
  	prev = 0
}
// 继续循环
for(seat in seats) {
  	seat = 9
  	prev != null 成立
  	prev = 0
    d = (9 - 0) / 2 = 4
  	4 > 0 成立
  	dist = 4
  	student = 0 + 4 = 4
  	prev = 9
}
// 循环结束
n = 10, seats.last() = 9, 10 - 1 - 9 > 0 不成立
seats.add(4)
seats.size = 3

第 4 次执行 examRoom.seat()，此时：

student = 0
seats.isNotEmpty 成立
dist = 0
prev = null
// for 循环
for(seat in seats) {
  	seat = 0
  	prev != null 不成立
  	prev = 0
}
// 继续循环
for(seat in seats) {
  	seat = 4
  	prev != null 成立
  	d = (4 - 0) / 2 = 2
  	2 > 0 成立
  	dist = 2
  	student = 0 + 2 = 2
  	prev = 4
}
// 继续循环
for(seat in seats) {
  	seat = 9
  	prev != null 成立
  	d = (9 - 4) / 2 = 2
  	2 > 2 不成立
  	prev = 9
}
n - 1 - seats.last(), 10 - 1 - 9 > 0 不成立
seats.add(2)
seats.size = 4

执行 examRoom.leave(4)：

seats.size = 4
seats.size = 3

再次执行 examRoom.seat()，此时：

student = 0
seats.isNotEmpty 成立
dist = 0
prev = null
// for 循环
for(seat in seats) {
  	seat = 0
  	prev != null 不成立
  	prev = 0
}
// 继续循环
for(seat in seats) {
  	seat = 2
  	prev != null 成立
  	d = (2 - 0) / 2 = 1
  	1 > 0 成立
  	dist = 1
  	student = 0 + 1 = 1
  	prev = 2
}
// 继续循环
for(seat in seats) {
  	seat = 9
  	prev != null 成立
  	d = (9 - 2) / 2 = 3
  	3 > 1 成立
  	dist = 3
  	student = 2 + 3 = 5
  	prev = 9
}
n - 1 - seats.last(), 10 - 1 - 9 = 0 > 0 不成立
seats.add(5)
seats.size = 4

15、16 Union - Find（并查集）

并查集是一种树形的数据结构。常用于处理与集合相关的合并与查询问题。例如，并查集可以快速合并两个不同的集合或者查询两个或更多的元素是否处于同一集合。

假设我们有一个含有若干条边的无向图，图中节点编号为 1 到 10。

通常情况下，并查集需要使用一个一维数组维护信息，又因为在开始时，每个节点都属于不同的集合，所以，我们初始化数组，如下图所示：

数组的第一个位置表示及节点 1 属于集合 1，第二个位置表示节点 2 属于集合 2，以此类推。

同时为了更直观地看到集合的合并情况，我们采用树形结果表示各集合的状态：

接下来，依次通过边来合并不同的集合。

对于第一条边，先通过数组查询节点 3 所属的集合：数组中节点编号 3 与集合编号 3 相同，所以节点 3 属于集合 3：

然后通过数组查询节点 6 所属的集合：数组中节点编号 6 与集合编号 6 相同，所以节点 6 属于集合 6。此时节点 3 和节点6 属于不同的集合，将节点 6 所属的集合信息改为 3，便能完成集合 3 与集合 6 的合并：

说明：如果不更改集合 6 的节点信息，将节点 3 所属的集合信息改为 6，也能达到相同的效果。在此次处理中，统一更改橙色提示框处对应的信息。

接下来继续处理第二条边。通过数组查询节点 5 所属的集合，数组中节点 5 与集合编号 5 相同，所以节点 5 属于集合 5，然后通过数组查询节点 3 所属的集合，数组中节点 3 与集合编号 3 相同，所以节点 3 属于集合 3，此时节点 5 与节点 3 属于不同的集合，将节点 3 所属的集合信息改为 5，完成集合 5 与集合 3 的合并：

对于第三条边，通过数组查询节点 1 所属的集合，数组中节点编号 1 与集合编号 1 相同，所以节点 1 属于集合 1，然后通过数据查询节点 5 所属的集合，数组中节点编号 5 与集合编号 5 相同，所以节点 5 属于集合 5，此时节点 1 与节点 5 属于不同的集合，将节点 5 所属的集合信息改为 1，完成集合 5 与集合 1 的合并：

对于第四条边，通过数组查询节点 4 所属的集合，，数组中节点编号 4 与集合编号 4 相同，所以节点 4 属于集合 4，然后通过数组查询节点 7 所属的集合，数组中节点编号 7 与集合编号 7 相同，所以节点 7 属于集合 7，此时，节点 4 与节点 7 属于不同的集合，将节点 7 所属的集合改为 4，完成集合 4 与集合 7 的合并：

对于第五条边，通过数组查询节点 8 所属的集合，数组中节点编号 8 与集合编号 8 相同，所以节点 8 属于集合 8，然后通过数组查询节点 9 所属的集合，数组中节点编号 9 与集合编号 9 相同，所以节点 9 属于集合 9，此时节点 8 与节点 9 属于不同的集合，将节点 9 所属的集合信息改为 8，完成集合 8 与集合 9 的合并：

对于第六条边，通过数组查询节点 9 所属的集合，数组中节点编号 9 与集合编号 8 不相同，当节点编号与集合编号不同时，可以理解为，节点 9 与节点 8 处于同一集合，所以我们可以寻找节点 8 所属的集合，数组中节点编号 8 与集合编号 8 相同，所以节点 8 属于集合 8，以为节点 9 与节点 8 处于同一集合，所以节点 9 属于集合 8。然后通过数组查询节点 10 所属的集合，数组中节点编号 10 与集合编号 10 相同，所以节点 10 属于集合 10，此时节点 9 与节点 10 属于不同的集合，将节点 10 所属的集合信息改为 8，完成集合 8 与集合 10 的合并：

对于第七条边，通过数组查询节点 2 所属的集合，数组中节点编号 2与集合编号 2 相同，所以节点 2 属于集合 2，然后通过数组查询节点 10 所属的集合，数组中节点编号 10 和集合编号 8 不相同，继续寻找节点 8 所属的集合，数组中节点编号 8 与集合编号 8 相同，所以节点 10 属于集合 8，此时节点 2 与节点 10 属于不同的集合，此时，节点 2 和节点 10 属于不同的集合，将节点 8 所属的集合信息改为 2，完成集合 2 与集合 8 的合并：

对于第八条边，通过数组查询节点 10 所属的集合，数组中节点编号 10 与集合编号 8 不相同，继续寻找节点 8 所属的集合，数组中节点编号 8 与集合编号 2 不相同，继续寻找节点 2 所属的集合，数组中节点编号 2 与集合编号 2 相同，所以节点 10 属于集合 2，然后通过数组查询节点 7 所属的集合，数组中节点编号 7 与集合编号 4 不相同，继续寻找节点 4 所属的集合，数组中节点编号 4 与集合编号 4 相同，所以，节点 7 属于集合 4，此时，节点 10 与节点 7 属于不同的集合，将节点 4 所属的集合信息改为 2，完成集合 2 与集合 4 的合并：

处理完所有的编号后，我们获得了两个集合。假设我们现在有一个查询问题，判断节点 6 与节点 8 是否处于同一个集合。首先通过数组查询节点 6 所属的集合，数组中节点编号 6 与集合编号 3 不相同，继续寻找节点 3 所属的集合，数组中节点编号 3 与集合编号 5 不相同，继续寻找节点 5 所属的集合，数组中节点编号 5 与集合编号 1 不相同，继续寻找节点 1 所属的集合，数组中节点编号 1 与集合编号 1 相同，所以节点 6 属于集合 1，然后通过数组查询节点 8 所属集合，数组中节点编号 8 与集合编号 2 不相同，继续寻找节点 2 所属的集合，数组中节点编号 2 与集合编号 2 相同，所以节点 8 属于集合 2，因此节点 6 和节点 8 属于不同的集合：

查询的复杂度较高，所以对并查集进行优化，这种优化成为路径压缩，在我们第一次查询节点 6 所属的集合时，我们已经知道，节点 6、3、5、1 均属于集合 1，所以，我们可以一次将它们在数组中对应的集合编号更改为 1，此时，我们查询节点 6 所属的集合是，只需要访问节点 6 和 1 两个节点，时间复杂度大大降低了：

并查集的代码实现：

class UnionFind(size: Int) {

    /**
     * 初始化时，每个数组的父节点是它自己（parent[i] == i）
     * 通过 find 方法查找根节点时，会更新父节点以实现路径压缩
     */
    private val parent = IntArray(size) { it }

    /**
     * 表示以当前元素为根的树的深度（秩）
     */
    private val rank = IntArray(size) { 1 }


    /**
     * 查找元素所属的集合，通常用根节点表示（带路径压缩优化）
     */
    fun find(x: Int): Int {
        if (parent[x] != x) {
            parent[x] = find(parent[x]) // 路径压缩
        }
        return parent[x]
    }

    /**
     * 合并元素 x 和 y 所在的集合（按秩合并优化），按秩合并可以避免树过深，提高效率
     */
    fun union(x: Int, y: Int) {
        val rootX = find(x)
        val rootY = find(y)

        if (rootX == rootY) return // 已经在同一个集合中

        // 按秩合并：将深度较小的树合并到深度较大的树
        if (rank[rootX] > rank[rootY]) {
          	// 将 rootY 合并到 rootX 的树中
            parent[rootY] = rootX
          	// 由于 rootX 的树更高，合并后 rootX 的高度不会增加。不需要 rank[rootX]++
        } else if (rank[rootX] < rank[rootY]) {
          	// 将 rootX 合并到 rootY 的树中
            parent[rootX] = rootY
          	// 由于 rootY 的树更高，合并后 rootY 的高度不会增加。不需要 rank[rootY]++
        } else {
            parent[rootY] = rootX
            rank[rootX]++ // 高度相同，合并后高度 + 1
        }
    }

    /**
     * 判断元素 x 和 y 是否在同一个集合中
     */
    fun isConnected(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }

}


fun main() {
    val uf = UnionFind(10)

    uf.union(1, 2)
    uf.union(2, 3)
    uf.union(4, 5)

    println(uf.isConnected(1, 3)) // true
    println(uf.isConnected(1, 4)) // false

    uf.union(3, 4)
    println(uf.isConnected(1, 5)) // true
}

第 1 步：val uf = UnionFind(10)， 数组初始化：

第 2 步：uf.union(1, 2)：

第 3 步：uf.union(2, 3)：

第 4 步，uf.union(4, 5) ：

第 5 步，uf.union(3, 4) ：

17 一行代码就能解决的算法题

17.1 Nim 游戏

Nim 游戏是一个经典的数学游戏，规则如下：

• 有一堆石头，两个玩家轮流取石头。
• 每次可以取走 1 到 3 块石头。
• 取走最后一块石头的玩家获胜。

这个游戏的关键在于 石头的数量是否是 4 的倍数：

• 如果石头数量是 4 的倍数，先手必输。
• 否则，先手可以通过策略确保胜利。

因此，解决这个问题的算法非常简单：只需要判断石头数量是否不是 4 的倍数即可。

代码实现：

fun canWinNim(n: Int): Boolean = n % 4 != 0

17.2 石头游戏

石头游戏（Stone Game）是一个经典的博弈论问题。问题的描述如下：

• 有一排石头堆，每堆石头有一定数量的石头。
• 两个玩家轮流进行游戏，每次可以从当前石头堆的最左端或最右端取走一堆石头。
• 游戏结束时，取走石头总数最多的玩家获胜。

这个问题的关键在于：先手玩家总能获胜。因为先手玩家可以采取策略确保自己取走的石头总数不少于对手。

因此，解决这个问题的算法非常简单：直接返回 true，表示先手玩家总能获胜。

代码实现：

fun stoneGame(piles: IntArray): Boolean = true

17.3 电灯开关问题

电灯开关问题（Bulb Switcher）是一个经典的数学问题。问题的描述如下：

• 有 n 盏电灯，初始状态都是关闭的。
• 进行 n 轮操作：
  • 第 i 轮操作会切换所有第 i 的倍数的电灯的状态（即打开关闭的电灯，或关闭打开的电灯）。
• 问：经过 n 轮操作后，有多少盏电灯是打开的？

规律发现： 最终亮着的电灯编号是 1，4，9 —— 即 1²、 2²、 3²，n 以内的完全平方数。

核心原理：约数的奇偶性

• 电灯的切换次数 = 其编号的「约数个数」，而约数个数的奇偶性由编号是否为「完全平方数」决定；
• 约数的性质： 约数总是成对出现（如 6 的约数 1&6、2&3），因此大多数的约数个数是偶数；
• 完全平方数的特殊性： 完全平方数的平方根是唯一的（如 4 的平方根是 2），会导致约数出现重复（如 4 的约数 2 只出现一次），因此，完全平方数的约数个数是奇数；
• 综上：只有编号为完全平方数的电灯，会被奇数次切换，最终保持亮着的状态；

因此，解决这个问题的算法非常简单：只需要计算 n 以内的完全平方数的个数，即 sqrt(n) 的整数部分。

代码实现：

fun bulbSwitch(n: Int): Int = Math.sqrt(n.toDouble()).toInt()

18 二分查找高效判定子序列

题目： 如何判定字符串 s 是否是字符串 t 的子序列。

例如：

• s = “abc”，t = “ahbgdc”，返回 true；
• s = “axc”，t = “ahbgdc”，返回 false；

18.1 双指针法

fun isSubsequence0(s: String, t: String): Boolean {
    var i = 0
    var j = 0

    while (i < s.length && j < t.length) {
        if (s[i] == t[j]) i++
        j++
    }
    return i == s.length
}

18.2 二分查找法

我们可以通过预处理字符串 t，构建一个字符到索引列表的映射表，然后利用二分查找来高效判断字符串 s 是否是 t 的子序列。以下是完整的 Kotlin 实现：

1. 预处理 t：

   • 使用一个 Map<Char, List<Int>> 来存储每个字符在 t 中的所有出现位置（索引）。

2. 遍历 s：

   • 对于 s 中的每个字符，在映射表中查找是否存在，并且其索引必须大于前一个字符的索引。
   • 使用二分查找（binarySearch）快速找到满足条件的最小索引。

3. 代码实现：

fun isSubsequence(s: String, t: String): Boolean {

    // 预处理 t，构建字符串到索引列表的映射
    var charToIndex = mutableMapOf<Char, ArrayList<Int>>()
    for ((index, char) in t.withIndex()) {
        charToIndex.getOrPut(char) { arrayListOf() }.add(index)
    }

    // 初始化前一个字符的索引
    var preIndex = -1

    // 遍历 s 中的每个字符
    for (char in s) {
        // 如果字符不在映射表中，直接返回 false
        val indices = charToIndex[char] ?: return false
        // 在 t 中查找大于 preIndex 的字符 char 的最小索引
        val pos = binarySearch(indices, preIndex)
        // 如果找不到符合条件的索引，说明 s 不是 t 的子序列，返回 false
        if (pos == indices.size || indices[pos] <= preIndex) return false
        // 更新 preIndex
        preIndex = indices[pos]
    }

    return true
}

// 在有序的整数列表 arr 中，通过二分查找找到第一个大于目标值 preIndex 的元素的索引（即「左边界」）
fun binarySearch(arr: ArrayList<Int>, preIndex: Int): Int {
    // 处理列表为空的情况
    if (arr.isEmpty()) return 0

    // 二分查找的左、右边界
    var lo = 0
    var hi = arr.size - 1

    // 当左边界小于右边界时，继续查找
    while (lo < hi) {
        // 计算中间位置
        val mid = lo + (hi - lo) / 2
        // 如果中间元素小于目标值，说明目标值在右半部分，更新左边界
        if (preIndex > arr[mid]) {
            lo = mid + 1
        } else {
            // 否则，目标值在左半部分，更新右边界
            hi = mid
        }
    }
    // 返回最终找到的左边界
    return lo
}

二分查找法分析：

arr = arrayListOf(0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)，preIndex = 2：

arr = arrayListOf(0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)，preIndex = 3：

arr = arrayListOf(0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12)，preIndex = 8

arr = arrayListOf(0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12)，preIndex = 9