考试平台: 时习知 题目类型: 3 道编程题 考试时间: 2023-09-06 (两小时) T1 每日股票价格 给定某只股票连续N天的价格列表stockPrices,其中stockPricesi表示股票某天的价格,请生成一个新列表,对应位置输出为:要想等到股票价格上涨,至少需要等待的天数,如果股票价格不上涨,对应位置输出为0。 输入 第一行 表示第二行元素的个数N 第二行为用空格隔开的整数,表示每天股票的价格 其中0<N<=1000000每天股票价格为正整数 输出 输出为用空格分隔的长度为N的列表,对应位置为:要想等到股票价格上涨至少需要等待的天数 示例1 输入:533 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 输入:512 13 14 15 16输出:1 1 1 1 0 题解 单调栈问题, 关键点: 不使用 FastScanner 快读只能通过 40 %; 不适用快速输出只能通过 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 34 7 88 6 62 6 4 第一行两个数字,分别为行数和每行的列数; 后续数据为矩阵地图内容: 矩阵边长范围:[1, 8]; 地形高度范围:[0, 100000]; 输出 一个整数,代表中庸行者在本地图内,能连续移动的最大次数。 示例1 输入:2 21 24 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