-
第 31 樓 / webdriver
- 時間: 2014-9-28 01:41S算法問題: Minimum Depth of Binary Tree
問題描述:
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node
down to the nearest leaf node. -
-
- 時間: 2014-9-28 01:42算法問題推薦解法來了...
1. Recursion. Pay attention to cases when the non-leaf node has only one child.
2. Iteration + Queue. Contributed by SUN Mian(孫冕).
解法（Java）
代碼:
public class MinimumDepthofBinaryTree {
public int minDepth(TreeNode root) {
if (root == null)
return 0;
if (root.left == null && root.right == null)
return 1;
else {
int leftDepth = root.left != null ? minDepth(root.left)
: Integer.MAX_VALUE;
int rightDepth = root.right != null ? minDepth(root.right)
: Integer.MAX_VALUE;
return Math.min(leftDepth, rightDepth) + 1;
}
}
} -
-
- 時間: 2014-9-28 01:46
-
- 時間: 2014-9-28 01:47算法問題推薦解法來了...
Dynamic Programming. Space O(N).
解法（Java）
代碼:
public class MinimumPathSum {
public int minPathSum(int[][] grid) {
int[][] path = new int[grid.length][grid[0].length];
path[0][0] = grid[0][0];
for (int i = 1; i < grid.length; i++) {
path[i][0] = path[i - 1][0] + grid[i][0];
}
for (int j = 1; j < grid[0].length; j++) {
path[0][j] = path[0][j - 1] + grid[0][j];
}
for (int i = 1; i < grid.length; i++)
for (int j = 1; j < grid[0].length; j++) {
path[i][j] = Math.min(path[i - 1][j], path[i][j - 1])
+ grid[i][j];
}
return path[grid.length - 1][grid[0].length - 1];
}
} -
- 時間: 2014-9-28 01:48S算法問題: Minimum Window Substring
問題描述:
Given a string S and a string T, find the minimum window in S which will contain all the
characters in T in complexity O(n).
For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".
Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there are multiple such windows, you are guaranteed that there will always be only one unique
minimum window in S. -
- 時間: 2014-9-28 01:48算法問題推薦解法來了...
1. Use two pointers: start and end.
First, move 'end'. After finding all the needed characters, move 'start'.
2. Use array as hashtable.
解法（Java）
代碼:
public class MinimumWindowSubstring {
public String minWindow(String S, String T) {
int[] hasFound = new int[256];
int[] needFound = new int[256];
int diffCount = T.length();
int length = S.length();
String window = "";
int size = Integer.MAX_VALUE;
if (length == 0 || diffCount == 0)
return window;
for (int l = 0; l < diffCount; l++) {
needFound[T.charAt(l)]++;
}
int i = 0, j = 0;
while (j < length) {
char c = S.charAt(j);
if (needFound[c] > 0 && ++hasFound[c] <= needFound[c]) {
diffCount--;
}
if (diffCount == 0) {
while (i <= j) {
char h = S.charAt(i);
i++;
if (needFound[h] > 0 && --hasFound[h] < needFound[h]) {
if (j - i + 1 < size) {
size = j - i + 1;
window = S.substring(i - 1, j + 1);
}
diffCount++;
break;
}
}
}
j++;
}
return window;
}
} -
- 時間: 2014-9-28 01:49
-
- 時間: 2014-9-28 01:49算法問題推薦解法來了...
Just like what we do when multiplying integers.
解法（Java）
代碼: public class MultiplyStrings {
public String multiply(String num1, String num2) {
int length1 = num1.length();
int length2 = num2.length();
int[] m = new int[length1 + length2];
for (int k = length2 - 1, offset2 = 0; k >= 0; k--, offset2++) {
for (int i = length1 - 1, offset1 = 0; i >= 0; i--, offset1++) {
m[length1 + length2 - 1 - offset1 - offset2] += (num1.charAt(i) - '0')
* (num2.charAt(k) - '0');
}
}
int add = 0;
for (int t = length1 + length2 - 1; t >= 0; t--) {
int value = m[t] + add;
add = value / 10;
m[t] = value % 10;
}
StringBuffer sb = new StringBuffer();
int w = 0;
for (; w < length1 + length2; w++) {
if (m[w] != 0)
break;
}
for (int e = w; e < length1 + length2; e++) {
sb.append(m[e]);
}
return sb.length() == 0 ? "0" : sb.toString();
}
}
-
- 時間: 2014-9-28 01:50S算法問題: Next Permutation
問題描述:
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 -> 1,3,2
3,2,1 -> 1,2,3
1,1,5 -> 1,5,1 -
- 時間: 2014-9-28 01:51算法問題推薦解法來了...
O(n)
Processes: Take A = {1,3,2} as an example:
1. Traverse from back to forth, find the turning point, that is A[i] = 3.
2. Sort from the turning point to the end (A[i] to A[end]), so {3,2} becomes {2,3}.
3. If i equals to 0, finish! Else, goto 4.
4. Let j = i, search from A[j] to A[end] to find the first elem which is larger than A[i-1], '2' here.
5. Swap the elem A[j] with A[i-1].
Finally, the next permutation is {2,1,3}.
解法（Java）
代碼:
import java.util.Arrays;
public class NextPermutation {
public void nextPermutation(int[] num) {
int i1 = 0;
int i2 = 0;
int i = num.length - 1;
int j = 0;
while (i > 0 && num[i - 1] >= num[i]) {
i--;
}
if (i == 0) {
Arrays.sort(num);
return;
} else {
i1 = i - 1;
}
j = i1 + 1;
while (j < num.length && num[i1] < num[j]) {
j++;
}
i2 = j - 1;
int temp = num[i1];
num[i1] = num[i2];
num[i2] = temp;
Arrays.sort(num, i1 + 1, num.length);
}
}
Leetcode Hacking Practice -- Solution in Java Part 2
