# LeetCode(61-70)

## 61. Rotate List¶

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

Solution

Runtime 1ms。

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {

// 获取链表长度以及末尾的指针
int length = 0;
while (p != null) {
length++;
tail = p;
p = p.next;
}

k = length - (k % length);
// 链成环状
// 从头节点移动n-k步，此时p就是新链表的头节点
for (int i = 0; i < k; i++) {
tail = p;
p = p.next;
}
// 断开环，返回p即可
tail.next = null;

return p;
}
}


## 62. Unique Paths¶

• Dynamic Programming

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there? Above is a 7 x 3 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1.Right -> Right -> Down
2.Right -> Down -> Right
3.Down -> Right -> Right

Example 2:

Input: m = 7, n = 3
Output: 28

Solution

Runtime 0ms

class Solution {
private static Map<Integer, Integer> map = new HashMap<>();

public int uniquePaths(int m, int n) {
return f(m, n);
}

private int f(int m, int n) {
if (m < n) {
int temp = m;
m = n;
n = temp;
}

if (m == 1 || n == 1) {
return 1;
}

int key = m * 1000 + n;
Integer value = map.get(key);
if (value != null) {
return value;
} else {
value = f(m - 1, n) + f(m, n - 1);
map.put(key, value);
return value;
}
}
}


## 63. Unique Paths II¶

• Dynamic Programming

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

Now consider if some obstacles are added to the grids. How many unique paths would there be? Above is a 7 x 3 grid. How many possible unique paths are there?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: m and n will be at most 100.

Example 1:

Input:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
Output: 2
Explanation:
There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1.Right -> Right -> Down -> Down
2.Down -> Down -> Right -> Right

Solution

Runtime 1ms

class Solution {
private Map<Integer, Integer> map = new HashMap<>();

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
final int m = obstacleGrid.length;
final int n = obstacleGrid.length;
return f(obstacleGrid, m, 0, n, 0);
}

private int f(int[][] obstacleGrid, int m, int row, int n, int col) {
if (row >= m ||
col >= n ||
obstacleGrid[row][col] == 1) {
return 0;
}

if (row == m - 1 && col == n - 1) {
return 1;
}

int key = row * 1000 + col;
Integer value = map.get(key);
if (value != null) {
return value;
} else {
value = f(obstacleGrid, m, row + 1, n, col) + f(obstacleGrid, m, row, n, col + 1);
map.put(key, value);
return value;
}
}
}


## 64. Minimum Path Sum¶

• Dynamic Programming

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example:

Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

Solution

Runtime 2ms, beats 93.47%

class Solution {
public int minPathSum(int[][] grid) {
final int rows = grid.length;
final int cols = grid.length;
int[] dp = new int[cols];

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int min = 0;
if (i > 0 && j > 0) {
min = Math.min(dp[j - 1], dp[j]);
} else if (i > 0) {
min = dp[j];
} else if (j > 0) {
min = dp[j - 1];
}

dp[j] = min + grid[i][j];
}
}

return dp[cols - 1];
}
}


## 65. Valid Number¶

• String

Validate if a given string can be interpreted as a decimal number.

Some examples:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false

Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. However, here is a list of characters that can be in a valid decimal number:

• Numbers - 0-9
• Exponent - "e"
• Positive/negative sign - "+"/"-"
• Decimal point - "."

Of course, the context of these characters also matters in the input.

Solution

class Solution {
private int index;

public boolean isNumber(String s) {
if (s == null) {
return false;
}

return isNumber(s.toCharArray());
}

private boolean isNumber(char[] ch) {
final int n = ch.length;

skipEmpty(ch, n);

boolean isNumber = scanInteger(ch, n);

if (index < n && ch[index] == '.') {
index++;
isNumber = scanUnsignedInteger(ch, n) || isNumber;
}

if (index < n && ch[index] == 'e') {
index++;
isNumber = isNumber && scanInteger(ch, n);
}

skipEmpty(ch, n);

return isNumber && index == n;
}

private void skipEmpty(char[] ch, int n) {
while (index < n) {
if (ch[index] == ' ') {
index++;
} else {
break;
}
}
}

private boolean scanInteger(char[] ch, int n) {
if (index < n && (ch[index] == '-' || ch[index] == '+')) {
index++;
}

return scanUnsignedInteger(ch, n);
}

private boolean scanUnsignedInteger(char[] ch, int n) {
int originIndex = index;

while (index < n && ch[index] >= '0' && ch[index] <= '9') {
index++;
}

return index > originIndex;
}
}


## 66. Plus One¶

• Array

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution

Runtime 0ms

class Solution {
public int[] plusOne(int[] digits) {
if (digits == null || digits.length == 0)
return digits;

final int n = digits.length;
int carry = 1;

for (int i = n - 1; i >= 0; i--) {
int sum = digits[i] + carry;
digits[i] = sum % 10;
carry = sum / 10;
}

if (carry > 0) {
int[] temp = new int[n + 1];
System.arraycopy(digits, 0, temp, 1, n);
temp = carry;
digits = temp;
}

return digits;
}
}


• Math

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Solution

Runtime 1ms

Tip

Tips: char转int不需要强转，int转char是需要的。
char转int： '9' - '0'
int转char: (char) (9 + '0')

class Solution {
public String addBinary(String a, String b) {
// make a becomes the larger one
if (a.length() < b.length()) {
String temp = a;
a = b;
b = temp;
}

}

private String addBinary(char[] a, char[] b) {
final int m = a.length;
final int n = b.length;
int i = m - 1, j = n - 1, carry = 0, sum = 0;

while (i >= 0) {
if (j >= 0) {
sum = a[i] + b[j] - '0' - '0' + carry;
} else {
sum = a[i] - '0' + carry;
}

a[i] = (char) ((sum % 2) + '0');
carry = sum / 2;

i--;
j--;
}

if (carry > 0) {
char[] result = new char[m + 1];
System.arraycopy(a, 0, result, 1, m);
result = (char) (carry + '0');
return new String(result);
} else {
return new String(a);
}
}
}


## 68. Text Justification¶

• String

Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

Note:

• A word is defined as a character sequence consisting of non-space characters only.
• Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
• The input array words contains at least one word.

Example 1:

Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]

Example 2:

Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified becase it contains only one word.

Example 3:

Input:
words = ["Science","is","what","we","understand","well","enough","to","explain", "to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]

Solution

Runtime 0ms

class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
final int n = words.length;
int[] width = new int[n];

for (int i = 0; i < n; i++) {
width[i] = words[i].length();
}

List<String> result = new ArrayList<>();
int index = 0;
while (index < n) {
int currentWidth = 0;
int spaceCount = -1;
while (index < n) {
currentWidth += width[index++];
spaceCount++;
if (currentWidth + spaceCount > maxWidth) {
currentWidth -= width[--index];
spaceCount--;
break;
}
}
int totalSpace = maxWidth - currentWidth;

StringBuilder sb = new StringBuilder();
if (index != n) {
int space = spaceCount == 0 ? 0 : totalSpace / spaceCount;
int extraSpace = spaceCount == 0 ? 0 : totalSpace % spaceCount;

int begin = index - spaceCount - 1;
for (int i = begin; i < index; i++) {
sb.append(words[i]);
if (space == 0) {
appendSpace(sb, totalSpace);
} else if (i <= index - 2) {
int size = space + (i < begin + extraSpace ? 1 : 0);
appendSpace(sb, size);
}
}
} else { // last line
int begin = index - spaceCount - 1;
for (int i = begin; i < index; i++) {
sb.append(words[i]);
if (i <= index - 2) {
appendSpace(sb, 1);
} else if (i == index - 1) {
appendSpace(sb, totalSpace - spaceCount);
}
}
}

}

return result;
}

private void appendSpace(StringBuilder sb, int size) {
char[] ch = new char[size];
Arrays.fill(ch, ' ');
sb.append(ch);
}
}


## 69. Sqrt(x)¶

• Binary Search

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Solution

Runtime 1ms

class Solution {
public int mySqrt(int x) {
int begin = 0;
int end = x;

while (begin <= end) {
int mid = (begin + end) >> 1;
long result = (long) mid * mid;
if (result == x) {
return mid;
} else if (result > x) {
end = mid - 1;
} else {
begin = mid + 1;
}
}

return end;
}
}


## 70. Climbing Stairs¶

-> Dynamic Programming

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Solution

Runtime 0ms, beats 100%

class Solution {
public int climbStairs(int n) {
if (n <= 1) return 1;

int[] results = new int[n + 1];
results = 1;
results = 1;

for(int i = 2; i <= n; i++) {
results[i] = results[i - 1] + results[i - 2];
}

return results[n];
}
}


O(1)空间复杂度：

class Solution {
public int climbStairs(int n) {
if (n <= 1) return 1;

int a = 1;
int b = 1;

for(int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}

return b;
}
}