救生艇
题目：第 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...这个题果然还是得老老实实双指针。而且随着做我发现了一个问题，其实贪心不贪心也不是那么重要。如果从后遍历的话：
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个人，所以很多都可以简单化，上面代码性能超过百分之九十七的人。我再去看看性能第一的代码：
好吧，性能第一的代码思路差不多，但是没有用系统的排序，而是用数组下标代替值，值代表个数。用了空间换时间，挺麻烦但是性能挺好的代码：
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) 面朝东面开始.这里，网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。现在，我们以顺时针按螺旋状行走，访问此网格中的每个位置。
每当我们移动到网格的边界之外时，我们会继续在网格之外行走（但稍后可能会返回到网格边界）。最终，我们到过网格的所有 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.当然了这里我觉得细节上可以再处理下，比如设置为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;
}
}
思路和我之前说的差不多。然后果然实现起来贼麻烦。简单来说把这个给定的数组用一个大范围包含住。保证所有的螺旋都有点可落。然后当所有的点都穿过了以后直接返回。这个代码性能不太好。我是觉得可能是我代码书写的问题。或者说思路有问题？我去试试不用这个布尔数组了。只看横纵坐标是不是在范围内，是的话放入结果集。去试试代码。
第二版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;
}
}
又是自己想不到，一看人家的代码恍然大悟秒懂的感觉。。同样也不用额外空间，单纯的一圈一圈去获取。然后判断的可能比我简单一些。同样的用一个变量统计当前多少个格子已经放入结果集了，什么时候所有的格子放入结果集返回。要说哪里是写不出来的也没有，就是没这么想。挺精巧的代码。这个题就这样吧。下一题了。
解码异或后的排序
题目：给你一个整数数组 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的每日一题。然后我之前做过一道和这个差不多的简单题目，唯一区别就是那道题给了第一个元素，然后整个题就很无脑的解决了。为什么我要特意提一下这个呢？因为我觉得这个题目，主要也是获取第一个数的值。当然了其实获取最后一个数的值也行。但是如何获取呢？还是应该从异或出发。虽然二进制位运算是我的知识盲区，但是我记得之前做过一个找出数组唯一出现过一次的元素，其中方法就是数组所有元素异或。相同元素异或会等于0 。别的元素都是成对出现变成0，所以唯一的出现一次的元素会成为异或的结果。而这个题首先是前n个数我们是知道的，所以能获取前n个数的异或结果。其次给出的解码结果是这样的：
a1 ^ a2.a2 ^ a3,a3 ^ a4,a4 ^ a5,a5 ^ a6.a6 ^ a7我就不往后写了，但是大家其实可以看到规律了：如果我们想获取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;
}
}
除了最后一句没有任何区别，性能天差地别。。。因为这个题我觉得思路比较清晰，所以就不多说了，下一题。
子数组异或查询
题目：有一个正整数数组 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到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循环的时候循环体中一句话不用大括号，各种压缩。看上去代码简洁好看，实际上可读性贼差。我就是这么有自知之明还明知故犯。
总而言之思路没问题，就是性能不太好。但是我觉得性能不好的原因应该在细节处理上，毕竟思路都已经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
思路：这个题咋说呢，好像是做过类似的，题目标签的深度优先。总而言之我现在的想法就是染色。第一个dislikes中两个元素分别红绿色（1，-1）。然后后面的我打算用map，把和key不和的放入结果集中。然后依次类推下去。接下来就正常判断就行了，注意下这里红绿色是我个人理解，其实就是分状态。比如讨厌的人两个阵营，那么一组讨厌中一定一个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集合。但是后来发现因为这个key是从1到N的，所以完全可以用数组下标代替。所以就变成了list数组。总而言之这个题是染色判断状态。递归看是否可以分成功。然后之间有一点我递归的时候没有阵营会默认扔到数值为1的阵营中。这里其实扔到1还是-1是无所谓的，我只是单纯的觉得1方便而已。
这个代码性能还好，超过了百分之九十多，所以我就不看性能第一的代码了，直接下一题。
停在原地的方案数
题目：有一个长度为 arrLen 的数组，开始有一个指针在索引 0 处。每一步操作中，你可以将指针向左或向右移动 1 步，或者停在原地（指针不能被移动到数组范围外）。给你两个整数 steps 和 arrLen ，请你计算并返回：在恰好执行 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的每日一题。还是困难的。题目的标签是动态规划。说真的这种数据需要取模的题目百分之就是都是dp没啥说的。dp最主要的是递推公式。分析下这个题：因为不能超过arrLen这个限制。所以我们可以用逆推的办法。在第steps-1步的时候处于0点，还有处于1点（因为可以向左一步移回去）的可能和。大概思路是这样，具体的递推公式我去慢慢想。
第一版本代码超时了。但是我觉得超时大概率是代码效率问题，而不是代码不对。所以依然贴出来：
class Solution {
public int numWays(int steps, int arrLen) {
int mod = 1000000007;
//因为这个dp是要记录上一步的全部状态，才能计算当前的状态。所以用两个数组
//不能原地操作的原因：每次元素都要更新的。原地操作得记录以前数据，太麻烦
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];
}
}
这里之所以用两个数组交换记录状态是因为arrLen的数据范围10的六次方。我觉得二维数据应该空间不够用。而且这个当前状态只和上一步的状态有关，所以用了两个数据交替记录状态的方式来实现的。
感觉思路上没啥错。每一步的下一步分前，不动，后三种选择。至于超时了优化的点，我其实是有想法的：如果过了一半时间还一直往前蹦跶的，最终肯定是回不来了，还有就是如果一共有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是要记录上一步的全部状态，才能计算当前的状态。所以用两个数组
//不能原地操作的原因：每次元素都要更新的。原地操作得记录以前数据，太麻烦
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];
}
}
注意上面两个代码唯一的区别就是一开始是遍历到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);
}
}
这个代码和我的思路大同小异。但是细节处理好多了。我还要每次判断越界没。但是人家是前后包了一层。所以不用每次都判断，直接加就行了。其实这种题只要思路懂了，具体的写法随便看看就行了，哈哈。这个题过。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利，生活健健康康~！路漫漫兮其修远，吾将上下而求索。
