324. Wiggle Sort II的题目大意为：

给你n个无序的数nums, 让你输出如下的顺序: nums[0] < nums[1] > nums[2] < nums[3]….

并且希望算法是O(n)的时间复杂度，O(1)的额外空间复杂度。

有这么一个问题，有一个10万条记录的文件，每条记录有两列，分别是用户一次访问在两个服务器上留下的两条cookie记录，可以记作cookie A 和 cookie B。同一个用户的多次访问记录，cookie可能相同，也可能不同（cookie有时效性）。任意两条数据i,j ，如果cookie A相同或者cookie B相同，则认为i, j 是同一个用户留下的记录。同一个用户留下的访问记录可以合并，输出每个用户的所有cookie。例如有文件记录如下(用小写字母表示cookie)：

面试的时候，有遇到这样一个问题：给你一个文件，每一行是一个IP段，IP段之间互不交叉。以后会给你很多IP，让你判断在不在这些IP段中，如果在则返回对应IP段。
文件格式可能如下:

125.25.59.1, 125.25.129.42
200.24.1.35, 250.142.0.0

136. Single Number题目大意为:
给出一个数组，其中只有一个数字出现了一次，其他数字都出现两次，找出只出现一次的数字。

137. Single Number II题目大意为:
给出一个数组，其中只有一个数字出现了一次，其他数字都出现了三次，找出只出现一次的数字。

260. Single Number III题目大意为:
给出一个数组，其中有两个数字出现了一次，其他出现两次，找出那两个出现一次的数字。

这三道题是一个系列，且非常类似，解题方法都是Bit Manipulation, 所以我把他们放到了一篇博客里。

268.Missing Number的题目大意为:
给出一个数组，包含n个数(取自0~n之间)，让你找出缺少了哪个数.

通过数组的大小可以知道n为多大，有两种方法来解这道题。

312.Burst Balloons的题目大意为：

有n个气球, 顺序编号为0~n-1. 如果戳破编号为i的气球, 你可以获得数量为 nums[left]*nums[i]*nums[right]的硬币. left和right代表气球i相邻的气球编号, 气球i戳破之后, left和right便是相邻的了. 找出你可以获得的最大硬币数量.

Naive的想法

首先我想, 如何保存状态?
假设4个气球数值为[3, 1, 5, 8]. 如果戳破3, 变为[1, 5, 8]. 如果戳破1, 变为[3, 5, 8]. 起初想用一位数(0或1)来表示气球是否被戳破. [3, 1, 5, 8]状态表示为(1, 1, 1, 1);[1, 5, 8]状态表示为(0, 1, 1, 1).[3, 5, 8]状态表示为(1, 0, 1, 1). 这样可以由状态(1, 1, 1, 1)转移到状态(0, 1, 1, 1)或(1, 0, 1, 1).
但是500个气球岂不是要大小为2^500的数来表示？遍历完每个状态的时间复杂度为O(2^n). 这样显然有问题.