华为0906秋招笔试真题解析

五分钟学算法

发布于 2023-09-09 10:29:14

4680

发布于 2023-09-09 10:29:14

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

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

今天解析的是华为0906秋招笔试真题。

题目一：每日股票价格

题目描述

给定某只股票连续N天的价格列表stockPrices，其中stockPrices[i]表示股票某天的价格，请生成一个新列表，对应位置输出为：要想等到股票价格上涨，至少需要等待的天数，如果股票价格不上涨，对应位置输出为0。

输入描述

第一行表示第二行元素的个数N

第二行为用空格隔开的整数，表示每天股票的价格

其中0 < N <= 1000000每天股票价格为正整数

输出描述

输出为用空格分隔的长度为N的列表，对应位置为：要想等到股票价格上涨，至少需要等待的天数

示例

输入

5
33 34 14 12 16

输出

1 0 2 1 0

说明

stockPrices = [33,34,14,12,16]

当i = 0时，stockPrices[0] =33,下次价格上涨stockPrices[1]=34，此处输出为1-0 = 1，以此类推。

时空限制

时间限制： C/C++500MS，其他语言1000MS

内存限制： C/C++256MB，其他语言512MB

解题思路

注意，本题和LeetCode739. 每日温度完全一致，属于单调栈模板题。

题目要求计算每一个元素右边最近的一个更大元素，看到这种设问，显然应该使用单调栈来解决，逆序遍历和正序遍历的方法均可解决此题。

代码

# 题目：【单调栈】华为2023秋招-每日股票价格
# 作者：闭着眼睛学数理化
# 算法：单调栈/逆序遍历
# 代码有看不懂的地方请直接在群上提问
# 微信：278166530


n = int(input())
stockPrices = list(map(int, input().split()))

# 初始化单调栈
# 单调栈中储存的是元素在stockPrices中的下标
stack = list()
# 初始化答案数组，长度为n
ans = [0] * n

# 逆序遍历原数组stockPrices
for i in range(n-1, -1, -1):
    curPrice = stockPrices[i]
    # 若栈不为空，且栈顶元素下标在stockPrices中对应的元素小于等于curPrice
    # 说明栈顶元素下标对应的price不是curPrice右边最近的下一个更大元素
    # 栈顶元素出栈
    while stack and stockPrices[stack[-1]] <= curPrice:
        stack.pop()
    # 退出循环后，若stack仍不为空，
    # 此时栈顶元素下标对应的price就是curPrice右边最近的下一个更大元素
    # 两者之间的距离为stack[-1] - i，更新ans[i]
    if stack:
        ans[i] = stack[-1] - i
    # 最终需要将当前下标i入栈
    stack.append(i)

print(" ".join(str(i) for i in ans))

时空复杂度

时间复杂度：O(N)。每个元素仅需进栈或出栈一次。

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

题目二：中庸行者

题目描述

给定一个m*n的整数阵作为地图，短阵数值为地形高度；

中庸行者选择地图中的任意一点作为起点，尝试往上、下、左、右四个相邻格子移动;

移动时有如下约束：

中庸行者只能上坡或者下坡，不能走到高度相同的点。

不允许连续上坡或者连续下坡，需要交替进行;

每个位置只能经过一次，不能重复行走；

请给出中庸行者在本地图内，能连续移动的最大次数。

输入描述

第一行两个数字，分别为行数和每行的列数

后续数据为矩阵地图内容

矩阵边长范围：[1,8]

地形高度范围：[0,100000]

输出描述

一个整数，代表中庸行者在本地图内，能连续移动的最大次数。

示例一

输入

2 2
1 2
4 3

输出

说明

3->4->1->2，一共移动3次。

时空限制

时间限制： C/C++500MS，其他语言1000MS

内存限制： C/C++256MB，其他语言512MB

解题思路

本题数据规模较小，最多只有8 * 8 = 64个点，因此可以使用DFS回溯的方式枚举出所有路径。

回溯过程中有几个问题需要注意：

上下坡是不断交替切换的，故在回溯函数中可以设置一个布尔型标记isUp来表示下一步移动是上坡还是下坡
和常规的DFS有所不同，checkList的更新是需要回滚的，因为同一个点有可能通过不同路径反复走到
需要用一个变量path_len来记录当前路径长度的变化，可以直接将path_len+1作为回溯的参数传入
回溯调用的入口，需要同时考虑第一步是上坡还是下坡的情况，故对于每一个特定的点(i, j)，其回溯入口都需要调用两次，分别设置isUp是True和False的情况。

代码

# 题目：【回溯】华为2023秋招-中庸行者
# 作者：闭着眼睛学数理化
# 算法：回溯
# 代码有看不懂的地方请直接在群上提问
# 微信：278166530


# 构建方向数组，表示上下左右四个方向
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]


# 回溯函数
# 参数含义如下
# i,j           为当前点的坐标
# m,n,gird      分别为地图行数列数和地图本身
# checkList     为检查地图某点是否访问过的二维数组，大小和grid一样，在递归过程中反复进行更新和回滚
# path_len      为当前路径长度，用于更新ans
# isUp          为一个布尔型变量，表示下一个移动是上坡还是下坡
def backtracking(i, j, m, n, grid, checkList, path_len, isUp):
    global ans
    ans = max(ans, path_len)
    # 对于i而言，考虑其上下左右四个方向的近邻位置(ni,nj)
    for di, dj in DIRECTIONS:
        ni, nj = i+di, j+dj
        # (ni,nj)必须未越界且尚未检查过，才可以继续进行检查
        if 0 <= ni < m and 0 <= nj < n and checkList[ni][nj] == 0:
            # 分别考虑以下两种情况，进行回溯
            # 此时是上坡，且grid[ni][nj]的值大于grid[i][j]
            # 此时是下坡，且grid[ni][nj]的值小于grid[i][j]
            if ((isUp and grid[ni][nj] > grid[i][j]) or
                (not isUp and grid[ni][nj] < grid[i][j])):
                # 更新状态，把(ni,nj)标记为已访问过，对(ni,nj)进行回溯
                checkList[ni][nj] = 1
                # 注意参数的传入，path_len需要+1，标志isUp需要取反，即上坡变下坡，下坡变上坡
                backtracking(ni, nj, m, n, grid, checkList, path_len+1, not isUp)
                # 回溯结束，需要回滚状态，把(ni,nj)重新标记为未访问过
                checkList[ni][nj] = 0


# 输入行数m，列数n
m, n = map(int, input().split())
# 构建地图
grid = list()
for _ in range(m):
    grid.append(list(map(int, input().split())))

ans = 0

# 遍历整个二维矩阵，选择点(i,j)作为出发点，调用回溯函数作为入口
for i in range(m):
    for j in range(n):
        # 构建用于回溯的checkList
        checkList = [[0] * n for _ in range(m)]
        # 将checkList[i][j]设置为1，表示已经检查过
        checkList[i][j] = 1
        # 回溯入口，分别考虑初始方向为上坡和下坡的情况
        backtracking(i, j, m, n, grid, checkList, 0, True)
        backtracking(i, j, m, n, grid, checkList, 0, False)

print(ans)