Golang每日一练(leetDay0021) 旋转链表、不同路径、不同路径II-阿里云开发者社区

Golang每日一练(leetDay0021) 旋转链表、不同路径、不同路径II

2024-01-30 56

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Golang每日一练(leetDay0021) 旋转链表、不同路径、不同路径II

61. 旋转链表 Rotate List

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：

输入：head = [1,2,3,4,5], k = 2

输出：[4,5,1,2,3]

示例 2：

输入：head = [0,1,2], k = 4

输出：[2,0,1]

提示：

链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 10^9

代码：

package main
import (
  "fmt"
)
type ListNode struct {
  Val  int
  Next *ListNode
}
func rotateRight(head *ListNode, k int) *ListNode {
  if head == nil || head.Next == nil || k == 0 {
    return head
  }
  n := 1
  cur := head
  for cur.Next != nil {
    cur = cur.Next
    n++
  }
  cur.Next = head
  k = n - k%n
  for i := 0; i < k; i++ {
    cur = cur.Next
  }
  head = cur.Next
  cur.Next = nil
  return head
}
func build(nums []int) *ListNode {
  if len(nums) == 0 {
    return nil
  }
  head := &ListNode{Val: nums[0]}
  p := head
  for i := 1; i < len(nums); i++ {
    node := &ListNode{Val: nums[i]}
    p.Next = node
    p = p.Next
  }
  return head
}
func (head *ListNode) travel() {
  for p := head; p != nil; p = p.Next {
    fmt.Print(p.Val)
    if p.Next != nil {
      fmt.Print("->")
    }
  }
  fmt.Println("<nil>")
}
func main() {
  nums := []int{1, 2, 3, 4, 5}
  head := build(nums)
  head.travel()
  rotateRight(head, 2).travel()
}

输出：

1->2->3->4->5<nil>

4->5->1->2->3<nil>

62. 不同路径 Unique Paths

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7

输出：28

示例 2：

输入：m = 3, n = 2

输出：3

解释：

从左上角开始，总共有 3 条路径可以到达右下角。

1. 向右 -> 向下 -> 向下

2. 向下 -> 向下 -> 向右

3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3

输出：28

示例 4：

输入：m = 3, n = 3

输出：6

提示：

1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

代码：

package main
import (
  "fmt"
)
func uniquePaths(m int, n int) int {
  dp := make([][]int, m)
  for i := range dp {
    dp[i] = make([]int, n)
    dp[i][0] = 1
  }
  for j := 0; j < n; j++ {
    dp[0][j] = 1
  }
  for i := 1; i < m; i++ {
    for j := 1; j < n; j++ {
      dp[i][j] = dp[i-1][j] + dp[i][j-1]
    }
  }
  return dp[m-1][n-1]
}
func main() {
  fmt.Println(uniquePaths(3, 7))
  fmt.Println(uniquePaths(3, 2))
}

输出：

63. 不同路径 II Unique Paths

一个机器人位于一个 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

代码：

package main
import (
  "fmt"
)
func uniquePathsWithObstacles(obstacleGrid [][]int) int {
  m, n := len(obstacleGrid), len(obstacleGrid[0])
  if obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1 {
    return 0
  }
  dp := make([][]int, m)
  for i := range dp {
    dp[i] = make([]int, n)
  }
  dp[0][0] = 1
  for i := 1; i < m; i++ {
    if obstacleGrid[i][0] == 0 {
      dp[i][0] = dp[i-1][0]
    }
  }
  for j := 1; j < n; j++ {
    if obstacleGrid[0][j] == 0 {
      dp[0][j] = dp[0][j-1]
    }
  }
  for i := 1; i < m; i++ {
    for j := 1; j < n; j++ {
      if obstacleGrid[i][j] == 0 {
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
      }
    }
  }
  return dp[m-1][n-1]
}
func main() {
  obstacleGrid := [][]int{{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}
  fmt.Println(uniquePathsWithObstacles(obstacleGrid))
}