20220829 阿里巴巴 开发岗笔试题
第一题：打印“里”字。
题目：输入“里”字的大小n，输出n倍大小的“里”字
思路：
- 首先，根据给的模板，二维数组保存1倍大小的“里”字；
- 每列的元素复制n份；（如n=3，‘--*--’变成‘------***------’）
- 每行往下复制n份;
- 就变成了n倍大小的“里”字了。
第二题：消消乐
题目：有个二维数组，保存4种颜色：r,b,g,p，对应4种分数：1,2,3,5。邻近的同色可以消除（上下左右），并获得消除掉的分数。小红可以点击k个块，问小红能获得得最高分数？
思路：
- 将r,b,g,p转成分数数组，然后dfs计算每个块的分数；（题目岛屿数量的思路）
- 求和topk的分数；
示例：
输入：3 3 3 （表示行，列，k）
rbr
rrp
bgg
输出：14
代码：
def cal_score(arr, mask, num, i, j, score): if i < 0 or j < 0 or i >= len(arr) or j >= len(arr[0]): # 判断越界 return score if arr[i][j] != num or mask[i][j] == 1: # 不属于同种颜色的 or 已经遍历过的 return score if mask[i][j] == 0: # 没遍历过 mask[i][j] = 1 score += arr[i][j] score = cal_score(arr, mask, num, i + 1, j, score) score = cal_score(arr, mask, num, i, j + 1, score) score = cal_score(arr, mask, num, i - 1, j, score) score = cal_score(arr, mask, num, i, j - 1, score) return score data = list(map(int, input().split())) # 获取n m k n = data[0] m = data[1] k = data[2] arr = [] for i in range(n): # 保存对应的分数数组 line = [] for c in input(): if c == 'r': line.append(1) elif c == 'b': line.append(2) elif c == 'g': line.append(3) elif c == 'p': line.append(5) arr.append(line) mask = [] for i in range(n): # 生成mask数组 l = [0 for j in range(m)] mask.append(l) res = [] for i in range(n): # 计算每个点的消消乐分数 for j in range(m): # 初始分数为0，如果arr[i][j]已经遍历过，返回0 res.append(cal_score(arr, mask, arr[i][j], i, j, 0)) res.sort(reverse=True) # 求和top k值 print(sum(res[:k]))
第三题：2022的倍数
题目：两个数组各选一个数，乘积是2022倍数，问有多少种组合？提示，2022=2*3*337
思路1：暴力判断所有的组合是否是2022的倍数，超时。因为每个数参与了多次计算。
思路2：2022的倍数=2的倍数*3的倍数*337的倍数，保证2、3、337的倍数各有一个，那么一定是2022的倍数。
- 一个数是2、3、337的倍数，可以表示为1，10，100；
- 将一个数分成8类：0，1，10，100，11，101，110，111；
- 两个数的类别相加，只要大于等于111，那么这个数一定是2022的倍数；（因为保证了2、3、337的倍数各有一个）
思路2与思路1相比：
- 思路2是，每个数求余3次，可以确定数的类别，然后就可以统计各个类别的组合数，时间O(n+m)；
- 思路1是，两两数的组合求余1次，统计组合数，时间O(n*m);
- 巧妙将原问题转成组合问题；
代码：
谢谢博主的分享！
查看9道真题和解析
