算法综合设计实验题解
题目不分先后顺序，仅以个人做题顺序为准。
21 合并两个有序链表
正常可使用双指针法遍历，但还可以用递归实现。
60 排序序列
试画出递归树，发现第 m m m 层分支下有 ( n − m ) ! (n-m)! (n−m)! 个情况。于是可以依次考察 k k k 对 ( n − 1 ) ! (n-1)! (n−1)! 到 1 ! 1! 1! 的模 r r r，其为剩余数字按顺序的第 r r r 个。分析边界问题：确定倒数第2位时，也确定了最后一位，即 1 ! = 1 1!=1 1!=1 同时序数从 0 0 0 开始。
此即逆康托展开。
143 重排链表
经典链表算法的结合：①快慢指针法找到链表中间结点；②对中间节点以后的部分进行三指针迭代翻转；③交错合并两个链表。
（注：分割链表时前链表尾指针需维护或指向空）
233 数字 1 的个数
数学题，关键在于正确写出计数表达式：
⌊ n 1 0 i + 1 ⌋ 1 0 i + min { max { n ( m o d 1 0 i + 1 ) − 1 0 i + 1 , 0 } , 1 0 i } . \lfloor \frac{n}{10^{i+1}}\rfloor10^i+\min\{\max\{n({\rm mod}\ 10^{i+1})-10^i+1,0\},10^i\}. ⌊10i+1n⌋10i+min{max{n(mod 10i+1)−10i+1,0},10i}.
342 4 的幂
掩码 (mask) 题： 2 2 2 的幂二进制中至多有 1 1 1 位为 0 0 0；在此基础上 4 4 4 的幂二进制中 1 1 1 只能出现在低位开始的偶数位上。
55 跳跃游戏
不难发现导致无法抵达终点的只有出现数字 0 0 0 的情况，反向遍历并记录所需跨度，最终跨度大于 1 1 1 等效于起点数字为 0 0 0。
134 加油站
正向遍历，若 x x x 无法抵达 y + 1 y+1 y+1，那么 x x x 到 y y y 间的任何一点也都不可能抵达 y + 1 y+1 y+1，从而剪支。
但还可以采用反向遍历，转而考虑额外油量需求：不存在解时需求为正；存在解时出发点一定为使得需求最小的点。
135 分发糖果
可以转而考察递增递减序列：递增序列中下一位比上一位多 1 1 1，递减序列中每多一位则前面所有位均多 1 1 1 （即增加序列长度值）。
边界情况：不增不减时，序列结束；递减序列长超过前面递增序列长时，递增序列的末位视为递减序列的初位。
605 种花问题
当前位置和前后位置都为 0 0 0 时待种花数 − 1 -1 −1，待种花为 0 0 0 时可直接返回以剪支。
46 全排列
回溯，全部数字选完时抵达叶子结点，载入记录每层剩余数字情况。
51 N 皇后
回溯，以行为分支，列为深度；递归遍历时判断是否合法，仅当合法时写入Q；判断合法时仅需判断列、左上、右上。
77 组合
回溯，全部数字选完时抵达叶子结点，载入遍历起点。
70 爬楼梯
动规入门， f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n)=f(n-1)+f(n-2) f(n)=f(n−1)+f(n−2)。
124 二叉树中的最大路径和
回溯，叶子结点返回 0 0 0，根节点返回根值与左右子树值中最大的和。根节点处最大值可能为：①左右子树最大值与根植和；②子树中的最大值。
997 找到小镇的法官
图论入门，即找到入度为 n − 1 n-1 n−1 的顶点。
148 排序链表
归并：①快慢指针法找到链表中间结点；②合并两个有序链表。
（注：分割链表时前链表尾指针需维护或指向空）
62 不同路径
不难发现路径数为 ( n + m − 2 m − 1 ) = ( n + m − 2 n − 1 ) {n+m-2 \choose m-1}={n+m-2 \choose n-1} (m−1n+m−2)=(n−1n+m−2)。
53 最大子数组和
记 f ( i ) f(i) f(i) 为以 i i i 位置结尾的最大子数组和，即求 max { f ( i ) } i = 1 n − 1 \max\{f(i)\}_{i=1}^{n-1} max{f(i)}i=1n−1；不难发现 f ( i − 1 ) ≤ 0 f(i-1)\leq 0 f(i−1)≤0 时， f ( i ) = n u m s [ i ] f(i)={\rm nums}[i] f(i)=nums[i]。
797 所有可能路径
DFS，深搜。
198 打家劫舍
动规， f ( i ) = max { f ( i − 2 ) + n u m s [ i ] , f ( i − 1 ) } f(i)=\max\{f(i-2)+{\rm nums}[i],f(i-1)\} f(i)=max{f(i−2)+nums[i],f(i−1)}。
621 任务调度器
贪心，按任务出现次数从最大到最小排布。
23 合并 K 个升序链表
分治，每层合并相邻的两个链表。
95 不同的二叉搜索树 II
二叉搜索树左子树值一定都比根节点小，右子树值一定都比根节点大，由此进行递归。
120 三角形最小路径和
自下向上原地修改数组， f ( i , j ) = min { f ( i + 1 , j ) , f ( i + 1 , j + 1 ) } + t r i [ i ] [ j ] f(i,j)=\min\{f(i+1,j),f(i+1,j+1)\}+{\rm tri}[i][j] f(i,j)=min{f(i+1,j),f(i+1,j+1)}+tri[i][j]；由于出发点唯一， f ( 0 , 0 ) f(0,0) f(0,0) 即为所求。
1446 重复规划路线
遍历结点集，使用 “1” 标记原方向边，使用 “0” 标记反方向边；从 “0” 出发 dfs，遇到 “1” 边则修改数量 + 1 +1 +1。
327 区间和个数
线段树，动态区间查询。
654 最大二叉树
单调栈。