Java工程师丨面试真题（四）
一、水仙花数
描述
春天是鲜花的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的：“水仙花数”是指一个三位数，它的各位数字的立方和等于其本身，比如：153=1^3+5^3+3^3。 现在要求输出所有在m和n范围内的水仙花数。
输入描述：
输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。
输出描述：
对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于m,并且小于等于n，如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开;如果给定的范围内不存在水仙花数，则输出no;每个测试实例的输出占一行。
示例1
输入：
100 120 300 380输出：
no 370 371
题解：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int m = sc.nextInt();
int n = sc.nextInt();
List<Integer> res = new ArrayList<>();
for(int i = m; i <= n; i++){ //遍历 m--n 范围内的数值
int tmp = 0, stp = i, ans = 0;
while(stp != 0){ // 判断当前取整后是否为0，不是则继续
// tmp 暂存当前数 i 除以10的余数（即从右开始取其位数）
tmp = stp % 10;
// stp 暂存当前数 i 除以10的整数（用于判断是否取余到最后一位）
stp /= 10;
// 计算每次所余数的位数的立方和
ans += tmp * tmp * tmp;
}
if(ans == i){ //如果立方和与当前数 i 相等，将其加入 res 数组中
res.add(i);
}
}
if (res.isEmpty()){ //判断得到的 res 数组是否为空，为空输出 no
System.out.println("no");
}else { //不为空，则输出对应符合的水仙花数
for (int index : res){
System.out.print(index + " ");
}
System.out.println();
}
}
}
}
二、万万没想到之聪明的编辑
描述
我叫王大锤，是一家出版社的编辑。我负责校对投稿来的英文稿件，这份工作非常烦人，因为每天都要去修正无数的拼写错误。但是，优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径：
1. 三个同样的字母连在一起，一定是拼写错误，去掉一个的就好啦：比如 helllo -> hello
2. 两对一样的字母（AABB型）连在一起，一定是拼写错误，去掉第二对的一个字母就好啦：比如 helloo -> hello
3. 上面的规则优先“从左到右”匹配，即如果是AABBCC，虽然AABB和BBCC都是错误拼写，应该优先考虑修复AABB，结果为AABCC
我特喵是个天才！我在蓝翔学过挖掘机和程序设计，按照这个原理写了一个自动校对器，工作效率从此起飞。用不了多久，我就会出任CEO，当上董事长，迎娶白富美，走上人生巅峰，想想都有点小激动呢！
……
万万没想到，我被开除了，临走时老板对我说： “做人做事要兢兢业业、勤勤恳恳、本本分分，人要是行，干一行行一行。一行行行行行；要是不行，干一行不行一行，一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……
请听题：请实现大锤的自动校对程序
数据范围： 1≤n≤50 1 \le n \le 50 \ 1≤n≤50 ，每个用例的字符串长度满足 1≤l≤1000 1 \le l \le 1000 \ 1≤l≤1000
输入描述：
第一行包括一个数字N，表示本次用例包括多少个待校验的字符串。
后面跟随N行，每行为一个待校验的字符串。
输出描述：
N行，每行包括一个被修复后的字符串。
示例1
输入：
2 helloo wooooooow输出：
hello woow
示例2
输入：
1 nowcoder输出：
nowcoder
题解：
import java.util.*;
import java.lang.*;
public class Main {
public static void main(String[] args) {
Scanner reader=new Scanner(System.in);
int n=reader.nextInt();
String [] list=new String[n];
for (int i=0;i<n;i++) {
list[i]=reader.next();
}
for (int i=0;i<n;i++) {
String res=solution(list[i]);
System.out.println(res);
}
}
static String solution(String str) {
char[] chars = str.toCharArray();
int n=chars.length;
Deque<Character> deque=new LinkedList<>();
int j=0;
int pre=1;
while (j<n) {
int cnt=1;
while (j+1<n&&chars[j+1]==chars[j]){
cnt++;
j++;
}
int sum=0;
if (cnt>=2&&pre==1) {
deque.offerLast(chars[j]);
sum++;
}
deque.offerLast(chars[j]);
sum++;
pre=sum;
j++;
}
StringBuilder sb=new StringBuilder();
int size=deque.size();
for (int i=0;i<size;i++){
sb.append(deque.pollFirst());
}
return sb.toString();
}
}
三、万万没想到之抓捕孔连顺
描述
我叫王大锤，是一名特工。我刚刚接到任务：在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工，我提议
1. 我们在字节跳动大街的 N 个建筑中选定 3 个埋伏地点。
2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过 D 。
我特喵是个天才! 经过精密的计算，我们从X种可行的埋伏方案中选择了一种。这个方案万无一失，颤抖吧，孔连顺！
……
万万没想到，计划还是失败了，孔连顺化妆成小龙女，混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了，就是杨过本人来了也发现不了的！
请听题：给定 N（可选作为埋伏点的建筑物数）、 D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
注意：
1. 两个特工不能埋伏在同一地点
2. 三个特工是等价的：即同样的位置组合( A , B , C ) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
数据范围： 0<n,d≤106 0 < n,d\le 10^6 \ 0<n,d≤106
输入描述：
第一行包含空格分隔的两个数字 N和D(1 ≤ N ≤ 1000000; 1 ≤ D ≤ 1000000)
第二行包含N个建筑物的的位置，每个位置用一个整数（取值区间为[0, 1000000]）表示，从小到大排列（将字节跳动大街看做一条数轴）
输出描述：
一个数字，表示不同埋伏方案的数量。结果可能溢出，请对 99997867 取模
示例1
输入：
4 3 1 2 3 4输出：
4说明：
可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)示例2
输入：
5 19 1 10 20 30 50输出：
1说明：
可选方案 (1, 10, 20)示例3
输入：
2 100 1 102输出：
0说明：
无可选方案
题解：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int d = sc.nextInt();
int[] locations = new int[n];
for (int i = 0; i < n; i++) {
locations[i] = sc.nextInt();
}
long count = dsp(locations, n, d);
System.out.println(count);
}
}
public static long dsp(int[] locations, int n, int d) {
int left = 0, right = 2;
long count = 0;
int mod = 99997867;
while (right < n) {
if (locations[right] - locations[left] > d)
left++;
else if (right - left < 2)
right++;
else {
long num = right - left; // 第二位和第三位之间的最远距离
count += num * (num - 1) / 2L; // 第二位和第三位可以排列组合的数量
right++;
}
}
count %= mod;
return count;
}
}
- 点赞
- 收藏
- 关注作者
评论（0）