Design Pattern

Singleton

Singleton ensures that at most one instance of a class exists at any given time.

public class SingletonDemo {
    private static SingletonDemo instance = null;
    //set the constructor private
    private SingletonDemo() {

    }

    public static synchronized SingletonDemo getInstance() {
        if (instance == null) {
            instance = new SingletonDemo();
        }
        return instance;
    }
}

Factory

The implementation is really simple

• The client needs a product, but instead of creating it directly using the new operator, it asks the factory object for a new product, providing the information about the type of object it needs.
• The factory instantiates a new concrete product and then returns to the client the newly created product(casted to abstract product class).
• The client uses the products as abstract products without being aware about their concrete implementation.

The advantage is obvious: New shapes can be added without changing a single line of code in the framework(the client code that uses the shapes from the factory). As it is shown in the next sections, there are certain factory implementations that allow adding new products without even modifying the factory class.

public class ProductFactory{
    public Product createProduct(String ProductID){
        if (id==ID1)
            return new OneProduct();
        if (id==ID2) return
            return new AnotherProduct();
        // so on for the other Ids
  
        return null; //if the id doesn't have any of the expected values
    }
    
}

CC150: Tree to LinkedList

Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth (e.g., if you have a tree with depth D, you'll have D linked lists).

第一眼感觉就是level by level，用BFS就行了。

但是实际可以用类似一直pre-order的顺序遍历，但是我们需要一个额外的变量level，来记录当前点是对应第几层的。
No BFS version

public class Solution {
    public ArrayList<LinkedList<TreeNode>> create(TreeNode root) {
     ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
     createHelp(root, lists, 0);
     return lists;
    }

    private void createHelp(TreeNode root, ArrayList<LinkedList<TreeNode>> lists, int level) {
     if (root == null) {
      return;
     }

     if (lists.size() == level) {
      //for current level, we didn't create a new list
      LinkedList<TreeNode> list = new LinkedList<TreeNode>();
      list.add(root);
      lists.add(list);
     } else {
      LinkedList<TreeNode> list = lists.get(level);
      list.add(root);
     }

     createHelp(root.left, lists, level + 1);
     createHelp(root.right, lists, level + 1);
    }

    public ArrayList<LinkedList<TreeNode>> create(TreeNode root) {
     ArrayList<LinkedList<TreeNode>> lists = new ArrayList<LinkedList<TreeNode>>();
     if (root == null) {
      return lists;
     }
 
     Queue<TreeNode> queue = new LinkedList<TreeNode>();
     queue.offer(root);
     while(!queue.isEmpty()) {
      int size = queue.size();
      LinkedList<TreeNode> list = new LinkedList<TreeNode>();
      for (int i = 0; i < size; i++) {
       TreeNode cur = queue.poll();
       if (cur.left != null) {
        queue.offer(cur.left);
       }
       if (cur.right != null) {
        queue.offer(cur.right);
       }
       list.add(cur);
      }
      lists.add(list);
     }
     return lists;
    }
}

Java多线程入门(三) H2O

题目：  实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个 call O的线程返回（产生一个水分子），其他的都block。

package multiThreads;

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

class H2O {
    int Hcount;
    int Ocount;
    Lock lock = new ReentrantLock();
    Condition cH = lock.newCondition();
    Condition cO = lock.newCondition();
 
    public void H() {
        lock.lock();
        Hcount++;
        if (Hcount >= 2 && Ocount >= 1) {
            Hcount -= 2;
            Ocount -= 1;
            cH.signal();
            cO.signal();
            System.out.println("H2O");
        } else {
            try {
                cH.await();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        lock.unlock();
    }
 
    public void O() {
        lock.lock();
        Ocount++;
        if (Hcount >= 2 && Ocount >= 1) {
            Hcount -= 2;
            Ocount -= 1;
            cH.signal();
            cH.signal();
            System.out.println("H2O");
        } else {
            try {
                cO.await();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        lock.unlock();
    }
}

class Hclass implements Runnable {
    private H2O obj;
 
    public Hclass(H2O obj) {
        this.obj = obj;
    }
    @Override
    public void run() {
        // TODO Auto-generated method stub
        obj.H();
    }
 
}

class Oclass implements Runnable {
    private H2O obj;
 
    public Oclass(H2O obj) {
        this.obj = obj;
    }
    @Override
    public void run() {
        // TODO Auto-generated method stub
        obj.O();
    }
 
}

public class H2Oexample {
    final private static H2O obj = new H2O();
 
    public static void main(String[] args) {
        for (int i = 0; i< 10; i++) {
            new Thread(new Hclass(obj)).start();
        }
        for (int i = 0; i< 5; i++) {
            new Thread(new Oclass(obj)).start();
        }
    }
}

Java多线程入门(二) Synchronized and Lock

转自Tia—Java synchronized 和 lock
一个process里面所有的threads是共享同一块memory space的， 所以有时候就需要去避免两个threads同时修改一块resource所引起的问题。 Java里引入Synchronized 和 Lock的概念。

1), synchronized method

?

1 2 3 4 5

class Myobject{   public synchronized void foo(String name){    .......................................   } }

synchronized 关键字限制的是Myobject这个类的一个对象的多个threads不能访问同一个资源，不同对象的线程是可以同时访问的。

2), 一个class多个synchronized 方法：

?

1 2 3 4 5 6 7 8

class Myobject{   public synchronized void bar(String name){    。。。。。。。。。   }   public synchronized void foo(String name){    。。。。。。。。。   } }

Java的每个对象都有一个锁(lock或monitor), 当一个thread访问synchronized方法时， 该对象就被锁住了， 在解锁(执行完毕或抛出异常)之前， 该对象的任何thread都不能再访问其他的synchronized的方法。注意：是对象被上锁，而不是一个synchronized方法一个锁。

3), Synchronized 和 Static Synchronized

?

1 2 3 4 5

class Myobject{    public static synchronized void bar(String name){     。。。。。。。。。    } }

静态变量时属于class的，不是属于对象的， 若一个thread访问static synchronized 方法时， 则这个class被上锁，在解锁之前，这个class的所有对象的所有thread都不能访问该方法和其他synchronized的方法。

4), Synchronized Block

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Myobject{   public void foo(String name){     synchronized(this){      。。。。。。。。。     }   } } class Myobject{   private AnotherClass object = new AnotherClass();   public void foo(String name){     synchronized(object){      。。。。。。。。。     }   } }

Block用来同步一段代码， 和synchronized method一样，对于每个对象，它只有一个thread可以访问Synchronized block里面的东西。注意synchronized里面的object可以是任意类的object。

5), Locks

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; class Myobject {   private Lock lock;   public Myobject(){     lock = new ReentrantLock();   }   public void foo(){     lock.lock();       ........     lock.unlock();  } }

和synchronized类似，一个对象在某一个时间只能有一个thread holds the lock。 避免了lock之间的资源被其他thread随意修改。 比较典型的例子是ATM取款存款机。
同时我们也可以用Lock生成各种condition，方便我们进行操作