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，方便我们进行操作