上星期六参加的笔试，当时AC两道，笔试完后再想第三道，本来以为自己队列+栈能解出来，但是发现始终有问题....参考了网上的做法，把没做出来的两道做完了。唉，幸好AC两道也够面试了。
在此，分享一下我的代码及思路给大家。欢迎和我探讨。（非acmer，没啥好技巧，但是思路肯定很好懂。）
ps：我投的是测开。星期六要面试了，希望能怼进头条。保佑保佑。
1. 硬币问题
Z国的货币系统包含面值1、4、16、64元共计4种硬币，以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为N(0<N<=1024)的商品，请问最少他会收到多少硬币？
输入描述：
一行，包含一个整数N
输出描述：
一行，包含一个数，表示最少收到的硬币数
示例1：
输入：200
输出：17
解释：824 = 64x12 + 16x3 + 4x2, 12 + 3 + 2 = 17
解题思路：没啥好说的，刚学C语言都能解出来。（送分题）
public class test1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//找零总计
int s = 1024 - n;
int count64 = s / 64;
int res64 = s - count64 * 64;
int count16 = res64 / 16;
int res16 = res64 - count16 * 16;
int count4 = res16 / 4;
int res4 = res16 - count4 * 4;
int count1 = res4;
int res = count1 + count4 + count16 + count64;
System.out.println(res);
}
}
2. 校对程序
实现一个单词校对程序，实现以下几个功能：
- 如果有三个同样的字母连在一起，则需要去掉一个，如’helllo’ -> ‘hello’
- 如果有两对同样的字母(AABB型)连在一起，去掉第二对的一个字母，如’helloo’ -> ‘hello’
- 上面的规则都必须优先从左到右匹配，如’AABBCC’，要先处理第一个’AABB’，结果为’AABCC’
输入描述：
第一行包含一个数字n，表示本次用例包括多少个待校验的字符串
之后n行，每行为一个待校验的字符串。
输出描述：
n行，每行包括一个被修复后的字符串
示例1：
输入：
2
helloo
wooooooooow
输出：
hello
woow
解题思路：不知道我的思路是不是太暴力..但是看起来很清晰，稍微需要注意一下循环停止的条件。
public class test2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<String> arrayList = new ArrayList<String>();
for (int i = 0; i < n; i++) {
arrayList.add(sc.next());
}
for (String s : arrayList) {
s = checkString(s);
System.out.println(s);
}
}
//检查字符串
private static String checkString(String s) {
String s2;
StringBuffer s1 = new StringBuffer(s);
//检查连续三个字母一样
for (int i = 0; i < s1.length() - 2; i++) {
if ((s1.charAt(i) == s1.charAt(i + 1)) && (s1.charAt(i) == s1.charAt(i + 2))) {
s1.deleteCharAt(i);
i--;
}
}
//检查AABB型
for (int i = 0; i < s1.length() - 3; i++) {
if ((s1.charAt(i) == s1.charAt(i + 1)) && (s1.charAt(i+2) == s1.charAt(i + 3))) {
s1.deleteCharAt(i+2);
i--;
}
}
s2 = s1.toString();
return s2;
}
}
做完这两题其实我只用了半个小时左右。没想到后面两题，一个半小时都没AC，我觉得主要是心理上没战胜它，觉得头条的笔试一定很难，其实难度是成阶梯上升的，给大家的建议是，在限制时间内首先保证AC两道题，也就是可以都下手，找到最好做出来的，然后一道题一道题刚，不然容易几道题都没做出来...
3. 奖品数量
有n个人参加编程比赛，比赛结束后每个人都有一个分数
现在所有人排成一个圈(第1个人和第n个人相邻)领取奖品，要求满足：
- 如果一个人比他相邻的人的分数高，那么他获得的奖品应该要多余相邻的人
- 每个人至少需要得到一个奖品
输入描述：
第一行是一个整数t，表示测试样例的个数
每个测试样例的第一行是一个正整数n，表示参加比赛的人数(0 < n < 100000)
第二行是n个整数a[i]，表示每个人的分数(0 < a[i] < 100000)
输出描述：
对每个测试样例，输出应该准备的最少奖品数
示例1
输入：
2
2
1 2
4
1 2 3 3
输出：
3
8
解题思路：原来的想法错了，怎么调都不对。看了网上的，思路是这样的。
首先从左往右遍历，如果后面的数大于前面的，奖品数+1，否则奖品数=1，这样确保可每个人都至少有一个奖品。
再从右往左遍历，如果后面的数小于前面的数，这时，如果前面的奖品大于后面，继续判断，否则，前面的奖品数得变，
Math.max(award[i],award[i+1]+1)。
public class test3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
//测试样例个数
int n = sc.nextInt();
//存结果
ArrayList<Integer> res = new ArrayList<Integer>();
while (n-- != 0) {
//人数
int people = sc.nextInt();
int[] score = new int[people+1];
//保存分数
for (int i = 0; i < people; i++) {
score[i] = sc.nextInt();
}
score[people] = score[0];
int res1 = countAward(score);
res.add(res1);
}
for (Integer i :res)
System.out.println(i);
}
private static int countAward(int[] score) {
int res1 = 0;
int[] award = new int[score.length];
score[0] = 1;
award[0] = 1;
//先从左往右遍历，满足了每个人都至少有一个奖品
for (int i = 1; i < score.length; i++) {
if (score[i] > score[i - 1])
award[i] = award[i - 1] + 1;
else
award[i] = 1;
}
//再从右往左遍历
for (int i = score.length - 2; i > -1; i--) {
if (score[i]> score[i+1]) {
if (award[i] > award[i+1])
continue;
else
award[i] = Math.max(award[i],award[i+1]+1);
}
}
for (int i = 0; i < award.length-1; i++) {
res1 += award[i];
}
return res1;
}
}
4. 绳子裁剪
有N根绳子，第i根绳子的长度为l[i]，现在需要M根等长的绳子。
你可以对这N根绳子进行任意裁剪（不能拼接），请你计算出这M根绳子最长的长度
输入描述：
第一行包括两个整数N,M，含义如题所述(1 <= N,M <= 100000)
第二行包含N个整数，分别对应N根绳子的长度(0 < l[i] < 10^9)
输出描述：
一个数字，表示裁剪后最长的长度，保留两位小数
示例1
输入：
3 4
3 5 4
输出：
2.50
解释： 第一根和第三根绳子分别裁剪出一根2.50长度的绳子，第二根绳子刚好可以裁剪出两根2.50的长度绳子，刚好4根。
解题思路：看了思路以后发现原来这么简单，划重点，如果要找一个数，首先想到二分法。二分法基本上大家都会写，所以清楚思路之后，建议大家自己写，这样才能提高。我是先把绳子的最大长度找到再去做二分，不过从10的九次方开始二分也可以。稍微需要注意的地方就是可能有小数。
public class test4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
for (int i = 0;i<n;i++)
a[i] = sc.nextInt();
int max = a[0];
for (int i = 1; i < n; i++) {
if (max < a[i])
max = a[i];
}
double high = max;
double low = 0;
double mid = 0;
//计算按照最大长度裁剪得到的绳子根数
int count = checkMax(a, high);
while (high - low > 1.0E-6) {
mid = (low + high) / 2;
count = checkMax(a, mid);
//如果计算出的结果小于m，说明最大长度大了，
if (count < m)
high = mid;
//如果计算出的结果大于m，说明最大长度小了，
else
low = mid;
}
System.out.println(String.format("%.2f",mid));
}
private static int checkMax(int[] a, double maxLength) {
int count = 0;
for (int i = 0; i < a.length; i++) {
Double s = a[i] / maxLength;
int s1 = s.intValue();
count += s1;
}
return count;
}
}
以上就是20190316的笔试题了。我还太菜了，很庆幸能拿到面试机会。虽然通过的概率很小，但是我也会尽力准备的。考研失败+互联网寒冬，让我真心懂得机会是留给有准备的人，不要等到机会来临的时候，你才意识到去争取，那已经晚了。
不过人一直要奋斗，也是很累的吧，所以“优秀是一种习惯”，这样的人才是真正的大神。
我还在路上。加油。
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)