Decode XORed Array
给一个数组, 是or后的数组, 并且给了第一个数字, 求原文数组. 这个题看下真值表即可.
给一个数组, 是or后的数组, 并且给了第一个数字, 求原文数组. 这个题看下真值表即可.
给一个数组, 求分成三份, 前一份小于等于后一份的分法有几种. 这个题开始的时候以为是dp, 后来想了想用presum也能做, 但是答案用的是二叉搜索, 我看了眼答案, 感觉面试不太容易想到这个优化.
给一个数组, 定一个子数组比另一个子数组大是子数组的第一个数字大. 求最大的子数组.
给一个2d数组, 第一项是物品个数, 第二项是物品价值, 给一个size, 求满足这个size最大的价值是什么. 看似dp,其实贪婪, 直接排序求即可.
给一个数字n,表示n个人, 给一个数字p, 表示最小的收益, 给两个数组,表示工作和工作需要的人, 问最多使用n个人并且满足最小收益的工作一共有多少种组合? 这个题一眼肯定是动态规划, 但是因为是求多少种组合, 所以每个条件都单做一维. Let dp[i][g][p] to be the first i’th jobs (including) with exact g members used and having exact p profit. 首先要初始化这个dp, 那么dp[0][0][0]是1 从背包问题,宽泛考虑, 可以知道, 如果不选当前的i, 那么对应的g和p就不会增加, 所以这也是一种组合: 当决定了选i’th job, 就要考虑当前i是否满足限制人数(不满足则不选): 通过上面这行后, 确定了ith job肯定能干, 接着考虑下面的, 如果ith job的profit和当前profit加起来超过了P(最小profit), 因为其实超过了多少无所谓, 我们就把所有超过P的job放到P的位置上, 这样便于统计. 如果加起来还是没有超过p, 那么我们只能先存着, 因为当前的运算可能作为以后某个答案的子集. 以上就是dp的构建, 最后的答案因为我们的dp只迭代了包含前i个job的子问题, 子问题并没有对人数进行迭代, 人数从0到G都是满足题意的答案, 所以需要在dp的中找到这些答案并且加起来. 全代码: