9.6 华为笔试面经 - 编程题 & 题解

考试平台： 时习知

题目类型： 3 道编程题

考试时间： 2023-09-06 （两小时）

T1 每日股票价格

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

输入

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

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

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

输出

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

示例1

输入：
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
当i=1时，stockPrices[1]=34,后续股票价格没有上涨，此处输出0
当i=2时，stockPrices[2]=14,下次价格上涨stockPrices[4]=16，此处输出为 4-2=2
当i=3时，stockPrices[3]=12下次价格上涨stockPrices[4]=16，此处输出为 4-3=1
当i=4时，stockPrices[3]=16,后续股票价格没有上涨，此处输出0所以输出为1 0 2 1 0

示例2

输入：
5
12 13 14 15 16
输出：
1 1 1 1 0

题解

单调栈问题，

关键点：

1. 不使用 FastScanner 快读只能通过 40 %;
2. 不适用快速输出只能通过 90 %;

import java.io.*;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        FastScanner cin = new FastScanner(System.in);//快读
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));//快速输出
        int n = cin.nextInt();

        int[] a = new int[n];
        LinkedList<int[]> stack = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            int price = cin.nextInt();
            while (!stack.isEmpty() && stack.peek()[1] < price) {
                int idx = stack.poll()[0];
                a[idx] = i - idx;
            }

            stack.push(new int[]{i, price});
        }

        for (int i = 0; i < n; i++) {
            out.print(a[i] + " ");
        }
        out.flush();
    }
}

class FastScanner {
    BufferedReader br;
    StringTokenizer st;

    public FastScanner(InputStream in) {
        br = new BufferedReader(new InputStreamReader(in), 16384);
        eat("");
    }

    public void eat(String s) {
        st = new StringTokenizer(s);
    }

    // 读一行
    public String nextLine() {
        try {
            return br.readLine();
        } catch (IOException e) {
            return null;
        }
    }

    public boolean hasNext() {
        while (!st.hasMoreTokens()) {
            String s = nextLine();
            if (s == null) return false;
            eat(s);
        }
        return true;
    }

    // 读取下一个元素
    public String next() {
        hasNext();
        return st.nextToken();
    }

    // 读int
    public int nextInt() {
        return Integer.parseInt(next());
    }
}

T2 中庸行者

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

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

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

输入

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

3 3
4 7 8
8 6 6
2 6 4

第一行两个数字，分别为行数和每行的列数; 后续数据为矩阵地图内容: 矩阵边长范围:[1, 8]; 地形高度范围:[0, 100000];

输出

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

示例1

输入：
2 2
1 2
4 3

输出：
3

解释： 6 > 3 > 5 > 2 > 4

题解

回溯法

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(), n = scanner.nextInt();

        int[][] grid = new int[m][n];
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                grid[r][c] = scanner.nextInt();
            }
        }

        Solution solution = new Solution();
        System.out.println(solution.solve(grid));

    }
}

class Solution {
    int max;

    public int solve(int[][] g) {
        this.max = 0;
        int m = g.length, n = g[0].length;
        boolean[][] vis = new boolean[m][n];
        // 从每个位置作为起点尝试获取最大的移动步数
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                vis[r][c] = true;
                dfs(g, vis, r, c, 0, true);
                dfs(g, vis, r, c, 0, false);
                vis[r][c] = false;
            }
        }

        return this