contestDouble-59

1.使用特殊打字机键入单词的最少时间(贪心)

顺时针移动代价，逆时针移动代价，选一个最小的

func minTimeToType(word string) int {
   cur := byte('a')
   res := 0
   for i := 0 ; i < len(word) ; i++ {
      if word[i] == byte(cur) {
         res++
      } else {
         p := int(math.Abs(float64(int(cur - 'a') - int(word[i] - 'a'))))
         q := 26 - p
         if p > q {
            res += q + 1
         } else {
            res += p + 1
         }
         cur = word[i]
      }
   }
   return res
}
复制代码

2.最大方阵和(脑筋急转弯)

一开始各种贪心，dp搞了半天发现不对，最后发现，偶数个负数最终可以全部变为正数，奇数个负数，最后会剩下一个负数，选一个最小的就行啦。

func maxMatrixSum(matrix [][]int) int64 {
   sum := 0
   count := 0
   minVal := math.MaxInt32
   for i := 0 ; i < len(matrix) ; i++ {
      for j := 0 ; j < len(matrix[i]) ; j++ {
         if matrix[i][j] < 0 {
            count++
            sum += -matrix[i][j]
         } else {
            sum += matrix[i][j]
         }
         if int(math.Abs(float64(matrix[i][j]))) < minVal {
            minVal = int(math.Abs(float64(matrix[i][j])))
         }
      }
   }
   if count % 2 == 0 {
      return int64(sum)
   } else {
      return int64(sum - 2 * minVal)
   }
}
复制代码

3.到达目的地的方案数(最短路径+记忆化搜索)

首先需要确定起点到终点的最短路径，然后需要确定哪些路径是在最短路径上的，比如a-b之间有一条路径权值为c，如果知道起点到a的最短路径和到b的最短路径，那如果c = dist[a] – dist[b]那a-b之间的这条路径一定在最短路径上，所以需要求出起点到所有顶点的最短路径，这里用佛洛依德和迪杰斯特拉都行。然后，dfs搜索，mem[i]表示i结点到终点有多少条路径，然后正常dfs就可以了，详情见代码，思路不难，只是代码略微有点长。

func countPaths(n int, roads [][]int) int {
   if n == 1 && len(roads) == 0 {
      return 1
   }
   const mod int = 1e9 + 7
   dist := make([][]int, n)
   for i := 0 ; i < len(dist) ; i++ {
      dist[i] = make([]int, n)
   }
   for i := 0 ; i < len(dist) ; i++ {
      for j := 0 ; j < len(dist[i]) ; j++ {
         dist[i][j] = math.MaxInt64 / 2
      }
   }
   for i := 0 ; i < n ; i++ {
      dist[i][i] = 0
   }
   for i := 0 ; i < len(roads) ; i++ {
      dist[roads[i][0]][roads[i][1]] = roads[i][2]
      dist[roads[i][1]][roads[i][0]] = roads[i][2]
   }
   for k := 0; k < n; k++ {
      for i := 0; i < n; i++ {
         for j := 0; j < n; j++ {
            if dist[i][j] > dist[i][k]+dist[k][j] {
               dist[i][j] = dist[i][k] + dist[k][j]
            }
         }
      }
   }
   adj := make([][]int, n)
   for i := 0 ; i < len(adj) ; i++ {
      adj[i] = make([]int, 0)
   }
   for i := 0 ; i < len(roads) ; i++ {
      a := roads[i][0]
      b := roads[i][1]
      if dist[0][a] - dist[0][b] == roads[i][2] {
         adj[b] = append(adj[b], a)
      }
      if dist[0][b] - dist[0][a] == roads[i][2] {
         adj[a] = append(adj[a], b)
      }
   }
   mem := make([]int, n)
   for i := 0 ; i < len(mem) ; i++ {
      mem[i] = -1
   }
   var f func(k int) int
   f = func(k int) int {
      if k == n - 1 {
         return 1
      }
      if mem[k] != -1 {
         return mem[k]
      }
      mem[k] = 0
      for i := 0 ; i < len(adj[k]) ; i++ {
         mem[k] = (mem[k] + f(adj[k][i])) % mod
      }
      return mem[k]
   }
   return f(0)
}
复制代码

4.划分数字的方案数 (dp)

这题好难，看老大的题解都看了半天才搞明白。。。首先大佬这个dp的定义，我就想不到。。

dp[i][j]定义为前j个字符划分数字中最后一个数字的起始位置为i，那么所求的答案就是对dp[k][n – 1]{0<=k<=n-1}求和。那每一个dp[i][j]怎么求呢？这里需要考虑最后一个整数和倒数第二个整数，假设倒数第二个整数的起始位置为k终止位置为i-1，那dp[i][j]=把dp[k][i-1]累加，这里需要注意，题目要求的最终是递增的，所以倒数第二个数必须长度如果比最后一个长，则不符合条件，不累加，如果小于则累加，如果等于则需要比较两个数谁大，这里如果采用遍历的方式，会超时。大佬们的做法首先预处理出所有num[i:]和num[j:]的最长公共前缀，这样在状态转移的时候可以o(1)时间内得出大小关系。除此之外，在状态的转移的过程中，如果每个状态是采用遍历的方式去累加，那也会超时，这里需要采用前缀和或者是从中心向两边扩展的方法。(这题不仅思路很难，各种优化，预处理的细节也是非常的复杂，大佬代码搬运工就是在下了)

func numberOfCombinations(num string) int {
   const mod int = 1e9 + 7
   if num[0] == '0' {
      return 0
   }
   n := len(num)
   // 计算最长公共前缀
   lcp := make([][]int, n + 1)
   for i := 0 ; i < len(lcp) ; i++ {
      lcp[i] = make([]int, n + 1)
   }
   // 以i j结尾的最长公共前缀的长度 
   // 如果num[i] != num[j]则lcp[i][j] = 0
   for i := n - 1 ; i >= 0 ; i-- {
      for j := n - 1 ; j >= 0 ; j-- {
         if num[i] == num[j] {
            lcp[i][j] = lcp[i + 1][j + 1] + 1
         }
      }
   }

   // 前j个字符在最后一个整数的起始位置在i位置时的方案数目
   f := make([][]int, n)
   for i := 0 ; i < len(f) ; i++ {
      f[i] = make([]int, n)
   }

   // 前j个字符最后一个整数的起始位置在0位置时 方案数目为1
   for j := 0 ; j < n ; j++ {
      f[0][j] = 1
   }
   // 返回 s[l1:l2] <= s[l2:r2]
   lessEq := func(l1, l2, r2 int) bool {
      l := lcp[l1][l2]
      return l >= r2-l2 || num[l1 + l] < num[l2 + l]
   }

   for i := 1 ; i < n ; i++ {
      if num[i] == '0' {
         continue
      }
      // 这个地方大佬处理得很巧妙 因为每次j往后走时 k还在前一次的位置
      // 所以上一轮计算的累加和可以直接填到最新的里面
      // 以i为中心 k j向两边扩展这样做充分利用了上一次计算的结果
      // 避免了每次计算一个新状态时需要全部重新计算
      for j, k, sum := i, i - 1, 0 ; j < n ; j++ {
         f[i][j] = sum
         if k < 0 {
            continue
         }
         if num[k] > '0' && lessEq(k, i, j + 1) {
            f[i][j] = (f[i][j] + f[k][i - 1]) % mod
         }
         sum = (sum + f[k][i - 1]) % mod
         k--
      }
   }
   ans := 0
   for i := 0 ; i < len(f) ; i++ {
      ans = (ans + f[i][n - 1]) % mod
   }
   return ans
}
复制代码