A step forward every day

1. 这题比起其他都是两个但有一个只出现一次要复杂一些，原来只需要统计（模2）出现0次，1次的情况，现在需要统计每一位出现了0次，1次和2次（模3）的状态。
2. 用one two three来统计每一位出现次数，出现在three中的可以从one two中约去
3. 每一个数，首先和one与一下，得到原来是1次，现在变成两次的情况，或到two中
4. 再和one抑或，原来是0的变成1，原来是1的由于进入two了变成0
5. one和two与，得到出现三次的情况，把他们从one two中抑或掉或者与非掉就行
6. 最后的one就是最后的结果（模3为1）

169 Majority Element

229 Majority Element II

摩尔投票法

这题既然是hard，那么就肯定要求复杂度在O(1)内完成。

考虑桶排序的方法，n个数大小相差最多为m的，那么大小相邻的两个数之间的间隔不会大于m / (n+1)

然后只要按照这个间隔构造足够的桶，维护每个桶中的最大值和最小值，同一个桶中的数字间隔不会多余答案所以只需要考虑每个桶的最小值与前面出现的最大值之间的差值就可以了。

1. 维护两个变量b与s，b[i]为前i日内买入的最大剩余钱量(可以为负)。s[i]为前i日卖出后的最大钱量。
2. s[i]由b[i]迭代而来，b[i]由前一轮的s[i]迭代而来，所以只用一轮循环就可以完成更新。

数位dp，先预处理出所有i位数字的情况

dp[i][j]，i代表数字的位数，j代表状况
dp[i][0],表示不存在不吉利数字的个数
dp[i][1],表示不存在不吉利数字，且最高位为2的个数
dp[i][2],表示存在不吉利数字的个数

按字典序排列1~n的数字字符串，找到第k个是什么数字

与leetcode 33有所不同，会存在重复出现数字的情况

编辑距离推导，动态规划。

动态规划问题。需要使用动态规划求出下面几个值

p[i][j]: 队i完成j题的概率，是题目的输入

dp[i][j][k]: 队i在前j题中完成k题的概率

s[i][j]: 队i完成不多于j题的概率，dp[i][m][0~j]的累加

p1: 所有队都至少完成一题的概率，(1-s[i][0])累乘

p2: 所有队都做出1~n-1题的概率，(s[i][n-1]-s[i][0])累乘

显然，最终的结果是p1-p2

给定一串K位二进制数字，需要给出最大区间的大小，使得在这个区间内每一位数字的和相等。

设一个数组sum[i][k]用于记录从第一个数字到第i个数字中第k位数字的和，这样就可以简单地计算出任意一个区间内每一位数字的和，也就是要求出sum[j][k] - sum[i][k]对于所有k都相等的区间[i, j]。

但是这样直接搜索的复杂度是O(N²)，所以需要用哈希来简化。

sum[j][0] - sum[i][0] = sum[j][1] - sum[i][1]

有

sum[j][1] - sum[j][0] = sum[i][1] - sum[i][0]

所以只要结点满足第k位数的总数与第0位数的总数差相等就可以。这一步可以使用哈希策略，详见代码。