旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
示例 2:
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL
分析
本题的话就是题意比较清晰，就是旋转链表将链表进行右移动k个。
但是具体的处理上可能存在时间复杂度的差距，比如你可以第一次遍历到结尾，然后构成一个循环链表不停遍历找到合适的位置。或者先遍历一次到尾，然后再找到需要移动的位置去进行操作，但是这样都避免不了循环两次。
那本题采用什么方法呢？使用快慢指针，快指针先走k步，然后快慢指针一起走，一直到快指针走到尾。 执行以下操作即可：
- fast.next=head
- ListNode team=slow
- slow.next=null
- return team
但是过程可能没那么顺畅，很可能k比整个链表的长度还大，所以可能k没跑完就遍历结束了，这种情况也不用担心，当fast到底的时候可以通过一次计算算出真实有效的移动位数。比如如果链表长10让你右移59，69，79这些和移动9次是一样的，所以只需要slow再次移动到真实有效的地方即可。
实现的代码为：
public ListNode rotateRight(ListNode head, int k) { if(k==0||head==null)return head; ListNode fast=head; ListNode slow=head; for(int i=0;i<k;i++) { if(fast.next==null)//说明超出范围了 但是此时知道最大长度了 { k=(k)%(i+1); if(k==0)return head; for(int j=0;j<i-k;j++) { slow=slow.next; } break; } fast=fast.next; } while (fast.next !=null) { fast=fast.next; slow=slow.next; } fast.next=head; ListNode team=slow.next; slow.next=null; return team; }
62不同路径
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1 . 向右 -> 向右 -> 向下
2 . 向右 -> 向下 -> 向右
3 . 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
分析：
可用搜素，但是更是入门级别的动态规划。其状态方程为： 在dp[i][j]=dp[i-1][j]+dp[i][j-1];当然有特殊情况是需要考虑的，就是最上一行和最左一列以及起始位置。因为会出现越界的情况。
- 你可以特殊判断，先处理边界然后再进行计算。
- 但是你也可以像我一样，设置的二维数组扩大一点，把边界也当成一个普通情况处理，只不过将
dp[0][1]或者dp[1][0]其中设为一个能够正确计算dp[1][1]=1即可(妙啊)。
实现代码为：
public int uniquePaths(int m, int n) { int dp[][]=new int[m+1][n+1]; dp[0][1]=1; for(int i=1;i<m+1;i++) { for(int j=1;j<n+1;j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } return dp[m][n]; }
不同路径Ⅱ
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1： 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释： 3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右 示例 2： 输入：obstacleGrid = [[0,1],[0,0]] 输出：1 提示： m == obstacleGrid.length n == obstacleGrid[i].length 1 <= m, n <= 100 obstacleGrid[i][j] 为 0 或 1
这题你可以使用搜索，其实跟搜索关系越来越大了，但依然可以使用dp，就是在遍历的时候遇到障碍物的位置跳过计算即可 。该位置始终为0即可。
实现代码为：
public int uniquePathsWithObstacles(int[][] obstacleGrid) { int m=obstacleGrid.length; int n=obstacleGrid[0].length; int dp[][]=new int[m+1][n+1]; dp[0][1]=1; for(int i=1;i<m+1;i++) { for(int j=1;j<n+1;j++) { if(obstacleGrid[i-1][j-1]!=1) dp[i][j]=dp[i-1][j]+dp[i][j-1]; } } //System.out.println(Arrays.deepToString(dp)); return dp[m][n]; }
最后
本次打卡结束了，明日继续更新，恳请csdn的朋友们帮个忙🙏，微信搜索「bigsai」关注我的原创公众号，新人初期希望大家能够支持一下，白嫖电子书，回复「进群」加入力扣打卡群，欢迎来撩谢谢！
