題目一
可以參考 力扣1411
題目描述
小明現在手里有3種數字卡片，卡片上的數字分別為1，2，3，3種數字卡片每種都有若干張,他想將這些數字放入有一個N*3的方格中，每個方格中只能放入一張卡片，且要求相鄰的上下左右方格不能放入同一種數字的卡片，現在問你有多少種可能的放入方案，
輸入描述：
每個檔案輸入第一行輸入一個整數T(1<=T<=500)，代表有T組測驗資料;
接下來T組，每一組輸入一個整數n(1<=n<=100000);
輸出描述：
對于每一組測驗資料，輸出一個答案代表可能的方案數，由于答案很大，請你對10^9+7取余;
示例1：
輸入：
2
1
2
輸出：
12
54
說明：
對于樣例第一組放入1*3的方格中，可能的方案有：(1,2,1)、(2,1,2)、(3,1,2)、(1,2,3)、(2,1,3)、(3,1,3)、(1,3,1)、(2,3,1)、(3,2,1)、(1,3,2)、(2,3,2)、(3,2,3)
先上代碼
import java.util.Scanner;
public class Main {
private static long[][] dp = new long[10001][2];
private static int now = 1;
public static void main(String[] args) {
dp[1][0] = 6L;
dp[1][1] = 6L;
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i = 0 ; i < t ; i++){
int n = sc.nextInt();
if(n<=now){
long res = (dp[n][0] + dp[n][1])%1000000007;
int realRes = (int) res;
System.out.println(realRes);
} else {
for(int j = now+1 ; j <= n ; j++){
dp[j][0] = (dp[j-1][0]*3 + dp[j-1][1]*2)%1000000007;
dp[j][1] = (dp[j-1][0]*2 + dp[j-1][1]*2)%1000000007;
}
long res = (dp[n][0] + dp[n][1])%1000000007;
int realRes = (int) res;
System.out.println(realRes);
now = n;
}
}
}
}
解題思路
第一想法是用dfs去做，但是肯定超時，上面也都提示了答案可能很大，所以dfs一個一個數肯定不行，
仔細分析題目給的示例輸入，可以發現這樣一個規律，2 * 3方格的方案都是由1 * 3方格方案拓展而來的！也就是說對于n * 3問題，我們只需要在n-1 * 3的方案基礎上，對每個方案來考慮最后一排能擴展出幾個方案即可，
而對于每一排的方案我們可以將其分為兩大類：
第一類：(1,2,1)、(2,1,2)、(3,1,3)、(1,3,1)、(2,3,2)、(3,2,3)，我們把這種稱為ABA類；
第二類：(3,1,2)、(1,2,3)、(2,1,3)、(2,3,1)、(3,2,1)、(1,3,2)，我們把這種稱為ABC類
下面推導一下前一排和后一排的關系
-
如果前一排為ABA，那么后一排有5種可能，分別為 (C,A,C)、(B,A,B)、(B,C,B)、(B,A,C)、(C,A,B)，而這五種方案實際上就是 3種ABA 和 2種ABC ；
-
如果前一排為(A,B,C)，那么后一排有4種可能，分別為(B,A,B)、(B,C,B)、(B,C,A)、(C,A,B)，而這四種方案實際上就是 2種ABA 和 2種ABC ；
所以我們假設n * 3問題為f(n) ， ABA 方案數量為Xn，ABC 方案數量為Yn，
那么遞推關系如下：
f(n+1) = Xn+1 + Yn+1；
Xn+1 = 3Xn + 2Yn；
Yn+1 = 2Xn + 2Yn；
最后可以用備忘錄dp來記錄之前計算過的問題，來防止重復計算，提高時間效率，
筆者為了防止溢位，用long型別來計算，并在每個地方都進行取余操作(應該不是很有必要)，
題目二
第二題是圖論問題，不會，
總結
總體上來說，阿里筆試題難度不低，題目型別與CCF、ACM競賽類題目類似，和力扣上的題目不是一個風格，之前只在力扣上刷題，感覺力扣只能鍛煉一下演算法題的解題思維，考前去牛客熟悉一下編程環境很重要，不然處理輸入就要花費好長時間了，推薦大家把這一個小時的時間都用在盡力解一道題上面，不要前面做一下，做不出來又去做后面，大概率兩道題都做出不（大牛應該不會看我的博客吧QAQ），
最后即使一題都沒做出來也沒關系，阿里的筆試和素質測評好像只是一個參考，做不出來也有機會進到面試，好好準備面試吧！祝大家早日拿到offer！加油！
ps.有任何關于面試的問題可以在下面留言，或者想要阿里的內推方式也可以聯系我哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/266991.html
標籤：其他
上一篇：16. FizzBuzz