Java工程师丨面试真题（8）
一、机器人跳跃问题
描述
机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号，从左到右排列。编号为0的建筑高度为0个单位，编号为i的建筑的高度为H(i)个单位。
起初， 机器人在编号为0的建筑处。每一步，它跳到下一个（右边）建筑。假设机器人在第k个建筑，且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值，否则它将得到 E - H(k+1) 的能量值。
游戏目标是到达第个N建筑，在这个过程中，能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏，才可以保证成功完成游戏？
输入描述：
第一行输入，表示一共有 N 组数据.
第二个是 N 个空格分隔的整数，H1, H2, H3, ..., Hn 代表建筑物的高度
输出描述：
输出一个单独的数表示完成游戏所需的最少单位的初始能量
示例1
输入：
5 3 4 3 2 4输出：
4示例2
输入：
3 4 4 4输出：
4示例3
输入：
3 1 6 4输出：
3
备注：
数据约束：
1 <= N <= 10^5
1 <= H(i) <= 10^5
题解：
import java.util.Scanner;
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
double res = 0;
for(int i=1;i<=N;i++){
res += sc.nextInt()*Math.pow(2, N - i);
}
System.out.println((int)Math.ceil(res/Math.pow(2, N)));
}
}
二、字典序
描述
给定整数n和m, 将1到n的这n个整数按字典序排列之后, 求其中的第m个数。
对于n=11, m=4, 按字典序排列依次为1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9, 因此第4个数是2.
对于n=200, m=25, 按字典序排列依次为1 10 100 101 102 103 104 105 106 107 108 109 11 110 111 112 113 114 115 116 117 118 119 12 120 121 122 123 124 125 126 127 128 129 13 130 131 132 133 134 135 136 137 138 139 14 140 141 142 143 144 145 146 147 148 149 15 150 151 152 153 154 155 156 157 158 159 16 160 161 162 163 164 165 166 167 168 169 17 170 171 172 173 174 175 176 177 178 179 18 180 181 182 183 184 185 186 187 188 189 19 190 191 192 193 194 195 196 197 198 199 2 20 200 21 22 23 24 25 26 27 28 29 3 30 31 32 33 34 35 36 37 38 39 4 40 41 42 43 44 45 46 47 48 49 5 50 51 52 53 54 55 56 57 58 59 6 60 61 62 63 64 65 66 67 68 69 7 70 71 72 73 74 75 76 77 78 79 8 80 81 82 83 84 85 86 87 88 89 9 90 91 92 93 94 95 96 97 98 99 因此第25个数是120…
输入描述：
输入仅包含两个整数n和m。
数据范围:
对于20%的数据, 1 <= m <= n <= 5 ;
对于80%的数据, 1 <= m <= n <= 10^7 ;
对于100%的数据, 1 <= m <= n <= 10^18.
输出描述：
输出仅包括一行, 即所求排列中的第m个数字.
示例1
输入：
11 4输出：
2
题解：
import java.util.Scanner;
class DictOrder {
public long solve(long n,long m){
//start with subtree which started with 1
long ans = 1;
while (m!=0){
long cnt = getCountWithPre(ans,n);
if(cnt>=m){
// go to subtree
m --;
if(m==0)
break;
ans *= 10;//go to subtree with "ans+ 0"
}else {
m-=cnt;
ans+=1;// goto brother tree
}
}
return ans;
}
public long getCountWithPre(long pre, long n){
/*
* get count of tree node which start with pre
* return count: count of tree node with pre
* */
long cnt = 1;
long p=10;
for(; pre * p <= n; p*=10){
//the max of this subtree not bigger than n
if(pre*p+p-1<n)
cnt+=p;
else {
cnt += n-p*pre+1;// n is include
}
}
return cnt;
}
}
public class Main{
public static void main(String[] args) {
DictOrder dictOrder = new DictOrder();
Scanner sc = new Scanner(System.in);
while (sc.hasNext())
{
long n = sc.nextLong();
long m = sc.nextLong();
System.out.println(dictOrder.solve(n,m));
}
}
}
三、异或
描述
给定整数m以及n各数字A1,A2,..An，将数列A中所有元素两两异或，共能得到n(n-1)/2个结果，请求出这些结果中大于m的有多少个。
输入描述：
第一行包含两个整数n,m.
第二行给出n个整数A1，A2，...，An。
数据范围
对于30%的数据，1 <= n, m <= 1000
对于100%的数据，1 <= n, m, Ai <= 10^5
输出描述：
输出仅包括一行，即所求的答案
示例1
输入：
3 10 6 5 10输出：
2
题解：
import java.util.Scanner;
public class Main {
private static class TrieTree {
TrieTree[] next = new TrieTree[2];
int count = 1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()){
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
System.out.println(solve(a, m));
}
}
private static long solve(int[] a, int m) {
TrieTree trieTree = buildTrieTree(a);
long result = 0;
for (int i = 0; i < a.length; i++) {
result += queryTrieTree(trieTree, a[i], m, 31);
}
return result / 2;
}
private static long queryTrieTree(TrieTree trieTree, int a, int m, int index) {
if(trieTree == null)
return 0;
TrieTree current = trieTree;
for (int i = index; i >= 0; i--) {
int aDigit = (a >> i) & 1;
int mDigit = (m >> i) & 1;
if(aDigit == 1 && mDigit == 1) {
if(current.next[0] == null)
return 0;
current = current.next[0];
} else if (aDigit == 0 && mDigit == 1) {
if(current.next[1] == null)
return 0;
current = current.next[1];
} else if (aDigit == 1 && mDigit == 0) {
long p = queryTrieTree(current.next[1], a, m, i - 1);
long q = current.next[0] == null ? 0 : current.next[0].count;
return p + q;
} else if (aDigit == 0 && mDigit == 0) {
long p = queryTrieTree(current.next[0], a, m, i - 1);
long q = current.next[1] == null ? 0 : current.next[1].count;
return p + q;
}
}
return 0;
}
private static TrieTree buildTrieTree(int[] a) {
TrieTree trieTree = new TrieTree();
for (int i = 0; i < a.length; i++) {
TrieTree current = trieTree;
for (int j = 31; j >= 0; j--) {
int digit = (a[i] >> j) & 1;
if(current.next[digit] == null) {
current.next[digit] = new TrieTree();
} else {
current.next[digit].count ++;
}
current = current.next[digit];
}
}
return trieTree;
}
}四、找零
描述
Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N(0<N≤1024)N (0 < N \le 1024)N(0<N≤1024)的商品，请问最少他会收到多少硬币？
输入描述：
一行，包含一个数N。
输出描述：
一行，包含一个数，表示最少收到的硬币数。
示例1
输入：
200输出：
17说明：
花200，需要找零824块，找12个64元硬币，3个16元硬币，2个4元硬币即可。
备注：
对于100%的数据，N(0<N≤1024)N (0 < N \le 1024)N(0<N≤1024)。题解：
import java.util.Scanner; //java.util为包名，Scanner为类名
public class Main
{
public static void main(String[] args) // 切莫少了传入参数
{
Scanner input = new Scanner( System.in ); //使用前先导入Scanner类
int N = input.nextInt(); //next() 为方法
input.close();
int Z = 1024-N;
int n64 = Z/64;
int S = Z-64*n64; // *不能少，和数学里的带分数的单项式不同
int n16 = S/16;
S = S-16*n16; //切莫重复定义，应用之前剩下的来减
int n4 = S/4;
S = S-4*n4;
int NS = n64+n16+n4+S;
System.out.println( NS ); //输出语句切莫和C语言搞混
}
}
- 点赞
- 收藏
- 关注作者
评论（0）