剑指Offer_5

发表于 2017-11-30 | 分类于剑指Offer

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

解题思路

两个栈，一个主栈，一个辅助栈。

主栈：负责pop出队操作
副栈：负责push入队操作

因为队列是先进先出，而栈是后进先出，两者顺序相反，所以利用在数据在两个栈里面走一遍，实现了队列的先进先出的顺序。当主栈里的元素为空时，就可以去副栈里索取数据。

import java.util.Stack;

public class Solution {
    private Stack<Integer> mainStack = new Stack<>();
    private Stack<Integer> auxStack = new Stack<>();

    public Integer pop(){
        if(mainStack.isEmpty()){
            while (!auxStack.isEmpty()){
                mainStack.push(auxStack.pop());
            }
        }
        if(mainStack.isEmpty()){
            return Integer.MIN_VALUE;
        }
        else{
            return mainStack.pop();
        }
    }

    public void push(Integer item){
        auxStack.push(item);
    }

}

剑指Offer_4

发表于 2017-11-30 | 分类于剑指Offer

题目

重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路

前序遍历和中序遍历的数组

通过前序遍历数组找各子树的根节点，中序遍历数组找各子树的左右子树包含的节点

根据图上的两个数组，我们可以知道该二叉树的根节点是1，左子树包含的节点有2,4,7，同理可得右子树节点们。

那么现在就可以在2, 4, 7继续上述的操作，进行递归操作，同理可得右子树。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre == null || in == null){
            return null;
        }
        return helper(pre, 0, pre.length-1, in, 0, in.length-1);
    }
    
    public TreeNode helper(int []pre, int pre_lo, int pre_hi, int []in, int in_lo, int in_hi){
        if(pre_lo > pre_hi || in_lo > in_hi){
            return null;
        }
        TreeNode root = new TreeNode(pre[pre_lo]);
        
        //for循环，目的是找出子树根节点在中序遍历数组中的位置，以此来分割左右子树
        for(int i = in_lo; i <= in_hi; ++i){
            if(pre[pre_lo] == in[i]){
            	//pre_lo为子树根节点，并且是前序遍历数组的第一位
            	//i为子树根节点在中序遍历数组的位置
            	//以此来划分两个数组的左右子树节点们
            	//前序遍历数组：左子树[pre_lo+1, i-in_lo+pre_lo], 右子树[i-in_lo+1+pre_lo, pre_hi]
            	//中序遍历数组：左子树[in_lo, i-1], 右子树[i+1, in_hi]
                root.left =  helper(pre, pre_lo+1, i-in_lo+pre_lo, in, in_lo, i-1);
                root.right = helper(pre, i-in_lo+1+pre_lo, pre_hi, in, i+1, in_hi);
            }
        }
        return root;
    }
}

剑指Offer_3

发表于 2017-11-30 | 分类于剑指Offer

题目

输入一个链表，从尾到头打印链表每个节点的值。

解题思路

这道题其实比反转链表还要简单，只要取出链表的节点值，然后插入到ArrayList的头部即可。

如果是逆转链表，就把ArraryList遍历，构造链表。

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> intList = new ArrayList<>();
        
        while(listNode != null){
            intList.add(0, listNode.val);
            listNode = listNode.next;
        }
        return intList;
    }
}

剑指Offer_2

发表于 2017-11-30 | 分类于剑指Offer

题目

请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

解题思路

解法一：Java API，感觉作弊了…

public class Solution {
    public String replaceSpace(StringBuffer str) {
        return str.toString().replaceAll("\\s", "%20");
    }
}

解法二：重构形参str，很直接地将空格替换为%20，替换时候可以从后往前进行替换，就可以不必再次复制str，节省了空间。

public class Solution {
    public String replaceSpace(StringBuffer str) {
    	if(str == null || str.length() == 0){
            return "";
        }
        int whiteSpace = 0;
        int old_length = str.length();
        
        for(int i = 0; i < old_length; ++i){
            if(str.charAt(i) == ' '){
                ++whiteSpace;
            }
        }
        
        int new_length = old_length + whiteSpace * 2;
        int n = new_length - 1;
        str.setLength(new_length);
        for(int i = old_length - 1 ; i >= 0; --i){
            if(str.charAt(i) == ' '){
                str.setCharAt(n--, '0');
                str.setCharAt(n--, '2');
                str.setCharAt(n--, '%');
            }
            else{
                str.setCharAt(n--, str.charAt(i));
            }
        }
        return str.toString();
    }
}

剑指Offer_1

发表于 2017-11-30 | 分类于剑指Offer

题目

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路

在一个以A[0][0]为起点，往X和Y方向增长的二维数组中，找一个特定的target。
为了降低算法平均的复杂度，选取+45°角的对角线两个顶点的任一一个为起点，这个选取左下角。

当A[x][y] == target 返回true
当A[x][y] < target，++y扩大A[x][y]的值，反之，缩小其值。

public class Solution {
    public boolean Find(int target, int [][] array) {
		if(array == null || array.length == 0 || array[0].length == 0){
            return false;
        }
        int row = array.length;
        int col = array[0].length;
        int x = --row;
        int y = 0;
        
        for( ; x >= 0 && y < col; ){
            if(array[x][y] == target){
                return true;
            }
            else if(array[x][y] < target){
                ++y;
            }
            else{
                --x;
            }
        }
        return false;
    }
}

Java并发编程的艺术学习笔记(2)

发表于 2017-10-31 | 分类于并发

Java并发机制的底层实现原理

在多线程并发编程中，volatile和synchronized都扮演者重要角色，volatile是轻量级锁，它在多处理器开发中保证了共享变量的“可见性”。可见性的意思是当一个线程修改了一个共享变量时，另一个线程能够读到这个修改的值。

如果volatile运用得当，它比synchronized的的使用和执行成本更低，因为它不会引起线程的上下文切换和调度。

volatile

Java语言提供volatile，如果一个字段被声明成volatile，Java线程内存模型确保所有线程看到这个变量的值是一致的。

实现原理

有volatile变量修饰的共享变量进行写操作的时候会多出一行汇编代码。

instance =  new Instance();	//instance是volatile变量
//转成汇编代码如下
0x01a3de1d: movb $0x0, 0x1104800(%esi);
0x01a3de24: lock addl $0x0, (%esp);

Lock前缀指令在多核处理器下会引发两件事情。

a. 将当前处理器的缓存行数据写回系统的内存

b. 这个写回内存的操作，会使其它CPU里缓存了该内存地址的数据无效

synchronized

重量级锁synchronized实现同步的基础：Java中每一个对象都可以作为锁。

a. 对于普通同步方法，锁是当前的实例对象

b. 对于静态同步方法，锁是当前类的Class对象

c. 对于同步方法块，锁是Synchonized括号里配置的对象

原子操作的实现原理

比较并交换(CAS)：CAS操作需要输入两个数值，一个旧值（期望操作前的值）和一个新值，在操作期间先比较旧值有没有发生变化，如果没有发生变化，才交换成新值，否则不交换。

处理器实现原子操作：

a. 通过总线锁保证原子性

b. 使用缓存锁保证原子性

总线锁把CPU和内存之间的通信锁住了，其他处理器不能操作其他的内存地址的数据，开销较大。

用循环CAS实现原子操作

在Java中可以使用锁和循环CAS实现原子操作

JVM中的CAS操作就是利用了处理器提供的CMPXCHG指令实现。自旋CAS实现的基本思路就是循环进行CAS操作直到成功为止。

使用自旋CAS实现的原子操作

package com.myConcurrent.Chapter2;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
public class Automic {
    private AtomicInteger atomicInteger = new AtomicInteger(0);
    private int i = 0;
    //非线程安全的计数器
    private void unSafeCount(){
        ++i;
    }
    //使用CAS实现线程安全的计数器
    private void safeCount(){
        for( ; ; ){
            int old = atomicInteger.get();
            boolean suc = atomicInteger.compareAndSet(old, ++i);
            if(suc){
                break;
            }
        }
    }
    public static void main(String []args){
        final Automic automic = new Automic();
        List<Thread> threadList = new ArrayList<>(600);
        long start = System.currentTimeMillis();
        for(int j = 0; j < 100; ++j){
            Thread t = new Thread(new Runnable() {
                @Override
                public void run() {
                    for(int i = 0; i < 1000000; ++i){
                        automic.unSafeCount();
                        automic.safeCount();
                    }
                }
            });
            threadList.add(t);
        }
        for(Thread t: threadList){
            t.start();
        }
        //等待所有线程执行完成
        for(Thread t: threadList){
            try{
                t.join();
            }catch (InterruptedException e){
                e.printStackTrace();
            }
        }
        System.out.println("unSafe: " + automic.i);
        System.out.println("  Safe: " + automic.atomicInteger.get());
        System.out.println("time(ms): " + String.valueOf(System.currentTimeMillis() - start));
    }
}

CAS实现原子操作的三大问题

a. ABA问题。从JDK1.5开始，提供AtomicStampedReference来解决问题。这个类的CompareAndSet方法的作用是首先检查当前引用是否等于预期引用，并且检查版本号是否等于预期版本。

public boolean compareAndSet(
	V	expectedReference,
	V	newReference,
  	int	expectedStamp,
  	int	newStamp 
)

b. 循环时间长，开销大

c. 只能保证一个共享变量的原子操作。从JDK1.5开始，提供AtomicReference类来保证引用对象之间的原子性，就可以把多个变量塞进一个对象进行原子操作。

比较

锁	优点	缺点	适用场景
轻量级锁	提高线程响应速度	会空旋，消耗CPU	同步块执行速度快
重量级锁	提高吞吐量	线程阻塞	同步块执行速度慢

Java并发编程的艺术学习笔记(1)

发表于 2017-10-31 | 分类于并发

并发编程的挑战

减少上下文切换

a. 无锁并发编程。多线程竞争锁的时候，会引起上下文切换，可以用一些办法来避免使用锁，如将数据的ID按照Hash算法取模分段，不同的线程处理不同段的数据。

b. CAS算法。Java的Atomic包使用CAS算法来更新数据，不需要加锁

c. 使用最少的线程，避免创建不需要的线程。

d. 协程。在单线程里面实现多任务调度，并在单线程里维持多个任务间的切换。

避免死锁

a. 避免一个线程同时获取多个锁

b. 避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源

c. 尝试使用定时锁，使用lock.tryLock(timeout) 来代替使用内部锁的机制

d. 对于数据库锁，加锁和解锁必须在一个数据库连接里，否则会出现解锁失效

设计模式--迭代器模式

发表于 2017-10-28 | 分类于设计模式

定义：提供一种方法访问一个容器对象中的每个元素，而又不暴露该对象的内部细节。

迭代器模式的运用

提到迭代器，首先它是与集合相关的，集合可以看作是一个可以包含对象的容器。例如List，Set，Map，迭代器的作用就是把容器中的对象一个接一个地遍历出来。

import java.util.ArrayList;
import java.util.Iterator;
public class IteratorPattern {
    public static void main(String[] args){
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0 ;i < 11; ++i){
            list.add(i);
        }
	
        Iterator it = list.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }
    }
}

迭代器的实现

迭代器模式的结构：

抽象容器，一般是一个接口，提供一个iterator() 方法，如java中的Collection、List和Set等类的接口。
具体容器，容器的实现类，如ArrayList, LinkedList和HashSet等。
抽象迭代器，定义遍历集合中的所需要的方法，一般包含三个方法。

>
next() 取得迭代器中准备的下一个元素
hasNext() 判断是否遍历结束
remove() 将迭代器的下一个元素移除

4.具体迭代器，实现抽象迭代器的方法。

抽象迭代器

interface MyIterator{
    public Object next();
    public boolean hasNext();
    public void remove();
}

具体迭代器

class ContreteIterator implements MyIterator{
    private List list;
    private int cursor;
    public ContreteIterator(List list){
        this.list = list;
        cursor = 0;
    }
    @Override
    public Object next(){
        if(cursor != list.size()){
            return list.get(cursor++);
        }
        return null;
    }
    @Override
    public boolean hasNext(){
        if(cursor == list.size()){
            return false;
        }
        return true;
    }
    @Override
    public void remove() {
        if(cursor != list.size()){
            list.remove(cursor);
        }
    }
}

抽象集合类

interface Container<T>{
    public void add(T obj);
    public void remove(T obj);
    public MyIterator myIterator();
}

集合类的实现

class ContreteContainer<T> implements Container<T>{
    private List<T> list;
    public ContreteContainer(){
        list = new ArrayList<T>();
    }
    @Override
    public void add(T obj){
        list.add(obj);
    }
    @Override
    public void remove(T obj){
        list.remove(obj);
    }
    @Override
    public MyIterator myIterator(){
        return new ContreteIterator(this.list);
    }
}

测试

public class IteratorPattern {
    public static void main(String[] args){
        ContreteContainer<Integer> contreteContainer = new ContreteContainer<>();
        for(int i = 1; i <= 10; ++i){
            contreteContainer.add(i);
        }
        MyIterator it = contreteContainer.myIterator();
        while(true){
           if(it.hasNext()){
               System.out.println(it.next());
           }
           if(it.hasNext()){
               it.remove();
           }
           else{
               break;
           }
        }
    }
}

总结

优点：
对于hsah表来说，使用迭代器的遍历会变得简单。
可以提供正反两种方向的遍历顺序

缺点：
对于简单数组或者有序列表，用迭代器反而会比较麻烦。比如对ArrayList一般使用for循环和get进行遍历。

设计模式--代理模式

发表于 2017-10-28 | 分类于设计模式

定义

代理模式：为其他对象提供一种代理以控制对这个对象的访问。

代理模式是指客户端并不直接调用实际的对象，而是通过调用代理，来间接的调用实际的对象。
为什么要采用这种间接的形式来调用对象呢？一般是因为客户端不想直接访问实际的对象，或者访问实际的对象存在困难，因此通过一个代理对象来完成间接的访问。

静态代理模式

代理模式中的角色：

抽象主题角色(Subject)：声明了目标对象和代理对象的共同接口，这样一来任何可以使用目标对象的地方都能用代理对象。
具体主题角色(RealSubject)：称为委托角色或被代理角色。实现了目标对象。
代理主题角色(Proxy)：也叫委托类、代理类。代理对象内部含有目标对象的引用，从而可以在任何时候操作目标对象。代理对象提供一个与目标对象相同的接口，以便可以在任何时候代替目标对象。

Subject

1
2
3

interface MySubject{
    public void operate();
}

RealSubject

class RealSubject implements MySubject{
    @Override
    public void operate(){
        System.out.println("RealSubject");
    }
}

Proxy

class Proxy implements MySubject{
    private MySubject mySubject;
    @Override
    public void operate(){
        if(mySubject == null){
            mySubject = new RealSubject();
        }
        System.out.println("0707, this is Proxy: ");
        this.mySubject.operate();
        System.out.println("over");
    }
}

来自客户端的调用

public class ProxyPattern {
    public static void main(String[] args){
        MySubject mySubject = new Proxy();
        mySubject.operate();
    }
}

输出结果

1
2
3

0707, this is Proxy: 
RealSubject
over

从上面的例子可以看出来，代理对象将客户端的调用派给目标对象，在调用目标对象的方法之前和之后都可以执行特定操作。

动态代理模式

在实现动态代理模式之前，首先了解一下以下内容：

Jdk通过java.lang.reflect.Proxy包来支持动态代理，在Java中要创建一个代理对象，必须调用Proxy类的静态方法newProxyInstance，该方法的原型如下：

1	Object Proxy.newProxyInstance(ClassLoader loader, Class<?> []interfaces, InvocationHandler handler) throws Exception;

loader：类加载器，使用null使用默认的加载器
interfaces：接口或对象的数组，代理对象和真实对象共有的接口
handler：调用处理器，必须是实现了InvocationHandler接口的对象，其作用是定义代理对象中需要执行的具体操作。

InvocationHandler接口中只有一个方法invoke，它的作用就跟Runnable中的run方法类似，定义了代理对象在执行真实对象的方法时所希望执行的动作。其原型如下：

1	Object invoke(Object proxy, Method method, Object[] objs) throws Throwable;

proxy：表示执行这个方法的代理对象
method：表示真实对象实际需要执行的方法
args：表示真实对象实际执行方法时所需的参数

Subject

interface MySubject{
    String CatSounds();
    String DogSounds();
    String SnakeSounds();
}

RealSubject1 && RealSubject2 ……

class RealSubject1 implements MySubject{
    @Override
    public String CatSounds(){
        return "miaomiaomiao~~~~";
    }
    @Override
    public String DogSounds(){
        return "wangwangwang~~~～";
    }
    @Override
    public String SnakeSounds(){
        return "sisisi~~~";
    }
}
class RealSubject2 implements MySubject{
    @Override
    public String CatSounds(){
        return "niaoniaoniao~~~";
    }
    @Override
    public String DogSounds(){
        return "aoaoao~~~~";
    }
    @Override
    public String SnakeSounds(){
        return "ssssss~~~~";
    }
}

Proxy

class ProxyHandler implements InvocationHandler {
    private Object object;
    public Object newProxyInstance(Object realObj){
        this.object = realObj;
        Class<?> classType = this.object.getClass();
        return Proxy.newProxyInstance(classType.getClassLoader(), classType.getInterfaces(), this);
    }
    @Override
    public Object invoke(Object proxy, Method method, Object[] args) throws Throwable{
        System.out.println("0707, this is AnimalProxy");
        Object object = method.invoke(this.object, args);
        System.out.println(object);
        return object;
    }
}

来自客户端的调用

public class ProxyPattern {
    public static void main(String[] args){
        MySubject mySubject1 = (MySubject) new ProxyHandler().newProxyInstance(new RealSubject1());
        mySubject1.CatSounds();
        MySubject mySubject2 = (MySubject) new ProxyHandler().newProxyInstance(new RealSubject2());
        mySubject2.DogSounds();
    }
}

动态代理模式通过使用反射，可以在运行期决定加载哪个类，避免了一个类对应一个代理的问题；同时，通过统一的invoke方法，统一了代理类对原函数的处理过程，使用动态代理很大程度上减少了重复的代码，降低了维护的复杂性和成本。

设计模式--观察者模式

发表于 2017-10-27 | 分类于设计模式

定义

观察者模式定义了对象之间的一对多的依赖，这样一来，当一个对象改变状态时，它的所有依赖者都会收到通知并自动更新。
实现观察者模式最常用的方法是用Subject与Observer接口的类设计。

观察者模式的实现

发布者接口

interface Subject{
    public void registerObserver(Observer o);
    public void removeObserver(Observer o);
    public void notifyObservers();
}

观察者接口

1
2
3

interface Observer{
    public void update(String message);
}

发布者具体实现

class OfficialCount implements Subject{
    private ArrayList<Observer> observers;	//观察者列表
    private String content;	//发布的内容
    public OfficialCount(){
        observers = new ArrayList<>();
    }
	//添加观察者
    public void registerObserver(Observer o){
        if(!observers.contains(o)){
            observers.add(o);
        }
    }
	//移除观察者
    public void removeObserver(Observer o){
        if(observers.contains(o)){
            observers.remove(o);
        }
    }
	//通知观察者
    public void notifyObservers(){
        for(Observer o: observers){
            o.update(content);
        }
    }
	//发布新消息内容
    public void releaseMessage(String content){
        this.content = content;
        notifyObservers();
    }
}

观察者具体实现

class User implements Observer{
    private Subject subject;
	//新用户关注公众号的时候就注册到发布者
    public User(Subject subject){
        this.subject = subject;
        subject.registerObserver(this);
    }
	//更新内容，message来自于发布者
    public void update(String message){
        System.out.println("订阅号\n" + message);
    }
}

客户端调用

public class ObserverPattern {
    public static void main(String[] args){
        OfficialCount officalCount = new OfficialCount();
        Observer o1 = new User(officalCount);
        Observer o2 = new User(officalCount);
        officalCount.notifyObservers();
        officalCount.releaseMessage("有生之年系列 猎人不休刊了");
        officalCount.releaseMessage("时事热评 台湾回归啦");
    }
}

总结

优点：
解除耦合，让耦合的双方都依赖于抽象，从而使得各自的变换都不会影响另一边的变换。

缺点：
在应用观察者模式时需要考虑一下开发效率和运行效率的问题，程序中包括一个被观察者、多个观察者，开发、调试等内容会比较复杂，而且在Java中消息的通知一般是顺序执行，那么一个观察者卡顿，会影响整体的执行效率，在这种情况下，一般会采用异步实现。

使用场景：

关联行为场景，需要注意的是，关联行为是可拆分的，而不是“组合”关系。
事件多级触发场景。
跨系统的消息交换场景，如消息队列、事件总线的处理机制。