Construct the Lexicographically Largest Valid Sequence
给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组. 这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.
给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组. 这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.
给一个原数组和一个目标数组, 给一个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,其实贪婪, 直接排序求即可.