给一个linked list, 里面是0和1,二进制 求变成整数后的数.

给两个数组, 一个数组是学生, 一个数组是三明治, 问轮转学生数组后, 有多少学生没有三明治吃 这个是个模拟题, 模拟一下即可.

给一个string, 问二分后, 是不是包含相同数目的元音字符.

Burnside: https://en.wikipedia.org/wiki/Burnside%27s_lemma Polya: https://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem Polya是Burnside一种特殊推定, 例题就几个, 都是染色类问题. 个人觉得难点在于如何准确归纳和构建置换.

给一个数组, 求能不能只改变一个元素, 使得数组变成非递减数组. 主要是很多corner cases. 考虑到了就可以

给一个数组,求通过两两交换后排序这个数组, 交换有代价, 代价是交换的两个元素之和, 求排序的最小代价. 这个题我第一眼看是dp的问题, 但是很难考虑边界的元素交换, 而且很容易超时. 后来看了看答案, 原来是群论的置换群问题, 后来补了补. 发现也不是置换群, 只是单纯的置换中的轮换的概念, 关键是从哪个角度看待问题的本质(排序). 首先看置换群的概念在这里的应用, 拿例题举例: 由例子可以得知, 上面的例子最好的解法是: 取最小的数字作为媒介与其他数字做交换, 得到的成本是最小的. 然而这并不是唯一的最优解, 考虑一下的例子: 这个例子中, 可以把一个数组写成两个三阶置换, 那么对与[1,3,2],交换最小的成本并不是1与其他两个数的交换, 而是把0(全数组中最小的数字)先和1(当前数组最小数字)交换, 然后再次交换.这个最优解我没有想到 下面是如何计算最优解一: 最优解二: 答案在两个最优解中选最小的成本. 最后还有个技巧, 就是如何找到一个数组的index在排序后的对应index, 这里要用counting sort, 在counting sort中取count和的时候, 可以找到index的位置.

给一个数组nums和一个p, 求删去最小的子数组后的数字和可以整除p. let s = sum of nums, r = s mod p -> r = (s + p) mod p 因为我们知道presum可以用两个指针表示其中间隔的和. let (i, j) = indexs in presum where 0 <=i <= j <= presum.length. since r = (s + p) mod p, then r = (pre[j] – pre[i] + p) mod p 因为我们知道2sum中, […]

给一些砖块的长宽高, 可以旋转, 问怎么摆放可以有最高的高度, 求高度. 这个题虽然可以旋转, 但是其实因为限制: 必须完全小于长宽高的砖块才能放到另一个砖块上边. 所以没有旋转没有任何意义. 通过排序, 找到最长的, 然后再通过排序找到最大的. 即可做dp. 设dp[i]是包含砖块i作为可用砖块的最佳规划方案. 那么dp[i] = max{dp[j], where j < i and (i,j) meet requirements} 这个是bottom-up.

定义了一个数组叫deci-binary, 是decimal, 并且有没有leading zeros的1和0组成, 问这个数字的和组成n. 这个题主要是读懂题, 问的其实只是怎么组成n, 因为只有1和0, 那么看n的最大的digit的大小即可.

给一个由n个team组成的比赛, 如果n是偶数, 则进行n/2个比赛, 如果n是奇数则进行(n – 1)/2 +１个比赛，问一共要有多少比赛才能决定胜者．