【2022-08-21】字节秋招笔试四道编程题

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经，目前已更新至美团、微软… 作者@TechGuide【全网同名】 点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

第一题：01数列 题目描述

双休在家的凯凯真的是太无聊了，他准备和他家的猫玩一个游戏。 凯凯随手写下一串01数列，定义这串数列的子串和为所有长度为2的子串的和。比如数列=010001，有如下长度为2的子串： 01 （前导0， =1） 10 00 （前导0，=0） 00 （前导0，=0） 01 （前导0，=1） 所以和为1+10+0+0+1 = 12

如果要只是算子串和的话，那对喵喵来说实在是太简单了，所以凯凯准备加大难度。 喵喵有k次机会可以交换数列里的相邻两个数（可以不用完这k次机会），使得交换完之后子串和最小。 这下喵喵不会做了，你可以帮帮它么？

输入描述

输入为先输入一个t，代表t组。然后分别是n、k，字符串。

3 4 0 1010 7 1 0010100 5 2 00110

输出描述

21 22 12

思路

分析字符串中每一个1，只有3种情况：

出现在字符串首部，贡献为10 出现在字符串中央，贡献为11 出现在字符串末尾，贡献为01 那么只需要考虑能不能把1换到头尾就好了。 注意：对于一个1来说。只要不在第一个位置或者最后一个位置，贡献一定是11。

代码 Python版本

for _ in range(int(input())):
    n,k=list(map(int,input().split()))
    s=input()
    n1=s.count('1')
    if n1==0:
        print(0)
        continue

    ans=n1*11
    ri=s.rindex('1')
    rneed=(n-1-ri)
    if k>=rneed:
        k-=rneed
        ans-=10

        # 后面交换成功了
        if n1==1:
            print(1)
            continue
        else:
            lneed=s.index('1')
            if k>=lneed:
                ans-=1
            print(ans)
    else:
        lneed=s.index('1')
        if k>=lneed:
            ans-=1
        print(ans)
# vx公众号关注TechGuide 实时题库 闪电速递

第二题：迷宫 题目描述

第一行输入两个整数n和m，表示迷宫的长和宽。 接下来n行，每行m 个字符， 用于描述迷宫构造，每个字符可能为以下几种： .表示空地， 玩家在空地时可以选择往 [上，下，左，右] 中的某个方向移动一格 U，D，L，R 分别表示朝向[上，下，左，右] 的传送带，站在传送带上的人会被强制移动到其指向的下一个位置 如果下一个位置还是传送带，会被继续传下去 如果传送带指向迷宫外，玩家会撞在墙上，昏过去，游戏结束，无法再到达出口 O表示迷宫出口

请你找到有多少点按照规则行走不能到达终点。

输入描述

n{'O', 'U', '.', '.'},