当前位置:   article > 正文

华为OD机考题目(自动化测试)_华为软件测试机考题

华为软件测试机考题

1.求第k长的字串的长度

描述

一个字符串只包含大写字母,求其连续相同字母子串中,长度第K长的子串长度,相同字母只取
最长那个子串。
例:AAAAHHHBBCDHHHH
K=3
输出:2

代码(python)

def test_007(k, target_str):
    print(f"输入的字符串是:{target_str}",end="")
    # 以字符串中的字母创建一个字典
    print("")
    dict_1 = {}
    for i in target_str:
        if i not in dict_1.keys():
            dict_1[i] = 0
    index = 0
    count = 0
    max_index = len(target_str) - 1
    # 临时变量a 初始值为字符串的第一个字母
    a = target_str[0]
    # 遍历字符串
    while index <= max_index:
        # 若字母相等,长度加1
        if a == target_str[index]:
            count += 1
        # 若不同,表示是下一个字串,
        # 记录当前字串的长度
        # 更新临时变量a,记录下一个
        else:
            if dict_1[a] < count:
                dict_1[a] = count
            count = 1
            a = target_str[index]
        index += 1
    # 上述代码只在else保存的时前一个字串的长度,
    # 在index=max_index时会出现计数未保存的情况
    # 1. 若n-1和n位置的字母相同,不会将更新的count加到字典
    # 2. 若n-1和n位置的字母不相同,不会将新字串的长度加到字典
    # 所以在最后加一次处理操作
    if dict_1[a] < count:
        dict_1[a] = count
    # for i, j in dict_1.items():
    #     print(i, j)
    # 利用set去重(不同字母构成的字串长度相同)然后转成list升序排序,题目答案是步不去重的结果
    # 最后输出k-1位置的值
    # out_list = sorted(list(set(dict_1.values())))
    out_list = sorted(dict_1.values())
    if k > len(out_list):
        print(f"k={k}大于字符串的子串长度大小构成的list的长度{len(out_list)}",end="")
    else:
        print(f"输入k={k},第{k}长的子串的长度是{out_list[k-1]}")
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

运行结果
在这里插入图片描述

2.上N阶台阶问题

描述

上台阶,一个阶梯有N阶台阶,每次只能上1步或者3步,求一共有多少种不同的方式上台阶?
例:N=50
输出:122106097

思路

动态规划:
假设上N阶台阶的方式有F(n)种,我们从后往前思考,最后一次上台阶的方式只能为1步或者3步,
那么倒数第二次的处于的台阶就是n-1阶或者n-3阶,所以完成n阶台阶的总组合数就可以转换成
F(n)=F(n-1)+F(n-3),依次往前推,可以等到F(6)=F(5)-F(3),F(5)=F(4)-F(2),F(4) = F(3) + F(1),
可以观察到规律,当n大于等于6的时候,等式右边的值就可以在之前的等式找到,所以我们只
需先手动计算基础项的值,F(1)= 1,F(2) =1,F(3)=2,就可以由前面的等式得到后面等式需要的值。

代码(python)

# 非递归代码实现,n大于等于4的时候可以用F(n)=F(n-1)+F(n-3)
def test_004(n):
    if n <= 2:
        return 1
    elif n == 3:
        return 2
    else:
        # 用来存放a值,因为a的更替存在跨度问题,所以用一个长度为2的list维护
        temp_a_list = [1, 1]
        a, b, sum1 = 2, 1, 0
        while n > 3:
            sum1 = a + b
            temp_a_list[0], temp_a_list[1] = temp_a_list[1], a
            b = temp_a_list[0]
            a = sum1
            n -= 1
    return sum1
# 递归实现 但是执行时间会很长
def test_0041(n):
    if n <= 2:
        return 1
    elif n == 3:
        return 2
    else:
        return test_0041(n-1)+test_0041(n-3)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25

运行截图
运行结果

3.踢出石子问题

描述

有一堆石子,一次编号1-100围成圈,给定一个数K,从1开始数K个,将此石子踢出,继续报
数,最后当石子总数小于K时,输出最后剩余石子编号。
例:K为3
输出:58,91

思路和代码(python)

def test_002(n):
    list_1 = [x for x in range(1, 101)]
    max_index = len(list_1) - 1
    index = 0  # 序列index
    count = 0  # 记录被踢出人的个数
    num_n = 0  # 记录报数
    # 循环退出条件,踢出(100 - n - 1)个人
    while count < 98:
        # 1.循环列表找到值不是-1的,报数值加1(-1的表示已经踢出)
        # 2.当报数num_n=n时,表示找到了踢出的人,设置计数count_n=0,退出循环
        # 3.将此时的list_1[index]赋值为-1,表示踢出
        # 4.重复1-3,直到count == (101-n)退出外层循环
        while True:
            # 当index 大于maxindex 表示需要从头开始计数了
            if index > max_index:
                index = 0
            # 找到值不是-1的就报数(-1表示以被踢出的),否则报数直接index增加
            if list_1[index] != -1:
                num_n += 1
            if num_n == n:
                num_n = 0
                break
            index += 1
        count += 1
        # print(f"第{count}次,踢出{list_1[index]}")
        list_1[index] = -1
    print("处理完毕!")
    for item in list_1:
        if item != -1:
            print(item, end=" ")
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

运行结果
运行截图

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/很楠不爱3/article/detail/152716
推荐阅读
相关标签
  

闽ICP备14008679号