春招第一个算法笔试 北京博***有限公司 游戏开发

已经很久没碰算法了，对我来说这个笔试题非常之难，没有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