救生艇
題目：第 i 個人的體重為 people[i]，每艘船可以承載的最大重量為 limit。每艘船最多可同時載兩人，但條件是這些人的重量之和最多為 limit。返回載到每一個人所需的最小船數。(保證每個人都能被船載)。
示例 1：
輸入：people = [1,2], limit = 3
輸出：1
解釋：1 艘船載 (1, 2)
示例 2：
輸入：people = [3,2,2,1], limit = 3
輸出：3
解釋：3 艘船分別載 (1, 2), (2) 和 (3)
示例 3：
輸入：people = [3,5,3,4], limit = 5
輸出：4
解釋：4 艘船分別載 (3), (3), (4), (5)
提示：
1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000
思路：莫名其妙的感覺最近的題目都是差不多的思路呢。判斷的話我覺得應該用貪心，就是盡量裝多的。所以先要排序體重。然后題目的標簽是雙指針。。算了，我先暴力遍歷試試吧，畢竟雙指針覺得有點復雜。我去代碼實現了。
暴力法超時了。。。emmm...這個題果然還是得老老實實雙指針。而且隨著做我發(fā)現了一個問題，其實貪心不貪心也不是那么重要。如果從后遍歷的話：
a1 a2 a3 a4四個數。a4可以和a1，a2分別組合。按照我們貪心的算法應該是a4+a2.但是其實本質上a4和a1一船也無所謂。因為a3比a4小。a4都能和a2一船，那么a3一定可以和a2一船。這樣根本不用貪心了。所以說這個題雙指針也簡單的很，我去換個方式寫代碼：
這個思路果然可以，而且性能還挺好：
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int ans = 0;
int l = 0;
int r = people.length-1;
while (true){
if(l >= r) return ans+r-l+1;
if(people[l]+people[r]<=limit){
l++;
r--;
ans++;
}else{
r--;
ans++;
}
}
}
}
超過了百分之九十七的人，一開始是我把這個題想的復雜了。因為只能乘2個人，所以很多都可以簡單化，上面代碼性能超過百分之九十七的人。我再去看看性能第一的代碼：
好吧，性能第一的代碼思路差不多，但是沒有用系統(tǒng)的排序，而是用數組下標代替值，值代表個數。用了空間換時間，挺麻煩但是性能挺好的代碼：
class Solution {
public int numRescueBoats(int[] people, int limit) {
int[] wights = new int[limit + 1];
for(int wight: people){
wights[wight]++;
}
int i = 0, j = limit;
int res = 0;
while(i <= j){
while(i <= j && wights[i] <= 0){
i++;
}
while(i <= j && wights[j] <= 0){
j--;
}
if(i > j){
break;
}
if(i!=j&&i + j <= limit){
int min=Math.min(wights[i],wights[j]);
res+=min;
wights[i]-=min;
wights[j]-=min;
}else if(i+j>limit){
res+=wights[j];
wights[j]=0;
}else if(i==j&&i+j<=limit){
res+=wights[i]%2==0?wights[i]/2:wights[i]/2+1;
wights[i]=0;
}
}
return res;
}
}
然后這個題就這樣了，下一題。
螺旋矩陣3
題目：在 R 行 C 列的矩陣上，我們從 (r0, c0) 面朝東面開始.這里，網格的西北角位于第一行第一列，網格的東南角位于最后一行最后一列。現在，我們以順時針按螺旋狀行走，訪問此網格中的每個位置。
每當我們移動到網格的邊界之外時，我們會繼續(xù)在網格之外行走（但稍后可能會返回到網格邊界）。最終，我們到過網格的所有 R * C 個空間。按照訪問順序返回表示網格位置的坐標列表。
示例 1：
輸入：R = 1, C = 4, r0 = 0, c0 = 0
輸出：[[0,0],[0,1],[0,2],[0,3]]
示例 2：
輸入：R = 5, C = 6, r0 = 1, c0 = 4
輸出：[[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]
提示：
1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C
思路：怎么說呢，這個題我覺得實現應該不難，但是代碼肯定不簡單。就是比較復雜的那種。初步思路因為任意一個點都可能是旋轉的中心點，所以最省事的辦法就是直接把這個二維數組用一個3乘3的范圍包起來。這樣能確定每一個旋轉都在這個給定范圍內。然后原數組有元素的位置就是33格的中心位置，也就是橫縱坐標都減100.當然了這里我覺得細節(jié)上可以再處理下，比如設置為boolean值，是true則是這個范圍。而且給定范圍是100乘100.這樣需要的空間也不過是300乘300.還能接受，然后順著轉直到所有元素都轉到了就行，反正思路如下，下面我去實現下。
第一版代碼：
class Solution {
public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
boolean[][] b = new boolean[300][300];
for(int i = 0;i<R;i++) {
for(int j = 0;j<C;j++) {
b[i+100][j+100] = true;
}
}
int n = R*C;
int[][] ans = new int[n][2];
int f = 0;//0是左到右。1是上到下。2是右到左。3是下到上
int l = c0+100;
int r = c0+100;
int top = r0+100;
int bottom = r0+100;
int temp = 0;
while(temp < n) {
if(f == 0) {
r += 1;
for(int i = l;i<r;i++) {
if(b[top][i] == true) {
ans[temp++] = new int[] {top-100,i-100};
}
}
f = 1;
}else if (f == 1) {
bottom += 1;
for(int i = top;i<bottom;i++) {
if(b[i][r] == true) {
ans[temp++] = new int[] {i-100,r-100};
}
}
f = 2;
}else if (f == 2) {
l -= 1;
for(int i = r;i>l;i--) {
if(b[bottom][i] == true) {
ans[temp++] = new int[] {bottom-100,i-100};
}
}
f = 3;
}else {
top -= 1;
for(int i = bottom;i>top;i--) {
if(b[i][l] == true) {
ans[temp++] = new int[] {i-100,l-100};
}
}
f = 0;
}
}
return ans;
}
}
思路和我之前說的差不多。然后果然實現起來賊麻煩。簡單來說把這個給定的數組用一個大范圍包含住。保證所有的螺旋都有點可落。然后當所有的點都穿過了以后直接返回。這個代碼性能不太好。我是覺得可能是我代碼書寫的問題?；蛘哒f思路有問題？我去試試不用這個布爾數組了。只看橫縱坐標是不是在范圍內，是的話放入結果集。去試試代碼。
第二版ac代碼：
class Solution {
public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
int n = R*C;
int[][] ans = new int[n][2];
int f = 0;//0是左到右。1是上到下。2是右到左。3是下到上
int l = c0;
int r = c0;
int top = r0;
int bottom = r0;
int temp = 0;
while(temp < n) {
if(f == 0) {
r += 1;
for(int i = l;i<r;i++) {
if(top<0 || top>=R) break;
if(i>=0 && i<C) ans[temp++] = new int[] {top,i};
}
f = 1;
}else if (f == 1) {
bottom += 1;
for(int i = top;i<bottom;i++) {
if(r<0 || r>=C) break;
if(i>=0 && i<R) ans[temp++] = new int[] {i,r};
}
f = 2;
}else if (f == 2) {
l -= 1;
for(int i = r;i>l;i--) {
if(bottom<0 || bottom>=R) break;
if(i>=0 && i<C) ans[temp++] = new int[] {bottom,i};
}
f = 3;
}else {
top -= 1;
for(int i = bottom;i>top;i--) {
if(l<0 || l>=C) break;
if(i>=0 && i<R) ans[temp++] = new int[] {i,l};
}
f = 0;
}
}
return ans;
}
}
怎么說呢，首先說點讓人開心的:第二版代碼除了結果集不難需要額外的空間了。然后說點不開心的：性能和之前第一版一樣，都是5ms。。。改了個寂寞。所以我決定直接看性能第一的代碼了：
附上性能第一的代碼:
class Solution {
public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
int[][] result = new int[R * C][];
if (R * C == 0) {
return result;
}
int index = 0;
if (r0 < R && r0 >= 0 && c0 < C && c0 >= 0) {
result[index++] = new int[]{r0, c0};
}
int step = 1;
while (index < R * C) {
for (int i = 0; i < step; i++) {
c0++;
if (r0 < R && r0 >= 0 && c0 < C && c0 >= 0) {
result[index++] = new int[]{r0, c0};
if (R * C == 0) {
return result;
}
}
}
for (int i = 0; i < step; i++) {
r0++;
if (r0 < R && r0 >= 0 && c0 < C && c0 >= 0) {
result[index++] = new int[]{r0, c0};
if (R * C == 0) {
return result;
}
}
}
step++;
for (int i = 0; i < step; i++) {
c0--;
if (r0 < R && r0 >= 0 && c0 < C && c0 >= 0) {
result[index++] = new int[]{r0, c0};
if (R * C == 0) {
return result;
}
}
}
for (int i = 0; i < step; i++) {
r0--;
if (r0 < R && r0 >= 0 && c0 < C && c0 >= 0) {
result[index++] = new int[]{r0, c0};
if (R * C == 0) {
return result;
}
}
}
step++;
}
return result;
}
}
又是自己想不到，一看人家的代碼恍然大悟秒懂的感覺。。同樣也不用額外空間，單純的一圈一圈去獲取。然后判斷的可能比我簡單一些。同樣的用一個變量統(tǒng)計當前多少個格子已經放入結果集了，什么時候所有的格子放入結果集返回。要說哪里是寫不出來的也沒有，就是沒這么想。挺精巧的代碼。這個題就這樣吧。下一題了。
解碼異或后的排序
題目：給你一個整數數組 perm ，它是前 n 個正整數的排列，且 n 是個 奇數 。它被加密成另一個長度為 n - 1 的整數數組 encoded ，滿足 encoded[i] = perm[i] XOR perm[i + 1] 。比方說，如果 perm = [1,3,2] ，那么 encoded = [2,1] 。給你 encoded 數組，請你返回原始數組 perm 。題目保證答案存在且唯一。
示例 1：
輸入：encoded = [3,1]
輸出：[1,2,3]
解釋：如果 perm = [1,2,3] ，那么 encoded = [1 XOR 2,2 XOR 3] = [3,1]
示例 2：
輸入：encoded = [6,5,4,6]
輸出：[2,4,1,5,3]
提示：
3 <= n < 105
n 是奇數。
encoded.length == n - 1
思路：這個題怎么說呢，是5/11的每日一題。然后我之前做過一道和這個差不多的簡單題目，唯一區(qū)別就是那道題給了第一個元素，然后整個題就很無腦的解決了。為什么我要特意提一下這個呢？因為我覺得這個題目，主要也是獲取第一個數的值。當然了其實獲取最后一個數的值也行。但是如何獲取呢？還是應該從異或出發(fā)。雖然二進制位運算是我的知識盲區(qū)，但是我記得之前做過一個找出數組唯一出現過一次的元素，其中方法就是數組所有元素異或。相同元素異或會等于0 。別的元素都是成對出現變成0，所以唯一的出現一次的元素會成為異或的結果。而這個題首先是前n個數我們是知道的，所以能獲取前n個數的異或結果。其次給出的解碼結果是這樣的：
a1 ^ a2.a2 ^ a3,a3 ^ a4,a4 ^ a5,a5 ^ a6.a6 ^ a7我就不往后寫了，但是大家其實可以看到規(guī)律了：如果我們想獲取a2到an的異或結果，只要上面這么取：
(a2 ^ a3) ^ (a4^a5) ^ (a6 ^ a7)....而且注意這個n是奇數，所以這個思路絕對沒問題。只要獲取了第一個數的值，后面都很容易順下來了，我去寫代碼：
第一版代碼：
class Solution {
public int[] decode(int[] encoded) {
int n = encoded.length;
int sum = 0;
int d = 0;
for(int i = 1; i<=n+1; i++) sum ^= i;
for(int i = 1;i<n;i+=2) d ^= encoded[i];
int[] ans = new int[n+1];
ans[0] = sum^d;
for(int i = 1;i<n+1;i++) ans[i] = encoded[i-1]^ans[i-1];
return ans;
}
}
emmmmmm....怎么說呢，雖然ac了，但是我完全理解不了為什么性能這么慘。。只超過了百分之十一。感覺時間復雜度也不高啊，這種題思路比代碼更重要，我覺得暫時我想不出別的思路了，我去看看性能第一的代碼：
就真的很莫名其妙，我以為是我思路有問題，結果性能第一的代碼和我思路是一樣的，幾乎只有最后一次遍歷我一開始是從1開始，人家是從0開始。結果我也改成從0開始了，性能立刻超過百分之九十八了，簡直黑人問號.jpg...
附上修改后的代碼：
class Solution {
public int[] decode(int[] encoded) {
int n = encoded.length;
int sum = 0;
int d = 0;
for(int i = 1; i<=n+1; i++) sum ^= i;
for(int i = 1;i<n;i+=2) d ^= encoded[i];
int[] ans = new int[n+1];
ans[0] = sum^d;
for(int i = 0;i<n;i++) ans[i+1] = encoded[i]^ans[i];
return ans;
}
}
除了最后一句沒有任何區(qū)別，性能天差地別。。。因為這個題我覺得思路比較清晰，所以就不多說了，下一題。
子數組異或查詢
題目：有一個正整數數組 arr，現給你一個對應的查詢數組 queries，其中 queries[i] = [Li, Ri]。對于每個查詢 i，請你計算從 Li 到 Ri 的 XOR 值（即 arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作為本次查詢的結果。并返回一個包含給定查詢 queries 所有結果的數組。
示例 1：
輸入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
輸出：[2,7,14,8]
解釋：
數組中元素的二進制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查詢的 XOR 值為：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8
示例 2：
輸入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
輸出：[8,0,4,4]
提示：
1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length
思路：2021/5/12的每日一題。總而言之這個題目不難、而且不知道為啥最近的每日一題都是異或的呢。。首先異或的特點是相同的數字異或=0.所以這個題我的想法就是用數組記錄從頭到i異或的結果，然后每次取值直接取r異或l-1.因為l小于r。所以得出的應該是l前面的都異或了兩次歸0了，其余l(xiāng)到r都異或一次。大概思路就這樣，我去代碼實現。
第一版代碼：
class Solution {
public int[] xorQueries(int[] arr, int[][] queries) {
int[] d = new int[arr.length+1];
d[0] = 0;
for(int i = 0;i<arr.length;i++) d[i+1] = d[i]^arr[i];
int[] ans = new int[queries.length];
for(int i = 0;i<queries.length;i++) ans[i] = d[queries[i][1]+1]^d[queries[i][0]];
return ans;
}
}
看我自己寫的這個代碼我莫名覺得好笑。果然學好不容易，學壞一出溜。
自動知道for循環(huán)的時候循環(huán)體中一句話不用大括號，各種壓縮?？瓷先ゴa簡潔好看，實際上可讀性賊差。我就是這么有自知之明還明知故犯。
總而言之思路沒問題，就是性能不太好。但是我覺得性能不好的原因應該在細節(jié)處理上，畢竟思路都已經O(n)了，我去小修改一下試試。改了一點點代碼的寫法就超過百分百了，嘖嘖，貼上截圖：
然后修改的地方也用紅框框框起來了，就不再貼一遍了。這個題就過了，下一題。
可能的二分法
題目：給定一組 N 人（編號為 1, 2, ..., N）， 我們想把每個人分進任意大小的兩組。每個人都可能不喜歡其他人，那么他們不應該屬于同一組。形式上，如果 dislikes[i] = [a, b]，表示不允許將編號為 a 和 b 的人歸入同一組。當可以用這種方法將所有人分進兩組時，返回 true；否則返回 false。
示例 1：
輸入：N = 4, dislikes = [[1,2],[1,3],[2,4]]
輸出：true
解釋：group1 [1,4], group2 [2,3]
示例 2：
輸入：N = 3, dislikes = [[1,2],[1,3],[2,3]]
輸出：false
示例 3：
輸入：N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
輸出：false
提示：
1 <= N <= 2000
0 <= dislikes.length <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
對于 dislikes[i] == dislikes[j] 不存在 i != j
思路：這個題咋說呢，好像是做過類似的，題目標簽的深度優(yōu)先?？偠灾椰F在的想法就是染色。第一個dislikes中兩個元素分別紅綠色（1，-1）。然后后面的我打算用map，把和key不和的放入結果集中。然后依次類推下去。接下來就正常判斷就行了，注意下這里紅綠色是我個人理解，其實就是分狀態(tài)。比如討厭的人兩個陣營，那么一組討厭中一定一個1，一個-1.都是一樣的數字說明撞色了，直接false。從1開始判斷。因為陣營又不影響結果，所以假裝1是紅色陣營的（賦值1）。然后順序往下1不喜歡的都放到綠色陣營-1中。然后遞歸1不喜歡的這些，他們不喜歡的又回到1.最終如果遇到應該是1結果之前已經是-1的或者應該-1之前是1的說明無法劃分了。思路就這樣。下面我去代碼實現
第一版代碼：
class Solution {
int[] color;
ArrayList[] lists;
public boolean possibleBipartition(int n, int[][] dislikes) {
lists = new ArrayList[n+1];
for(int i = 0;i<lists.length;i++) lists[i] = new ArrayList<Integer>();
for(int[] i:dislikes) {
lists[i[0]].add(i[1]);
lists[i[1]].add(i[0]);
}
//染色做法，1代表第一陣營，-1代表第二陣營。0代表未分陣營。
color = new int[n+1];
for(int i = 1;i<lists.length;i++) {
if(color[i] == 0) {//沒顏色的默認第一陣營
if(!dfs(i, 1)) return false;
}
}
return true;
}
public boolean dfs(int i,int temp) {
List<Integer> list = lists[i];
for(int cur:list) {
if(color[cur] == temp) return false;//敵人是一個陣營。直接false
if(color[cur] == 0) {
color[cur] = -temp;
if(!dfs(cur, -temp)) return false;
}
}
return true;
}
}
其實一開始我確實是打算用map來存儲，key是當前元素，value是不喜歡的list集合。但是后來發(fā)現因為這個key是從1到N的，所以完全可以用數組下標代替。所以就變成了list數組。總而言之這個題是染色判斷狀態(tài)。遞歸看是否可以分成功。然后之間有一點我遞歸的時候沒有陣營會默認扔到數值為1的陣營中。這里其實扔到1還是-1是無所謂的，我只是單純的覺得1方便而已。
這個代碼性能還好，超過了百分之九十多，所以我就不看性能第一的代碼了，直接下一題。
停在原地的方案數
題目：有一個長度為 arrLen 的數組，開始有一個指針在索引 0 處。每一步操作中，你可以將指針向左或向右移動 1 步，或者停在原地（指針不能被移動到數組范圍外）。給你兩個整數 steps 和 arrLen ，請你計算并返回：在恰好執(zhí)行 steps 次操作以后，指針仍然指向索引 0 處的方案數。由于答案可能會很大，請返回方案數 模 10^9 + 7 后的結果。
示例 1：
輸入：steps = 3, arrLen = 2
輸出：4
解釋：3 步后，總共有 4 種不同的方法可以停在索引 0 處。
向右，向左，不動
不動，向右，向左
向右，不動，向左
不動，不動，不動
示例 2：
輸入：steps = 2, arrLen = 4
輸出：2
解釋：2 步后，總共有 2 種不同的方法可以停在索引 0 處。
向右，向左
不動，不動
示例 3：
輸入：steps = 4, arrLen = 2
輸出：8
提示：
1 <= steps <= 500
1 <= arrLen <= 10^6
思路：2021/5/13的每日一題。還是困難的。題目的標簽是動態(tài)規(guī)劃。說真的這種數據需要取模的題目百分之就是都是dp沒啥說的。dp最主要的是遞推公式。分析下這個題：因為不能超過arrLen這個限制。所以我們可以用逆推的辦法。在第steps-1步的時候處于0點，還有處于1點（因為可以向左一步移回去）的可能和。大概思路是這樣，具體的遞推公式我去慢慢想。
第一版本代碼超時了。但是我覺得超時大概率是代碼效率問題，而不是代碼不對。所以依然貼出來：
class Solution {
public int numWays(int steps, int arrLen) {
int mod = 1000000007;
//因為這個dp是要記錄上一步的全部狀態(tài)，才能計算當前的狀態(tài)。所以用兩個數組
//不能原地操作的原因：每次元素都要更新的。原地操作得記錄以前數據，太麻煩
int[] dp = new int[arrLen];//單數結果，步數1,3,5，7等等
int[] dp1 = new int[arrLen];//雙數結果，步數2,4,6,8等。
//初始都在0點，所以0本身不動就是一種可能。
dp1[0] = 1;
for(int i = 0;i<steps;i++) {
if(i%2==0) {//單數結果，所以用dp1推到dp。這里因為下標0本身代表第一步。
for(int j = 0;j<arrLen;j++) {
dp[j] = dp1[j];
if(j>0) dp[j] = (dp[j]+dp1[j-1])%mod;
if(j<arrLen-1) dp[j] = (dp[j]+dp1[j+1])%mod;
}
}else {
for(int j = 0;j<arrLen;j++) {
dp1[j] = dp[j];
if(j>0) dp1[j] = (dp1[j]+dp[j-1])%mod;
if(j<arrLen-1) dp1[j] = (dp1[j]+dp[j+1])%mod;
}
}
}
return steps%2==0?dp1[0]:dp[0];
}
}
這里之所以用兩個數組交換記錄狀態(tài)是因為arrLen的數據范圍10的六次方。我覺得二維數據應該空間不夠用。而且這個當前狀態(tài)只和上一步的狀態(tài)有關，所以用了兩個數據交替記錄狀態(tài)的方式來實現的。
感覺思路上沒啥錯。每一步的下一步分前，不動，后三種選擇。至于超時了優(yōu)化的點，我其實是有想法的：如果過了一半時間還一直往前蹦跶的，最終肯定是回不來了，還有就是如果一共有x步，那么往前蹦跶最多只能蹦跶到2/x。不然肯定回不來。我去試試把這個加入到限制中。
加了個限制，立刻從超時wa變成了性能超過百分百。。嘖嘖，附上ac代碼：
class Solution {
public int numWays(int steps, int arrLen) {
int mod = 1000000007;
//最長往前蹦的長度
int maxLong = Math.min(arrLen, steps/2+1);
//因為這個dp是要記錄上一步的全部狀態(tài)，才能計算當前的狀態(tài)。所以用兩個數組
//不能原地操作的原因：每次元素都要更新的。原地操作得記錄以前數據，太麻煩
int[] dp = new int[maxLong];//單數結果，步數1,3,5，7等等
int[] dp1 = new int[maxLong];//雙數結果，步數2,4,6,8等。
//初始都在0點，所以0本身不動就是一種可能。
dp1[0] = 1;
for(int i = 0;i<steps;i++) {
if(i%2==0) {//單數結果，所以用dp1推到dp。這里因為下標0本身代表第一步。
for(int j = 0;j<maxLong;j++) {
dp[j] = dp1[j];
if(j>0) dp[j] = (dp[j]+dp1[j-1])%mod;
if(j<maxLong-1) dp[j] = (dp[j]+dp1[j+1])%mod;
}
}else {
for(int j = 0;j<maxLong;j++) {
dp1[j] = dp[j];
if(j>0) dp1[j] = (dp1[j]+dp[j-1])%mod;
if(j<maxLong-1) dp1[j] = (dp1[j]+dp[j+1])%mod;
}
}
}
return steps%2==0?dp1[0]:dp[0];
}
}
注意上面兩個代碼唯一的區(qū)別就是一開始是遍歷到arrLen，后來是遍歷到Math.min(arrLen, steps/2+1)、
就像我說的不能超過arrLen就不說了，重點的一共10步。那么最多右蹦跶5步，再用五步回來。但凡蹦跶6步就回不來了，而且如果一共11步。也只能向右5步。畢竟回來的步數多還可以原地蹦跶兩下。但是去的步數多肯定不行。思路就這樣，我去看看性能第一的代碼：
class Solution
{
public int numWays(int steps, int arrLen)
{
int n=Math.min(steps/2+1, arrLen);
int m=steps;
int MOD=1_000_000_007;
int[] dp=new int[n+2];
int[] tmp=new int[n+2];
dp[1]=1;
for(int k=1; k<=m; k++)
{
for(int i=1; i<=n; i++)
{
if(i-1>k)
break;
tmp[i]=((dp[i]+dp[i-1])%MOD+dp[i+1])%MOD;
}
for(int i=1; i<=n; i++)
{
if(i-1>k)
break;
dp[i]=tmp[i];
tmp[i]=0;
}
}
return (int)(dp[1]%MOD);
}
}
這個代碼和我的思路大同小異。但是細節(jié)處理好多了。我還要每次判斷越界沒。但是人家是前后包了一層。所以不用每次都判斷，直接加就行了。其實這種題只要思路懂了，具體的寫法隨便看看就行了，哈哈。這個題過。
本篇筆記就記到這里，如果稍微幫到你了記得點個喜歡點個關注。也祝大家工作順順利利，生活健健康康~！路漫漫兮其修遠，吾將上下而求索。
