练手的题:
331. Verify Preorder Serialization of a Binary Tree
334. Increasing Triplet Subsequence
341. Flatten Nested List Iterator
347. Top K Frequent Elements
356. Line Reflection
357. Count Numbers with Unique Digits
351. Android Unlock Patterns
355. Design Twitter
361. Bomb Enemy
365. Water and Jug Problem *
372. Super Pow *
377. Combination Sum IV * 这道题我倒是真的不是很会,比较诡异的背包思路
378. Kth Smallest Element in a Sorted Matrix: 试一遍按值二分法 * 二分法有点超纲啊
368. Largest Divisible Subset
376. Wiggle Subsequence
380. Insert Delete GetRandom O(1) *
375. Guess Number Higher or Lower II
385. Mini Parser
386. Lexicographical Numbers
不会的题:
324. Wiggle Sort II:又是一道万年不会的题(沉下心做了做竟然AC,开心),基本的想法是把比较大的倒序放在前面偶数位,比较小的正序放在后面奇数位,然后把剩下的位置插入中间值。只是如何实现O(1)的空间复杂度,比较麻烦。要注意的是我现在的quickselect的模板只能保证选出中位数,并不能实现中位数区分左右两边,因为有重复的中位数。比如说quickselect完找到5这个数但是会出现[3,1,2,5,6,7,8,5,5] 这种情况,也就是说所有5这个值在数组中并没有完全被放到中间位置。出现这种情况的时候,要再一次做partition,利用head和tail依次复制的那种方法就可以了loop两遍,很好写。 *
332. Reconstruct Itinerary: 又是一道不太会的题目,好像得先画画图理解下数学原理,然后再去做才行 *
382. Linked List Random Node: 蓄水池采样法