主要记录一些LeetCode上没有的题以及解法。

圆环回原点问题

题目描述：
圆环上有9个点，编号为0~8。从0点出发，每次可以逆时针和顺时针走一步，问走n步回到0点共有多少种走法？

解法：

  1. package main
  3. import "fmt"
  5. type Node struct {
  6.     Next *Node
  7.     Prev *Node
  8.     Val  int
  9. }
  11. func main() {
  12.     root := makeListCircle(9)
  13.     n := 8
  14.     fmt.Println(returnBack1(root, n))
  15.     fmt.Println(returnBack2(root, n))
  16. }
  18. // 构造特定长度的圆环双链表
  19. func makeListCircle(length int) *Node {
  20.     root := &Node{nil, nil, 0}
  21.     t := root
  22.     for i := 1; i < length; i++ {
  23.         t.Next = &Node{nil, t, i}
  24.         t = t.Next
  25.     }
  26.     t.Next, root.Prev = root, t
  27.     return root
  28. }
  30. // 解法一：哈希
  31. func returnBack1(root *Node, n int) (ans int) {
  32.     m := map[int][]*Node{0: {root}} // m[n]: 走 n 步可以到达的节点集合
  34.     // 每轮通过走 i-1 步可以到达的点的集合，统计出走 i 步可到达的点的结合
  35.     for i := 1; i <= n; i++ {
  36.         nodeList := m[i-1] // 走 i-1 步可以到达的点的集合
  37.         for _, v := range nodeList {
  38.             m[i] = append(m[i], v.Next, v.Prev) // i-1 加一步为 i 步到达的集合
  39.         }
  40.     }
  42.     for _, v := range m[n] {
  43.         if v == root {
  44.             ans++
  45.         }
  46.     }
  47.     return
  48. }
  50. // 解法二：动态规划
  51. func returnBack2(root *Node, n int) int {
  52.     length := 9
  53.     dp := make([][]int, n+1) // dp[i][j]: 走i步到达序号为j的点的次数
  54.     for i := range dp {
  55.         dp[i] = make([]int, length)
  56.     }
  57.     dp[0][0] = 1
  59.     for i := 1; i <= n; i++ {
  60.         for j := 0; j < 9; j++ {
  61.             dp[i][j] = dp[i-1][(j-1+length)%length] + dp[i-1][(j+1)%length]
  62.         }
  63.     }
  64.     return dp[n][0]
  65. }

阿拉伯数字转中文数字

题目描述：输入一个 int 类型数字，输出 string 类型的中文数字。
如图：
image.png
解法：

  1. func num2cn(n int) (ans string) {
  2.     str := strconv.Itoa(int(math.Abs(float64(n))))
  3.     dict := []string{
  4.         "零", "一", "二", "三", "四", 
  5.         "五", "六", "七", "八", "九", 
  6.         "十", "百", "千", "万", "亿"
  7.     }
  8.     if n == 0 {
  9.         return dict[0]
  10.     }
  11.     t := 0 // 第几个四位
  12.     for i := len(str) - 1; i >= 0; {
  13.         // 每次处理四位数
  14.         curStr := ""
  15.         cnt := 0
  16.         for cnt < 4 && i >= 0 {
  17.             num := int(str[i] - '0')
  18.             // 处理当前数为 0 的情况
  19.             if num == 0 {
  20.                 for cnt < 4 && i > 0 && num == 0 { // 去除当前四位的重复 0
  21.                     i--
  22.                     num = int(str[i] - '0')
  23.                     cnt++
  24.                 }
  25.                 if curStr != "" {
  26.                     curStr = dict[0] + curStr
  27.                 }
  28.             } else {
  29.                 if cnt > 0 {
  30.                     curStr = dict[9+cnt] + curStr
  31.                 }
  32.                 // 避免“11”被翻译为“一十一”
  33.                 if !(num == 1 && i == 0 && cnt == 1) { 
  34.                     curStr = dict[num] + curStr
  35.                 }
  36.                 cnt++
  37.                 i--
  38.             }
  39.         }
  40.         if t > 0 && curStr != "" { // 如果不是第一个四位或者四位都为0，加上一个单位
  41.             curStr += dict[12+t]
  42.         }
  43.         ans = curStr + ans
  44.         t++
  45.     }
  46.     if n < 0 {
  47.         ans = "负" + ans
  48.     }
  49.     return
  50. }