leetCode进阶算法题+解析（九）
现在每天混低保，一天三道题很稳。
旋转链表
题目：给定一个链表，旋转链表，将链表每个节点向右移动 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
思路：感觉这道题实现是很容易的，甚至超容易，我直接把链表存成数组，然后旋转弄能新数组，再然后一个个挂上。实现是能实现了，但是感觉太傻了吧。我不知道这个题是不是有啥隐含的要求，但是目前看来是没说不能用数组或者一次遍历啥的。我先去最笨的方式实现了再说。
就是用这种无脑的方式写出来了，然后两次ac了，甚至性能都如我所料，可怜的一批。但是毕竟无脑方便，我还是贴出来分享下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
LinkedList<Integer> list = new LinkedList<Integer>();
ListNode cur = head;
while(cur!=null){
list.add(cur.val);
cur = cur.next;
}
if(list.size()==0) return head;
k = k%list.size();
if(k==0) return head;
while(k>0){
list.addFirst(list.removeLast());
k--;
}
ListNode res = new ListNode(0);
ListNode temp = res;
for(int i = 0;i<list.size();i++){
temp.next = new ListNode(list.get(i));
temp = temp.next;
}
return res.next;
}
}
性能超过百分之九点八
说正经的这道题，我其实做过类似的，我记得好像是双指针，一个先走k个节点，然后两个指针同时往后走啥的，我先理理思路。
我直接贴代码：
public ListNode rotateRight(ListNode head, int k) {
if (head == null) {
return null;
}
int length = 0;
ListNode cur = head;
ListNode tail = null;
while (cur != null) {
length++;
if (cur.next == null) {
tail = cur;
}
cur = cur.next;
}
tail.next = head;
int n = k % length;
for (int i = 0; i < length - n; i++) {
tail = tail.next;
}
cur = tail.next;
tail.next = null;
return cur;
}
细品吧，感觉思路绕点，但是理解了代码不难。其实这个就是首尾相连，然后找断点。就酱吧，下一题。
不同路径
题目:一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
题目截图
说明：m 和 n 的值均不超过 100。
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
思路：审题完第一反应，这个绝对是dp。典型的动规题。至于要怎么写，还是要好好理理思路的，我去实现啦。
做完回来了，咱们继续说思路。如果对动规不太理解的建议去看看我有一篇专门讲动态规划的笔记。动态规划 ——用数组记录中间过程的递归
其实看名字就能明白，所谓动规，就是用数组记录中间过程。
这个题我反正做的时候是用二维数组来理解的。我直接上图吧（一如既往的渣，但是我用心了啊）其中注意点：
- 当只有一排和一列的情况下，肯定答案是1.因为只有一种走法。
- n = 2 ，m=3 和n = 3，m=2是一个性质，次数是相同的。所以其实这个二维数组还勉强可以用中间对称来看。
- 咱们从左上角开始算，左边的块再走一步到右边这块，上面的块再走一步到下边这块。也就是当一个块不是挨着边的，那么不同路径数就是左边的路径数加上上边的路径数。
图解
（如图表示，我没画完，反正大概就是这个意思。）然后只要看懂这个图就能直接写出代码了，反正我是一个个填进来的。我直接贴代码：
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 1;
else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
然后这道题就这么过了，下一题我看了是不同路径2.不知道是怎么在这个基础上的变种。
不同路径2
题目：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
题目截图
示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: 2
解释:
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
- 向右 -> 向右 -> 向下 -> 向下
- 向下 -> 向下 -> 向右 -> 向右
思路:其实这个题数组还是那个数组，只不过区别就是当遇到1，也就是障碍物时。这条路就不通了。比如这个1在目标的上面，那么到目标的路径数就不是上+左。而只有左。同理在左边，就是只有上。当然如果障碍物在目标 的右下方就一点影响没有，反正二维数组还是这个数组。只不过在填充这个数组的时候做点处理而已。我去实现了。
好了，实现是实现了，本以为是手到擒来，但是还是不断在测试案例的教训下不断修改。我直接贴代码：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//因为可能有次数是1的，我想在这个二维数组基础上操作，所以把1换成-1
for(int i = 0;i<obstacleGrid.length;i++){
for(int j=0;j<obstacleGrid[0].length;j++){
if(obstacleGrid[i][j]==1) obstacleGrid[i][j] = -1;
}
}
for(int i = 0;i<obstacleGrid.length;i++){
for(int j=0;j<obstacleGrid[0].length;j++){
if(i == 0 || j == 0){
if(i == j){
if(obstacleGrid[i][j] == -1){
return 0;
}else{
obstacleGrid[i][j] = 1;
}
}else if(obstacleGrid[i][j] == -1){
continue;
}else if(i == 0 && obstacleGrid[i][j-1] == -1){
obstacleGrid[i][j] = -1;
}else if(j == 0 && obstacleGrid[i-1][j] == -1){
obstacleGrid[i][j] = -1;
}else{
obstacleGrid[i][j] = 1;
}
}else if(obstacleGrid[i][j] != -1){
int sum = 0;
if(obstacleGrid[i][j-1] != -1) sum += obstacleGrid[i][j-1];
if(obstacleGrid[i-1][j] != -1) sum += obstacleGrid[i-1][j];
obstacleGrid[i][j] = sum;
}
}
}
int res = obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
return res==-1?0:res;
}
}
首先这个边边的1 是不能直接写了，因为如果有障碍物以后的就不能写了。其次如果终点是障碍物则直接0.反正不难,就是测试案例真的考虑情况很多,一点点微调才做完的.....
好了,稍微改良版出来了:
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int len = obstacleGrid.length;
if(len==0) return 0;
int row = obstacleGrid[0].length;
if(row ==0) return 0;
//入口出口有障碍物直接0
if(obstacleGrid[0][0]==1 || obstacleGrid[len-1][row-1]==1) return 0;
//因为可能有次数是1的，我想在这个二维数组基础上操作，所以把1换成-1
for(int i = 0;i<len;i++){
for(int j=0;j<row;j++){
if(obstacleGrid[i][j]==1) obstacleGrid[i][j] = -1;
}
}
for(int i = 0;i<len;i++){
for(int j=0;j<row;j++){
if(i == 0 || j == 0){
if(i == j){
obstacleGrid[i][j] = 1;
}else if(obstacleGrid[i][j] == -1){
continue;
}else if(i == 0){
obstacleGrid[i][j] = obstacleGrid[i][j-1];
}else if(j == 0){
obstacleGrid[i][j] = obstacleGrid[i-1][j];
}
}else if(obstacleGrid[i][j] != -1){
int sum = 0;
if(obstacleGrid[i][j-1] != -1) sum += obstacleGrid[i][j-1];
if(obstacleGrid[i-1][j] != -1) sum += obstacleGrid[i-1][j];
obstacleGrid[i][j] = sum;
}
}
}
return obstacleGrid[len-1][row-1];
}
}
反正这道题就这样了,然后就是多种情况考虑吧.这道题过.
最小路径和
题目:给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
思路:这几个动态规划的题又凑到一块了.反正就是典型动规.然后知道一个点的上面最小路径和左边最小路径.然后取最小的加上当前值就行了.感觉这个题不需要画图了,和上面的差不多,我直接撸代码吧.
好了,这道题并没有什么坑,一次过了,我直接贴代码:
class Solution {
public int minPathSum(int[][] grid) {
int len = grid.length;
if(len == 0) return 0;
int row = grid[0].length;
if(row == 0) return 0;
for(int i = 0;i<len;i++){
for(int j = 0;j<row;j++){
if(i == 0 || j == 0){
int sum = 0;
if(i != 0) sum += grid[i-1][j];
if(j != 0) sum += grid[i][j-1];
grid[i][j] = grid[i][j] + sum;
}else{
grid[i][j] = grid[i][j] + Math.min(grid[i][j-1],grid[i-1][j]);
}
}
}
return grid[len-1][row-1];
}
}
今天的笔记也就到这里吧,如果稍微帮到你了记得点个喜欢点个关注,也祝大家新年快乐!
