正文

幕布

幕布链接

91. 解码方法

解法

官方解法​

动态规划

object Solution {
  def numDecodings(s: String): Int = {
    //开头不能为 0
    if (s(0) == '0') return 0
    val n = s.length
    //dp 表示前 i+1 项对应的解码总数，这里长度取 n+1 是为了方便处理临界场景
    val dp = new Array[Int](n + 1)
    //初始赋值
    dp(0) = 1
    dp(1) = 1
    for (i <- 2 to n) {
      //遍历的当前项对应的数字，s 的索引为 dp 的索引 - 1
      val cur = s(i - 1) - '0'
      //遍历的前一项对应的数字
      val pre = s(i - 2) - '0'
      //不存在下面2种情况：1.连续两项都为 0  2.30
      if (cur + pre == 0 || (cur == 0 && pre > 2)) return 0
      //如果当前项为 0，则必须依赖前一项的数字，解码总数等于 dp(i-2)，如果当前项不为 0，前一项为 0，则等于 dp(i-1)
      else if (cur == 0 || pre == 0) dp(i) = if (cur == 0) dp(i - 2) else dp(i - 1)
      //考虑前一项和当前项组成的数字是否大于 26
      else dp(i) = if (pre * 10 + cur > 26) dp(i - 1) else dp(i - 2) + dp(i - 1)
    }
    dp(n)
  }
}

92. 反转链表 II

解法

Simple Java solution with clear explanation​

双指针+哨兵

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null) return null;
        ListNode dummy = new ListNode(0), pre = dummy;
        dummy.next = head;
        for(int i = 0; i < m - 1 ; i++) pre = pre.next;
        
        ListNode start = pre.next;
        ListNode then = start.next;
        
        // 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
        // dummy-> 1 -> 2 -> 3 -> 4 -> 5
        
        for(int i = m; i < n; i++)
        {
            start.next = then.next;
            then.next = pre.next;
            pre.next = then;
            then = start.next;
        }
        
        // first reversing : dummy->1 - 3 - 2 - 4 - 5; pre = 1, start = 2, then = 4
        // second reversing: dummy->1 - 4 - 3 - 2 - 5; pre = 1, start = 2, then = 5 (finish)
        
        return dummy.next;
        
    }
}