大家好，我是吴师兄，关注我，每周更新大厂最新笔试题解析。
今天更新的是荣耀 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.一定包含运算符 (" "或"-")
输出描述
算式结果，一个整数。
示例
输入
代码语言：javascript复制1 2 99-10-10
输出
代码语言：javascript复制82
解题思路
本题属于经典的中缀表达式计算类栈题，维护preSign变量来表示上一个数字是加法还是减法即可。由于本题只涉及到加减法，相比起LeetCode上的几道类似题目相对简单（甚至不涉及到出栈操作，只需要考虑入栈即可），要注意遇到等于号"="的情况，直接跳过即可。
也可以直接调用eval()API，直接根据"="对字符串进行切割，将切割后的各个字串传入eval()得到各个子串的计算结构，再做求和。
代码
代码语言：javascript复制# 题目：【栈】荣耀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。
示例一
输入
代码语言：javascript复制[1 2 4 7 11 15]
6
输出
代码语言：javascript复制1 2 4
解题思路
注意，本题和LeetCode167. 两数之和 II - 输入有序数组基本完全一致，属于贪心类的相向双指针题目，唯一的区别在于输出上有些区别。
另外，由于数据范围较小，本题用暴力解也可以通过，但还是建议使用双指针解法。
代码
代码语言：javascript复制# 题目：【双指针】荣耀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码值比较从小到大进行排序;
- 如果两个字符串完全一样，则只需要输出一个。
示例一
输入
代码语言：javascript复制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
输出
代码语言：javascript复制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的切片查看是否为时间戳，再根据题意进行模拟排序即可，去重可以使用哈希集合操作。
代码
代码语言：javascript复制# 题目：【模拟】荣耀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])
时空复杂度
时间复杂度：O(NlogN NT)。N为字符串个数，T为字符串平均长度。排序需要O(NlogN)的复杂度，获取时间戳需要O(NT)的时间复杂度。
空间复杂度：O(N)。哈希集合所需时间复杂度。
