Offer06（从尾到头打印链表）

发表于 2019-07-16 | 分类于算法，剑指offer

题目：

　　输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

思路：

　　倒序相关的题很容易想到递归或者利用栈。

代码：

// 递归
   public ArrayList<Integer> printListFromTailToHead2(ListNode listNode) {
   	ArrayList<Integer> arrayList = new ArrayList<>();
   	return help(listNode, arrayList);
   }
   public ArrayList<Integer> help(ListNode listNode,ArrayList<Integer> arrayList) {
   	if (listNode != null) {
		help(listNode.next, arrayList);
		arrayList.add(listNode.val);
	}
   	return arrayList;
   }
   // 辅助栈
   public ArrayList<Integer> printListFromTailToHead3(ListNode listNode) {
   	ArrayList<Integer> arrayList = new ArrayList<>();
   	Deque<ListNode> stack = new LinkedList<>();
   	while(listNode != null) {
   		stack.push(listNode);
   		listNode = listNode.next;
   	}
   	while(!stack.isEmpty()) {
   		arrayList.add(stack.pop().val);
   	}
   	return arrayList;
   }

复杂度分析：

递归：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

辅助栈：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(n)。

Offer05（替换空格）

发表于 2019-07-16 | 分类于算法，剑指offer

题目：

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

思路：

　　最开始想到的思路是从头到尾遍历字符串，遇到字符串即替换，并插入%20，但字符串插入需要将后面的所有字符后移，算法复杂度较高。为优化时间复杂度，可以先统计出
替换空格后的字符串长度，然后从后到前插入。

代码：

// 从前往后
public static String replaceSpace1(StringBuffer str) {
   	int i = 0;
   	while(i < str.length()) {
   		if (str.charAt(i) == ' ') {
			str.replace(i, i+1, "%");
			str.insert(i+1, "20");
		}
   		i++;
   	}
   	return str.toString();
   }
// 从后往前
public static String replaceSpace2(StringBuffer str) {
	int count = 0;
	for(int i = 0;i < str.length();i++) {
		if (str.charAt(i) == ' ') {
			count++;
		}
	}
	int newLength = count*2 + str.length();
	int p1 = str.length() - 1;
	int p2 = newLength - 1;
	str.setLength(newLength);
	while(p1 >=0 && p2 >= 0) {
		if (str.charAt(p1) == ' ') {
			str.setCharAt(p2--, '0');
			str.setCharAt(p2--, '2');
			str.setCharAt(p2--, '%');
			p1--;
		}else {
			str.setCharAt(p2, str.charAt(p1));
			p1--;
			p2--;
		}
	}
	return str.toString();
}

复杂度分析：

从前往后：

　　时间复杂度：
　　　　O(n**2)。
　　空间复杂度：
　　　　O(1)。

从后往前：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

总结：

　　在合并数组或者字符串时，如果从前往后需要重复移动后面数字，可以考虑从后往前进行合并。这样能减少数字移动的次数，大大增加效率。

Offer04（二维数组中的查找）

发表于 2019-07-16 | 分类于算法，剑指offer

题目：

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

思路：

　　此题很容易想到通过每行进行二分查找来解题，但此法时间复杂度较高。通过从右上角开始查找，如果该处数字大于要查找的数字，则可以排除该列，如果该处数字小于要
查找的数字，则可以排除该行，如果等于要查找的数字，则直接返回true。这种思路的时间复杂度明显高于通过每行进行二分法查找。

代码：

 public boolean Find1(int target, int [][] array) {
 	int row = 0;
 	int columns = array[0].length - 1;
 	while(row < array.length && columns >= 0) {
 		if (array[row][columns] == target) {
	return true;
}else if (array[row][columns] > target) {
	columns--;
}else {
	row++;
}
 	}
 	return false;
 }

复杂度分析及总结：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

单例设计模式

发表于 2019-07-15 | 分类于设计模式，创建型模式

什么是单例设计模式？

　　单例设计模式是一种创建型设计模式，该模式涉及到一个类，该类负责创建自己的对象，同时确保只有单个对象被创建。这个类提供了一种
访问其唯一对象的方式，可以直接访问，不需要实例化该类的对象。

优缺点

　　单例设计模式可以减少内存开销，提升运行效率，避免对资源的多重占用，并且可以实现数据共享。

实现：

　　实现单例模式的关键是：构造方法私有化；提供访问唯一对象的方法。
　　1.懒汉式（双检锁）
　　　　所谓懒汉式即在调用时在创建对象。由于添加锁，效率不高。
　　注意：由于指令重排序的原因，加上volatile很有必要。
　　代码：

public class Singleton {
	private volatile static Singleton instance;
	private Singleton() {}
	public static Singleton getInstance() {
		if (instance == null) {
			synchronized(Singleton.class) {
				if (instance != null) {
					instance = new Singleton();
				}
			}
		}
		return instance;
	}
}

　　2.饿汉式：
　　　　利用类加载机制，解决了懒汉式中多线程访问不安全的问题，提高了效率，但有可能浪费内存。
　　代码：

public class Singleton1 {
	private static Singleton1 instance = new Singleton1();
	private Singleton1(){}
	private static Singleton1 getInstance() {
		return instance;
	}
}

应用：

　　application对象、连接池。

剑指offer03-2（重复数字）

发表于 2019-07-15 | 分类于算法，剑指offer

题目：

　　在一个长度为n+1的数组里的所有数字都在1~n的范围内，找出数组中的任意一个重复数字，但不能修改原数组。

思路：

　　由于题目要求不可以修改原数组，故不可用先排序再找重复数字的思路，也不可用Offer03-1中的思路。因此可以考虑使用特殊的哈希表，
即同样大小的数组，将原数组的数字放在对应的索引处，但需要O(n)的空间。利用此题的特殊条件：所有数字都在1n的范围内，可以想到利用二分法
寻找。n+1个数字在1n的范围内，所有1~~n中必定有重复数字，取1~~n的中间值mid，若1~~mid的数量大于mid，则重复数字必定在1~~mid中，这便是二分法
的典型思路。

代码：

二分法：

public int getDuplication(int[] nums,int length) {
	int start = 1;
	int end = length - 1;
	while(start <= end) {
		int mid = (start + end) >> 1;
		int count = countRange(nums, start, mid);
		if (start == end) {
			if (count > 1) {
				return start;
			}else {
				break;
			}
		}
		if (count > mid - start + 1) {
			end = mid;
		}else {
			start = mid + 1;
		}
	}
	return -1;
}
public static int countRange(int[] nums,int start,int end) {
	int count = 0;
	for(int i = 0;i < nums.length;i++) {
		if (nums[i] >= start && nums[i] <= end) {
			count++;
		}
	}
	return count;
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(nlogn)。
　　空间复杂度：
　　　　O(1)。
　　与利用哈希表相比，此方法用时间换取了空间。

剑指offer03-1（重复数字）

发表于 2019-07-15 | 分类于算法，剑指offer

题目：

　　在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的。
也不知道每个数字重复几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么
对应的输出是第一个重复的数字2。

思路：

　　对于重复数字问题常规解法有先排序后比较相邻数字，或者利用哈希表，但这两种解法前者需要O(nlogn)的时间复杂度，
后者需要O(n)的空间复杂度，时空复杂度没有达到最佳。但此题给出了特殊的条件：所有数字都在0到n-1的范围内。利用
此条件可以优化时间复杂度。具体实现见代码。

代码：

public boolean duplicate1(int numbers[],int length,int [] duplication) {
	for(int i = 0;i < length;i++) {
		if (numbers[i] != i) {
			if (numbers[numbers[i]] == numbers[i]) {
				duplication[0] = numbers[i];
				return true;
			}
			int temp = numbers[i];
			numbers[i] = numbers[temp];
			numbers[temp] = temp;
		}
	}
	return false;
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

剑指offer58-2（反转字符串）

发表于 2019-07-15 | 分类于算法，剑指offer

题目：

　　左旋转字符串，即把字符串前面的若干字符转移到字符串的尾部。如输入“abcdefg”和数字2，输出“cdefgab”。

思路：

　　先整体反转字符串，然后局部反转。

代码：

public String LeftRotateString(String str,int n) {
       if (str == null || n < 0) {
		return null;
	}
       if (str.length() == 0) {
		return "";
	}
       char[] s = str.toCharArray();
       reverse(s, 0, s.length - 1);
       reverse(s, 0, s.length - n - 1);
       reverse(s, s.length - n, s.length-1);
       return new String(s);
   }
public static void reverse(char[] arr,int low,int high) {
	while(low < high) {
		char temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
		low++;
		high--;
	}
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

剑指offer58-1（反转字符串）

发表于 2019-07-15 | 分类于算法，剑指offer

题目：

　　输入一个英文句子，反转句子中单词的顺序，但单词内字符的顺序不变。如输入字符串“I am a student.”输出“student. a am I”

思路：

　　先整体反转字符串，然后按各个字符再次反转。

代码：

public String ReverseSentence1(String str) {
	char[] arr = str.toCharArray();
	reverse(arr, 0, arr.length-1);
	int startIndex = -1;
	for(int i = 0;i < arr.length;i++) {
		if (arr[i] == ' ') {
			int endIndex = i;
			reverse(arr, startIndex+1, endIndex-1);
			startIndex = endIndex;
		}
	}
	reverse(arr, startIndex+1, arr.length-1);
	return new String(arr);
}
public static void reverse(char[] arr,int low,int high) {
	while(low < high) {
		char temp = arr[low];
		arr[low] = arr[high];
		arr[high] = temp;
		low++;
		high--;
	}
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

LeetCode557（反转字符串2）

发表于 2019-07-15 | 分类于算法， LeetCode

题目：

　　给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
　　示例:
　　　　输入: “Let’s take LeetCode contest”
　　　　输出: “s’teL ekat edoCteeL tsetnoc”

思路：

　　利用双指针分别反转每个单词。

代码：

   public String reverseWords(String s) {
   	char[] c = s.toCharArray();
       int l = 0 ;
       int r = 0;
       for(int i = 0;i < s.length();i++) {
       	if (c[i] == ' ') {
			r = i - 1;
			reverse(c, l, r);
			l = i + 1;
		}
       	if (i == s.length()-1) {
			reverse(c, l, s.length()-1);
		}
       }
       return new String(c);
   }
   public static void reverse(char[] c,int l,int r) {
       while(l < r) {
       	c[l] ^= c[r];
       	c[r] ^= c[l];
       	c[l++] ^= c[r--];
       }
}

复杂度分析及总结：

循环：

　　时间复杂度：
　　　　O(n)。
　　空间复杂度：
　　　　O(1)。

设计模式-代理模式

发表于 2019-07-13 | 分类于设计模式，结构型模式

什么是静态代理模式？

　　在代理模式中，用一个类代表另一个类的功能，从而达到控制对真实对象的访问的目的。静态代理模式的代理类由程序员编写。

优缺点

　　静态代理设计模式可以保护真实对象，让真实对象的职责更加清晰，同时使对象具有高可扩展性。
　　但如果代理功能较多，代理类中需要编写较多的方法，同时代理模式可能会使效率下降。

实现：

UML图：

// 功能接口
public interface Image {
	void display();
}
// 真实类
public class RealImage implements Image{
	String fileName;
	
	public RealImage(String fileName) {
		super();
		this.fileName = fileName;
		loadFromDisk(fileName);
	}
	
	@Override
	public void display() {
		System.out.println("Displaying" + fileName);
	}
	
	private void loadFromDisk(String fileName) {
		System.out.println("Loading" + fileName);
	}
}
// 代理类
public class ProxyImage implements Image{
	private RealImage realImage;
	private String fileName;
	
	public ProxyImage(String fileName) {
		this.fileName = fileName;
	}

	@Override
	public void display() {
		if (realImage == null) {
			realImage = new RealImage(fileName);
		}
		realImage.display();
	}
	
}
// 测试代码
public class Test {
	public static void main(String[] args) {
		Image image = new ProxyImage("test.jpg");
		image.display();
		System.out.println("----");
		image.display();
	}
}

应用场景

什么是JDK动态代理模式？

　　相比于静态代理，JDK动态代理解决了静态代理模式频繁编写代理功能的缺点。
　　用到的核心技术有：反射与静态代理。

优缺点：

　　其不需要自己实现代理类，但由于使用了反射机制，效率不高，且真实对象需要实现接口。

实现：

　　实现时需要用到java.lang.reflect.Proxy和java.lang.reflect.InvocationHandler，前者用来动态生成代理类和对象，后者是处理器接口,用来实现具体的逻辑，可以通过invoke方法实现对真实角色的代理访问。
　　具体实现原理为：Proxy类通过newProxyInstance动态生成了一个代理类，当执行代理方法时，代理类直接调用了InvocationHandler处理器（相当于静态代理）
对象的invoke方法，并把通过反射产生的相应方法当做参数传入，InvocationHandler加入逻辑后通过反射调用真实对象的方法：method.invoke(readSubject, args);

// 功能接口
public interface Subject {
	public int sellBooks() ;
	public String speak();
}
// 真实类
public class RealSubject implements Subject{

	@Override
	public int sellBooks() {
		System.out.println("买书");
		return 1;
	}

	@Override
	public String speak() {
		System.out.println("说话");
		return "张三";
	}
	
}
// 处理器
public class MyInvocationHandler implements InvocationHandler{
	Subject readSubject;
	
	public MyInvocationHandler(Subject readSubject) {
		super();
		this.readSubject = readSubject;
	}

	@Override
	public Object invoke(Object proxy, Method method, Object[] args) throws Throwable {
		if (method.getName().equals("sellBooks")) {
			int invoke = (int) method.invoke(readSubject, args);
			System.out.println("调用买书方法");
			return invoke;
		}else {
			String string = (String) method.invoke(readSubject, args);
			System.out.println("调用说话方法");
			return string;
		}
	}

}
// 代理类
public class Client {
	public static void main(String[] args) {
		Subject realSubject = new RealSubject();
		MyInvocationHandler myInvocationHandler = new MyInvocationHandler(realSubject);
		Subject proxyClass = (Subject) Proxy.newProxyInstance(ClassLoader.getSystemClassLoader(), new Class[] {Subject.class}, myInvocationHandler);
		proxyClass.sellBooks();
		proxyClass.speak();
	}
}

应用场景：

　　spring中的aop。由于JDK动态代理使用了反射，性能比cglib差，且不能进行类代理，只能进行接口代理。

什么是cglib动态代理？

cglib动态代理通过继承要被动代理的类，重写父类的方法，在子类方法中加入业务逻辑代码，从而实现代理。

　　首先要明白cglib是什么。它是一个强大的代码生成类库，它可以在运行期扩展Java类与实现Java接口。其底层依赖asm库实现。asm库是一个字节码处理类库，它可以转换字节码并生成新的类。
　　cglib用到的主要技术点有：字节码技术。

优缺点：

　　JDK动态代理要求被代理对象实现了接口，而cglib动态代理则不需要被代理对象实现接口，并且由于JDK动态代理使用了反射机制，cglib运行效率会更高。

实现：

// 被代理类
public class Engineer {
	// 可以被代理
	public void eat() {
		System.out.println("工程师吃饭");
	}
	// 不会被子类覆盖
	public final void work() {
		System.out.println("工程师正在工作");
	}
	// 不会被子类覆盖
	public void play() {
		System.out.println("工程师在玩游戏");
	}
}
// 代理
public class CglibProxy implements MethodInterceptor{
	private Object target;
	public CglibProxy(Object target) {
		this.target = target;
	}
	@Override
	public Object intercept(Object arg0, Method arg1, Object[] arg2, MethodProxy arg3) throws Throwable {
		System.out.println("前置通知");
		Object result = arg1.invoke(target);
		System.out.println("后置通知");
		return result;
	}
	public static Object getProxy(Object target) {
		Enhancer enhancer = new Enhancer();
		enhancer.setSuperclass(target.getClass());
		enhancer.setCallback(new CglibProxy(target));
		return enhancer.create();
	}
}
// 测试代码
public class Test {
	public static void main(String[] args) {
		Engineer engineerProxy = (Engineer) CglibProxy.getProxy(new Engineer());
		engineerProxy.eat();
	}
}

应用场景：

　　spring中的aop。由于cglib创建对象花费时间较久，所有cglib适合代理单例对象，或者具有实例池的对象。　　

参考文献

https://www.runoob.com
https://segmentfault.com/a/1190000018923333?utm_source=tag-newest
http://www.chenglong.ren/2019/02/18/cglib%E5%8A%A8%E6%80%81%E4%BB%A3%E7%90%86%E4%BD%BF%E7%94%A8%E4%B8%8E%E5%8E%9F%E7%90%86%E7%9A%84%E7%AE%80%E5%8D%95%E5%88%86%E6%9E%90/
《精通spring4.x企业应用开发实战》