為什麼80%的碼農都做不了架構師？>>>
嘗試挑戰了下網易2017校招的筆試程式設計題，共三題，AC第一題，第二題思考了很久勉強用一種low逼的方式完成，第三題沒有完成，希望路過的ACM大神點醒。下面附上原題和我的解法，不喜勿噴。
第一題：rev翻轉
實作一個rev操作，使得一個整數反轉，如輸入"123"，輸出"321"，并去掉前導0，如輸入“100”，輸出"1"。然後輸入兩個數a,b，輸出rev(rev(a)+rev(b))的結果。
輸入輸出示例：
輸入：
100 322
輸出：
422
解題思路：這題較為簡單，隻要能寫出rev函數就可以解決問題。我采用的方法是從個位開始逐個提取數字拼接字元串的方式實作，設定首0标志，凡遇到0則剔除，當遇到非0數字時，取消首0檢驗。不多說，附上代碼：
import java.util.Scanner;
public class Main {
public static int rev(int a){
StringBuffer string =new StringBuffer();
int b = 0 ;
boolean flag=true;
while(a>0){
b = a%10;
a = (a-b)/10;
if(flag){
if(b!=0){
flag = false;
string.append(Integer.toString(b));
}
}else{
string.append(Integer.toString(b));
}
}
return Integer.parseInt(string.toString());
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {//注意while處理多個case
int a = in.nextInt();
int b = in.nextInt();
System.out.println(rev(rev(a)+rev(b)));
}
}
}
第二題：暗黑的字元串
使用“A”，“B”，“C” 三個字元建構字元串，對于一個建構好的字元串，如果存在連續三個字元，“A”，“B”，“C” 三個字元剛好各出現一次，如“ABCA”，那麼稱這樣的字元串是“純淨”的。如果找不到這樣的連續三個字元滿足條件，那麼稱這樣的字元串是“暗黑”的，如“ABAA”。
現在給定一個整數n，試輸出能構成的n位暗黑字元串的個數。
輸入輸出示例：
輸入：
3
輸出：
21
分析：這題筆一開始筆者采用的是暴力窮舉的方法，就是列出所3^n種可能，然後逐一判斷是否暗黑來進行統計。在建構出所有的字元串時采用了遞歸的方法，即通過一位一位地增加位數的方式得到，算法複雜度較高。代碼如下：
import java.util.Scanner;
public class Main {
public static boolean isWhite(String testString){
boolean flag = false;
String[] abc = new String[]{"ABC","ACB","BAC","BCA","CBA","CAB"};
for (int i = 0; i < abc.length; i++) {
if(testString.contains(abc[i])){
flag = true;
break;
}
}
return flag;
}
public static String[] generateABC(int n){
String[] init = new String[]{"A","B","C"};
if(n==1){
return init;
}else{
String[] abc = generateABC(n-1);
String[] ABC = new String[abc.length*init.length];
for (int i = 0; i < abc.length; i++) {
for (int j = 0; j < init.length; j++) {
ABC[j*abc.length+i] =abc[i]+init[j];
}
}
return ABC;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
StringBuffer testString = new StringBuffer();
if(n<3){
System.out.println((int)(Math.pow(3,n)));
}else{
int count = 0;
String[] result = generateABC(n);
for (int i = 0; i
然後很快發現，這種寫法在n=14時就堅持不住記憶體溢出了。
于是請教了ACM高手，在高手的指點下，使用了數位DP算法，完成了此題的求解。代碼如下：
import java.util.Scanner;
public class DpResovle {
private static int[][] blacks ;
private static boolean flag = true;//标記用以判斷是否是首次調用
public static int[][] BlackCount (int length){
if(flag){
blacks = new int[length+1][4];
flag =false;
}
if(length==3){
//用二維數組blacks 存儲暗黑字元串的個數
//第一個次元代表字元串長度
// 第二個次元的代表末尾狀況
// 0 代表末尾以AAA，BBB，或CCC結尾
// 1 代表末尾以AAB，AAC，BBC，BBA，CCA，CCB結尾
// 2 代表末尾以ABA，CBC，ACA，BCB，BAB，CAC結尾
// 3 代表末尾以ABB，ACC，BCC，BAA，CAA，BAA結尾
blacks[3][0] =3;
blacks[3][1] =6;
blacks[3][2] =6;
blacks[3][3] =6;
}else {
BlackCount (length-1);
blacks[length][0] = blacks[length-1][0]+blacks[length-1][3];
blacks[length][1] = 2*(blacks[length-1][0]+blacks[length-1][3]);
blacks[length][2] = blacks[length-1][1]+blacks[length-1][2];
blacks[length][3] = blacks[length-1][1]+blacks[length-1][2];
}
return blacks;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
StringBuffer testString = new StringBuffer();
if(n<3){
System.out.println((int)(Math.pow(3,n)));
}else{
long time1 = System.currentTimeMillis();
int[][] result = BlackCount(n);
int count = 0;
for (int i = 0; i < 4; i++) {
count+=result[n][i];
}
System.out.println(count);
long time2 = System.currentTimeMillis();
System.out.println("用時:"+(time2-time1)+"ms");
}
}
}
第三題：回文序列
對于{1,2,1},{345},{2,3,3,2}這樣對稱的序列我們稱之為回文序列。
現在對于任意一個輸入的序列，如{1,2,3,4}，我們有一種操作，将相鄰兩個數相加并放回到這兩個數原來的位置。對于{5,2,3,4}，可以通過一次操作變為{7,3,4}，兩次操作變為{7,7}。
現在試求出對于任意一個輸入的序列，将其變為回文序列的最小步數。
輸入輸出示例：
輸入：
4(代表序列個數)
5 2 3 4
輸出：
2
分析：本題筆者沒有寫出代碼。不知道這題是否可以用動态規劃的方法求解，如果可以，還請大神指教。