2018.10.14 腾讯笔试

总结：共3道算法题，2AC，1WA（90% passed），题目都很有意思。

不过腾讯也是不当人，前些天国内的笔试题，两次都是3道算法题，那真叫一个难啊，我都只A了一道，这次笔试面向海外，md题目就相对简单了很多，这是不是在搞区别对待啊？

1. 包含k个’1’的子串(AC)

一个字符串如果只包含’0’和’1’，那么久称这个字符串为二进制字符串。

一个字符串w的子串v是一个非空字符串，并且它由从w的某个位置开始的一段连续字符构成。比如’010’有6个子串，’0’,’1’,’0’,’01’,’10’,’010’

如果两个子串出现的位置不相同，那么就认为这两个子串是不同。给出一个二进制字符串s，计算s中刚好包含k个字符’1’的子串的个数。

输入描述:
第一行一个整数k,含义如题
第二行一个非空二进制字符串s
满足0 <= k <= 10^6, 1 <= len(s) <= 10^6

输出描述：
一个整数，表示恰好包含k个’1’的子串的个数。

示例1：
2
111

输出：
2

示例2：
3
1101

输出：
1

思路：
对于 s = '001010011', k = 2，我们先找到两个1，然后向两边扩散，观察能有多少种扩散方式，先将所有的1的下标存储
index = [2,4,7,8]，比如对于前两个’1’，2可以往左边扩散0个，1个，2个，分别对应下标2，下标1，下标0；对于4可以往右边扩散0个，1个，2个，分别对应下标4，下标5，下标6，所以总共扩散方式就是3x3 = 9种。
为了处理边界情况，在index数组左右两边分别加上-1,以及len(s)。

k = int(input())
s = input()
n = len(s)
res = 0
if s.count('1') < k:
    print(0)
else:
    index = [-1]
    for i in range(n):
        if s[i] == '1': index.append(i)
    index.append(n)
    for i in range(1,len(index)):
        if i+k < len(index):
            j = i+k
            res += (index[i]-index[i-1]) * (index[j] - index[j-1])
    print(res)

2. 很酷的子序列(WA, 90% PASSED)

小Q定义A(i,j)(i<=j并且都是A的合法下标)表示数组A中下标从i到j的这段子序列，即A(i,j) = {A[i],A[i+1],…,A[j]}。

对于A(i,j)，能找到一个正整数v(v>1)，使得v可以整除A(i,j)中不低于一半的元素，小Q就认为A(i,j)是一段很酷的子序列。

例如A(i,j) = {3,3,7,9,1,10}，六个元素中三个元素可以被v=3整除，所以A(i,j)是酷的。
现在给出一个数组A，让你找出最长的酷的子序列的长度。

输入描述：
输入包括两行。
第一行包括一个正整数n(1 <= n <= 50)，表示数组的长度。
第二行包括n个正整数A[i]，(1 <= A[i] <= 1000)，表示数组中的每个元素。

输出描述：
一个整数，表示最长的酷的子序列的长度，如果没有解，输出0.

示例1：
输入：
5
8 8 5 5 4

输出：
5

解释：
8 8 4都能被4整除，3个数已经超过序列长度的一半，所以长度为5

思路分析：
假设对于一段序列，A[i],…,A[j],…,A[k]

我们知道这段序列中只有A[i],A[j],A[k]这三个数同时能被v整除，那如何来计算序列长度呢？
我们知道这段序列的长度l = k-i+1,如果 3 >= l//2(这是前提)，那么我们可以说已经找到了个长度为l的酷的序列，当然实际上3个数能构成长度为6的序列，所以我们可以说已经找到了长度6的酷的序列（当然前提是A的长度要大于等于6）

你需要注意到实际计算时并不是l越大越好，因为数量可能跟不上，比如对于A[1],A[3],A[8]，直接看1和8会发现这段序列太长，我们数的个数并没有超过长度的一半。所以我们得先看1,3再看1,8，再看3,8，把所有的可能都计算才行。

那么怎么来找上面所说的A[i],A[j],A[k]呢

我们知道v其实就是他们的相同公约数，我们注意到A[i]的取值是不超过1000的，我们完全可以把1000以内所有的质数都计算出来，然后依次遍历，例如对于质数2，A中所有A[i] % 2 == 0的数的下标都存进d[2]中。这样我们就找到了A[i],A[j],A[k]，然后使用n^2的遍历方法对每一段进行分析

# 90% passed，可能是某种特殊情况没想到
from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

n = int(input())
a = read()

def isPrime(val):
    if val == 1: return False
    for i in range(2, int(val**0.5) +1):
        if val % i == 0: return False
    return True

# p中存储1000以内的质数
p = []
for i in range(1, 1001):
    if isPrime(i): p.append(i)

def solve(a):
    if len(a) == 1: return 1
    d = defaultdict(list)
    for val in p:
        for i in range(n):
            if a[i] % val == 0:
                d[val].append(i)
    res = 2
    for key in d:
        l = len(d[key])
        for i in range(l):
            for j in range(i+1,l):
                # ka表示这段序列的长度,cnt表示这段序列中能被v整除的数的个数
                ka = d[key][j] - d[key][i] + 1
                cnt = j-i+1
                if cnt >= (ka+1) // 2:
                    res = max(res, min(2*cnt,n))
    return res

print(solve(a))

3. 数字拼凑(AC)

小Q有一个长度为n的序列S，序列中有n个正整数。小Q现在和你玩数字游戏，每次小Q说出一个正整数X，你需要从序列中挑选出若干个数字出来进行相加，使结果等于X，如果你不能完成拼凑你就输了。

小Q现在想知道能让你输掉游戏的最小的正整数X是多少？

输入描述：
输入包括两行
第一行为一个正整数n，表示序列的长度 1 <= n <= 20
第二行包括n个正整数a[i]，用空格隔开， 1 <= a[i] < 10^5

输出描述：
一个正整数，表示最小的正整数X

示例1：
输入：
3
2 1 4
输出：
8

思路分析：
这道题是非常经典的一道题型，对于给定的数组，需要分析其所有可能组成的和(每个数字用一次)
PS：如果每个数字能用多次，其实就是一个零钱凑整问题

使用dp[i]表示序列中的数字能否组成正整数i
因为序列所能组成的最大数字为 sum(a)，所以dp = [0] * (sum(a) + 2)
对于每个dp[i]需要反向遍历来确保不会重复利用数字,dp[i] = any(dp[j] for j= i-a[k] for k in range(n))

用文字描述逻辑可能有点乱，建议读者直接使用测试样例的数据来分析这个代码，那样理解得更快

from collections import Counter, defaultdict, deque
read = lambda: list(map(int,input().split()))

mod = 10**9+7
inf = float('inf')

n = int(input())
a = read()
dp = [0] * (sum(a) + 2)
dp[0] = 1
for i in range(n):
    for j in range(len(dp)-1,a[i]-1,-1):
        val = j - a[i]
        if dp[val] == 1:
            dp[j] = 1
# 找到第一个dp[i] = 0的位置
index = 0
while dp[index] == 1:
    index += 1
print(index)