Java工程师丨面试真题（一）
【摘要】 一、附加题描述存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略： A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1； B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；现在路人甲想知道...
一、附加题
描述
存在n+1个房间，每个房间依次为房间1 2 3...i，每个房间都存在一个传送门，i房间的传送门可以把人传送到房间pi(1<=pi<=i),现在路人甲从房间1开始出发(当前房间1即第一次访问)，每次移动他有两种移动策略：
A. 如果访问过当前房间 i 偶数次，那么下一次移动到房间i+1；
B. 如果访问过当前房间 i 奇数次，那么移动到房间pi；
现在路人甲想知道移动到房间n+1一共需要多少次移动；
输入描述：
第一行包括一个数字n(30%数据1<=n<=100，100%数据 1<=n<=1000)，表示房间的数量，接下来一行存在n个数字 pi(1<=pi<=i), pi表示从房间i可以传送到房间pi。
输出描述：
输出一行数字，表示最终移动的次数，最终结果需要对1000000007 (10e9 + 7) 取模。
示例1
输入：
2 1 2输出：
4说明：
开始从房间1 只访问一次所以只能跳到p1即 房间1， 之后采用策略A跳到房间2，房间2这时访问了一次因此采用策略B跳到房间2，之后采用策略A跳到房间3，因此到达房间3需要 4 步操作。
题解：
/**
* { 0 i=1
* dp[i] = { dp[i-1]+2 i>1,pi[i-1]=i-1
* { dp[i-1]+(dp[i-1]-dp[pi[i-1]])+2 i>1,pi[i-1]<i-1
*/
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// 1-n
int[] pi = new int[n + 1];
// 1-(n+1)
long[] dp = new long[n + 2];
// 1-n
for(int i = 1; i <= n; ++i){
pi[i] = sc.nextInt();
}
sc.close();
long mod = (long)(1e9+7);
// 2-(n+1)
for(int i = 2; i <= n + 1; ++i){
if(pi[i - 1] == i - 1){
dp[i] = (dp[i - 1] + 2) % mod;
}else{
dp[i] = (dp[i - 1] + (dp[i - 1] - dp[pi[i - 1]]) + 2) % mod;
}
}
// System.out.println(Arrays.toString(dp));
System.out.println(dp[n + 1] < 0 ? dp[n + 1] + mod : dp[n + 1]);
}
}
二、编程题1
描述
有三只球队，每只球队编号分别为球队1，球队2，球队3，这三只球队一共需要进行 n 场比赛。现在已经踢完了k场比赛，每场比赛不能打平，踢赢一场比赛得一分，输了不得分不减分。已知球队1和球队2的比分相差d1分，球队2和球队3的比分相差d2分，每场比赛可以任意选择两只队伍进行。求如果打完最后的 (n-k) 场比赛，有没有可能三只球队的分数打平。
输入描述：
第一行包含一个数字 t (1 <= t <= 10)
接下来的t行每行包括四个数字 n, k, d1, d2(1 <= n <= 10^12; 0 <= k <= n, 0 <= d1, d2 <= k)
输出描述：
每行的比分数据，最终三只球队若能够打平，则输出“yes”，否则输出“no”
示例1
输入：
2 3 3 0 0 3 3 3 3输出：
yes no说明：
case1: 球队1和球队2 差0分，球队2 和球队3也差0分，所以可能的赛得分是三只球队各得1分 case2: 球队1和球队2差3分，球队2和球队3差3分，所以可能的得分是 球队1得0分，球队2得3分, 球队3 得0分，比赛已经全部结束因此最终不能打平。
题解：
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = Integer.parseInt(sc.nextLine());
for(int i=0;i<t;i++){
String s = sc.nextLine();
String[] ss = s.split(" ");
long n = Long.parseLong(ss[0]);
long k = Long.parseLong(ss[1]);
long d1 = Long.parseLong(ss[2]);
long d2 = Long.parseLong(ss[3]);
// 利用剩余比赛场次解决
String res = solve2(n,k,d1,d2);
System.out.println(res);
}
}
private static String solve2(long n, long k, long d1, long d2) {
long m1 = k + 2*d1 + d2; //情况1
if(m1 >= 0 && m1 % 3 == 0){ //m有解是大前提
long left = (n - k) - (2*d1 + d2); //需要2d1+d2才能让两个较低的追上最高的达到平局，
if(left >= 0 && left % 3 == 0){ //那么剩下的场次要继续能被3整除才能继续保持平局。
return "yes";
}
}
long m2 = k + 2*d1 - d2;//情况2
if(m2 >= 0 && m2 % 3 == 0){
long left;
if(d1 >= d2){
left = (n - k) - (2*d1 - d2);
}else{
left = (n - k) - (2*d2 - d1);
}
if(left >= 0 && left % 3 == 0){
return "yes";
}
}
long m3 = k - 2*d1 + d2; //情况3
if(m3 >= 0 && m3 % 3 == 0){
long left = (n - k) - (d1 + d2);
if(left >= 0 && left % 3 == 0){
return "yes";
}
}
long m4 = k - 2* d1 - d2; //情况4
if(m4 >= 0 && m4 % 3 == 0){
long left = (n - k) - (d1 + 2*d2 );
if(left >= 0 && left % 3 == 0){
return "yes";
}
}
return "no";
}
}三、 编程题2
描述
有一个仅包含’a’和’b’两种字符的字符串s，长度为n，每次操作可以把一个字符做一次转换（把一个’a’设置为’b’，或者把一个’b’置成’a’)；但是操作的次数有上限m，问在有限的操作数范围内，能够得到最大连续的相同字符的子串的长度是多少。
输入描述：
第一行两个整数 n , m (1<=m<=n<=50000)，第二行为长度为n且只包含’a’和’b’的字符串s。
输出描述：
输出在操作次数不超过 m 的情况下，能够得到的 最大连续 全’a’子串或全’b’子串的长度。
示例1
输入：
8 1 aabaabaa输出：
5说明：
把第一个 'b' 或者第二个 'b' 置成 'a'，可得到长度为 5 的全 'a' 子串。
题解：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int oper = sc.nextInt();
String str = sc.next();
System.out.println(Math.max(arraySolve(len, oper, str, 'a'), arraySolve(len, oper, str, 'b')));
}
public static int arraySolve(int n, int m, String s, char c) {
int res = 0;
List<Integer> indexes = new ArrayList<>(); // 用来存储a/b的所有下标位置
for (int i = 0; i < n; i++) {
if (s.charAt(i) == c) { //用c来替换其他字符，将c所在下标位置加入
indexes.add(i);
}
}
// 如果要替换的字符个数小于可替换个数，那么直接全部替换即可
if (indexes.size() <= m) {
return n;
}
// 注意端点位置的处理
indexes.add(s.length());
res = indexes.get(m);
for (int i = m + 1; i < indexes.size(); i++) {
res = Math.max(res, indexes.get(i) - indexes.get(i - m - 1) - 1);
}
return res;
}
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）