2013年1月27日 星期日

[Q1-3]EQ_COUNT

[SOURCE]
名題精選百則_題1.3

[INPUT]
two number set f[ ] and g[ ] which are sorted in increment order
ex. 
f =1,3,5,7,9  
g =1,5,6,8,10
lengthF= number of elements in f
lengthG= number of element in g

[OUTPUT]
f[j]=g[i] means "equal" , count totally "equal" value number
ex.
g[0]=f[0]=1
g[1]=f[2]=5

therefore, totally "equal" value number is 2

[THINK]
f, g都是已經排序好的數列
借用Q1-2的想法,f[idxF]==g[idxG]表示f[idxF], g[idxG]之前的數不用拿來做比較
分成3種情況
Case 1: f[idxF]==g[idxG]
Case 2: f[idxF]>g[idxG]
Case 3: f[idxF]<g[idxG]

Case 1就是我們想要的, count加1, f[ ]和g[ ]的idx都往後移

Case 2表示現在f[idxF]較大, 所以我們將g[ ]的idx往後移

Case 3表示現在g[idxG]較大, 所以我們將f[ ]的idx往後移

[SCv1]


//idxG is index of g
//idxF is index of f
    while(idxG< lengthG && idxF< lengthF){
      if(f[idxF]==g[idxG]){
        sum++;
        idxG++;
        idxF++;
      }             
      else if(f[idxF]>g[idxG]){
        idxG++;
      }
      else{   
        idxF++;
      }
    }


2013年1月13日 星期日

[Q1-2]GT_COUNT

[SOURCE]
名題精選百則_題1.2

[INPUT]
two number set f[ ] and g[ ] which are sorted in increment order
ex. 
f =1,3,5,7,9  
g =1,4,5,8,10
lengthF= number of elements in f
lengthG= number of element in g
    
[OUTPUT]
f[j]>g[i] means "greater" , count totally "greater"
ex. 
g[0]→3,5,7,9→"greater" count is 4
g[1]→5,7,9→"greater" count is 3
g[2]→7,9→"greater" count is 2
g[3]→9→"greater" count is 1
g[4]→none→"greater" count is 0

therefore, totally "greater" is 4+3+2+1+0=10

[THINK]
f, g都是已經排序好的數列
所以當 f[j]>g[i] 時表示f[j]之後的數也都會大於g[i]
"greater"個數為 lengthF-j
當 f[j]<=g[i] 時,往f[j]的下一個元素 f [j+1]比較

[SCv1]
//i is index of g
//j is index of f
//sum is the result    
    for(i=0;i<lengthG;i++){
      for(j=idx;j<lengthF;j++){
        if(f[j]>g[i]){
          tmpL=lengthF-j;
          idx=j;
          break;
        }        
      }
      if(j==lengthF)
        break;
      else
        sum=sum+tmpL;
    }

[SCv2]
//i is index of g
//j is index of f
//sum is the result    
    while(i< lengthG && j< lengthF){
      if(f[j]>g[i]){
        sum+=(lengthF-j);
        i++;
      }             
      else
        j++;
    }


2013年1月12日 星期六

抽象類別Abstract Class

[概念]
pic 1:polymorphism

每位超級英雄有自己的穿衣風格,蜘蛛人簡單地穿上紅藍蜘蛛衣,
蝙蝠俠回家換上蝙蝠裝,鋼鐵人拿出箱子,換上鋼鐵裝備,

//Base Class
public class SuperHero{
  public void power(){
    System.out.println("superhuman strength");
  }
  public void vest(){
    //each hero has their own style
  }
}

//Sub Class
public class Spiderman extends SuperHero{
  public void power(){
    System.out.println("spin a web");
  }
  public void vest(){
    System.out.println("simply change his equipment");
  }
}

public class Batman extends SuperHero{
  public void power(){
    System.out.println("shadow his body");
  }
  public void vest(){
    System.out.println("go cave and put on his equipment");
  }
}

public class Ironman extends SuperHero{
  public void power(){
    System.out.println("energy repulsors");
  }
  public void vest(){
    System.out.println("take out his box and put on his equipment");
  }
}

SuperHero這個Base Class並不需要特別實作vest(),
只需要交給個別的Sub Class去實作自己的vest(),
在這情況下,定義了所謂的抽象方法(Abstract Method),意即不特別去實作方法的內容,
一個類別中若包含抽象方法,則可稱為抽象類別(Abstract Class),
需要注意的是,不能生成抽象類別的物件,但可以宣告抽象類別的變數


//Base Class
public abstract class SuperHero{
  public void power(){
    System.out.println("superhuman strength");
  }
  public abstract void vest(); //abstract method
}

//Sub Class
public class Spiderman extends SuperHero{
  public void power(){
    System.out.println("spin a web");
  }
  public void vest(){
    System.out.println("simply change his equipment");
  }
}

public class Batman extends SuperHero{
  public void power(){
    System.out.println("shadow his body");
  }
  public void vest(){
    System.out.println("go cave and put on his equipment");
  }
}

public class Ironman extends SuperHero{
  public void power(){
    System.out.println("energy repulsors");
  }
  public void vest(){
    System.out.println("take out his box and put on his equipment");
  }
}

public class Test{
  public static void main(String[] args){
    SuperHero sh1 = new Spiderman();
    SuperHero sh2 = new Batman();
    SuperHero sh3 = new Ironman();

    sh1.vest(); //"simply change his equipment"
    sh2.vest(); //"go cave and put on his equipment"
    sh3.vest(); //"take out his box and put on his equipment"
  }
}


[細節]

[延伸]

[參考]
1. 良葛格學習筆記

如有錯誤,請不吝指教

多型Polymorphism

[概念]
多型作用於Instance Method上,不作用在Class Method、Class Variable和Instance Variable上

目的是為了在執行時期讓Sub Class的物件動態地選擇合適的method

pic 1: polymorphism

//Base Class
public class SuperHero{
  power(){
    System.out.println("superhuman strength");
  }
  fortune(){
    System.out.println("fortune type");
  }
}

//Sub Class
public class Spiderman extends SuperHero{
  power(){
    System.out.println("spin a web");
  }
}

public class Test{
  public static void main(String[] args){
    SuperHero sh = new Spiderman();
    sh.power();    //"spin a web"
    sh.fortune();  //"fortune type"
  }
}

變數sh宣告為SuperHero型態(稱為型式型態),但實際型態卻為Spiderman

sh.power( )會執行實際型態的method,也就是
power(){
    System.out.println("spin a web");
}


[細節]

[延伸]
抽象類別Abstract Class
介面Interface


[參考]
1. O'Reilly技術短文 OO

如有錯誤,請不吝指教

繼承Inheritance

[概念]
物件導向重要的概念之一

Sub Class繼承Base Class

//Base Class
public class Human{
  height
  weight
  
  walk(); 
  eat();  
}

//Sub Class
public class Ken extends Human{
  code();
  playguitar();
}

一般來說,Instance Variable、Instance Method、Class Variable、Class Method都會被繼承


[細節]
public, protected, private, package的影響

Base Class和Sub Class的Instance Variable名稱相同時會發生甚麼事

Method Overriding

[延伸]
多型Polymorphism
抽象類別Abstract Class
介面Interface

[參考]
1. O'Reilly技術短文 OO
2. 良葛格學習筆記

如有錯誤,請不吝指教

2013年1月11日 星期五

[Q1-1] Longest Plateau

[SOURCE]
名題精選百則_題1.1

[INPUT]
number set which is sorted in increment order
ex. 1,2,2,3,3,3,4,5,5,6

[OUTPUT]
find the longest plateau
ex. 3,3,3

[THINK]

[SCv1]
    //arr is sorted array
    //maxL is result length
    //maxN is result element
    int i=0,tmpL=0,tmpN=0;
    int maxL=0,maxN=0;

    for(i=0;i<10;i++){
      if(i==0){
        tmpL=1;
        tmpN=arr[i];
      }
      else{ 
        if(arr[i]==arr[i-1]){
          tmpL++;
        }
        else{
          if(tmpL>maxL){
            maxL=tmpL;
            maxN=arr[i-1];
            tmpL=1;
          }
          else{
            tmpL=1;
            tmpN=arr[i];     
          }     
        }
      }
    }

[SCv2]