贝壳找房秋招机器学习笔试卷

奇特区间数

给出一个大小为n的数组a和整数t，定义区间[l,r](0<=l<r<=n-1)，若存在下标i,j(l<=i<j<=r)属于区间[l,r]，且a[i]异或a[j]=t，那么称[l,r]是非奇特区间，如不存在，则[l,r]是奇特区间，求a数组里的奇特区间个数。

示例1

输入例子：[2,4,8],6
输出例子：1
例子说明：因为2异或4为6，等于t，所以只有区间[1,2]是奇特区间，对应的数组是[4,8]，数组不能为[2,4]，数组也不能为[2,4,8]，因为里面包含了2和4

代码：

class Solution:
    def section(self , a , t ):
        # write code here
        n = len(a)
        dp = [-1] * n
        res = 0
        maps_index = {} #记录当前出现的数最后一个下标
        maps_index[a[0]] = 0
        for i in range(1,n):
            maps_index[a[i]] = i
            target = a[i] ^ t # 异或是可恢复的
            dp[i] = dp[i-1]
            if target in maps_index:
                dp[i] = max(dp[i],maps_index[target]) # 比较前一个的最早的下标和自己的奇异数下标哪个大
            res += i-dp[i]-1
        return res

使用动态规划，dp[i]代表以a[i]结尾的区间左端点最多在哪，这个值一定大于等于dp[i-1]所代表的值，那么就用两数之和的想法，维护一个hashmap找到在i左端的最近的一个奇异值，与dp[i-1]相比较。最后以a[i]结尾的区间最长为i-dp[i]最短为2