今天练习的是Shopee最新机考笔试题3题。

各大厂真题都整理了近两年的机考题，题库里面有详细思路和答案~

肥猫学长也提供机考辅导助攻和面试辅导欢迎咨询。

微信号：jackwwang8

目前已经整理的题库有如下：如果有需要可以加我微信获取哦

虾皮笔试春招题目3.28

第一题：艾尔罗大迷宫

题干描述

设计一个迷宫游戏系列艾尔罗。在设计初期为了方便，使用矩阵表示。

0代表可到达区域，1表示不可到达区域。

例如有：[[0, 1, 0, 0][0, 0, 0, 0][0, 1, 0, 1][0, 0, 1, 0]]

在这个例子中，因为周围都是障碍物。

所以相对于起点[0,0]来说，[1,3]的位置是不可达的，只允许左右上下移动。

为了方便评估设计的艾尔罗迷宫的难易程度，需要有一个方便的算法统计每个迷宫不可到达的网格有多少个。

比如上面的不可达区域为原生不可达的区域加上衍生的被四面围堵产生的不可达区域，也就是所有不可达的格子总数。

约束：起点统一定义为[0,0]。

给定的迷宫二维数组矩阵形式是N*N二维数组，且[0,0]也总是可达，值为0，原生不可达的用值1表示。

测试用例

输入:

[[0,1,1,0],[1,0,0,0],[0,1,0,1],[0,1,1,0]]

输出:

15

输入:

[[0,0,0,0],[1,0,0,1],[0,0,1,0],[0,0,0,1]]

输出:

5

解题思路

问题转化

可达区域：从起点出发，只能走数值为0的格子（障碍物1无法通过）。不可达区域：包含原生障碍物（值为1的格子），以及那些被障碍物包围而无法从起点到达的0格子。

搜索策略：BFS和DFS

初始化：起点[0,0]一定是可到达的（题目保证该处值为0）。搜索过程：使用BFS或DFS遍历所有可以到达的0格子。每个位置只能向上下左右四个方向移动。使用一个访问数组（或直接在原数组上标记）防止重复访问。统计结果：矩阵总格子数为N*N，减去从起点访问到的格子数量，即为不可到达的格子数。

## 第一题 艾尔罗大迷宫from collections import dequeclass Solution:    def apply(self, generated_map):        ## 获取迷宫的行数（列数相同）        n = len(generated_map)        ## 记录每个位置是否访问过        visited = [[False] * n for _ in range(n)]        ## 四个方向：上、下、左、右        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]        ## 广度优先搜索队列，存储当前可达的位置        q = deque()        q.append((0, 0))        visited[0][0] = True        ## 统计从起点0,0能够到达的格子数        reachable_count = 1        while q:            x, y = q.popleft()            ## 向四个方向进行广度搜索            for dx, dy in directions:                nx = x + dx                ny = y + dy                ## 新位置必须在边界内、值为0、且没有访问过                if 0 <= nx < n and 0 <= ny < n and generated_map[nx][ny] == 0 and not visited[nx][ny]:                    visited[nx][ny] = True                    q.append((nx, ny))                    reachable_count += 1        ## 总格子数减去可达格子数等于不可达格子数        return n * n - reachable_count

第二题：2的N次方的十进制结果

题干描述

对于一个整数N，计算2的N次方并在屏幕显示十进制结果。

测试用例

输入:

1024

输出:

"179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216"

输入:

1025

输出:

"359538626972463181545861038157804946723595395788461314546860162315465351611001926265416954644815072042240227759742786715317579537628833244985694861278948248755535786849730970552604439202492188238906165904170011537676301364684925762947826221081654474326701021369172596479894491876959432609670712659248448274432"

解题思路

本题要求计算2的N次方的十进制结果。由于N的结果位数非常多，已经远远超出普通整型范围，因此需要使用高精度算法来完成计算。

相关算法是：高精度乘法（大整数模拟）

核心思路如下：

用数组或字符串来保存这个大整数的每一位数字。初始值设为1。接下来循环执行N次乘以2。每次乘法时，从低位到高位逐位计算：当前位乘以2，再加上进位；当前位保留个位；十位以上作为新的进位。一次遍历结束后，如果还有进位，就继续加入结果中。最后将高位到低位依次输出，即可得到十进制答案。

这里本质上是在模拟我们手算大整数乘法的过程，只不过乘数固定为2，所以实现起来更简单。用一个数组保存数字，按低位在前，高位在后的方式存储，方便处理进位。

## 第2题 2的N次方的十进制结果class Solution:    def Power2N(self, n):        ## 使用列表存储大整数，采用低位在前的数组方式存储，方便进位操作        digits_array = [1]         ## 进行n次乘2的操作        for _ in range(n):            carry_num = 0            ## 每一位乘2并且处理进位            for i in range(len(digits_array)):                ## 当前位乘2并加上之前的进位                current_temp = digits_array[i] * 2 + carry_num                ## 获取当前位的个位数字                digits_array[i] = current_temp % 10                ## 获取十位数字作为下一次进位                carry_num = current_temp // 10            ## 当循环结束后，如果最高位还有进位，则不断追加到数组后面            while carry_num > 0:                digits_array.append(carry_num % 10)                carry_num //= 10        ## 转换为字符串时，需要将数组翻转以符合高位在前的阅读习惯        final_result = ''.join(str(d) for d in reversed(digits_array))        return final_result

第三题：寻找数组中只出现过一次的数字

题干描述

给定一个数组，数组中除了两个数字只出现过一次外，其余数字都恰好出现两次，找出这两个数字，并且从小到大输出。

测试用例

输入:

[1,2,2,3]

输出:

[1,3]

解题思路

本题的最优解法是使用位运算中的异或算法。

由于数组中除了两个只出现一次的数之外，其余数字都出现两次，因此把所有数字整体异或后，成对的数字都会被抵消，最终结果就是这两个只出现一次数字的异或值。

这一位说明，这两个数字的二进制表示在这一位上是不同的。接下来，利用这一位是否为1，把原数组中的所有数分成两组：

一组这一位是1；

一组这一位是0。

由于两个只出现一次的数字在这一位上不同，所以它们一定会被分到不同组中；而那些出现两次的数字一定完全相同，因此也一定会落入同一组，并在组内异或抵消。于是分别对两组做异或，最终就能得到这两个只出现一次的数字。

实现步骤如下：

遍历数组，求出所有数字的整体异或值。取出异或值的最低位1，作为分组依据。再遍历数组，按这一位是否为1分组并分别异或。得到两个答案后，按从小到大输出。

## 第3题 寻找数组中只出现过一次的数字class Solution:    def singleNumber(self, num_array):        ## 先将所有数字进行异或操作        ## 因为相同数字异或结果为0，最后得到的是两个只出现一次的数字的异或值        total_xor_result = 0        for num in num_array:            total_xor_result ^= num        ## 取出整体异或值二进制中最低位的1        ## 这一位可以用来区分这两个只出现一次的数字        diff_bit = total_xor_result & (-total_xor_result)        ## 分别建立两个变量用于两组数字做异或        ## 相同的数字一定会被分到同一组，并在组内抵消        first_unique = 0        second_unique = 0        for num in num_array:            ## 根据diff_bit这一位是否为1，将数字分为两组            if num & diff_bit:                first_unique ^= num            else:                second_unique ^= num        ## 按题目要求按从小到大返回        if first_unique > second_unique:            first_unique, second_unique = second_unique, first_unique        return [first_unique, second_unique]