Yi
BAN USERpublic class TwoSum {
// find pairs whose sum to target
public static ArrayList<ArrayList<Integer>> solution(int[] num, int target){
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if(num == null || num.length < 2){
return result;
}
Arrays.sort(num);
int before = 0;
int after = num.length - 1;
while(before < after){
int sum = num[before] + num[after];
if(sum < target){
before++;
}else if(sum > target){
after--;
}else{
ArrayList<Integer> temp = new ArrayList<Integer>();
temp.add(num[before]);
temp.add(num[after]);
result.add(temp);
do{
before++;
}while(before < after && num[before] == num[before - 1]);
do{
after--;
}while(before < after && num[after] == num[after + 1]);
}
}
return result;
}
// find all pairs' sum in an array
public static ArrayList<Integer> findAllValue(int[] num){
ArrayList<Integer> result = new ArrayList<Integer>();
HashSet<Integer> values = new HashSet<Integer>();
for(int i = 0; i < num.length - 1; i++){
for(int j = i + 1; j < num.length; j++){
values.add(num[i] + num[j]);
}
}
for(Integer value: values){
result.add(value);
}
return result;
}
// display pairs in an ArrayList
private static void display(ArrayList<ArrayList<Integer>> list){
for(ArrayList<Integer> pair: list){
System.out.println(pair);
}
}
public static void main(String[] args){
int[] num = {1,4,1,4,2,3};
ArrayList<Integer> values = TwoSum.findAllValue(num);
for(Integer value: values){
System.out.println(value);
ArrayList<ArrayList<Integer>> result = TwoSum.solution(num, value);
TwoSum.display(result);
System.out.println();
}
}
}
public String infixToPos(String infix){
Stack<Character> stack = new Stack<Character>();
StringBuffer pos = new StringBuffer();
for(int i = 0; i<infix.length(); i++){
char c = infix.charAt(i);
if(c!='+' && c!='-' && c!='*' && c!='/' ){
pos.append(c);
}else if(stack.empty()){
stack.push(c);
}else{
if(c == '*' || c == '/'){
System.out.println("Peek" + stack.peek());
while(stack.peek() == '*' || stack.peek() == '/'){
if(!stack.isEmpty()){
pos.append(stack.pop());
}
}
stack.push(c);
}else{
while(!stack.isEmpty()){
pos.append(stack.pop());
}
stack.push(c);
}
}
}
while(!stack.empty()){
pos.append(stack.pop());
}
return pos.toString();
}
public int Postifix(String str) throws Exception {
Stack<Integer> stack = new Stack<Integer>();
int one = 0;
int two = 0;
for (int i = 0; i < str.length(); i++) {
switch (str.charAt(i)) {
case '+':
try {
one = stack.pop();
two = stack.pop();
} catch (Exception e) {
System.out
.printf("You can't make pop in an empty stack!\n");
}
stack.push(one + two);
break;
case '*':
try {
one = stack.pop();
two = stack.pop();
} catch (Exception e) {
System.out
.printf("You can't make pop in an empty stack!\n");
}
stack.push(one * two);
break;
case '-':
try {
one = stack.pop();
two = stack.pop();
} catch (Exception e) {
System.out
.printf("You can't make pop in an empty stack!\n");
}
stack.push(two - one);
break;
case '/':
try {
one = stack.pop();
two = stack.pop();
} catch (Exception e) {
System.out
.printf("You can't make pop in an empty stack!\n");
}
stack.push(two / one);
break;
default:
stack.push(Integer.parseInt("" + str.charAt(i)));
break;
}
}
return stack.pop();
}
public boolean isOmorphic(String str1, String str2){
if(str1.length() != str2.length()){
return false;
}
if(str1.length() == 0){
return true;
}
HashMap<Character, Character> map = new HashMap<Character, Character>();
for(int i=0; i<str1.length(); i++){
if(map.containsKey(str1.charAt(i))){
if(map.get(str1.charAt(i)) != str2.charAt(i)){
return false;
}
else{
continue;
}
}else{
map.put(str1.charAt(i), str2.charAt(i));
}
}
return true;
}
public Node findNextNode(Node node){
- Yi April 23, 2014// special base case
if(node == null || node.parent == null){
return null;
}
// base case
if(node = node.parent.left && node.parent.right != null){
return node.parent.right;
}
Node parent_Neighbor = findNextNode(node.parent);
while(parent_Neighbor != null){
if(parent_Neighbor.left != null){
return parent_Neighbor.left;
}
if(parent_Neighbor.right != null){
return parent_Neighbor.right;
}
parent_Neighbor = findNextNode(parent_Neighbor);
}
return null;
}