讨论/求职面试/面试题|面试题一例,面试官说用动态规划求解,实在没想明白。/
面试题|面试题一例,面试官说用动态规划求解,实在没想明白。

数组里有值为小于n的数组成,找出包含所有0~n-1个数的最小区间。例如:
array = [1,2,0,0,1,2,3,4,1]
n = 5

1
共 14 个回复
4

1

咱不知道你所谓的面试官说的“动态规划”是从哪个角度进行规划,反正不可能是简单的区间dp,那比暴力还慢的做法好意思自称“规划”吗

如果n很小的情况下,比如小于64,那倒可以进行状态压缩的区间dp,虽说也就跟暴力一个速度
(这里说的暴力是指枚举左边界,固定好之后,向右推动右边界,枚举所有区间,时间复杂度O(n2))

你这个所谓的“优化”是画蛇添足,花里胡哨一顿操作对时间复杂度没有影响,还不如每个区间重新遍历一遍进行统计

你这不搞笑吗,你这转移了个寂寞,与其转移还不如重新统计来得快

如果不让用哈希表,用一个count数组加一个变量代替也行,count数组统计[i, j]范围每种数的出现次数,额外变量统计[i, j]上有多少种数。如果某个数出现次数降为0就把变量减一。典型的滑动窗口题目,不懂为什么要求动态规划求解。

第一感觉就是滑动窗口

为啥要用动态规划,直接双指针滑动窗口+哈希表O(n)时间解决。哈希map统计每个数的出现次数,不断右移j枚举新位置,如果map的size到达n,那么此时[i,j]就是一个包含n种数的区间,然后右移i(相应得减去每个数的出现次数),更新最小区间长度,直到哈希表size不足n为止,继续右移j。

f[l][r]可以从f[l+1][r]或f[l][r-1],只需看l和r处是否相等,相等就取两个之中的大的,不等的话还得考虑l+1--r-1它的值,如果存在的话,和右边等大就取左边,左边比较同理,如果都不等,就加2

区间dp,dp【i】【j】代表区间内,不同元素的个数,i等于j的时候初始化1,然后先把步长为1的求出来,j和i相差1,求完后步长一直往上加,知道找到第一个结果为n的截止