61. Rotate List
分析：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
先求出链表的长度，再用k%len，如果k等于0，相当于不旋转，直接返回头结点。
找到当前的尾结点last，在找到断链部分的两个结点q和newHead，把q的下一个结点设置为null，再把尾结点last的下一个结点设置为头结点head， 即可完成翻转。
Java：
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null) {
return null;
}
ListNode p = head;
int len = 0;
while (p != null) {
len++;
p = p.next;
}
k %= len;
if (k == 0) {
return head;
}
ListNode last = head;
while (last.next != null) {
last = last.next;
}
ListNode q = head;
for (int i = 0; i < len - k - 1; i++) {
q = q.next;
}
ListNode newHead = q.next;
last.next = head;
q.next = null;
return newHead;
}
}
62. Unique Paths
分析：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？
方法一：排列组合
一共需要往右走n-1步，往下走m-1步。
所以总共要走n+m-2步。
从这n+m-2步中向右走n-1步一共有多少种选法，排列组合问题。
等于
计算排列组合的时候，需要边乘边约分，这样数据才不会溢出。
方法二：动态规划
dp[i][j]代表到达第i行第j列的路径个数。
边界是第0行的所有列路径个数是1，第0列的所有行路径个数是1。
转移方程是 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
Java：
class Solution {
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
public int uniquePaths(int m, int n) {
int up = 1, down = 1, sum = n + m - 2;
int k = n - 1;
for (int i = 1; i <= n - 1; i++) {
down *= k;
k--;
up *= sum;
sum--;
int g = gcd(up, down);
up /= g;
down /= g;
}
return up / down;
}
}
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
63. Unique Paths II
分析：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
使用动态规划，dp[i][j]代表到达第i行第j列的路径个数。
边界是 第0行到达障碍物前的所有列路径个数是1，第0列到达障碍物前的所有行路径个数是1。
转移方程只有当第i行第j列不是障碍物时， dp[i][j] = dp[i-1][j] + dp[i][j-1] 。
Java：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
if (obstacleGrid[i][0] == 0) {
dp[i][0] = 1;
} else {
break;
}
}
for (int i = 0; i < n; i++) {
if (obstacleGrid[0][i] == 0) {
dp[0][i] = 1;
} else {
break;
}
}
for (int i = 1; i < m; i++) {
for (int 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];
}
}
64. Minimum Path Sum
分析：
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。
使用动态规划，dp[i][j]代表到达第i行第j列的最短路径长度。
边界，第一行和第一列的dp先计算出来。
转移方程dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
Java:
class Solution {
public int minPathSum(int[][] grid) {
if (grid.length == 0) {
return 0;
}
int row = grid.length, col = grid[0].length;
int[][] dp = new int[row][col];
for (int i = 0; i < row; i++) {
if (i == 0) {
dp[i][0] = grid[i][0];
} else {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
}
for (int i = 0; i < col; i++) {
if (i == 0) {
dp[0][i] = grid[0][i];
} else {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
}
65. Valid Number
分析：
以后再做。
Java：
class Solution {
public boolean isNumber(String s) {
if (s == null || s.length() == 0) {
return false;
}
boolean numSeen = false;
boolean dotSeen = false;
boolean eSeen = false;
char[] arr = s.trim().toCharArray();
for (int i = 0; i < arr.length; i++) {
if (arr[i] >= '0' && arr[i] <= '9') {
numSeen = true;
} else if (arr[i] == '.') {
if (dotSeen || eSeen) {
return false;
}
dotSeen = true;
} else if (arr[i] == 'E' || arr[i] == 'e') {
if (eSeen || !numSeen) {
return false;
}
eSeen = true;
numSeen = false;
} else if (arr[i] == '+' || arr[i] == '-') {
if (i != 0 && arr[i - 1] != 'e' && arr[i - 1] != 'E') {
return false;
}
} else {
return false;
}
}
return numSeen;
}
}
网友评论