Shu
BAN USERpublic class Power{
public static double pow(double a, int b){
//check the validity of a and b
if(a == 0 && b == 0)
return Integer.MIN_VALUE;
if(a == 0)
return 0;
if(b == 0)
return 1;
if(b == 1)
return a;
boolean aMinus = a < 0? true: false;
boolean bMinus = b < 0? true : false;
int bAbs = Math.abs(b);
double aAbs = Math.abs(a);
//check if b is odd
double tempAnswer;
if( (b & 1) != 0){
tempAnswer = pow(aAbs, bAbs - 1) * aAbs;
}
else{
tempAnswer = pow(aAbs * aAbs, bAbs / 2);
}
if(bMinus)
tempAnswer = 1.0 / tempAnswer;
if(aMinus && (b&1)!= 0)
tempAnswer *= -1;
return tempAnswer;
}
public static void main(String[] args){
System.out.println(Power.pow(-2,9));
return ;
}
}
import java.util.Scanner;
//given a string, find the start position of the largest block of repeated
//chars
//
public class LargestCharBlocks{
public static int getStart(String s){
//never forget to check the null...
if(s == null || s.length() == 0)
return -1;
int tempStartRecord = 0;
int startRecord = 0;
char previousChar;
int maxLength = 0;
int tempLength = 0;
char[] string = s.toCharArray();
previousChar = string[0];
startRecord = 0;
maxLength = 1;
tempLength = 1;
for(int i = 1; i < string.length; i ++){
if(string[i] == previousChar){
tempLength ++;
}
else if(string[i] != previousChar){
if(tempLength > maxLength){
maxLength = tempLength;
startRecord = tempStartRecord;
}
tempStartRecord = i;
tempLength = 1;
previousChar = string[i];
}
}
return startRecord;
}
public static void main(String[] args){
Scanner s = new Scanner(System.in);
String string = s.next();
System.out.println(LargestCharBlocks.getStart(string));
return;
}
}
public class ReverseSentence{
public static String reverseSentence(String sentenceString){
char[] rev = new char[sentenceString.length()];
char[] sentence = sentenceString.toCharArray();
//traverser for the back
int wordEnd = sentence.length -1;
int revPointer = 0;
for(int i = sentence.length - 1; i >= 0; i --){
if(sentence[i] == ' '){
int traverser = i + 1;
while(traverser <= wordEnd){
rev[ revPointer++ ] = sentence[ traverser++ ];
}
wordEnd = i - 1;
rev[revPointer++] = ' ';
}
}
//copy the first word!
int traverser = 0;
while(traverser <= wordEnd){
rev[revPointer ++] = sentence[traverser ++];
}
return new String(rev);
}
public static void main(String[] args){
String sentence = "We will we will rock you";
System.out.println(ReverseSentence.reverseSentence(sentence));
return;
}
}
Recursive call might be cleaner and easier.
public class SpiralPrint{
//print the elements of matrix in the spiral order.
//my idea is to use recursive, for each outer loop
public static void printSpiral(int[][] mat, int layer){
int up = layer;
int buttom = mat.length - layer - 1;
int left = layer;
int right = mat[0].length - layer - 1;
if(up > buttom+1 || left > right + 1)
return; // termination condition
//traverse the other frame,
//print up
for(int i = left; i <= right; i ++){
System.out.print( mat[up][i]+ " " );
}
//print right
for(int i = up + 1; i <=buttom; i ++){
System.out.print(mat[i][right] + " ");
}
//print buttom
for(int i = right - 1; i >= left; i --){
System.out.print(mat[buttom][i] + " ");
}
//print left
for(int i = buttom - 1; i > up; i --){
System.out.print(mat[i][left] + " ");
}
//recursive call for the next level
printSpiral(mat, layer + 1);
}
public static void main(String[] args){
int[][] mat = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
int[][] mat2 = {{1,2,3}, {4,5,6}, {7,8,9}, {10,11,12}};
SpiralPrint.printSpiral(mat2,0);
return;
}
}
Recursive calls.
public static LinkedList<LinkedList<Integer>> getSumPaths(int number){
if(number == 0){
LinkedList<LinkedList<Integer>> lls = new LinkedList<LinkedList<Integer>>();
lls.add(new LinkedList<Integer>());
return lls;
}
LinkedList<LinkedList<Integer>> toreturn = new LinkedList<LinkedList<Integer>>();
for(int i = 1; i <= number; i ++){
LinkedList<LinkedList<Integer>> llreturn = getSumPaths(number - i);
for(LinkedList<Integer> ls : llreturn){
ls.add(i);
toreturn.add(ls);
}
}
return toreturn;
}
I'd use the priority to help computation.
Everytime pop an answer with index pair(i,j) (which is the smallest sum now), and add the (i,j+1) and (i+1,j) pair into the heap.
import java.util.LinkedList;
import java.util.PriorityQueue;
class PairSum implements Comparable<PairSum>{
public int value1;
public int value2;
public int sum;
public int index1;
public int index2;
public PairSum(int _value1, int _value2, int _index1, int _index2){
value1 = _value1;
value2 = _value2;
sum = value1 + value2;
index1 = _index1;
index2 = _index2;
}
public int compareTo(PairSum another){
if(this.sum < another.sum)
return -1;
else if(this.sum == another.sum)
return 0;
else
return 1;
}
public String toString(){
String res = "[ " + value1 + "," + value2 + " " + sum + " ]";
return res;
}
}
public class SortSum{
public static LinkedList<PairSum> sortSum(int[] array1, int[] array2){
LinkedList<PairSum> res = new LinkedList<PairSum>();
PriorityQueue<PairSum> heap = new PriorityQueue<PairSum>();
heap.offer(new PairSum(array1[0],array2[0],0,0));
while(heap.size() != 0){
PairSum popped = heap.poll();
res.add(popped);
int i = popped.index1;
int j = popped.index2;
if( (i < array1.length) && (j < array2.length - 1)){
heap.offer(new PairSum(array1[i], array2[j+1], i, j + 1));
}
if( (i < array1.length - 1) && (j < array2.length)){
heap.offer(new PairSum(array1[i+1], array2[j], i+1, j));
}
}
return res;
}
public static void main(String[] args){
int[] array1 = {1,3,6};
int[] array2 = {4,5,6};
System.out.println(SortSum.sortSum(array1, array2));
return;
}
}
use a recursive solution. I think it will be much easier in way of thinking.
import java.util.Scanner;
//partition a linked list around value x
//
class Node{
public int value;
public Node next;
public Node(Node prev, int _value){
this.value = _value;
if(prev == null)
return;
prev.next = this;
next = null;
return;
}
}
public class ReversePart{
public static void printNodes(Node head){
Node traverser = head;
while(traverser != null){
System.out.print(traverser.value + " ");
traverser = traverser.next;
}
}
public static Node reversePart(Node head, int part){
if(head == null || head.next == null)
return head;
int count = 0;
Node pre = head;
Node later = head.next;
Node next = null;
while(count < part - 1 && later != null){
next = later.next;
later.next = pre;
pre = later;
later = next;
count ++;
}
if(next != null){
head.next = reversePart(next, part);
}
//important
if(next == null){
//termination condition
//no sufficient elements
head.next = null;
}
return pre;
}
public static final void main(String[] args){
Scanner scanner = new Scanner("1 2 3 4 5 6 7 8 9 10 11");
Node head = null;
Node prev = null;
while(scanner.hasNext()){
if(prev == null){
head = new Node(prev, scanner.nextInt());
prev = head;
}
else
prev = new Node(prev, scanner.nextInt());
}
Node newHead = ReversePart.reversePart(head,3);
ReversePart.printNodes(newHead);
return;
}
}
Generally, because there are some recomputations on the subproblems, we can use a hash map to store the sub solutions.
- Shu February 09, 2013The recursive calls on each string are sometimes called twice(because there might be combination of two numbers which are possible to map to a char) , and combine the two sub solutions into one, and then return.