春招第一个算法笔试 北京博***有限公司 游戏开发
已经很久没碰算法了，对我来说这个笔试题非常之难，没有100%通过的题
1.一组字符串类似下面：
判断每个字符串是否都能通过一个轨迹得到
现在来看其实非常简单，只需要不断递归，每次向四个方向查找，如果是下一个字符，就继续递归，否则返回false，直到四个三个方向都返回false或者找到整个字符串
输入：
map = [
['a', 'b', 'c', 'e'],
['s', 'f', 'c', 's'],
['a', 'd', 'e', 'e']
]
strArr = ["abc", "ass", "bad", "see", "fcs"]
返回：[True, False, False, True, True]
实现代码参考：
from typing import List
class Solution:
def findWords(self, map: List[List[str]], strArr: List[str]) -> List[bool]:
row = len(map)
col = len(map[0])
visited = [[False]*col for _ in range(row)]
def find_index(i, j, index, word):
if len(word) <= index:
return True
if i < 0 or i >= row or j < 0 or j >= col \
or visited[i][j] or map[i][j] != word[index]:
return False
# 当前元素等于word[index],遍历寻找下一个
visited[i][j] = True
found = find_index(i-1, j , index + 1, word) or \
find_index(i+1, j , index + 1, word) or \
find_index(i, j-1, index + 1, word) or \
find_index(i, j+1, index + 1, word)
visited[i][j] = False
print(found)
return found
re = []
for word in strArr:
if len(word) == 0:
re.append(False)
continue
found = False
for i in range(row):
for j in range(col):
if map[i][j] == word[0]:
found = find_index(i, j, 0, word) or found
re.append(found)
return re
if __name__=="__main__":
map = [
['a', 'b', 'c', 'e'],
['s', 'f', 'c', 's'],
['a', 'd', 'e', 'e']
]
strArr = ["abc", "sad", "saf", "fcd"]
re = Solution().findWords(map, strArr)
print(re)
2.考察给一个整数n，判断所有从[1,n]的整数中字符1-9出现的次数
当时给我整蒙了，后来问deepseek搞明白了，其实思路也挺简单，就是每一次只判断某一位出现某个数的次数
比如：先算从[1-n] 所有整数的个位出现1的次数，很容易，比如 51000就出现5101次，然后依次计算出现2、3...，十位百位
参考代码:
from typing import List
class Solution:
def CountNumber(self, n:int) -> List[int]:
result = [0]*10
def count_one_number(digtal, n):
i = 1
while i <= n: # 注意这里是<= ，如果是< ，当最高位为1是会漏掉一个1
driver = i*10 # 用来分割位数，将数字分割为 high, cover, low
high = n // driver
cover = (n //i)% 10
low = n % i
# 单独处理0
if digtal == 0:
if high == 0:
# 高位为0,当前数是前导0,不机算
i *= 10
continue
if cover == 0:
# 当前位为0, 高位有 high个值可选(比如high=2时,可选1,2),但是高位不变时，低位只有 low+1 个值可选
result[digtal] += (high-1) * i + (low + 1)
elif cover > 0:
# 高位 有high个值可选，低位所有值可选
result[digtal] += high * i
else:
# 当前位不为0时
if cover == digtal:
# 当前位于digtal一致，高位有 high+1个值可选(包括0), 当高位为0时，低位只有low+1个值可选
result[digtal] += high*i + (low + 1)
elif cover > digtal:
# 当前位大于digtal,高位有 high+1个值可选(包括0)
result[digtal] += (high+1) * i
else:
# 当前位小于digtal,高位只有high个值可选(0不行)
result[digtal] += high * i
# 处理完当前位，处理下一位
i *= 10
for i in range(10):
count_one_number(i, n)
return result
if __name__=="__main__":
re = Solution().CountNumber(100000)
print(re)
3.写希尔排序，给出移动的次数
这个以前应该也没接触过，接触过也早忘了，待会学一下
学成归来，感觉好简单：- _ - 等啥时候常见的排序算法都得重新学习一下
from typing import List
class Solution:
def shell_sort(self, numlist: List[int], gaplist: List[int]) -> int:
count = 0
for gap in gaplist:
for i in range(gap, len(numlist)):
j = i # j表示当前需要决定的位置(若temp大于前一个值就将temp插入这里,否则后移前一个元素，判断更前面一个)
temp = numlist[j]
while j >= gap and temp < numlist[j-gap]:
numlist[j] = numlist[j - gap]
j -= gap
count += 1
numlist[j] = temp
return count
if __name__ == "__main__":
sol = Solution()
arr = [9, 8, 7, 6, 5, 4, 3, 2, 1,10,11,5,2,3,6,2,1,6,11]
gaps = [4, 2, 1]
print("初始数组:", arr)
moves = sol.shell_sort(arr, gaps)
print("\n最终排序结果:", arr)
print("总移动次数:", moves)
4.划船，多少次能划到岸边，描述是第一次能划x米，然后休息，倒退y米，每一次休息都减少下一次1/5的移动距离，判断划几次能到m米的岸边
这个刚写的时候给我搞出等比数列去了，我以为会上很大的数，其实这么简单就过了
正确代码参考：
from typing import List
class Solution:
def HuaChuang(self, x:float, y: float, m:float) -> List[int]:
now_x = x
total = 0
count = 0
while total < m:
if now_x <= y:
return -1
total = total + now_x - y
now_x *= 0.8
count += 1
return count
if __name__=="__main__":
re = Solution().HuaChuang(10900,2,39900)
print(re)
第一次写的代码：
等有时间看看哪里错了
from math import log, pow
class Solution:
def max_len(self, x: float, y: float, n: int) -> bool:
sum_ = x*(1 - pow(0.8, n))/(0.2) - y*n
return sum_
def rowTheBoat(self , x: float, y: float, m: float) -> int:
# 没x米休息一次，每次休息退行y米，起始距离为m米，问最终能到达终点吗
# l1 = x - y
# l2 = x*(4/5) - y
# l3 = x*(4/5)^2 - y
# l4 = x*(4/5)^3 - y
# ...
# l_last = x*(4/5)^n - y = 0
# y = x*(4/5)^n
n = log(y/x, 0.8)
n = int(n)
# sum = l1 + l2 + l3 + ... + l_last = x*(1 + (4/5) + (4/5)^2 + ... + (4/5)^n) - y*n
# sum = x*(1 - pow(0.8, n + 1))/(0.2) - y*n
sum = self.max_len(x, y, n)
if sum < m:
# 判断再来一次是否可以
if sum + x*(0.8**(n)) + x*(0.8**(n)) >= m:
return n + 1
else:
return -1
while self.max_len(x, y, n) >= m:
n = n // 2
while self.max_len(x, y, n) < m:
n = n + 1
return n
25年春招笔试面试记录 文章被收录于专栏
记录一下春招的笔面试
