Array

#最长连续子区间

最长连续子区间定义为：对于子区间{A[i],A[i+1]…A[j]}，其值范围为{B..B+j}，且不包含重复元素。

如对于数组：9 7 2 5 4 3 10 6
最长相邻连续子区间表示为 2 5 4 3

  1. 双向扫描

    枚举每个点p作为区间的起点，向右进行扫描，并维护遇到的最小元素和最大元素。
    当最大元素-最小元素的值 = cur-pos(p)时，表明此段区间连续，复杂度为O(n^2)
    数组中最长连续子区间不要求相邻
    如： 9 7 2 5 4 3 10 6
    最长连续子区间为: 2 3 4 5 6 7

  2. 哈希
    采用哈希存储数组，对于每一个元素，检查其相邻元素，找到最长能延伸的位置，并在此过程中删除元素
    时间复杂度为O(n)，空间复杂度为O(n)

#最大完整包编号
维护TCP移动窗口服务端不断向客户端发送数据包，客户端不断向服务端返回收到的最大完整包的位置。

输入： 3 5 2 1 6 8 4 7 表示客户端返回的包的编号
输出： 0 0 0 3 3 3 6 8 表示客户端返回的确认包编号

思路：维护收到的最小编号，用数组保存收到的所有数据，当收到的包编号与最小编号相等时，向后进行确认，直到某个包未收到，并更新最小编号

1
def slidingWindow(a):
    buffSize = 10
    buff = set()
    nextPacket = 1
    for val in a:
        if val-nextPacket < buffSize:
            buff.add(val)
            if nextPacket == val:
                while nextPacket in buff:
                    buff.remove(nextPacket)
                    nextPacket += 1
        print nextPacket-1

#和大于k的最长子序列

思想：求前缀和数组prefix,找到最大i和j，使得prefix[j] - prefix[i] > k, 其中j > i

  1. 构造单调递减栈
  2. 从右向左进行扫描i，当prefix[i] - 单调栈顶 > k，则弹出，计算最长子序列长度

#和小于k的最长子序列
数组中的数都是整数

思想：维护序列的起始位置i，以及结束位置j，当sum(i, j) > k时，向前移动i，直到和小于k。
由于全是整数，对于起点i，当sum(i, j) > k时，说明sum(i, t) > k, 如果 t > j。从而这里找到了以i为起始的最长子序列，可以安全向前移动。

1
def maxLength(a, k):
    i, length, sum = 0, 0, 0
    for j, val in enumerate(a):
        sum += val
        if sum <= k:
            length = max(length, j-i+1)
        else:
            while sum > k:
                sum -= a[i]
                i += 1
    return length

#和等于k的最长子序列

  1. 数组中的数字都是正数
    思想：维护序列的起始位置i，以及结束位置j，当sum(i, j) > k时，向前移动i，直到和小于等于k。

    1
    def maxLength(a, k):
    i, length, sum = 0, 0, 0
    for j, val in enumerate(a):
        sum += val
        while sum > k:
            sum -= a[i]
            i += 1
        if sum == k:
            length = max(length, j-i+1)
            i += 1
            sum -= a[i]
    return length

  2. 存在负数
    思想：使用哈希存前缀和的值，对于每个前缀和val，检查val-k是否在前缀和集合中

    1
    def maxLength(a, k):
    dict, length, sum = {}, 0, 0
    dict[0] = -1
    for j, val in enumerate(a):
        sum += val
        if (sum-k) in dict:
            length = max(length, j-dict[sum-k])
        if sum not in dict:
            dict[sum] = j
    return length

#求序列和能被P整除的数量
思想：对于序列的前缀和, 如果(prefix[j] - prefix[i]) % P = 0，则说明子序列(a[i], a[i+1], …, a[j])的和能被P整除。
解法：

  1. 使用哈希表保存各个前缀和出现的次数
  2. 对于某个相等的前缀和的数量n，存在C(n,2)个能被P整除的序列
  3. 对于前缀和为0的，还需再加上n
    1
    def subsequenceDivisibleByP(a, p):
    n, prefix, cnt, prefixMap = len(a), 0, 0, {}
    C = prepareC(n) #预处理C[k][2]
    for i in range(n):
        prefix = (prefix + a[i]) % p
        if prefix not in prefixMap:
            prefixMap[prefix] = 1
        else:
            prefixMap[prefix] += 1

    for num, val in prefixMap.items():
        cnt += C[val]
        if num == 0:
            cnt += val
    return cnt

#修改最少的数值使得数组变成有序

给一个数组A，把A编程严格递增，每个数对多只能 +/- M，找到最小的M
输入: 1 2 4 2 3
输出：

1.二分搜索m, 采用贪心验证，尽量使得每个数尽可能的小。
复杂度O(nlgn)
2.维护数组B[i] = A[i]-i, 找到最大diff = B[i]-B[j],其中j > i，M = [diff/2]
时间复杂度O(n)，空间复杂度O(n)
有黑名单的随机数生成给定随机数生成范围，以及一个黑名单数组，数组中的数字不允许生成

解法：

  1. 维护数组a[i] = black[i]-i。
  2. 生成随机数(start, end-num) 其中num表示黑名单数字的数量
  3. 生成的随机数r,搜索其在数组a中的pos，返回pos+r