华为机试(臻选)

牛客网华为机试

合唱队（动态规划与队列）

import bisect
def deal(arr):
    d = []
    count = []
    for val in arr:
        if not d: 
            d.append(val)
            count.append(1)
        elif d[-1] < val:
            d.append(val)
            count.append(count[-1]+1)
        else:
            d[bisect.bisect_left(d, val)] = val
            count.append(count[-1])
    return count
    
while True:
    try:
        n = int(input())
        height = list(map(int, input().split()))
        forward = deal(height)
        back = deal(height[::-1])[::-1]
        result = max(forward[i]+back[i] for i in range(n))
        print(n-result+1)
    except:
        break

放苹果（递归及动态规划）

def f(m,n):
    if m == 0 or n == 1:#没有苹果或者只剩1个盘子
        return 1
    if m < n: #n>m 必定有n-m盘子空着，去掉他们对摆放苹果方法，数目不受影响
        return f(m, m)
    else: #m>n 1.至少有一个盘子空着m,n-1 2.所有盘子都有苹果m-n,n
        return (f(m, n-1)+f(m-n, n))
while True:
    try:
        m,n = map(int,input().split())
        print(f(m,n))
        
    except:
        break

密码验证（加法思想）

while True:
    try:
        x = input()
        # print(x)
        a=0
        b=0
        c=0
        d=0
        pd = True
        for i in x:
            # print(i)
            if i.isdigit():
                a = 1
            elif i.isupper():
                b = 1
            elif i.islower():
                c = 1
            else:
                d = 1
        for j in range(len(x)-3):
            if x.count(x[j:j+3]) > 1:
                pd = False
        if len(x) > 8 and (a+b+c+d) >= 3 and pd:
            print('OK')
        else:
            print('NG')
    except:
        break

数据分类（排序）

while True:
    try:
        a = input().split()[1:]
        b = input().split()[1:]
        c = sorted(list(map(int,set(b))))
        f = []
        for i in c:
            d = 0
            g = []
            for index,item in enumerate(a):
                if str(i) in str(item):
                    d += 1
                    g.append(index)
                    g.append(item)
            g.insert(0, i)
            g.insert(1, d)
            if g[1] != 0:
                f.append(g)
        lenth = 0
        for i in f:
            lenth += len(i)
        h = str(lenth)
        for i in range(len(f)):
            for j in f[i]:
                j = str(j)
                h = h +' ' + j
        print(h)
    except:
        break

字符串排序（空格排序思想）

while True:
    try:
        a=input()
        #构造两个列表，一个列表用来放全字母的字符串2，另外一个列表取出来
        char=[] #构造一个列表用来存放字符串
        res=[False]*len(a)#构造一个列表用来记住非字母的位置
        for i,v in enumerate(a):
            if v.isalpha(): #如果全是字母则放入char中
                char.append(v)
            else:
                res[i]=v
        #然后对char进行排序
        char.sort(key=lambda c:c.lower())
        #重构,在res中的false项中放入char
        for i,v in enumerate(res):
            if not v:
                res[i]=char[0]
                char.pop(0)
        print(''.join(res))        
    except:
        break

素数伴侣（匈牙利算法）

def issu(x): #判断素数
    tem = 2
    while tem**2<=x:
        if x%tem==0:
            return False
        tem+=1
    return True
def find(a,l1,l2,l3):
    for i in range(0,len(l3)):
        if issu(a+l3[i]) and l1[i]==0:
            l1[i]=1 #如果是素数伴侣且无占位 使用占位列表进行占位
            if l2[i]==0 or find(l2[i],l1,l2,l3):
                l2[i] = a#判断偶数使用情况，若未使用，则添加至l2
                return True
    return False

try:
    while True:
        n = input()
        n = int(n)
        l = list(map(int,input().split()))
        ji,ou = [],[]
        for i in range(n): #分奇数偶数
            if l[i]%2==0:
                ou.append(l[i])
            else:
                ji.append(l[i])
        result = 0
        match = [0]*len(ou) #创建偶数匹配列表
        for i in range(0,len(ji)):
            used = [0]*len(ou) #创建偶数匹配占位列表
            if find(ji[i],used,match,ou):
                result+=1
        print(result)
except:
    pass

密码截取（回文判断）

def longp(s):
    res = ''
    for i in range(len(s)):
        #先判定奇数的，从i开始左右对比
        tmp = helper(s,i,i)
        if len(tmp) > len(res):res = tmp
        #再判定偶数的，从i和i+1开始对比
        tmp = helper(s,i,i+1)
        if len(tmp) > len(res):res = tmp
    print(len(res))

def helper(s,l,r):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        l -= 1
        r += 1
    return s[l+1:r]
 
while True:
    try:
        s = input()
        longp(s)
    except:
        break

蛇形矩阵（杨辉三角）

while True:
    try:
        n, curNum = int(input()), 1  
        res = [[0 for i in range(n)] for j in range(n)]
        for i in range(n):
            for j in range(i + 1):
                res[i - j][j] = curNum
                curNum += 1
        for i in res:
            print(" ".join(map(str, (filter(lambda i: i != 0, i)))))
    except:
        break

称砝码

while True:
    try:
        n = int(input())
        m = list(map(int, input().split()))
        x = list(map(int, input().split()))
        res = [0]
        for i in range(n):
            tmp = [m[i]*j for j in range(x[i]+1)]
            res = list(set(a+b for a in tmp for b in res))
        print(len(res))
    except:
        break

走方格（递归）

def f(n,m):
    if n == 0 or m == 0:
        return 1
    else:
        return f(n-1,m) + f(n,m-1)
while True:
    try:
        n,m = map(int, input().split())
        print(f(n,m))
    except:
        break

寻找数字串(暴力替换)

while True:
    try:
        a = input()
        e = ''
        for i in range(len(a)):
            if a[i].isalpha():
                a = a.replace(a[i], '.')
        b = a.split('.')
        c = max(len(i) for i in b)
        for i in b:
            if len(i) == c:
                e += i
        print(e+','+str(c))
    except:
        break

梅花桩走法（排序）

import bisect
while True:
    try:
        a = input()
        b = list(map(int, input().split()))
        c = []
        d = 0
        for i in range(len(b)):
            if bisect.bisect_left(c, b[i]) == d:
                c.append(b[i])
                d += 1
            elif bisect.bisect_left(c, b[i]) != d:
                c[bisect.bisect_left(c, b[i])] = b[i]
        print(len(c))
    except:
        break