-
第 51 樓 / webdriver
- 時間: 2014-9-28 02:33S算法問題: Partition List
問題描述:
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5. -
-
- 時間: 2014-9-28 02:34算法問題推薦解法來了...
...
解法（Java）
代碼:
public class PartitionList {
public ListNode partition(ListNode head, int x) {
ListNode start = new ListNode(0);
start.next = head;
ListNode slow = start;
while (slow.next != null) {
if (slow.next.val < x) {
slow = slow.next;
} else {
break;
}
}
ListNode fast = slow;
while (fast.next != null) {
if (fast.next.val >= x) {
fast = fast.next;
} else {
ListNode target = fast.next;
fast.next = target.next;
target.next = slow.next;
slow.next = target;
slow = slow.next;
}
}
return start.next;
}
} -
-
- 時間: 2014-9-28 02:37
-
- 時間: 2014-9-28 02:38算法問題推薦解法來了...
from back to forth...
解法（Java）
代碼:
import java.util.ArrayList;
public class PascalsTriangleII {
public ArrayList<Integer> getRow(int rowIndex) {
ArrayList<Integer> ret = new ArrayList<Integer>();
int[] tmp = new int[rowIndex + 1];
for (int i = 0; i <= rowIndex; i++) {
ret.add(1);
tmp[i] = 1;
}
for (int k = 2; k <= rowIndex; k++) {
int mid = k / 2;
for (int i = 1; i <= mid; i++) {
ret.set(i, tmp[i - 1] + tmp[i]);
}
for (int m = k; m > mid; m--) {
ret.set(m, ret.get(k - m));
}
for (int n = 0; n <= k; n++) {
tmp[n] = ret.get(n);
}
}
return ret;
}
}
-
- 時間: 2014-9-28 02:41
-
- 時間: 2014-9-28 02:43算法問題推薦解法來了...
.....
解法（Java）
代碼:
import java.util.ArrayList;
public class PascalTriangle {
public ArrayList<ArrayList<Integer>> pascalTriangle(int numRows) {
ArrayList<ArrayList<Integer>> pt = new ArrayList<ArrayList<Integer>>();
int k = 1;
for (int i = 0; i < numRows; i++) {
ArrayList<Integer> r = new ArrayList<Integer>();
for (int j = 0; j < k; j++) {
r.add(1);
}
k++;
pt.add(r);
}
for (int f = 2; f < pt.size(); f++) {
ArrayList<Integer> prev = pt.get(f - 1);
ArrayList<Integer> current = pt.get(f);
for (int g = 1; g < current.size() - 1; g++) {
current.set(g, prev.get(g - 1) + prev.get(g));
}
}
return pt;
}
} -
- 時間: 2014-9-28 02:43
-
- 時間: 2014-9-28 02:44算法問題推薦解法來了...
DFS.
解法（Java）
代碼:
import java.util.ArrayList;
public class PathSumII {
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root != null) {
ArrayList<Integer> path = new ArrayList<Integer>();
findPathSum(root, sum, result, path);
}
return result;
}
public void findPathSum(TreeNode root, int sum,
ArrayList<ArrayList<Integer>> result, ArrayList<Integer> path) {
if (root == null)
return;
if (root.left == null && root.right == null && root.val == sum) {
ArrayList<Integer> clone = new ArrayList<Integer>(path);
clone.add(root.val);
result.add(clone);
} else {
path.add(root.val);
if (root.left != null) {
findPathSum(root.left, sum - root.val, result, path);
}
if (root.right != null) {
findPathSum(root.right, sum - root.val, result, path);
}
path.remove(path.size() - 1);
}
}
} -
- 時間: 2014-9-28 02:44S算法問題: Path Sum
問題描述:
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up
all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22. -
- 時間: 2014-9-28 02:45算法問題推薦解法來了...
Recursion.
解法（Java）
代碼:
public class PathSum {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null)
return false;
if (root.left == null && root.right == null && root.val == sum)
return true;
boolean l = root.left != null ? hasPathSum(root.left, sum - root.val)
: false;
boolean r = root.right != null ? hasPathSum(root.right, sum - root.val)
: false;
return l || r;
}
}
Leetcode Hacking Practice -- Solution in Java Part 2
