荣耀 0905 秋招算法面试题解析

五分钟学算法

发布于 2023-09-09 17:58:23

4490

发布于 2023-09-09 17:58:23

文章被收录于专栏：五分钟学算法五分钟学算法

大家好，我是吴师兄，关注我，每周更新大厂最新笔试题解析。

今天更新的是荣耀 2023/09/05 秋招算法面试题。

题目一：算式求解

题目描述

要开发一款教育类App，帮助幼儿在识数阶段做一百以内自然数[0.99]的加减法。

屏幕上会显示"1" "2" "3" "4" "5" "6" "7" "8" "9" "0" "+" "-" "="这些按钮，用户在按了若工按钮之后，如果按了"="，则会把按"="之前的字符串作为一个算式，计算结果。

中间结果或最后结果可以为负数。

输入描述

输入为一个字符串，形如"23+86-6+37+24-8-13"。

输入字符串中保证:

1.不会包含除"1" "2" "3" "4" "5" "6" "7" "8" "9" "0" "+" "-" "="之外的字符

2.长度不为0

3.不以"+"或"-"开始，不以"+"或"-"结束

4.不会出现连续两个或两个以上"+"

5.不会出现连续两个或两个以上"-"

6."+" "-"不会相邻

7.操作数为范围为[0，99]

8.一定包含运算符 ("+"或"-")

输出描述

算式结果，一个整数。

示例

输入

1+2+99-10-10

输出

解题思路

本题属于经典的中缀表达式计算类栈题，维护preSign变量来表示上一个数字是加法还是减法即可。由于本题只涉及到加减法，相比起LeetCode上的几道类似题目相对简单（甚至不涉及到出栈操作，只需要考虑入栈即可），要注意遇到等于号"="的情况，直接跳过即可。

也可以直接调用eval()API，直接根据"="对字符串进行切割，将切割后的各个字串传入eval()得到各个子串的计算结构，再做求和。

代码

# 题目：【栈】荣耀2023秋招-算式求解
# 作者：闭着眼睛学数理化
# 算法：栈
# 代码有看不懂的地方请直接在群上提问


# 输入字符串
line = input()
stack = list()
# 初始化数字num
num = 0
# 初始化上一个符号preSign
# 1表示"+"，-1表示"-"
preSign = 1

# 遍历line中的字符ch
for ch in line:
    # 如果ch是数字，则更新num
    if ch.isdigit():
        num = num * 10 + int(ch)
    # 如果ch是符号，则需要把之前得到的num加入stack中
    else:
        # 根据preSign的正负性，将preSign*num加入stack中
        stack.append(preSign*num)
        # 重置num为0
        num = 0
        # 若ch是"+"或"="
        # 则设置preSign为1，表示加号
        # 这里也可以在遇到"="的时候
        # 直接对stack进行求和操作，更加符合对题意的模拟
        if ch == "+" or ch == "=":
            preSign = 1
        else:
            preSign = -1

# 退出循环后，还需要把最后一个num加入stack中
stack.append(preSign*num)
# 最终输出stack中所有元素的求和
print(sum(stack))

时空复杂度

时间复杂度：O(N)。字符串line中的每一个元素仅需遍历一次。

空间复杂度：O(N)。栈所占空间。

题目二：找出升序数组中和为给定值的两个数字

题目描述

输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。

如果有多对数字的和等于输入的数字，输出找到的第一对即可。

输入描述

第一行输入一个按升序排序过的整数数组，数组元素不可重复，数组最大不超过1000个元素，起始和结束用中括号。

第二行输入一个整数，表示要在第一行数组中要查找的两个数字的和。

输出描述

输出一行三个整数，第一个表示结果是否正常(0表示异常或未找到，1表示正常)，第二个对应找到的数组索引小的数字，第三个对应找到的数组索引大的数字。

三个整数用单个空格隔开。

如果结果异常或未找到，后两个数字返回均为0。

示例一

输入

[1 2 4 7 11 15]
6

输出

1 2 4

解题思路

注意，本题和LeetCode167. 两数之和 II - 输入有序数组基本完全一致，属于贪心类的相向双指针题目，唯一的区别在于输出上有些区别。

另外，由于数据范围较小，本题用暴力解也可以通过，但还是建议使用双指针解法。

代码

# 题目：【双指针】荣耀2023秋招-找出升序数组中和为给定值的两个数字
# 作者：闭着眼睛学数理化
# 算法：双指针/贪心
# 代码有看不懂的地方请直接在群上提问

# 注意输入的起始位置和终止位置包含中括号，必须使用切片后再做分割
nums = list(map(int, input()[1:-1].split()))
# 输入目标和
target = int(input())

# 初始化一左一右两个双指针
left, right = 0, len(nums)-1
# 初始化标记findFlag，表示是否找到答案
findFlag = False

# 进行循环
while left < right:
    # 对left和right所指元素进行求和
    SUM = nums[left] + nums[right]
    # 若SUM恰好等于target，则修改findFlag为True，退出循环
    if SUM == target:
        findFlag = True
        break
    # 若SUM > target，说明SUM太大，right需要左移
    elif SUM > target:
        right -= 1
    # 若SUM < target，说明SUM太小，left需要右移
    elif SUM < target:
        left += 1

# 根据findFlag的结果进行输出
if findFlag:
    # 注意此处输出的是nums[left]和nums[right]，而不是left和right
    print("1 {} {}".format(nums[left], nums[right]))
else:
    print("0 0 0")

时空复杂度

时间复杂度：O(N)。每个元素仅需经过一次。

空间复杂度：O(1)。仅需若干常数变量。

题目三：根据字符串中的时间信息排序并输出

题目描述

解析输入的字符串数组，提取出字符串中的时间戳信息，并且将字符串按照时间戳排序后，输出到控制台。

输入描述

第1行指定数组的size;

第2行到第n行，每行为一个独立的字符串，n为size的值。

每行的字符串由"-:"和字母、数字组成，时间戳在字符串中的位置不确定，时间戳格式为2019-01-01T07:30:20表示2019年1月1日，7点30分20秒。时间为24小时制。

输出描述

将输入的字符串按照时间戳进行从小到大排序后，输出。符合如下规则:

如果时间戳信息相同，按照字符串长度从小到大进行排序;
如果长度相同，则按照从首字符开始的ASCII码值比较从小到大进行排序;
如果两个字符串完全一样，则只需要输出一个。

示例一

输入

5
my/2019-01-01T09:00:01
my/2019-01-01T09:00:01
abc/2018-12-24T08:00:00/test/you
1/2018-12-24T08:00:00/test/Test1
123/2018-12-24T08:00:09/test/me

输出

1/2018-12-24T08:00:00/test/Test1
abc/2018-12-24T08:00:00/test/you
123/2018-12-24T08:00:09/test/me
my/2019-01-01T09:00:01

解题思路

非常无聊的模拟排序题。遍历每一个子串中长度为19的切片查看是否为时间戳，再根据题意进行模拟排序即可，去重可以使用哈希集合操作。

代码

# 题目：【模拟】荣耀2023秋招-根据字符串中的时间信息排序并输出
# 作者：闭着眼睛学数理化
# 算法：模拟/排序
# 代码有看不懂的地方请直接在群上提问


# 根据年、月、日、小时、分钟、秒，判断是否是一个有效的时间戳
def checkAvailable(YYYY, MM, DD, hh, mm, ss):
    # hh、mm、ss超出限度，返回False
    if hh >= 24 and mm >= 60 and ss >= 60:
        return False
    # MM超出限度，返回False
    if MM >= 13:
        return False
    # MM和DD不能是0，否则返回False
    if MM == 0 or DD == 0:
        return False
    # 31天的月数，DD超出限度，返回False
    if MM in {1, 3, 5, 7, 8, 10, 12} and DD > 31:
        return False
    # 30天的月数，DD超出限度，返回False
    if MM in {4, 6, 9, 11} and DD > 30:
        return False
    # 闰年，2月，DD天数超过29天，返回False
    if YYYY % 400 == 0 or YYYY % 4 == 0 and YYYY % 100 != 0 and MM == 2 and DD > 29:
        return False
    # 平年，2月，DD天数超过28天，返回False
    if DD > 28:
        return False
    return True

# 获取s中时间戳的函数
def getTimeStamp(s):
    for i in range(0, len(s)-18):
        # 获得长度为19的切片
        sub_s = s[i:i+19]
        # 判断"-"是否在正确的位置
        if sub_s[4] != "-" or sub_s[7] != "-":
            continue
        # 判断"T"是否在正确的位置
        if sub_s[10] != "T":
            continue
        # 判断":"是否在正确的位置
        if sub_s[13] != ":" or sub_s[16] != ":":
            continue
        try:
            # 根据切片获取时间戳信息
            YYYY, MM, DD, hh, mm, ss = map(int, [sub_s[:4], sub_s[5:7], sub_s[8:10], sub_s[11:13], sub_s[14:16], sub_s[17:]])
            # 若时间戳信息通过了检查，则直接返回一个六元元组
            if checkAvailable(YYYY, MM, DD, hh, mm, ss):
                return (YYYY, MM, DD, hh, mm, ss)
        except:
            continue

n = int(input())
# 哈希集合，用于去重
hash_set = set()
ans = list()
for _ in range(n):
    s = input()
    # 只有没出现过的s，才需要进行计算
    if s not in hash_set:
        hash_set.add(s)
        # ans中储存时间戳和字符串s本身
        ans.append((getTimeStamp(s), s))

# 对ans进行排序，
# 先根据时间戳即x[0]排序
# 再根据原字符串s的长度即len(x[1])排序
# 再根据原字符串s的字典序即x[1]进行排序
ans.sort(key = lambda x: (x[0], len(x[1]), x[1]))
for item in ans:
    print(item[1])