3 sum
First, 2 sum is needed.
/** first sort, then search target
* actually, the problem is as the same as search a target in Young matrix
* Notice: repeated number
*/
public class Solution {
private ArrayList<ArrayList<Integer>> twoSum(int[] num, int startIndex, int target) {
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
int low = startIndex;
int high = num.length - 1;
while (low < high) {
int sum = num[low] + num[high];
if (sum < target) {
while (++low < high && num[low] == num[low - 1]);
} else if (sum > target) {
while (--high > low && num[high] == num[high + 1]);
} else {
ArrayList<Integer> pair = new ArrayList<Integer>();
pair.add(num[low]);
pair.add(num[high]);
rst.add(pair);
while (++low < high && num[low] == num[low - 1]);
while (--high > low && num[high] == num[high + 1]);
}
}
return rst;
}
public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
Arrays.sort(num);
for (int i = 0; i < num.length - 2;) {
ArrayList<ArrayList<Integer>> twoSum = twoSum(num, i + 1, -num[i]);
for (ArrayList<Integer> pair : twoSum) {
pair.add(0, num[i]);
rst.add(pair);
}
while (++i < num.length - 2 && num[i] == num[i - 1]);
}
return rst;
}
}
2013年4月1日星期一
sqrt
sqrt
Babylonian method for square root
why (x + y)/2 is always bigger than square root of n:
public double sqrt(double n) {
double x = n;
double y = 1;
double e = 0.0001
while (x - y > e) {
x = x + (y - x) / 2;
y = n / x;
}
return x;
}
BST的中序遍历每个node的next()函数实现
First, let's write a program to inorder traverse BST using iterative way.
public void inorder(Node node) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
visit(node);
node = node.right;
}
}
class InorderIterator {
Stack<Node> stack;
Node next;
Node node;
InorderIterator(Node root) {
if (root== null) {
throw new NullPointerException();
}
node = root;
stack = new Stack<Node>();
while (node != null) {
stack.push(node);
node = node.left;
}
next = stack.pop();
node = node.right;
}
Node next() {
Node temp = next;
if (stack.isEmpty() && node == null) {
thrwo new NoSuchElementException();
} else {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
next = node;
node = node.right;
}
return temp;
}
}
public Node next(Node node) {
if (node.right != null) {
return leftMost(node.right);
} else {
while (node.p != null && node == node.p.right) {
node = node.p;
}
return node.p;
}
}
public Node next(Node root, Node node) {
if (node.right != null) {
return leftMost(node.right);
} else {
Node next = null;
while (root != node) {
if (node.val <= root.val) {
next = root;
root = root.left;
} else {
root = root.right;
}
}
return next;
}
}
public void inorder(Node node) {
Stack<Node> stack = new Stack<Node>();
while (!stack.isEmpty() || node != null) {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
visit(node);
node = node.right;
}
}
class InorderIterator {
Stack<Node> stack;
Node next;
Node node;
InorderIterator(Node root) {
if (root== null) {
throw new NullPointerException();
}
node = root;
stack = new Stack<Node>();
while (node != null) {
stack.push(node);
node = node.left;
}
next = stack.pop();
node = node.right;
}
Node next() {
Node temp = next;
if (stack.isEmpty() && node == null) {
thrwo new NoSuchElementException();
} else {
while (node != null) {
stack.push(node);
node = node.left;
}
node = stack.pop();
next = node;
node = node.right;
}
return temp;
}
}
public Node next(Node node) {
if (node.right != null) {
return leftMost(node.right);
} else {
while (node.p != null && node == node.p.right) {
node = node.p;
}
return node.p;
}
}
public Node next(Node root, Node node) {
if (node.right != null) {
return leftMost(node.right);
} else {
Node next = null;
while (root != node) {
if (node.val <= root.val) {
next = root;
root = root.left;
} else {
root = root.right;
}
}
return next;
}
}
订阅:
博文 (Atom)