4 月 12 日笔试

目录

1. 第一题
2. 第二题
3. 第三题
4. 第四题

一共四道题，2 小时，快手笔试

第一题

输入一个字符串，返回一个字符串，返回的字符串中把原字符串连续的超过两个相同字母删掉，如果一次删除后还有连续超过两个相同字母则继续删除。

例如：输入 'abbcccba' 输出 'aa'

字符串长度 10 ^ 5

我只想到模拟方法，虽然过了，但是实际上极端数据是过不了的例如：

l = []
x = 10 ** 5 // 3
for i in range(x):
    l.append('a')
    l.append('b')
for i in range(x):
    l.append('bb')
    l.append('aa')
s = ''.join(l)

我的代码：

s = list(input())
while True:
    skip = []
    i = 2
    while i < len(s):
        if s[i-1] == s[i-2] == s[i]:
            j = i 
            while j < len(s) and s[j] == s[i]:
                j += 1
            skip.append((i-2, j))
            i = j + 2
        else:
            i += 1
    if not skip:
        break
    ss = []
    i = 0
    for x, y in skip:
        ss += s[i:x]
        i = y
    ss += s[i:]
    s = ss
print(''.join(s))

第二题

用火柴棒摆数字，要求只能且必须移动一根火柴棒，问能得到的最大的数是多少。输入一个正数，输出一个整数。所有移动都无效时输出 -1

样例：109 输出 705

我先写了表示火柴棒数字的代码：

def pn(n):
    assert len(n) == 7
    if n[0]:
        print(' _ ')
    else:
        print('   ')
    l = '| ' if n[1] else '  '
    l += '| ' if n[2] else '  '
    print(l)
    print(' _ ' if n[3] else '   ')
    l = '| ' if n[4] else '  '
    l += '| ' if n[5] else '  '
    print(l)
    print(' - ' if n[6] else '   ')
    
num = [[1,1,1,0,1,1,1], [0,0,1,0,0,1,0], [1, 0, 1, 1, 1, 0, 1],[1, 0, 1, 1, 0, 1, 1],[0, 1, 1, 1, 0, 1, 0],[1, 1, 0, 1, 0, 1, 1],[1, 1, 0, 1, 1, 1, 1],[1, 0, 1, 0, 0,1, 0],[1,1,1,1,1,1,1],[1,1,1,1,0,1,1]]
for i in range(10):
    print('----', i, '----')
    pn(num[i])

---- 0 ----
 _ 
| | 
   
| | 
 - 
---- 1 ----
   
  | 
   
  | 
   
---- 2 ----
 _ 
  | 
 _ 
|   
 - 
---- 3 ----
 _ 
  | 
 _ 
  | 
 - 
---- 4 ----
   
| | 
 _ 
  | 
   
---- 5 ----
 _ 
|   
 _ 
  | 
 - 
---- 6 ----
 _ 
|   
 _ 
| | 
 - 
---- 7 ----
 _ 
  | 
   
  | 
   
---- 8 ----
 _ 
| | 
 _ 
| | 
 - 
---- 9 ----
 _ 
| | 
 _ 
  | 
 -

然后写了搜索数字间转换关系的代码：

selfx = [[] for _ in range(10)]
def change(i):
    cn = num[i]
    for j in range(7):
        if cn[j] == 1:
            for k in range(7):
                if k == j:
                    continue
                if cn[k] == 0:
                    cx = num[i][::]
                    cx[j] = 0
                    cx[k] = 1
                    if cx in num:
                        nn = num.index(cx)
#                         print(nn)
#                         if nn > i:
                        selfx[i].append(nn)
for i in range(10):
    change(i)
selfx # [[6, 9], [], [3], [5, 2], [], [3], [0, 9], [], [], [6, 0]]

remove = [[] for _ in range(10)]
def change(i):
    cn = num[i]
    for j in range(7):
        if cn[j] == 1:
            cx = num[i][::]
            cx[j] = 0
            if cx in num:
                nn = num.index(cx)
                remove[i].append(nn)
for i in range(10):
    change(i)
remove # [[], [], [], [], [], [], [5], [1], [6, 0, 9], [3, 5]]
add = [[] for _ in range(10)]
def change(i):
    cn = num[i]
    for j in range(7):
        if cn[j] == 0:
            cx = num[i][::]
            cx[j] = 1
            if cx in num:
                nn = num.index(cx)
                add[i].append(nn)
for i in range(10):
    change(i)
add # [[8], [7], [], [9], [], [9, 6], [8], [], [], [8]]

selfx：当前数字自身移动可以变成哪些数字

add：当前数字加上一根变成哪些数字

remove：当前数字去掉一根可以变成哪些数字

这题过了 97 %，最后是 WA。估计是第二种情况的问题，原来只考虑了数字变大的情况，实际上是不对的，因为题意要求（开始没读好题意）无论变大变小，必须移动，只有所有移动都无效时才输出 -1。

add = [[8], [7], [], [9], [], [9, 6], [8], [], [], [8]]
remove = [[], [], [], [], [], [], [5], [1], [6, 0, 9], [3, 5]]
selfx = [[6, 9], [], [3], [5], [], [], [9], [], [], []]
selfx2 = [[6, 9], [], [3], [5, 2], [], [3], [0, 9], [], [], [6, 0]]
n = list(map(int, list(input())))
# n = [1, 0, 9]
# print(n)

def find_inc(i,e, x, ii=99999, s=1):
    for j in range(i, e, s):
        if j == ii: continue
        if x[n[j]] and max(x[n[j]]) > n[j]:
            return j, max(x[n[j]])
def find_dec(i, e, x, ii=99999, s=-1):
#     print(i, e)
    for j in range(i, e, s):
        if j == ii: continue
        if x[n[j]]:
            return j, max(x[n[j]])

for i in range(len(n)):
#     print('iiii', i)
    op = []
    if add[n[i]] and max(add[n[i]]) > n[i]:
        op.append([max(add[n[i]]), 'a'])
    if remove[n[i]] and max(remove[n[i]]) > n[i]:
        op.append([max(remove[n[i]]), 'r'])
    if selfx[n[i]] and max(selfx[n[i]]) > n[i]:
        op.append([max(selfx[n[i]]), 's'])
    op.sort(reverse=True)
#     print(n[i], op)
    f = False
    for o in op:
        if o[1] == 's':
            n[i] = o[0]
            f = True
            break
        elif o[1] == 'a':
            xx = find_inc(i+1, len(n), remove)
            if not xx:
                xx = find_dec(len(n)-1, i, remove)
            if xx:
                n[i] = o[0]
                n[xx[0]] = xx[1]
                f = True
                break
        else:
            xx = find_inc(i+1, len(n), add)
            if not xx:
                xx = find_dec(len(n)-1, i, add)
            if xx:
                n[i] = o[0]
                n[xx[0]] = xx[1]
                f = True
                break
            if f:
                break 
        if f:
            break
    if f:
            break
if f:
    print(''.join(map(str,n)))
else:
    for i in range(len(n)-1, -1, -1):
    #     print('iiii', i)
        op = []
        if add[n[i]] and max(add[n[i]]) < n[i]:
            op.append([max(add[n[i]]), 'a'])
        if remove[n[i]] and max(remove[n[i]]) < n[i]:
            op.append([max(remove[n[i]]), 'r'])
        if selfx2[n[i]] and max(selfx2[n[i]]) < n[i]:
            op.append([max(selfx2[n[i]]), 's'])
        op.sort(reverse=True)
    #     print(n[i], op)
        f = False
        for o in op:
            if o[1] == 's':
                n[i] = o[0]
                f = True
                break
            elif o[1] == 'a':
                xx = find_inc(0, len(n), remove, i)
                if not xx:
                    xx = find_dec(len(n)-1, -1, remove, i)
                if xx:
                    n[i] = o[0]
                    n[xx[0]] = xx[1]
                    f = True
                    break
            else:
                xx = find_inc(0, len(n), add, i)
                if not xx:
                    xx = find_dec(len(n)-1, -1, add, i)
                if xx:
                    n[i] = o[0]
                    n[xx[0]] = xx[1]
                    f = True
                    break
                if f:
                    break 
            if f:
                break
        if f:
            break
    if f:
        print(''.join(map(str,n)))
    else:
        print(-1)

第三题

输入两个数 k，n，返回数列的第 n 项模 397 的结果。

数列规则如下，前 k 项（0 ~ k-1）都是 1。第 k+1 项开始，每一项都是前面 k 项的和（那么说第 k + 1 项一定等于 k）

样例是：

2 4 输出 5

解释： 1 1 2 3 5 8 13 ……

我写了模拟，只出了 10%

n = 6
x = [k]
cur = k
for i in range(k - 1):
    kk = (sum(x) + k-i-1) % 397
    x.append(kk)
i = 0
j = k*2 - 1
while j < n:
    j += 1
#     print(x, i)
    x[i] = sum(x) % 397
#     print(x)
    i = (i + 1)% k
print(x[i-1])

第四题

物资分配，n 个物资集散中心，有一个蓝对勾中心负责分配物资，物资都要运到蓝对勾，现在要额外修建 k 个蓝对勾分部，分部都建立在物质中心。

输入：第一行 n，k

以后 n 行每行四个数：物资中心编号（从 1 开始），货物数量，距离最近的物资中心编号，距离

单位货物运输单位距离需要 100 块。求如何修建分部使运输成本最小，输出最小成本。

每个物资中心能直接到达临近物资中心或者直接到蓝对勾总部（用编号 0 代表）保证无环。

这题没记下样例，也没写出来