上星期六參加的筆試，當時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=)