今天笔试考的很差，梳理了网上的答案，记录总结下
package com.hwx.test;import java.util.*;/*题目描述：第一题： 某部队举办了一届军事运动会，其中有一个团体马拉松项目，有n名选手按顺序从起跑线出发， 并且记录下他们到达终点的顺序。在跑步过程中超越了其他人的选手要给予表彰。 受表彰的选手需要满足的条件是，如果存在一名出发顺序排在选手X之后的选手Y先于X到达终点，则认为Y超越了X。 对于每一个选手，只要他超越了任意一个人，就有资格受到表彰。请你计算出有多少人可以得到表彰。 输入: 输入第一行仅包含一个正整数n，表示选手数量。(1<=n<=10^5) 输入第二行包含n个正整数，是一个1-n的排列A，表示出发顺序，A[i]表示第i个出发的选手的编号。 输入第三行同样包含一个1-n的排列B，表示到达顺序，B[i]表示第i个到达的选手的编号。 输出: 输出仅包含一个整数，表示得到表彰的人数。 样例输入 5 5 3 1 4 2 2 4 5 1 3 样例输出 3 提示 样例解释： 显然除了5号和3号以外，其他人都可以受到表彰，因为他们均超越了3号。第二题： 输入包含三行 第一行一个正整数x，表示今天是rqdzc。(1<=x<=7) 第二行是一个24小时制的时间表示，时和分均含前导0，例如，1时1分表示为01:01。保证时间格式是合法的。 第三行是一个正整数n，表示要求的是n分钟之前的时间。(1<=n<=10^9) 输出 输出同样包含两行，第一行仅包含一个正整数，表示n分钟之前是周几。 一个24小时制的时间表示，时和分均含前导0，例如，1时1分表示为01:01。表示n分钟之前的时刻。 样例输入 3 02:10 200 样例输出 2 22:50 提示 本题中我们认为： 周四 00:01的前1分钟为 周四 00:00 周四 00:00的前1分钟为 周三 23:59 */public class meituan { public static void main(String[] args) { meituan m = new meituan(); m.method3(); } public void method() { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); sc.nextLine(); if (n <= 0) { System.out.println(0); return; } int[] start = new int[n]; int[] end = new int[n]; for (int i = 0; i < n; i++) { start[i] = sc.nextInt(); } HashMap<Integer, Integer> map = new HashMap<>(); //记录一开始各选手的起跑顺序 for (int i = 0; i < n; i++) { map.put(start[i], i);//利用hash表查找效率比顺序查找高 } for (int i = 0; i < n; i++) { end[i] = sc.nextInt(); } int min = 0;//从后往前记录开跑顺序最早的选手顺序，如果查询的顺序>min，则一定超过了至少该min int count = 0; for (int i = n - 1; i >= 0; i--) { if (i == n - 1) {//最后一名时，当前最早的顺序即为该选手 min = map.get(end[i]); continue; } if (map.get(end[i]) > min) {//只要自己的顺序比前面其中一个大，就符合，那直接比较min count++; continue; } min = map.get(end[i]);//到了这一步，则表示map.get(end[i]) < min// min=Math.min(min,map.get(end[i])); } System.out.println(count); } public void method2() { Scanner sc = new Scanner(System.in); int day = sc.nextInt(); sc.nextLine(); String hm = sc.nextLine(); long forward = sc.nextLong(); String[] str = hm.split("\:"); long oneday = 60 * 24; forward %= oneday * 7; long totalMin = oneday * (day - 1) + Integer.parseInt(str[0]) * 60 + Integer.parseInt(str[1]); long thattime = (totalMin + oneday * 7 - forward) % (oneday * 7);//得到减去forward后在当周的正数分钟数 long thatday = thattime / (oneday) + 1; long thatHour = thattime % (oneday) / 60; long thatMin = thattime % (oneday) % 60; System.out.println(thatday); if (thatHour < 10) System.out.print(0); System.out.print(thatHour + ":"); if (thatMin < 10) System.out.print(0); System.out.print(thatMin); } /* 作为一个程序员，修bug（补漏洞）是一项基本的工作。bzdct刚刚完成一个工作的时候，甲方说你的程序里面有n个bug。 但是你已经很累了，你希望第一天修x个bug,第二天修[x/k]个bug，第三天修[x/k2]个bug，以此类推，第n天修⌊x/k^(n-1) ⌋个bug，直到修不了bug为止。 [x]的意思是x向下取整。在k大于1的时候，总有一天会修不了一个bug的。所以，你希望在这一天来临之前，修完所有的bug。 你要计算，你第一次至少要修多少个bug，即x的最小值为多少。 输入 输入包含一行两个整数n , k 分别代表漏洞总数和题目中的参数k 输出 输出包含一个数，即x的最小值 样例输入 10 3 样例输出 8 提示 范围 1<=n<=10^9 , 2<=k<=10 样例解释： 第一天修8个bug，第二天修2个bug，从第三天开始修不了bug，总共修了10个，修完了所有的bug。 如果第一天只修7个bug，那么第二天只能修2个bug，从第三天修不了bug，总共修了9个bug，不能完成目标， 所以第一天至少修8个bug。 */// 二分x,然后暴力判断即可 public void method3() { Scanner sc = new Scanner(System.in); long n = sc.nextInt(); long k = sc.nextInt(); long l = 1;//第一天至少修一个 long r = n;//第一天最多修n个// 二分，不断逼近最后的l，目的是得到l=r时唯一的最小的x，所以一开始不能r=n， while (l < r) { long mid = (l + r) / 2; if (judgeX(mid, n, k)) { r = mid; } else { l = mid + 1; } } System.out.println(l); } public boolean judgeX(long x, long n, long k) { while (x > 0) { n -= x;//n不断减少 x /= k;//向下取整 if (n <= 0) break; } return n <= 0; }// 【dp，不懂，以后看】S,A,B,C互通，从S出发，走k次回到S的走法个数 public void method4(int k) { long[][] recorder = new long[4][k + 1]; recorder[0][0] = 1; long mod = 1000000007; for (int i = 1; i < k + 1; ++i) { for (int j = 0; j < 4; ++j) { for (int m = 0; m < 4; ++m) { if (m == j) { continue; } recorder[j][i] += recorder[m][i - 1] % mod; recorder[j][i] %= mod; } recorder[j][i] %= mod; } } System.out.println(recorder[0][k] % mod); } public static void quickSort2(int[] arr, int left, int right) { if (left >= right) { return; } int leftNum = left; int rightNum = right; int base = arr[left]; while (left < right) { while (arr[right] >= base && left < right) { right--; } while (arr[left] <= base && left < right) { left++; } swap(arr, left, right); } swap(arr, leftNum, left); quickSort2(arr, leftNum, left - 1); quickSort2(arr, right + 1, rightNum); } /** * 交换两个数组的元素 */ public static void swap(int[] arr, int left, int right) { int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; } public int search(int[] arr, int value) { // 线性查找是逐一比对，发现有相同值，就返回下标 for (int i = 0; i < arr.length; i++) { if (arr[i] == value) { return i; } } return -1; }}