22年秋招B站测试开发编程题

发表于 更新于 分类于
本文字数： 2.3k 阅读时长 ≈ 8 分钟

前言

23秋招B站测试开发笔试。

1

题目描述：
现在给出一个大小为n的序列A=a1,a2,a3,…ai...anA = {a_1,a_2,a_3, …a_i...a_n}。现在你可以随意交换任意两个数（至多只交换一次），使得$\sum_{i=1}{i=n}(-1){i-1}\times a_i=a_1-a_2+a_3+\dots a_n $的值最大。
求出最大值。
输入描述：

第一行输入一个正整数n，表示序列A的大小
随后一行给出n个正整数a1,a2,a3…ai…ana_1, a_2, a_3 \dots a_i \dots a_n
2≤n≤1052 \le n\le 10^5
1≤ai≤10001\le a_i\le1000

输出描述:

输出$ \sum_{i=1}{i=n}(-1){i-1}\times a_i$的最大值

示例1
输入：

1
2
11
4 10 7 5 4 5 3 8 3 2 5

输出：

1
10

示例2
输入：

1
2
4
1 1 1 1

输出：

1
0

解答思路：

题目很简单，就是奇数位置的数为加，偶数位置的数为减，即从偶数位置中选取最大的数和奇数位置中最小的数做交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxSum(self, nums):
        odd_nums = [nums[i] for i in range(len(nums)) if i % 2 == 0]
        even_nums = [nums[i] for i in range(len(nums)) if i % 2 != 0]
        # print(odd_nums, even_nums)
        odd_sum = sum(odd_nums)
        even_sum = sum(even_nums)
        # print(odd_sum, even_sum)
        ans = odd_sum - even_sum + max(even_nums) * 2 - min(odd_nums) * 2
        return ans


if __name__ == '__main__':
    s = Solution()
    count = eval(input())
    nums = input().split(' ')
    nums = [eval(i) for i in nums]
    # nums = [4, 10, 7, 5, 4, 5, 3, 8, 3, 2, 5]
    # print(nums)
    ans = s.maxSum(nums)

    print(ans)

2

题目描述：
给出一个大小为n×mn \times m的矩阵，你可以修改矩阵的数字，将该矩阵的每一行每一列都成为一个回文序列。
请问：最少的修改次数是多少。
输入描述：

第一行输入一个正整数n,m，表示矩阵的大小。
随后n行m列，给出矩阵的数xi,jx_{i , j}。
2≤n,m≤10002 \le n, m\le 1000
1≤xi,j≤10001\le x_{i ,j}\le1000

输出描述:

输出修改的最少次数。

示例1
输入：

1
2
3
4
3 3
1 2 1
1 2 1
1 3 1

输出：

1
1

示例2
输入：

1
2
3
4
5
4 4
1 2 2 1
2 1 2 1
2 1 1 2
1 2 1 2

输出：

1
6

解答思路：
该题的主要思想为判断四角数值是否相等。

使用了一个哈希表，来进行判断，也可以将四角的数据依次判断。

其中注意当行或列为奇数时，最中间的单独一列会在比较中重复一次，所以如果数值不同，只需要加一。

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
import collections

class Solution:
    def changeCount(self, m, n, nums):
        ans = 0
        m, n = m - 1, n - 1
        m_m, n_m = m // 2, n // 2
        i = 0
        while (i <= m_m):
            j = 0
            while (j <= n_m):
                # print([nums[i][j], nums[m - i][j], nums[i][n - j], nums[m - i][n - j]])
                a = collections.Counter([nums[i][j], nums[m - i][j], nums[i][n - j], nums[m - i][n - j]])
                # print(a)
                # print(max(a.values()))
                if (m % 2 == 0 and i == m // 2) or (n % 2 == 0 and j == n // 2):  # 说明为奇数且目前在中间一列
                    if len(a) == 2:
                        ans += 1
                else:
                    ans += 4 - max(a.values())
                j += 1
            i += 1
        return ans


if __name__ == '__main__':
    s = Solution()
    # 输入输出格式
    # shape = [eval(i) for i in input().split(' ')]
    # m, n = shape[0], shape[1]
    # # print(m, n)
    # array = [[0] * n for _ in range(m)]
    # for i in range(m):
    #     array[i] = [eval(j) for j in input().split(' ')]

    array = [[1, 2, 2, 1],
             [1, 2, 2, 1],
             [2, 1, 1, 2],
             [1, 2, 1, 2]]
    # array = [[1, 2, 1],
    #          [2, 1, 2],
    #          [1, 1, 1]]
    m, n = len(array), len(array[0])
    # print(array)
    ans = s.changeCount(m, n, array)
    print(ans)
----------到结尾啦！！ Hoohoo----------