LeetCode 61~65

本文隶属于专栏《LeetCode 刷题汇总》，该专栏为笔者原创，引用请注明来源，不足和错误之处请在评论区帮忙指出，谢谢！

本专栏目录结构请见LeetCode 刷题汇总

幕布链接

My clean C++ code, quite standard (find tail and reconnect the list)​

object Solution {
  def rotateRight(head: ListNode, k: Int): ListNode = {
    if (head == null || head.next == null) return head
    val dummy = new ListNode(0)
    dummy.next = head
    var fast, slow = dummy
    var n = 0
    while (fast.next != null) {
      fast = fast.next
      n += 1
    }
    for (_ <- 0 until n - k % n) slow = slow.next
    fast.next = dummy.next
    dummy.next = slow.next
    slow.next = null
    dummy.next
  }
}

官方题解​

class Solution {
    public int uniquePaths(int cols, int rows) {
        int[] cur = new int[cols];
        for(int i = 1; i < rows; i++)
            for(int j = 1; j < cols; j++)
                cur[j] += cur[j-1] + 1;
        return cur[cols-1] + 1;
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}

官方题解​

object Solution {
  def uniquePathsWithObstacles(obstacleGrid: Array[Array[Int]]): Int = {
    if (obstacleGrid(0)(0) == 1) return 0
    val m = obstacleGrid.length
    val n = obstacleGrid(0).length
    val dp = Array.ofDim[Int](m, n)
    dp(0)(0) = 1
    for (x <- 0 until m; y <- 0 until n if obstacleGrid(x)(y) == 0) {
      if (x > 0) dp(x)(y) += dp(x - 1)(y)
      if (y > 0) dp(x)(y) += dp(x)(y - 1)
    }
    dp.last.last
  }
}

最小路径和 （动态规划，规范流程，清晰图解）​

class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        dp[0] = grid[0][0];
        for(int j = 1; j < n; j++){
            dp[j] = dp[j - 1] + grid[0][j];
        }
        for(int i = 1; i < m; i++){
            for(int j = 0; j < n; j++){
                if(j == 0){
                    dp[0] += grid[i][0];
                }else{
                    dp[j] = grid[i][j] + Math.min(dp[j], dp[j - 1]);
                }
            }
        }
        return dp[n - 1];
    }
}

AC Java solution with clear explanation​

public class Solution {
	public boolean isNumber(String s) {
		if (s == null) return false;
		s = s.trim().toLowerCase();
		int n = s.length();
		if (n == 0) return false;
		// flags
		int signCount = 0;
		boolean hasE = false, hasNum = false, hasPoint = false;
		for (int i = 0; i < n; i++) {
			char c = s.charAt(i);
			// invalid character
			if (!isValid(c)) return false;
			// digit is always fine
			if (c >= '0' && c <= '9') hasNum = true;
			// e or E
			if (c == 'e') {
				// e cannot appear twice and digits must be in front of it
				if (hasE || !hasNum) return false;
				// e cannot be the last one
				if (i == n - 1) return false;
				hasE = true;
			}
			// decimal place
			if (c == '.') {
				// . cannot appear twice and it cannot appear after e
				if (hasPoint || hasE) return false;
				// if . is the last one, digits must be in front of it, e.g. "7."
				if (i == n - 1 && !hasNum) return false;
				hasPoint = true;
			}
			// signs
			if (c == '+' || c == '-') {
				// no more than 2 signs
				if (signCount == 2) return false;
				// sign cannot be the last one
				if (i == n - 1) return false;
				// sign can appear in the middle only when e appears in front
				if (i > 0 && s.charAt(i - 1) != 'e') return false;
				signCount++;
			}
		}
		return true;
	}

	boolean isValid(char c) {
		return c == '.' || c == '+' || c == '-' || c == 'e' || c >= '0' && c <= '9';
	}
}