复习算法
My personal study notes for learning Algorithhms 4th Edition by Robert Sedgewick, Kevin Wayne.
1. Decimal to Binary converter **use recursion***
public static int convertInt(int num){
switch (num){
case 1: return 1;
case 0: return 0;
}
int binary = num;
int bits = binary % 2;
int rests = binary / 2;
System.out.print (convertInt(rests));
return bits;
}
2. Check for balanced parentheses in an expression
private static inttypeDetector(chars) {
switch(s) {
case'{':
return1;
case'}':
return-1;
case'[':
return2;
case']':
return-2;
case'(':
return3;
case')':
return-3;
default:
return0;
}
}
public static booleanbracesCheck(String s){
intforCB =0;//{}
intforBR =0;//[]
intforBC =0;//()
for(inta =0;a < s.length();a ++ ){
if(Math.abs((typeDetector(s.charAt(a)))) ==1){
forCB =typeDetector(s.charAt(a)) + forCB;
if(forCB <0){return false;}
}else if(Math.abs((typeDetector(s.charAt(a)))) ==2){
forBR =typeDetector(s.charAt(a)) + forBR;
if(forBR <0){return false;}
}else{
forBC =typeDetector(s.charAt(a)) + forBC;
if(forBC <0){return false;}
}
}
if(forCB == forBR && forBR == forBC && forBC ==0){
return true;
}
return false;
}
3. Weighted Quick Union
The punchline of weighted quick union is to create a new array to store height of the trees. The time expenditure of the find() method is reduced to logN of base 2 from N which was linear time.
4.(代码有bug未解决)You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input:(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:7 -> 0 -> 8
static intsum(ListNode l){
intsum =0;
intdegree =1;
do{
sum = sum + l.val* degree;
l = l.next;
degree = degree *10;
}while(l!=null);
returnsum;
}
static publicListNodeaddTwoNumbers(ListNode l1,ListNode l2) {
intsum1 =sum(l1);
intsum2 =sum(l2);
inttSum = sum1 + sum2;
ListNode L1 =newListNode(tSum %10);
ListNode S1 = L1.next;
while(tSum/10!=0){
S1.val= (tSum/10)%10;
S1 = S1.next;
tSum = tSum /10;
print(tSum);
}
returnL1;
}
public static voidmain(String args[]){
ListNode L1 =newListNode(2);
ListNode L2 =newListNode(4);
ListNode L3 =newListNode(3);
L1.next= L2;
L2.next= L3;
L3.next=null;
ListNode S1 =newListNode(5);
ListNode S2 =newListNode(6);
ListNode S3 =newListNode(4);
S1.next= S2;
S2.next= S3;
S3.next=null;
addTwoNumbers(L1,S1);
}
5.在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
public class Solution {
public boolean Find(int target, int [][] array) {
if(array==null||array.length==0||(array.length==1&&array[0].length==0)) return false;
int column = array[0].length - 1;
int row = 0;
while(true) {
if (target == array[row][column]){return true;}
if (target < array[row][column]) {
if (column - 1 < 0){return false;}
column = column - 1;
continue;
}else{
if (row + 1 == array.length){return false;}
row = row + 1;
continue;
}
}
}
}
