Minimize Hamming Distance After Swap Operations
给一个原数组和一个目标数组, 给一个2d数组表示可以交换原数组的index对, 求使用这些交换后, 原数组不能成为目标数组元素的个数. 这个题是典型并查集的题, 先预装一下所有的swap, 然后再找原数组中的index是否在某个集合中, 需要注意的还有一个是因为有重复元素, 所以还需要一个map记录并查集中每个小集合中元素的频率.
给一个原数组和一个目标数组, 给一个2d数组表示可以交换原数组的index对, 求使用这些交换后, 原数组不能成为目标数组元素的个数. 这个题是典型并查集的题, 先预装一下所有的swap, 然后再找原数组中的index是否在某个集合中, 需要注意的还有一个是因为有重复元素, 所以还需要一个map记录并查集中每个小集合中元素的频率.
给一个已经排序好的二维数组. 第一个数字表示顾客到达的时间, 第二个表示准备顾客order的时长, 求平均服务顾客的时间. 这个题就是分类讨论, 通过看例子, 知道如果前后两个人在同一时间到达, 那么后一个人的服务时间是要把给前边人准备的时间也算进去的. 然后再按照当前时间进行分类, 还是第二个例子, 能看出如果两个人不是同一时间到达, 但是两个人的准备时间不重叠, 那么只需要分别算服务时间, 如果重叠, 需要先找到上一个顾客的完成时间, 然后计算出当前顾客的服务时间, 所以还需要一个变量记录上一个顾客的完成时间.
给一个数字n, 代表天数, 从第一周开始, 每个星期第一天算1, 一共7天, 第二个星期从2开始,到8. 求n天赚多少钱
给一个链表, 给一个数组k, 求交换开始第k个node和倒数第k个node的值. 这个题我看答案是扫了三次, 我用的stack
给一个数组, 是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的中找到这些答案并且加起来. 全代码:
给一个linked list, 里面是0和1,二进制 求变成整数后的数.