搜尋此網誌

2015年7月14日 星期二

Is Power of Two

public class IsPowerOfTwo {

 public boolean isPowerOfTwo(int n) {
  {
   while (((n % 2) == 0) && n > 1)
    /* While x is even and > 1 */
    n /= 2;
   return (n == 1);
  }
 }
}

Count Primes

package leetcode;

public class Solutions {
     public int countPrimes(int n) {
          if (n <<= 2)
               return 0;
          boolean[] primes = new boolean[n];
          for (int i = 2; i << n; i++)
               primes[i] = true;
          for (int i = 2; i <<= Math.sqrt(n - 1); i++) {
               if (primes[i]) {
                    for (int j = i + i; j << n; j += i)
                         primes[j] = false;
               }
          }
          int count = 0;
          for (int i = 2; i << n; i++)
               if (primes[i])
                    count++;
          return count;
     }
}

2015年7月8日 星期三

Contains Duplicate


import java.util.Arrays;
public class Solution {
    public boolean containsDuplicate(int[] nums) {
        if (nums.length > 1) {
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i] == nums[i + 1]) {
                    return true;
                }
            }
        }
        return false;
    }
}

Invert Binary Tree solution


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null){
            return root;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        
        if(root.left != null){
            invertTree(root.left);
        }
        if(root.right != null){
            invertTree(root.right);
        }
        return root;
    }
}


2015年6月21日 星期日

Java 8 新功能概述

Default Methods


以前如果為interface加入新的方法, 那麼所有的實作類別都必須要實作這個新方法.

有了default method這個功能後, 只要在新方法前面加上default關鍵字,然後實做它的內容.

那麼那些之前的實作類別, 也都可以使用這個新方法, 而不必自己實作. 範例如下:

package lang;

public class DefaultMethodDemo {

 public static void main(String[] args){
  
  new Client().run();
  new Client().runDefault();
  
 }
}

interface Run {
 public void run();
 default void runDefault(){
  System.out.println("default run .");
 }
}

class Client implements Run {

 @Override
 public void run() {
  System.out.println("client run .");
 }
 
}

Type Annotaion

Java 8之前, Annotaion只能用在宣告上 , 例如宣告類別, 或是宣告方法 , 或是宣告變數.

而Java 8對於 Annotaion的支援範圍擴大到 , 只要有使用到type的地方, 都可以使用Annotaion.

  1. 型別創建的時候 
    
    new @Interned MyObject();
  2. 轉型的時候
    myString = (@NonNull String) str;
3. implements 子句時:
          
class UnmodifiableList implements
        @Readonly List<@Readonly T> { ... }

4. 丟出例外的宣告:
void monitorTemperature() throws
        @Critical TemperatureException { ... }




Repeating Annotations.

Java 8 可以在同一個宣告上, 重複使用同一種Annotation.

@Schedule(dayOfMonth="last")
@Schedule(dayOfWeek="Fri", hour="23")
public void doPeriodicCleanup() { ... }

代表這個method, 有兩種不同的的排程 , 分別用同一種Annotation,賦予不同值來表示.



Java Lambda 簡單介紹.

Lambda 是Java 8 支援的新功能 . 對於簡化functional interface的實作很方便. 所謂的functional

interface就是只有一個public method的interface. 下面是範例.


package lang;

public class LambdaDemo {

 public static void main(String[] args) {
  LambdaDemo ld = new LambdaDemo();
  
  /**
   * Using Lambda
   */
  ld.lambdaTest(t -> {
   System.out.println("a lambda run");
  });
  
  /**
   * Without using Lambda
   */
  ld.lambdaTest(new Test(){

   @Override
   public void run(Test t) {
    System.out.println("not a lambda run");
   }
   
  });
 }

 public void lambdaTest(Test t) {
  t.run(t);
 }

}

interface Test {
 public void run(Test t);
}

以前必須要把run()的method signature寫一遍,然後裡面是實作,有了Lambda之後, 諸如此類的實作就可以大幅簡化了.

2015年2月12日 星期四

回朔法(Backtracking)求所有數字的排列


public class NumberPermutation {

    public static void main(String[] args){
      /*
      * 123,132,213,231,312,321
      */
     int[] numbers = new int[] {1,2,3};
     backTrackPermutation(numbers ,0 ,2);
    }
    
    private static void backTrackPermutation(int[] numbers,int startIdx , int endIdx){
 
 if(startIdx == endIdx){
     printArray(numbers);
 }else{
     for(int j = startIdx; j <= endIdx ; j++){
  swap(numbers, startIdx , j);
  backTrackPermutation(numbers ,startIdx+1, endIdx);
  swap(numbers, startIdx , j);
     }
     
 }
 
    }
    
    private static void swap(int[] numbers,int idx1 , int idx2){
 int temp = numbers[idx1];
 numbers[idx1] = numbers[idx2];
 numbers[idx2] = temp;
    }
    
    private static void printArray(int[] numbers){
 for(int i = 0 ; i < numbers.length ; i++){
     System.out.print(numbers[i]);
 }
 System.out.println();
    }
    
}

2015年2月6日 星期五

用動態規劃演算法計算費波南西數列

動態規劃比遞迴寫法快好多.

public static void main(String[] args){
 long start = System.currentTimeMillis();
 System.out.println(new Fib().calFib(40));
 long end = System.currentTimeMillis();
 System.out.println("Dynamic Programming :" + (end - start) +" million seconds");
 start = System.currentTimeMillis();
 System.out.println(new Fib().recurFib(40));
 end = System.currentTimeMillis();
 System.out.println("Recurrence :" + (float)(end - start) +" million seconds");
 
    }
    
    int calFib(int toNumber){
  int[] value = new int[100];
  value[1] = 1;
  for(int i = 1; i <= toNumber ; i++){
      value[i+1] = value[i] + value[i-1];
  }
  return value[toNumber];
    }
    
    int recurFib(int toNumber){
 if(toNumber == 0){
     return 0;
 }else if(toNumber == 1){
     return 1;
 }else{
     toNumber -= 1;
     return recurFib(toNumber)+recurFib(toNumber-1);
 }
    }