笔试时间：2023年9月6日 秋招

第一题

题目：每日股票价格

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

解答要求

时间限制:C/C++ 500ms其他语言: 1000ms内存限制: C/C++ 256MB,其他语言:512MB

输入描述

第一行表示第二行元素的个数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++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> price(N);

    for (int i = 0; i < N; i++) {
        cin >> price[i];
    }

    vector<int> sk;
    vector<int> res(N, 0);

    for (int i = 0; i < N; i++) {
        while (!sk.empty() && price[sk.back()] < price[i]) {
            int tp = sk.back();
            sk.pop_back();
            res[tp] = i - tp;
        }
        sk.push_back(i);
    }

    for (int i = 0; i < N - 1; i++) {
        cout << res[i] << " ";
    }
    cout << res[N - 1] << endl;

    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int[] price = new int[N];

        for (int i = 0; i < N; i++) {
            price[i] = input.nextInt();
        }

        Stack<Integer> sk = new Stack<>();
        int[] res = new int[N];

        for (int i = 0; i < N; i++) {
            while (!sk.isEmpty() && price[sk.peek()] < price[i]) {
                int tp = sk.pop();
                res[tp] = i - tp;
            }
            sk.push(i);
        }

        for (int i = 0; i < N - 1; i++) {
            System.out.print(res[i] + " ");
        }
        System.out.println(res[N - 1]);
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

N = int(input())
price = [int(c) for c in input().split()]

sk = []
res = [0]*N
for i in range(N):
    while sk and price[sk[-1]] < price[i]:
        tp = sk.pop()
        res[tp] = i-tp
    sk.append(i)

for i in range(N-1):
    print(res[i], end=" ")
print(res[-1])

第二题

题目：中庸行者

给定一个m*n的整数阵作为地图，短阵数值为地形高度；中庸行者选择地图中的任意一点作为起点，尝试往上、下、左、右四个相邻格子移动;

移动时有如下约束:

• 中庸行者只能上坡或者下坡，不能走到高度相同的点；
• 不允许连续上坡或者连续下坡，需要交替进行;
• 每个位置只能经过一次，不能重复行走；

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

解答要求

时间限制: C/C++500ms,其他语言:1000ms内存限制: C/C++ 256MB,其他语言:512MB

输入描述

一个只包含整数的二维数组:

1.3 3

2.4 7 8

3.8 6 6

4.2 6 4

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

后续数据为矩阵地图内容

矩阵边长范围:[1,8];

地形高度范围:[0,100000];

输出描述

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

样例输入

2 2

1 2

4 3

样例输出

3

解释

3->4->1->2

参考题解

回溯

C++：

#include <iostream>
#include <vector>
#include <set>

using namespace std;

int m, n;
vector<vector<int>> matrix;

int dfs(int i, int j, int k, set<pair<int, int>>& vst) {
    int ans = 0;
    int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    
    for (int d = 0; d < 4; d++) {
        int ni = i + dir[d][0];
        int nj = j + dir[d][1];

        if (ni < 0 || nj < 0 || ni >= m || nj >= n || matrix[ni][nj] == matrix[i][j] || vst.count({ni, nj}) > 0) continue;
        
        if ((k == 0 && matrix[ni][nj] <= matrix[i][j]) || (k == 1 && matrix[ni][nj] >= matrix[i][j])) continue;
        
        vst.insert({i, j});
        ans = max(ans, dfs(ni, nj, k ^ 1, vst) + 1);
        vst.erase({i, j});
    }
    
    return ans;
}

int main() {
    cin >> m >> n;
    matrix.resize(m, vector<int>(n));

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    int res = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            set<pair<int, int>> vst; // 使用set存储已访问的点
            res = max(res, max(dfs(i, j, 0, vst), dfs(i, j, 1, vst)));
        }
    }

    cout << res << endl;

    return 0;
}

Java：

import java.util.*;

public class Main {
    static int m, n;
    static int[][] matrix;

    static int dfs(int i, int j, int k, Set<Pair> vst) {
        int ans = 0;
        int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        for (int[] d : dir) {
            int ni = i + d[0];
            int nj = j + d[1];

            if (ni < 0 || nj < 0 || ni >= m || nj >= n || matrix[ni][nj] == matrix[i][j] || vst.contains(new Pair(ni, nj))) continue;

            if ((k == 0 && matrix[ni][nj] <= matrix[i][j]) || (k == 1 && matrix[ni][nj] >= matrix[i][j])) continue;

            vst.add(new Pair(i, j));
            ans = Math.max(ans, dfs(ni, nj, k ^ 1, vst) + 1);
            vst.remove(new Pair(i, j));
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        m = input.nextInt();
        n = input.nextInt();
        matrix = new int[m][n];

        for (int i = 0; i < m; i++) {