[数据结构与算法]ARTS挑战第十七周

Algorithm

【前序遍历，备忘录】96. 不同的二叉搜索树

使用helper(left,right)进行递归计算。构造二叉树为前序遍历过程.

? 先选定root节点，确定root节点后，总的树的数量就是左子树的种类 x 右子树的种类

? |–如果left >= right 返回1（乘法）

? |–枚举【left,right】闭区间的所有元素作为根节点i

? |–sum+=helper(left,i-1)*helper(i+1,right)

? |-- 返回sum

? 可以使用备忘录减少重复子问题

【后序遍历】95. 不同的二叉搜索树 II

后序遍历，使用helper(left,right)进行递归，函数返回根节点列表

? 这里使用后序而不是前序是因为对于每一个组合都要构建新的root节点

? |–如果left>right return [nullptr]

? |–遍历 i in 【left，right】

? |–leftChildren=helper(left,i-1)

? |–rightChildren=helper(i+1,right)

? |–for lc in leftChildren

? |–for rc in rightChildren

? |–根据i，lc，rc构造树

? |–将i加入结果集

【快速选择】215. 数组中的第K个最大元素

第k大的数在升序数组中下标为n-k

? 使用快速选择法，函数输入为left,right,target

? |–使用partition函数得到partition后的index

? |–如果index=target，则返回当前index对应值

? |–如果index<target, 则在右区间【index+1，right】递归寻找

? |–如果index>target, 则在左区间【left，index-1】递归查找

【DFS回溯】46. 全排列

? DFS回溯算法backtrack(nums,trace,cur)

? 路径：trace为已经做的选择

? 选择列表：cur帮助当下进行选择，由于全排列问题是一步一步的确定每一个位置的数，cur表示当前选到哪个位置了

? 结束条件：cur >= nums.size

? |–如果达到结束条件，则将trace加入结果集

? |–做选择：对于cur以及其后面的所有的元素i

? |–并将元素i加入trace,将cur元素与i交换

? |–backtrack(nums,trace,cur+1);

? |–将元素i从trace中删除,将cur元素与i交换

【回溯】78. 子集

回溯算法：

trace 当前集合的元素,进入函数时将当前trace加入结果集

choice 从start开始往后选择一个backtrack中只能往start后面开始选

end start >= nums.size()

【回溯】37. 解数独

trace：棋盘

choice：使用r，c表示当前位置，则如果当前位置为’.’，尝试所有1~9的数。如果数字满足要求，则往右递归，如果无法往右则往左下走

end：r==9，返回true

【回溯】494. 目标和

回溯算法：trace 无需保存；choice：当前位置为i，则可以选择+或-，对应target-或+；end：i==nums.size

时间复杂度O(2^n), 可以使用备忘录加速。

【BFS】752. 打开转盘锁

BFS解题框架，主要容易疏漏的地方在于visited集合的更新以及每一层内循环大小为队列当前大小，应该使用一个变量来控制这个循环大小。

【BFS】773. 滑动谜题

要点：1）转换成一维字符串。2）将每个位置的neighbor提前算出来放到数组里。

【位运算】191. 位1的个数

利用n&(n-1) 消除二进制表示的最后一个1，直到n=0.统计循环执行的次数

【位运算】231. 2 的幂

要点：1）小于0的不是2的幂；2）n&(n-1) 来统计1的个数或者 判断n 是否等于 n&(-n)

【数学运算】 172. 阶乘后的零

零出现的个数就是因子分解后，2*5 出现的个数。因子2的个数多于因子5的个数，因此只需计算n的阶乘中因子5的个数

? 首先被5整除的数是间隔5出现一个，它能贡献1个因子：5, 10, 15…

? 然后被25整除的数是间隔25出现一个，它能贡献2个因子：25, 50, 75…

? …

? 因此，1,…,n这n个数中，能被5整除的数做多有n/5个，能被25整除的有n/25个全部加起来就好了

【数学运算】793. 阶乘函数后 K 个零

? 统计因子5的个数的方法来计算n!末尾有多少0，即函数f的作用。

? 显然x越大，0越多，因此f函数是单调递增函数，从而可以采用二分搜索法找到f(x)=K的左右边界，然后用右边界减去左边界+1.

? 二分搜索的右边界可以初始化为LLONG_MAX-1

【数学运算，分治】372. 超级次方

? 分治思想：a¹ = a^3 * (a^[1,2])10

? pow(int a, int b) 表示 a^b，则 a^b = a*a^(b-1) 如果b为奇数，a^b = (a^(b/2))2 如果b为偶数

? 注意数据溢出问题。

【数组操作】26. 删除有序数组中的重复项

使用快慢指针算法，问题关键不是找重复的元素，而是找不重复的元素，并将它放到它应该在的位置。

|–使用慢指针初始化为第一个不重复元素，快指针同样指向慢指针

|–while快指针没有走到头：

? |–当快指针指向的元素与慢指针指向的元素相同时，仅快指针继续前进

? |–否则快指针指向的是下一个不重复的元素，与慢指针的下一个位置的元素交换位置，快慢指针均前进

|–最后慢指针所在的位置是最后一个不重复元素的位置，数组大小为slow+1

【动态规划】416. 分割等和子集

? step1：状态：当前需要考虑的元素i，以及当前背包的容量

? 选择：是否将当前元素放入背包

? step2：定义：dp(i,j)表示前i个元素是否能恰好填满容量为j的背包。dp(0,…)=false,dp(…,0)=true

? step3：状态转移：dp(i,j) = dp(i-1,j-nums[i-1])|dp(i-1,j)

【动态规划】322. 零钱兑换

step1：状态。硬币i，总金额j。选择。硬币i选择放入一个以上或不放入

step2：定义。dp(i,j)表示使用前i个硬币至少需要多少个硬币才能凑成金额j。base case. dp(0,j)=99999表示不可能, dp(i,0)=0，dp(0,0)=0

step3：状态转移。dp(i,j)=min(dp(i-1,j),dp(i,j-coins(i))+1)

【动态规划】712. 两个字符串的最小ASCII删除和

step1: 状态，(i,j)表示s1的第i个字符和s2的第j个字符。选择，是否删除这两个字符

step2：定义。dp(i,j)表示s1前i个字符和s2前j个字符的最小ASCII删除和。base case.

? dp(0,j)=sum(s2[0…j-1]) dp(0,0)=0;

step3: 状态转移。如果s1[i-1]==s2[j-1],dp(i,j)=dp(i-1,j-1).否则，dp(i,j) = min(dp(i-1,j-1)+s1[i-1]+s1[j-1],dp(i-1,j)+s1[i],dp(i,j-1)+s2[j])

【差分数组】1109. 航班预订统计

Review

阿里面试官问我：如何设计秒杀系统？

秒杀系统需要解决的问题：

1. 高并发：时间极短，瞬间用户量大。涉及到缓存雪崩、缓存击穿、缓存穿透等问题，还有Redis的一写多读集群，nginx 负载均衡，资源静态化，按钮控制，库存预热等。
2. 超卖：Redis 使用Lua脚本实现原子性
3. 链接暴露：链接加盐
4. 影响其它服务：隔离，服务单一职责

服务熔断、隔离、降级、限流 介绍

• 服务降级：在高并发的情况下，防止用户一直等待，使用服务降级方式进行处理（返回友好的提示给客户端）
• 服务隔离：每个服务接口不相互影响。可以让每个服务设置自己的线程池，或者使用信号量的方式控制每个服务的最多访问次数。
• 服务熔断：在高并发的情况下，如果达到一定的极限，直接拒绝访问。
• 服务限流：使用限流算法控制服务器处理请求的速度

Tips

1. 最长公共子串与最长公共子序列是有区别的。
2. caplock+这个软件可以把caplocks键映射成类似ctrl这样的控制键，并且有很多快捷键。基本可以实现类似HHKB一样，上下左右啥的都不需要手移动到键盘右下角去了。

Share

• 贝尔曼福特和迪杰斯特拉算法区别
• 最长公共子序列与最长公共子串区别