给一个字符串, 里面有0,1和?, ?可以是1或者0, 求这个字符串的子字符串中可以变成1和0 交替出现的字符串的个数. 这题就是counting问题, 做的时候用的dp, 想了半天都有错, 后来想想, ?基本没啥用的地方, 因为0和1交替出现的字符串就两种, 一种是0101或者1010…所以如果我们强制替换奇数位上的1变成0, 0变成1, 那么如果是以上两种, 就会变成0000或者1111, 所以我们只需要用两个指针count一下每个substring是否是答案即可.

给两个鸡蛋和n层楼, 已知一个鸡蛋从x层楼掉下去不会碎,但是从x+1层就会碎 求最少多少次扔鸡蛋可以知道x是多少. 典型的dp题, 可以用一个memo存当前的状态: 首先, 如果只有一个鸡蛋, 那么测n层楼需要测n次. 这里不用binary search, 因为我们的求的是最少多少次扔鸡蛋, 而binary search不一定能找到正确的解, 最坏情况我们还是要扔n次. 转移方程中, 两个状态是:1. 扔了没有碎, x肯定在当前i floor的上边: drop(egg, floor – i), 2. 扔了碎了, x肯定在当前i floor的下边 drop(egg – 1, i – 1). 因为同样数量的move下,我们需要找的是两个解中, 最”高”的一层所以取两个状态的max. 然后和当前的所有状态中的每个状态取min.

给三个字符串, 问前两个的值转换成数字是否加起来等于第三个.

给一个二叉树, 然后给一个node的值是coin的数量, 求把这个coins分给每个node需要几步, 一步只能往下推一个node. 这题就是divide and conquer, 例题给的很明确, 如果是root有3个, 左右是0, 那么分下去需要2步(给左边一个, 给右边一个), 这题还给了一共n个node和n个coin, 所以不存在溢出的情况. 所以只需要计算left和right的和-1 就是需要的步骤.

给两个数组设计一个数据结构, 可以add一个数字到第二个数组, 还有count两个数组的数字等于total有几对儿. 这个就是第一个数组大, 第二个小, 所以先处理大的数组. 然后count的时候直接减一下即可.

给一个binary字符串, 求是否最长的1比最长的0长.

各一个2d数组, 里面有石头, 空格和障碍, 求右转90度后, 石头落下, 数组的状态. 这题先转90度, 然后从下往上看到空格就往上找石头然后swap, 注意检查边界.

给一个string组, 求是否有一个string的所有prefix都出现在组里. Trie找一下

给一个一直增加的数, 和两个memory, 每次都放到剩余最大的memory里, 求最后的状态

给一个数组, 求其中subset的xor的和.