几道Leetcode题解
最近在 leetcode 上做了寄到练习题，运气很好，最新的几道 hard 题目都是少量代码可以搞定的。
image
773. Sliding Puzzle
https://leetcode.com/problems/sliding-puzzle/description/
题目大意：给你一个 2x3 的board，例如：
[
[1, 2, 3],
[4, 5, 0]
]
你只能移动 0，问最少需要多少步可以变成排列和上面一样的board。
我的解法：因为数量少，所有的board数量才 6! = 720 个，直接用BFS，注意一下用动态语言搜的时候，下一个board入队的时候要注意重复引用的问题，在ruby里面我是用 Marshal.load(Marshal.dump(top)) 来处理的。
891. Sum of Subsequence Widths
https://leetcode.com/problems/sum-of-subsequence-widths/description/
题目大意：一个整型数组 A，对于A的所有非空子序列，定义这个序列的宽度是序列里面最大值和最小值的差，求A所有非空子序列的宽度之和。
我的解法：
A的长度最大是 20000，naive的解法是 O(n^2)，但是所有子序列只需要知道最大和最小值，所以先将数组A排序，只需要计算例子中每个数字在所有子序列里面是最小值和最大值的次数。
例子 [2, 1, 3] 排序后就是 [1, 2, 3]
1是最小值的子序列就是 [1] [1, 2] [1, 3] [1, 2, 3]，用0来代表不选择，用1来代表选择的话，那么上面子序列[2, 3]的二进制位表示就是00 01 10 11，yes，二进制。
同理可以知道 1 是最大值的子序列数是 2^i where i=0 is the index of 1，2^0=1 1是最大值时的子序列就是 [1]。
因为题目要求答案最后要模 10^9 + 7，所以我用 python，pow 函数很好用。
895. Maximum Frequency Stack
https://leetcode.com/problems/maximum-frequency-stack/description/
题目大意：设计一个FreqStack，要求能实现入栈和出栈，出栈的要求是，元素数量多的先出栈，数量一样多的元素实现LIFO。
例子
push 5
push 7
push 5
push 7
push 4
push 5
pop # 返回5，因为 5 的数量最多
pop # 返回7，此时 5 和 7 数量都是 2，但是 7 最后入栈
pop # 返回5
pop # 返回4
我的解法：
维护一个字典保存每个元素的数量，每个数量一个单独的栈，同时用一个数字max维护当前最大的单个元素数量
当一个空栈依次 push 完 5, 7, 5, 7, 5, 4的时候
stackByCount: {"1":[5,7,4],"2":[5,7],"3":[5]}
countByNum = {"4":1,"5":3,"7":2}
max = 3
push num 的时候先自增 countByNum[num]，然后stackByCount[countByNum[num]].push(num)，按需更新max值
pop 的时候直接 popNum = statckByCount[max].pop()，同时更新 countByNum[popNum]，如果 statckByCount[max] 变空了还要更新 max
数量的增长也可以看成是 LIFO，这样看的话用一个二维数组就可以减少一个max变量，更加优雅。
899. Orderly Queue
https://leetcode.com/problems/orderly-queue/description/
题目大意：给一个字符串 S 和一个数字 K，每一次操作可以把前K个字符中的一个字符删掉然后贴到当前字符串的末尾，求任意多次操作后可以得到最小的字符串。
我的解法：
K = 1 的时候直接模拟操作，没什么好说的
K >= 2 的时候，不难发现 K = 2 的时候就可以对任意相邻两个字符排序了，那么经过任何多次操作后字符串里面的字符排列都是有序的，这就是经典的 Javascript 面试题答案了 return s.split('').sort().join('');
878. Nth Magical Number
https://leetcode.com/problems/nth-magical-number/description/
题目大意：给出N, A, B 三个数字，求第 N 个能被 A 或 B整除的数字。
我的提示:
- 答案不会大于 10^18
- 会列出 100 以内能被 5 或 3 整除的数字你就会做了
- 会写正确的二分查找你就能做对这道题了
- 求最大公约数和最小公倍数的代码可以网上找
最后总结：
Leetcode的题不难，锻炼脑筋最合适。
