Kanaries雾角科技算法岗位笔试
笔试时间：2022年10月13号
时长：120分钟
几乎是刷过的算法题，最后一题是难度题，其他都是中等题目。
1、 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
（1）题目
总共有 n 个颜色片段排成一列，每个颜色片段要么是 ‘A’ 要么是 ‘B’ 。给你一个长度为 n 的字符串 colors ，其中 colors[i] 表示第 i 个颜色片段的颜色。
Alice 和 Bob 在玩一个游戏，他们 轮流 从这个字符串中删除颜色。Alice 先手 。
如果一个颜色片段为 ‘A’ 且 相邻两个颜色 都是颜色 ‘A’ ，那么 Alice 可以删除该颜色片段。Alice 不可以 删除任何颜色 ‘B’ 片段。
如果一个颜色片段为 ‘B’ 且 相邻两个颜色 都是颜色 ‘B’ ，那么 Bob 可以删除该颜色片段。Bob 不可以 删除任何颜色 ‘A’ 片段。
Alice 和 Bob 不能 从字符串两端删除颜色片段。
如果其中一人无法继续操作，则该玩家 输 掉游戏且另一玩家 获胜 。
假设 Alice 和 Bob 都采用最优策略，如果 Alice 获胜，请返回 true，否则 Bob 获胜，返回 false。
示例 1：
输入：colors = “AAABABB”
输出：true
解释：
AAABABB -> AABABB
Alice 先操作。
她删除从左数第二个 ‘A’ ，这也是唯一一个相邻颜色片段都是 ‘A’ 的 ‘A’ 。
现在轮到 Bob 操作。
Bob 无法执行任何操作，因为没有相邻位置都是 ‘B’ 的颜色片段 ‘B’ 。
因此，Alice 获胜，返回 true 。
示例 2：
输入：colors = “AA”
输出：false
解释：
Alice 先操作。
只有 2 个 ‘A’ 且它们都在字符串的两端，所以她无法执行任何操作。
因此，Bob 获胜，返回 false 。
示例 3：
输入：colors = “ABBBBBBBAAA”
输出：false
解释：
ABBBBBBBAAA -> ABBBBBBBAA
Alice 先操作。
她唯一的选择是删除从右数起第二个 ‘A’ 。
ABBBBBBBAA -> ABBBBBBAA
接下来轮到 Bob 操作。
他有许多选择，他可以选择任何一个 ‘B’ 删除。
然后轮到 Alice 操作，她无法删除任何片段。
所以 Bob 获胜，返回 false 。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-colored-pieces-if-both-neighbors-are-the-same-color
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
（2）解析
计算满足删除条件的字符，每次删除都计数。当Alice 的操作数大于Bob 的操作数时，Alice 获胜；否则，Bob 获胜。
（3）Python实现
class Solution:
def winnerOfGame(self, colors: str) -> bool:
count = 0
for i in range(1,len(colors)-1):
if colors[i] ==colors[i-1] and colors[i]==colors[i+1]:
if colors[i]=='A':
count+=1
else:
count-=1
return count>0
2、LeetCode 478. 在圆内随机生成点
（1）题目
给定圆的半径和圆心的位置，实现函数 randPoint ，在圆中产生均匀随机点。
实现 Solution 类:
Solution(double radius, double x_center, double y_center) 用圆的半径 radius 和圆心的位置 (x_center, y_center) 初始化对象
randPoint() 返回圆内的一个随机点。圆周上的一点被认为在圆内。答案作为数组返回 [x, y] 。
示例 1：
输入:
[“Solution”,“randPoint”,“randPoint”,“randPoint”]
[[1.0, 0.0, 0.0], [], [], []]
输出: [null, [-0.02493, -0.38077], [0.82314, 0.38945], [0.36572, 0.17248]]
解释:
Solution solution = new Solution(1.0, 0.0, 0.0);
solution.randPoint ();//返回[-0.02493，-0.38077]
solution.randPoint ();//返回[0.82314,0.38945]
solution.randPoint ();//返回[0.36572,0.17248]
提示：
0 < radius <= 108
-107 <= x_center, y_center <= 107
randPoint 最多被调用 3 * 104 次
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/generate-random-point-in-a-circle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
（2）解析
极坐标变换的方法，随机一个半径长度ρ，[0,2π]内再随机一个角度θ，就可以得到一个圆内的点：x=ρ×cos(θ)，y=ρ×sin(θ)。需要注意的是这个半径ρ需要从[0,r×r]内随机抽样然后再开方，不能直接从[0,r]上随机采样得到。因为圆的面积是π×r×r，正比于r的平方，必须从[0,r×r]内随机才能保证是整个圆面中的均匀分布。
（3）Python实现
import random
import math
class Solution:
def __init__(self, radius: float, x_center: float, y_center: float):
self.radius = radius
self.x_center = x_center
self.y_center = y_center
def randPoint(self) -> List[float]:
theta = random.random()*2*math.pi
r = math.sqrt(random.random() * self.radius**2)
x = self.x_center + r*math.cos(theta)
y = self.y_center + r*math.sin(theta)
return x,y
3、LeetCode 73. 矩阵置零
（1）题目
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/set-matrix-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
（2）解析
先确定元素0 的位置，再根据位置，将每行和每列设置为0。
（3）Python实现
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
temp = []
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]==0:
temp.append((i,j))
for row,col in temp:
matrix[row]=[0]*len(matrix[0])
for i in range(len(matrix)):
matrix[i][col] =0
4、 牛客. 数组中未出现的最小正整数
（1）题目
给定一个无序数组arr，找到数组中未出现的最小正整数
例如arr = [-1, 2, 3, 4]。返回1
arr = [1, 2, 3, 4]。返回5
[要求]
时间复杂度为O(n)，空间复杂度为O(1)
链接：https://www.nowcoder.com/questionTerminal/030cabe03d94484c819e87c2e38c41bd?f=discussion
来源：牛客网
输入描述:
第一行为一个整数N。表示数组长度。
接下来一行N个整数表示数组内的数
输出描述:
输出一个整数表示答案
示例1
输入
4
-1 2 3 4
输出
1
示例2
输入
4
1 2 3 4
输出
5
（2）解析
合法的元素序列是，索引和nums元素对应，即索引0对应1，索引1对应2，依次递增。
边排序，边判断不合法元素的位置。
不合法的情况有三种：
- 当前值小于索引
- 当前值大于索引
- 当前值与前面的元素重复
（3）Python实现
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
i = 0
while (i<n):
# 合法的情况：nums中元素与索引对应。索引0对应1，索引1对应2，依次递增
if nums[i]==i+1:
i+=1
'''
出现不合法情况
1.nums的当前值小于索引
2.nums的当前值大于索引
3.nums当前值出现了重复
'''
elif (nums[i]<=i or nums[i]>n or nums[nums[i]-1]==nums[i]):
n -=1
nums[i] = nums[n]
# 表示当前值是一个合法的值，但是没有在理想的位置上，需要进行交换处理
else:
temp = nums[i]
nums[i] = nums[nums[i]-1]
nums[temp-1] = temp
return i+1
5、LeetCode 剑指 Offer 32 - III. 从上到下打印二叉树 III
（1）题目
请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：
[ [3], [20,9], [15,7]]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
（2）解析
思路和【剑指 Offer 32 - II. 从上到下打印二叉树 II】一样，区别在此基础上，只改进一点，奇数层列表是正序，偶数层列表是反序。
（3）Python实现
def levelOrder(self, root: TreeNode) -> List[List[int]]:
if not root: return []
res,queue = [],[root,]
count = 1
while queue:
level_list = []
for _ in range(len(queue)):
node = queue.pop(0)
level_list.append(node.val)
if node.left:queue.append(node.left)
if node.right:queue.append(node.right)
if count%2==0:
res.append(level_list[::-1])
else:
res.append(level_list)
count+=1
return res
6、LeetCode50. Pow(x, n)
（1）题目
实现 Pow(x, n)， 即计算 x 的整数 n 次幂函数（即$x^n$）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/powx-n
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
（2）解析
递归分治法，如果n是1，则返回1，如果是负数，就是求正的分之一，如果是正数，分为两种情况，是奇数，拆出一个x出来，剩余的n-1次幂是偶数继续递归。是偶数，分为两部分乘积，对n对半去递归求解。例如求 $x^4$拆分为$x^2 × x^2$。
（3）Python实现
class Solution:
def myPow(self, x: float, n: int) -> float:
if n==0:
return 1
if n<0:
return 1 / self.myPow(x,-n)
if n%2:
return x*self.myPow(x,n-1)
return self.myPow(x*x,n/2)
7、leetcode1467. 两个盒子中球的颜色数相同的概率
（1）题目
桌面上有 2n 个颜色不完全相同的球，球上的颜色共有 k 种。给你一个大小为 k的整数数组 balls`，其中 balls[i] 是颜色为 i 的球的数量。
所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。
注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例 1 的解释部分）。
请计算「两个盒子中球的颜色数相同」的情况的概率。
示例 1：
输入：balls = [1,1]
输出：1.00000
解释：球平均分配的方式只有两种：
- 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子
- 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子
这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。
示例 2：
输入：balls = [2,1,1]
输出：0.66667
解释：球的列表为 [1, 1, 2, 3]
随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 1/12 ：
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。
这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。
概率 = 8/12 = 0.66667
示例 3：
输入：balls = [1,2,1,2]
输出：0.60000
解释：球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。
概率 = 108 / 180 = 0.6 。
示例 4：
输入：balls = [3,2,1]
输出：0.30000
解释：球的列表为 [1, 1, 1, 2, 2, 3]。要想显示所有 60 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 18 种情况是比较容易的。
概率 = 18 / 60 = 0.3 。
示例 5：
输入：balls = [6,6,6,6,6,6]
输出：0.90327
提示：
- 1 <= balls.length <= 8
- 1 <= balls[i] <= 6
- sum(balls) 是偶数
- 答案与真实值误差在 10^-5 以内，则被视为正确答案
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
（2）解析
参考知乎文章讲解：https://zhuanlan.zhihu.com/p/145606485
（3）Python实现
def get_num(self,balls):
summ = math.factorial(sum(balls))
temp = 1
for ball in balls:
temp *= math.factorial(ball)
return summ/temp
def dfs(self,c,balls,left_arr,right_arr,left_sum,right_sum,n):
if left_sum > n or right_sum > n:
return 0
if c == len(balls):
left_color = 0
right_color = 0
for x in left_arr:
if x:
left_color += 1
for x in right_arr:
if x:
right_color += 1
if left_color == right_color:
return self.get_num(left_arr) * self.get_num(right_arr)
else:
return 0
res = 0
for i in range(balls[c]+1):
left_arr[c] = i
right_arr[c] = balls[c] - i
res += self.dfs(c+1,balls,left_arr,right_arr,left_sum+left_arr[c],right_sum+right_arr[c],n)
return res
def getProbability(self, balls: List[int]) -> float:
total = self.get_num(balls)
print(total)
n = sum(balls)
left_arr = [0 for _ in range(len(balls))]
right_arr = [0 for _ in range(len(balls))]
return self.dfs(0,balls,left_arr,right_arr,0,0,n)/total
es = 0
for i in range(balls[c]+1):
left_arr[c] = i
right_arr[c] = balls[c] - i
res += self.dfs(c+1,balls,left_arr,right_arr,left_sum+left_arr[c],right_sum+right_arr[c],n)
return res
def getProbability(self, balls: List[int]) -> float:
total = self.get_num(balls)
print(total)
n = sum(balls)
left_arr = [0 for _ in range(len(balls))]
right_arr = [0 for _ in range(len(balls))]
return self.dfs(0,balls,left_arr,right_arr,0,0,n)/total
