2021届自己参加的秋招笔试题记录

Code

2021届秋招正如火如荼地进行着，截止目前，我已经参加了绝大部分互联网企业的秋招，我想将自己写过的代码保存一下，供以后再来回味。
代码基本都是用Python写的，有些并没有100%AC。

不匹配括号数量

Input: 包含若干(, ), [, ]的字符串。

Output: 不能配对的括号的数量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
def BracketsMatch(text, flag):
    arr = []
    if flag == 1:
        left = '('
        right = ')'
    else:
        left = '['
        right = ']'
    for c in text:
        if c == left:
            arr.append(c)
        elif c == right:
            if len(arr) == 0:
                arr.append(c)
            else:
                if arr[-1] == left:
                    arr.pop()
                else:
                    arr.append(c)
    return len(arr)
text = input().strip()
print(BracketsMatch(text, 0) + BracketsMatch(text, 1))

分析

针对任意一对括号，可以用栈来存储无法匹配的括号。同时这种写法可以拓展到其他需要前后配对的字符上，例如{和}或者『和』等。

前m个值最大选项的序号

Input: 第一行n和m，n代表有几个物品，m代表取价值前m大；以后n行输入n个物品的重量和体积。

Output: 从小到大输出价值前m大的物品编号。

*物品价值 = 重量 + 2 × 体积

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
line1 = input().split(' ')
n = int(line1[0])
m = int(line1[1])
matrix = [[0 for i in range(4)] for j in range(n)]
for i in range(n):
    line_n = input().split(' ')
    matrix[i][0] = float(line_n[0])
    matrix[i][1] = float(line_n[1])
    matrix[i][2] = float(line_n[0]) + 2 * float(line_n[1])
    matrix[i][3] = i + 1
matrix = sorted(matrix, key = lambda item:item[2])[::-1]
max_m = int(matrix[0][2])
result_m = [[0 for i in range(n + 1)] for j in range(max_m + 1)]
for i in range(len(matrix)):
    result_m[int(matrix[i][2])][int(matrix[i][3])] = 1
result = []
for i in range(max_m, -1, -1):
    for j in range(n + 1):
        if result_m[i][j] == 1:
            result.append(j)
result = sorted(result[0 : m])
strs = ''
for i in range(m):
    strs += str(result[i]) + ' '
print(strs.strip())

分析

类似于Excel之中排序，主排序标准和次排序标准。

0/1背包

0/1背包作为经典的动态规划问题，经常考察，但是只要掌握状态转移方程，动态规划基本上很少的代码就可以写出来。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
def Package(W, V, max_w):
    len_w = len(W)    
    dp = [[0 for i in range(max_w + 1)] for j in range(len_w)]
    for i in range(len_w):
        for j in range(max_w + 1):
            if W[i] > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j - W[i]] + V[i], dp[i - 1][j])
    return dp[-1][-1]
W = [10, 20, 20, 30]
V = [12, 18, 17, 32]
max_w = 50
print(Package(W, V, max_w))

根据输入操作数字串

Input: 一行n和m，代表长度为n的值为下标的数字串；m行不同的操作。（1：将串首元素移动到最尾；2：交换第“2 × i + 1”和第“2 × i + 2”号元素，其中i从1开始。）

Output: 操作结束的数字串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
line1 = input().split(' ')
n = int(line1[0])
m = int(line1[1])
line2 = input().split(' ')
line = []
for i in range(n):
    line.append(i + 1)
def OP1(line):
    new_line = []
    for i in range(1, len(line)):
        new_line.append(line[i])
    new_line.append(line[0])
    return new_line
def OP2(line):
    for i in range(0, len(line), 2):
        t = line[i]
        line[i] = line[i + 1]
        line[i + 1] = t
    return line
for i in range(m):
    if int(line2[i]) == 1:
        line = OP1(line)
    elif int(line2[i]) == 2:
        line = OP2(line)
    else:
        line = line
ret = ''
for i in range(n):
    ret += str(line[i]) + ' '
print(ret)

分析

这种题目就是按照题目要求，写出不同操作的函数，然后调用就OK啦。在今年的秋招中，出现过很多次类似的题目，虽然操作不尽相同。

计算面积

求y = 0, x = C, x = D 与y = Ax^2 + x + B相交区域的面积。

Input: A，B，C和D。

Output: 面积（保留6位小数）

代码

1
2
3
4
5
6
7
8
9
10
11
 
n = int(input())
ret = []
def Area(a, b, c, d):
    right = (float(a) / 3) * d * d * d + 0.5 * d * d + float(b) * float(d)
    left = (float(a) / 3) * c * c * c + 0.5 * c * c + float(b) * float(c)
    return right - left
for i in range(n):
    line = input().split(' ')
    ret.append(Area(int(line[0]), int(line[1]), int(line[2]), int(line[3])))
for i in range(n):
    print("%.6f" % ret[i])

分析

这种题乍一看没有思路，需要结合数学知识，求面积就是求一定范围内的积分。当函数变化时，也是同样的做法。

全组合

Input: 一个正整数n。

Ouput: 从1到n的全组合，并且每种组合从组合中选一个代表的总可能数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
n = int(input())
ret = 0
def C(n, i):
    ret = 1
    d = 1
    while i > 0:
        ret *= n % (pow(10, 9) + 7)
        n -= 1
        d *= i % (pow(10, 9) + 7)
        i -= 1
    return int(ret/ d) % (pow(10, 9) + 7)
for i in range(1, n + 1):
    ret += (i * C(n, i)) % (pow(10, 9) + 7)
print(ret % (pow(10, 9) + 7))

分析

全组合可以通过转化成2进制，然后数1的个数来确定，也可以使用从1到n组合求和来做。

求图中链接相同元素的节点对的数量

Input: 节点数n，边数m；以后m行，m条边。

Output: 链接相同元素的节点对的数量

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
line = input().split(' ')
n = int(line[0])
m = int(line[1])
matrix = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
    tmp = input().split(' ')
    matrix[int(tmp[0])][int(tmp[1])] = 1
    matrix[int(tmp[1])][int(tmp[0])] = 1
def Equal(list1, list2, n):
    flag = True
    for i in range(1, n + 1):
        if list1[i] != list2[i]:
            flag = False
    return flag
ret = 0
for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        if Equal(matrix[i], matrix[j], n):
            ret += 1
print(ret)

分析

我这里用了一种最笨的方法，将图存成邻接矩阵，然后两行完全相同（不包含全为0），则代表他们链接的节点相同。

蛇形输出

蛇形输出或者蛇形赋值在很多地方都出现了，在此提供一个模板。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
def Right(i, j, right_end, bottom_end, ret, matrix):
    if j == right_end and i < bottom_end:
        return Down(i, j, right_end, bottm_end, ret, matrix)
    elif j == right_end and i == bottom_end:
        return 
    else:
        ret.append(matrix[i][j + 1])
        if i == bottom_end:
            return RightUp(i, j + 1, right_end, bottom_end, ret, matrix)
        else:
            return LeftDown(i, j + 1, right_end, bottom_end, ret, matrix)
def Down(i, j, right_end, bottom_end, ret, matrix):
    if i == bottom_end and j == right_end:
        return
    elif i == bottom_end and j < right_end:
        Right(i, j, right_end, bottom_end, ret, matrix)
    else:
        ret.append(matrix[i + 1][j])
        if j == right_end:
            return LeftDown(i + 1, j, right_end, bottom_end, ret, matrix)
        else:
            return RightUp(i + 1, j, right_end, bottom_end, ret, matrix)
def LeftDown(i, j, right_end, bottom_end, ret, matrix):
    if i == bottom_end and j == right_end:
        return
    elif i == bottom_end:
        return Right(i, j, right_end, bottom_end, ret, matrix)
    elif j == 0:
        return Down(i, j, right_end, bottom_end, ret, matrix)
    else:
        ret.append(matrix[i + 1][j - 1])
        return LeftDown(i + 1, j - 1, right_end, bottom_end, ret, matrix)
def RightUp(i, j, right_end, bottom_end, ret, matrix):
    if i == bottom_end and j == right_end:
        return
    elif j == right_end:
        return Down(i, j, right_end, bottom_end, ret, matrix)
    elif i == 0:
        return Right(i, j, right_end, bottom_end, ret, matrix)
    else:
        ret.append(matrix[i - 1][j + 1])
        return RightUp(i - 1, j + 1, right_end, bottom_end, ret, matrix)
n = int(input())
matrix = [[str(j) + '+' + str(i) for i in range(n)] for j in range(n)]        
ret = []
ret.append(matrix[0][0])
Down(0, 0, n - 1, n - 1, ret, matrix)
print(ret)

子串长度

Input: 只包含小写字母的字符串。

Output: 包含连续两个“abcde”或者不包含“abcde”的子串最长长度。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
strs = input()
chars = 'abcde'
dp = [0 for i in range(len(strs) + 1)]
for i in range(len(strs)):
    if strs[i] not in chars:
        dp[i + 1] = dp[i] + 1
    else:
        if i == 0:
            dp[i + 1] = dp[i]
        elif strs[i] == strs[i - 1]:
            dp[i + 1] = dp[i - 1] + 2
        else:
            dp[i + 1] = 0
max = 0
for i in range(len(strs) + 1):
    if dp[i] > max:
        max = dp[i]
print(max)

字符串分割相等

Input: ","分隔的两个字符串。

Output: 如果两个字符串相同或者分隔成子串相同，则输出“true”，否则输出“false”。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
line = input().split(',')
str1 = line[0]
str2 = line[1]
def Equal(str1, str2):
    if len(str1) != len(str2):
        return False
    elif len(str1) == 1 and str1 != str2:
        return False
    elif str1 == str2:
        return True
    elif len(str1) % 2 == 1:
        return Equal(str1[0: int(len(str1) / 2)], str2[int(len(str2) / 2) - 1:]) and Equal(str2[0: int(len(str2) / 2) - 1], str1[int(len(str1) / 2):]) or (Equal(str1[0: int(len(str1) / 2) - 1], str2[int(len(str2) / 2):]) and Equal(str2[0: int(len(str2) / 2)], str1[int(len(str1) / 2) - 1:]))
    else:
        return Equal(str1[0: int(len(str1) / 2)], str2[int(len(str2) / 2):]) and Equal(str2[0: int(len(str2) / 2)], str1[int(len(str1) / 2):]) 
if Equal(str1, str2):
    print('true')
else:
    print('false')

分析

递归的思想，如果当前串相同则返回True，否则将串二等分，看子串是否相等。

杨辉三角

Input: 行数n；每一行有2 × i - 1个数字，构成一个三角形。

Output: 从第一行走到最后一行最大的和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
n = int(input().strip())
matrix = [[0 for i in range(2 * n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    line = input().split(' ')
    for j in range(n + 1 - i, n + 1 - i + len(line)):
        matrix[i][j] = int(line[j - n + i - 1])
dp = [[0 for i in range(2 * n + 1)] for j in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, 2 * n):
        if i == 1:
            dp[i][j] = matrix[i][j]
        else:
            dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j]
print(max(dp[-1]))

分析

比较经典的动态规划题。动态规划与递归的区别在于动态规划利用“最优子结构”这个特性，所以下一个状态由上一个状态推出，写代码时是从头往后，而递归则是从后往前。

回字形写入斐波拉契数列

Input: 矩阵的边长n。

Output: 回字形写入斐波拉契数列的n × n矩阵。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
def Trans(matrix):
    if len(matrix) == 0:
        return
    new_matrix = []
    tmp_line = []
    for j in range(len(matrix[0]) - 1, -1, -1):
        tmp_line = []
        for i in range(len(matrix)):
            tmp_line.append(matrix[i][j])
        new_matrix.append(tmp_line)
    return new_matrix
ret = []
def ReadLine(matrix):
    if len(matrix) > 1:
        ret.append(matrix[0])
        return ReadLine(Trans(matrix[1:]))
    elif len(matrix) == 1:
        ret.append(matrix[0])
    else:
        return
n = int(input()) 
matrix = [['' for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        matrix[i][j] = str(i) + '+' + str(j)
ReadLine(matrix) 
m = n * n
def FB(m):
    fb_arr = []
    fb_arr.append(0)
    for i in range(1, m + 1):
        if i == 1 or i == 2:
            fb_arr.append(1)
        else:
            fb_arr.append(fb_arr[i - 2] + fb_arr[i - 1])
    return fb_arr
fb_arr = FB(m)[::-1]
ret_matrix = [[0 for i in range(n)] for j in range(n)]
for i in range(len(ret)):
    for j in range(len(ret[i])):
        tmp = ret[i][j].split('+')
        t = int(tmp[0])
        k = int(tmp[1])
        ret_matrix[t][k] = fb_arr[0]
        fb_arr = fb_arr[1:]
print(ret_matrix)

分析

回字形输出，等价于先输出矩阵第一行，然后将矩阵旋转（这个时候之前的最右列就变成了第一行）再输出，往复到矩阵为空。

前K大的数

求一堆数中前K大的数。 一般可以使用小顶堆来实现。用数组保存堆的时候：左子树 = 父节点 × 2；右子树 = 父节点 × 2 + 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
k = 4
k_tree = [-1 for i in range(0, k + 1)]
def FindLeft(root):
    if root * 2 <= k:
        return root * 2
    return -1
def FindRight(root):
    if root * 2 <= k - 1:
        return root * 2 + 1
    return -1
def BuildTree(val, root):
    if val <= k_tree[root]:
        return
    else:
        swap(val, root)
def swap(val, root):
    if FindLeft(root) != -1 and val <= k_tree[FindLeft(root)]:
        k_tree[root] = val
    elif FindRight(root) != -1 and val >= k_tree[FindRight(root)]:
        k_tree[root] = k_tree[FindRight(root)]
        k_tree[FindRight(root)] = val
        swap(k_tree[root], root)
        swap(val, FindRight(root))
    elif FindLeft(root) != -1 and FindRight(root) != -1 and val > k_tree[FindLeft(root)] and val < k_tree[FindRight(root)]:
        k_tree[root] = k_tree[FindLeft(root)]
        k_tree[FindLeft(root)] = val
        swap(val, FindLeft(root))
    elif FindLeft(root) != -1 and FindRight(root) == -1 and val >= k_tree[FindLeft(root)]:
        k_tree[root] = k_tree[FindLeft(root)]
        k_tree[FindLeft(root)] = val
        swap(val, FindLeft(root))
for i in [12,32,53,45,6,7,6,8,9,9,324,6,5,4]:
    BuildTree(i, 1)
    print(k_tree)

两个有序的整数列表合并

简单版的归并排序。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
def Sort(list1, list2):
    ret_list = []
    len1 = len(list1)
    len2 = len(list2)
    idx1 = idx2 = 0
    while idx1 < len1 or idx2 < len2:
        if idx1 >= len1:
            ret_list.append(list2[idx2])
            idx2 += 1
        elif idx2 >= len2:
            ret_list.append(list1[idx1])
            idx1 += 1
        elif list1[idx1] < list2[idx2]:
            ret_list.append(list1[idx1])
            idx1 += 1
        else:
            ret_list.append(list2[idx2])
            idx2 += 1
    return ret_list
list1 = [1,2,5,6,7,32,44]
list2 = [32,43,45,56,767]
print(Sort(list1, list2))

快速排序

快速排序作为排序的代表，原型或者其变型经常被考察。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
def quick_sort(array, left, right):
    if left >= right:
        return
    low = left
    high = right
    key = array[left]
    while left < right:
        if left < right and array[right] > key:
            right -= 1
        array[left] = array[right]
        if left < right and array[left] <= key:
            left += 1
        array[right] = array[left]
    array[left] = key
    quick_sort(array, low, left - 1)
    quick_sort(array, left + 1, high)
array = [1,4,2,3,45,46,6,57,68,79,98,223]
quick_sort(array, 0, len(array) - 1)
print(array)

矩阵查找

一个行、列都递增的矩阵中查找某个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
def solution(matrix, target):
    if not matrix:
        return False
    if not matrix[0]:
        return False     
    if target > matrix[-1][-1] or target < matrix[0][0]:
        return False
    j = 0
    i = len(matrix) - 1
    while True:                    
        if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]):
            return False
        if matrix[i][j] > target:
            i -= 1
        elif matrix[i][j] < target:
            j += 1
        else:
            return True

连续不为0的区间和最大

Input: 数组长度n；数组的n个值；m个不同分割下标。

Output: 分别输出m个以对应下标分割的子区间的连续不为0的最大和。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
n = int(input())
line2 = input().split(' ')
line3 = input().split(' ')
line = [0 for i in range(n + 1)]
for i in range(n):
    line[i + 1] = int(line2[i])
def BIG(sep, line):
    line[sep] = 0
    ret_sep = []
    tmp = 0
    for i in range(n + 1):
        if line[i] == 0:
            ret_sep.append(tmp)
            tmp = 0
        else:
            tmp += line[i]
    ret_sep.append(tmp)
    max = 0
    for item in ret_sep:
        if item > max:
            max = item
    return max
for i in range(n):
    sep = int(line3[i])
    print(BIG(sep, line))

矩阵中“CHINA”的个数

Input: 矩阵大小n，以及n × n的字符矩阵。

Output: "CHINA"的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
n = int(input())
n_lines = []
for i in range(n):
    n_lines.append(input()) 
china_num = 0
arr_i = [1, -1, 0, 0]
arr_j = [0, 0, 1, -1]
def DFS(i, j, len):
    if len == 5:
        china_num += 1
    else:
        for t in range(4):
            new_i = i + arr_i[t]
            new_j = j + arr_j[t]
            if new_i >= 0 and new_j >= 0 and new_i < n and new_j < n:
                if len == 1 and n_lines[new_i][new_j] == 'H':
                    DFS(new_i, new_j, len + 1)
                elif len == 2 and n_lines[new_i][new_j] == 'I':
                    DFS(new_i, new_j, len + 1)
                elif len == 3 and n_lines[new_i][new_j] == 'N':
                    DFS(new_i, new_j, len + 1)
                elif len == 4 and n_lines[new_i][new_j] == 'A':
                    DFS(new_i, new_j, len + 1)
for i in range(n):
    for j in range(len(n_lines[i])):
        if n_lines[i][j] == 'C':
            DFS(i, j, 1)
print(china_num)

分析

在矩阵中可以上下左右组合的字符串或者递增子序列之类的问题，都可以使用DFS来做。

字符串中“Good”的数量

Input: 字符串。

Output: Good的数量

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
line = input().strip()
mark = [0 for i in range(len(line))]
ret = 0
for i in range(len(line)):
    if line[i] == 'G':
        mark[i] = 1
        j = i
        o_count = 0
        d_count = 0
        while j < len(line) and o_count < 2:
            if line[j] == 'o' and mark[j] == 0:
                o_count += 1
                mark[j] = 1
                j += 1
        if o_count == 2:
            while j < len(line) and d_count < 1:
                if line[j] == 'd' and mark[j] == 0:
                    d_count += 1
                    j += 1
            if d_count == 1:
                ret += 1
            else:
                break
        else:
            break
print(ret)

分析

字符串中存在某种子序列，做法大致相同。

矩阵的递增序列

Input: n × n矩阵。

Output: 最长递增序列的长度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
n = int(input())
matrix = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
    line = input().strip().split(' ')
    for j in range(n):
        matrix[i][j] = int(line[j])
dfs = [[0 for i in range(n)] for j in range(n)]
x_d = [0, 0, 1, -1]
y_d = [1, -1, 0, 0]
def DFS(x, y, dfs):
    if dfs[x][y] != 0:
        return dfs[x][y]
    for i in range(len(x_d)):
        new_x = x + x_d[i]
        new_y = y + y_d[i]
        if new_x >= 0 and new_y >= 0 and new_x < n and new_y < n:
            if matrix[new_x][new_y] > matrix[x][y]:
                dfs[x][y] = max(DFS(new_x, new_y, dfs) + 1, dfs[x][y])
            else:
                dfs[x][y] = max(1, dfs[x][y])
    return dfs[x][y]
for i in range(n):
    for j in range(n):
        dfs[i][j] = DFS(i, j, dfs)
print(max(max(dfs)))

分析

一个很明显的思路就是从某点出发，DFS查找最长的递增路径，但是考虑到某些节点可能在之前已经遍历过，可以使用其保存的信息。

不重叠区间

Input: n个不同区间。

Output: 去掉多少区间之后，剩下的区间构成不重叠区间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
interval_list = []
n = int(input())
for i in range(n):
    line = input().strip().split(' ')
    interval_list.append([int(line[0]), int(line[1])])
interval_list = sorted(interval_list, key = lambda item:item[1])
dp = [1 for i in range(n)]
for i in range(n):
    for j in range(i - 1, -1, -1):
        if interval_list[i][0] >= interval_list[j][1]:
            dp[i] = max(dp[j] + 1, dp[i])
        else:
            dp[i] = max(dp[i], dp[j])
print(n - dp[-1])

机器人行走

Input: 有t组测试，每一组机器人从(0, 0)位置朝向向上，向右为x轴正方向，向下为y轴正方向，指令有：向左转(L)，向右转®，前进N步或者到头(G N)以及打印当前位置(P)。

Output: 打印每个Case的编号以及执行P指令之后的输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
t = int(input())
cur_x = 0
cur_y = 0
cur_t = 1
Turns = ['L', 'U', 'R', 'D']
step_x = [0, -1, 0, 1]
step_y = [-1, 0, 1, 0]
def Turn(cur_t, turn):
    if turn == 'R':
        cur_t += 1 % len(Turns)
    else:
        cur_t -= 1 % len(Turns)
    return cur_t  
def Walk(cur_x, cur_y, cur_t, step, n):
    if cur_x + step * step_x[cur_t] >= 0 and cur_x + step * step_x[cur_t] < n and cur_y + step * step_y[cur_t] >= 0 and cur_y + step * step_y[cur_t] < n:
        return cur_x + step * step_x[cur_t], cur_y + step * step_y[cur_t]
    elif cur_x + step * step_x[cur_t] < 0:
        cur_x = 0
    elif cur_y + step * step_y[cur_t] < 0:
        cur_x = 0
    elif cur_x + step * step_x[cur_t] >= n:
        cur_x = n - 1
    elif cur_y + step * step_y[cur_t] >= n:
        cur_y = n - 1   
    return cur_x, cur_y
ret = ''  
for times in range(t):
    ret += 'Case #' + str(times + 1) + ':\n'
    n_m = input().strip().split(' ')
    n = int(n_m[0])
    m = int(n_m[1])
    cur_x = 0
    cur_y = 0
    cur_t = 1
    for i in range(m):
        line = input().strip().split(' ')
        if line[0] == 'L' or line[0] == 'R':
            cur_t = Turn(cur_t, line[0])
        elif line[0] == 'G':
            cur_x, cur_y = Walk(cur_x, cur_y, cur_t, int(line[1]), n)
        elif line[0] == 'P':
            ret += str(cur_y) + ' ' + str(cur_x) + '\n'
print(ret)

将0/1表示的字符串根据莫斯密码转化成字符串

以‘1’表示摩斯密码中的‘·’，以‘111’表示摩斯密码中的‘-’。
以‘0’表示莫斯密码中的分割。
以‘000’表示不同字符摩斯密码的分割。
以‘0000000’表示不同单词的分割。

Input: 以0/1表示的字符串

Output: 转化后的字符串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
line = input().strip()
ret = ''
last = 0
letter = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890'
ms = ['01', '1000', '1010', '100', '0', '0010', '110', '0000', '00', '0111', '101', '0100', '11', '10', '111', '0110', '1101', '010', '000', '1', '001', '0001', '011', '1001', '1011', '1100', '01111', '00111', '00011', '00001', '0000', '10000', '11000', '11100', '11110', '11111']
def DealC(line):
    chr = ''
    for i in line.split('0'):
        if i == '1':
            chr += '0'
        else:
            chr += '1'
    for i in range(len(ms)):
        if ms[i] == chr:
            return letter[i]
def DealL(line):
    ret = ''
    lst = 0
    for i in range(len(line) - 3):
        if line[i: i + 3] == '000':
            ret += str(DealC(line[lst: i]))
            lst = i + 3
    ret += str(DealC(line[lst:]))
    return ret
for i in range(len(line) - 7):
    if line[i:i + 7] == '0000000':
        ret += str(DealL(line[last: i])) + ' '
        last = i + 7
ret += str(DealL(line[last:]))
print(ret)

数n中各位数字全排列能整除数m的个数

Input: 两个数字n和m。

Output: 数n中各位数字全排列能整除数m的个数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
line = input().split(' ')
n = int(line[0])
m = int(line[1])
num_list = [0 for i in range(10)]
lens = 0
while n > 0:
    num_list[n % 10] += 1
    n //= 10
    lens += 1
ret = 0    
def IN(num, num_list):
    tmp_num_list = [0 for i in range(10)]
    while num > 0:
        tmp_num_list[num % 10] += 1
        num //= 10
    if tmp_num_list[0] <= num_list[0]:
        for i in range(1, 10):
            if tmp_num_list[i] != num_list[i]:
                return False
        return True
    else:
        return False
for i in range(1, int(pow(10, lens) / m)):
    if IN(m * i, num_list):
        print(m * i)
        ret += 1
print(ret)

分析

我的思路是通过逆向观察m倍数需要的那些数字是否都在n里面来判断n的各位全排列能否得到m的倍数。当然，如果n中0的个数大于m的倍数中0的个数是不影响的。

最长回文子串

Input: 字符串

Output: 最长回文子串

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
 
line = input().strip()
dp = [0] * len(line)
for i in range(1, len(line)):
    if line[i] == line[i - dp[i - 1] - 1] and i - dp[i - 1] - 1 >= 0:
        dp[i] = dp[i - 1] + 2
    elif line[i] == line[i - 2] and dp[i - 1] == 0:
        dp[i] = 3
    else:
        dp[i] = 0

for i in range(len(dp)):
    if max(dp) == dp[i]:
        print(line[i + 1 - max(dp): i + 1])

分析

简单的动态规划，但是要考虑两种情况：（1）回文串长度为偶数；（2）回文串长度为奇数即中间的字母不用回文。

大鱼吃小鱼

Input: 长度为n的整数串

Output: 每次大鱼吃小鱼，可以同时进行，输出大鱼吃小鱼的次数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
n = int(input())
line = input().split(' ')
int_list = [int(line[i]) for i in range(len(line))]
live = [1] * len(int_list)
left = len(int_list)
new_left = 65535
ret = -1
while left < new_left:
    new_left = left
    key = int_list[0]
    for i in range(1, len(int_list)):
        new_k = int_list[i]
        if key > int_list[i]:
            int_list[i] = -1
        key = new_k
    ret += 1
    for i in range(len(int_list)- 1, -1, -1):
        if int_list[i] == -1:
            int_list.pop(i)
    left = len(int_list)
print(ret)

非递归版二叉树深度

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 
num =int(input())
class TreeNode:
    def __init__(self, val = None, left = None,right = None):
        self.val = val
        self.left = left
        self.right = right
def Depth(root):
    if root == None:
        return 0
    else:
        queue = []
        depth = 0
        queue.append(root)
        while len(queue):
            depth += 1
            cur = len(queue)
            tmp = 0
            while(tmp < cur):
                tmp += 1
                node = queue.pop(0)
                if node.left != None:
                    queue.append(node.left)
                if node.right != None:
                    queue.append(node.right)
        return depth
treenode = [None for i in range(num)]
for i in range(num):
    treenode[i] = TreeNode(i)
for i in range(num):
    if i * 2 + 1 < num:
        treenode[i].left = treenode[i * 2 + 1]
    if i * 2 + 2 < num:
        treenode[i].right = treenode[i * 2 + 2]
print(Depth(treenode[0]))

分析

二叉树深度就是二叉树层数，所以可以使用层序遍历二叉树实现。

数组中出现超过一半的数字

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
def majorityElement(nums: List[int]) -> int:
        dp = [0] * len(nums)
        dp[0] = 1
        votes = nums[0]
        for i in range(1, len(nums)):
            if dp[i - 1] == 0:
                votes = nums[i]
                dp[i] = 1
                continue
            if votes == nums[i]:
                dp[i] = dp[i - 1] + 1
            else:
                dp[i] = dp[i - 1] - 1
        return votes

分析

每一步设定当前值为“大于一半的数”并将此时的值记为“+1”，往后遇到不同的值在该值上“-1”，遇到值为0，则将前面的序列舍弃，重新开始计数。最终在序列扫描一遍之后的假设“大于一半的数”的值即为最终结果。

最长不含重复字符的子字符串

描述

从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

Input: “abcabcbb”
Output: 3
Reason: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) <= 1:
            return len(s)
        maxs = 1
        dp = [1 for i in range(len(s))]
        def Find_i(s, idx):
            if idx == 0:
                return 0
            for i in range(idx - 1, -1, -1):
                if s[i] == s[idx]:
                    return i
            return -1
        for i in range(1, len(s)):
            if dp[i - 1] < i - 1 - Find_i(s, i):
                dp[i] = dp[i - 1] + 1
            else:
                dp[i] = i - Find_i(s, i)
        return max(dp)

分析

可以用动态规划来解，首先定义函数Find_i，用来找到当前i节点往前最近与之相同的字符的位置（没有则返回-1）。

然后，状态转移方程为：

  • dp[i] = dp[i - 1] + 1，当dp[i - 1] < i - Find_i(s, i)时，否则：
  • dp[i] = i - Find_i(s, i)。

最后返回dp最大值，即为所求。



The link of this page is https://blog.nooa.tech/articles/fdc308a8/ . Welcome to reproduce it!

© 2018.02.08 - 2024.05.25 Mengmeng Kuang  保留所有权利！

:D 获取中...

Creative Commons License