来源：投稿 作者：LSC
编辑：学姐
unset
unset
一面
unset
unset
1.自我介绍，我说了10min
2.Coding
原代码的fll和 over函数是空白的，完善下面代码的"
Design an algorithm to fill the entire chessboard with gobang(五子棋), which
means every grid on the board should be occupied by either a black or a white piece.
The chessboard is a 2D array of size n x n, where n is an odd integer.
The first player is Black, and the second player is White. The chessboard is
initially empty.
from enum import Enum
class State(Enum):
EMPTY = 0
BLACK = 1
WHITE = 2
# &&&&****&&
# ****&&&&**
# &&&&****&&
class Gobang:
def __init__(self, size: int = 15):
self.size = size
self.chessboard: list[list[State]] = [
[State.EMPTY for _ in range(size)] for _ in range(size)
]
def fill(self) -> None:
"""
fill the entire chessboard
"""
for i in range(self.size):
for j in range(self.size):
if i % 2 == 0:
if (j // 4) % 2 == 0:
self.chessboard[i][j] = State.BLACK
else:
self.chessboard[i][j] = State.WHITE
else:
if (j // 4) % 2 == 0:
self.chessboard[i][j] = State.WHITE
else:
self.chessboard[i][j] = State.BLACK
def is_over(self) -> bool:
"""
check if the game is over
"""
for i in range(self.size):
for j in range(self.size):
if self.chessboard[i][j] != State.EMPTY:
count = 1
state = self.chessboard[i][j]
for left in range(j + 1, self.size):
if self.chessboard[i][left] == state:
count += 1
else:
break
if count >= 5:
return True
count = 1
for down in range(i + 1, self.size):
if self.chessboard[down][j] == state:
count += 1
else:
break
if count >= 5:
return True
count = 1
for dic in range(1, 5):
if i + dic if self.chessboard[i + dic][j + dic] == state:
count += 1
else:
break
else:
break
if count >= 5:
return True
count = 1
for dic in range(1, 5):
if i + dic = 0:
if self.chessboard[i + dic][j - dic] == state:
count += 1
else:
break
else:
break
if count >= 5:
return True
return False
def check(self) -> bool:
black_count, white_count = 0, 0
for row in self.chessboard:
for state in row:
if state == State.BLACK:
black_count += 1
elif state == State.WHITE:
white_count += 1
else:
return False
return (
not self.is_over()
and self.size * self.size // 2 == white_count
and black_count + white_count == self.size * self.size
)
if __name__ == "__main__":
gobang = Gobang()
gobang.fill()
if gobang.check():
print("correct")
else:
print("wrong")
unset
unset
二面
unset
unset
1.根据以下代码完善SelfAttention
import torch
import torch.nn as nn
# multi-head self attention
class SelfAttention(nn.Module):
def __init__(self):
super().__init__()
def forward(self,
hidden_state : torch.FloatTensor, # (batch, length, hidden_size)
mask : torch.FloatTensor # (batch, length, length)
):
2.有一颗二叉树，在里面找一条路径，路径节点的和是最大的，节点可能有正负数和零
class Node:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def maxsum(self, root):
self.res = -float('inf')
self.dfs(root)
return self.res
def dfs(self, root):
if root is None:
return 0
maxleft = self.dfs(root.left)
maxright = self.dfs(root.right)
tmp = root.val
if maxleft > 0:
tmp += maxleft
if maxright > 0:
tmp += maxright
# tmp = maxleft + maxright + root.val
self.res = max(self.res + tmp)
return root.val + max(max(maxleft, maxright), 0)
# 1
# 2 3
# 4 5 6
三面
自我介绍+coding+反问
Coding：
# 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数，以及最少个数的全部组合。
# 如果没有任何一种硬币组合能组成总金额，返回-1。
# 假设每一种面额的硬币有无限个。
#
# 输入: coins = [1, 3, 7], amount = 9
# 输出: 3 [3,3,3], [1,1,7]
# 解释:
# 3 -> 9 = 3×3 = 1+1+7
# 9 -> 9 = 1×9
def fun(coins, amount):
inf = float('inf')
dp = [inf] * (amount + 1)
coins = sorted(coins)
dp[0] = 0 # *********
d = {}
d[0] = [[]]
s = [set()] * (amount + 1)
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
# dp[i] = min(dp[i], dp[i - coin] + 1)
if dp[i - coin] + 1 # if i not in d:
# d[i] = []
d[i] = []
s[i] = set()
for tmp in d[i - coin]:
t = tmp + [coin]
t = sorted(t)
p = tuple(t)
if p not in s[i]:
s[i].add(p)
d[i].append(t)
dp[i] = dp[i - coin] + 1
elif dp[i - coin] + 1 == dp[i]:
if i not in d:
d[i] = []
