【好书推荐】《剑指Offer》之硬技能（编程题1~6）
本文例子完整源码地址：https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword
前一篇《【好书推荐】《剑指Offer》之软技能》中提到了面试中的一些软技能，简历的如何写等。《剑指Offer》在后面的章节中主要是一些编程题并配以讲解。就算不面试，这些题多做也无妨。可惜的是书中是C++实现，我又重新用Java实现了一遍，如果有错误或者更好的解法，欢迎提出交流。
1.赋值运算符函数
Java不支持赋值运算符重载，略。
2.实现Singleton模式
饿汉模式
1 /**
2 * 饿汉模式
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Singleton {
7
8 private static Singleton singleton = new Singleton();
9
10 private Singleton() {
11
12 }
13 public static Singleton getInstance() {
14 return singleton;
15 }
16 }优点：线程安全、不易出错、性能较高。
缺点：在类初始化的时候就实例化了一个单例，占用了内存。
饱汉模式一
1 /**
2 * 饱汉模式一
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Singleton {
7
8 private static Singleton singleton ;
9
10 private Singleton() {
11
12 }
13 public static synchronized Singleton getInstance() {
14 if (singleton == null) {
15 singleton = new Singleton();
16 }
17 return singleton;
18 }
19 }饱汉模式二
1 /**
2 * 饱汉模式二
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Singleton {
7
8 private static Singleton singleton ;
9
10 private Singleton() {
11
12 }
13 public static Singleton getInstance() {
14 if (singleton == null) {
15 synchronized (Singleton.class) {
16 if (singleton == null) {
17 singleton = new Singleton();
18 }
19 }
20 }
21 return singleton;
22 }
23 }优点：线程安全，节省内存，在需要时才实例化对象，比在方法上加锁性能要好。
缺点：由于加锁，性能仍然比不上饿汉模式。
枚举模式
1 /**
2 * 枚举模式
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public enum Singleton {
7 INSTANCE;
8
9 Singleton() {
10
11 }
12 }在《Effective Java》书中，作者强烈建议通过枚举来实现单例。另外枚举从底层保证了线程安全，这点感兴趣的读者可以深入了解下。尽管枚举方式实现单例看起来比较“另类”，但从多个方面来看，这是最好且最安全的方式。
3.数组中重复的数字
题目：给定一个数组，找出数组中重复的数字。
解法一：时间复杂度O(n),空间复杂度O(n)
1 /**
2 * 找出数组中重复的数字
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Solution {
7
8 public void findRepeat(Integer[] array) {
9 Set<Integer> noRepeat = new HashSet<>();
10 for (Integer number : array) {
11 if (!noRepeat.contains(number)) {
12 noRepeat.add(number);
13 } else {
14 System.out.println("重复数字：" + number);
15 }
16 }
17 }
18 }*Set底层实现也是一个Map
通过Map散列结构，可以找到数组中重复的数字，此算法时间复杂度为O(n)，空间复杂度为O(n)（需要额外定义一个Map）。
解法二：时间复杂度O(n^2),空间复杂度O(1)
1 /**
2 * 找出数组中重复的数字
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Solution {
7
8 public void findRepeat(Integer[] array) {
9 for (int i = 0; i < array.length; i++) {
10 Integer num = array[i];
11 for (int j = i + 1; j < array.length; j++) {
12 if (num.equals(array[j])) {
13 System.out.println("重复数字：" + array[j]);
14 }
15 }
16 }
17 }
18 }解法二通过遍历的方式找到重复的数组元素，解法一相比于解法二是典型的“以空间换取时间”的算法
变形：给定一个长度为n的数组，数组中的数字值大小范围在0~n-1，找出数组中重复的数字。
变形后的题目也可采用上面两种方法，数字值大小范围在0~n-1的特点，不借助额外空间（空间复杂度O(1)），遍历一次（时间复杂度为O(n)）的算法
1 /**
2 * 找出数组中重复的数字，数组中的数字值大小范围在0~n-1
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Solution {
7 public void findRepeat(Integer[] array) {
8 for (int i = 0; i < array.length; i++) {
9 while (array[i] != i) {
10 if (array[i].equals(array[array[i]])) {
11 System.out.println("重复数字：" + array[i]);
12 break;
13 }
14 Integer temp = array[i];
15 array[i] = array[temp];
16 array[temp] = temp;
17 }
18 }
19 }
20 }分析：变形后的题目中条件出现了，数组中的值范围在数组长度n-1以内，且最小为0。也就是说，数组中的任意值在作为数组的下标都不会越界，这是一个潜在的条件。根据这个潜在的条件，我们可以把每个值放到对应的数组下标，使得数组下标=数组值。例如：4,2,1,4,3,3。遍历第一个值4，此时下标为0，数组下标≠数组值，比较array[0]与array[4]不相等->交换，4放到了正确的位置上，得到3,2,1,4,4,3。此时第一个值为3，数组下标仍然≠数组值，比较array[0]与array[3]不想等->交换，3放到了正确的位置，得到4,2,1,3,4,3。此时数组下标仍然≠数组值，比较array[0]与array[4]相等，退出当前循环。依次类推，开始数组下标int=1的循环。
4.二维数组中的查找
题目：给定一个二维数组，每一行都按照从左到右依次递增的顺序排序，每一列都按照从上到下依次递增的顺序排序。输入一个二维数组和一个整数，判断该整数是否在二维数组中。
解法一：遍历n*m大小的二维数组，时间复杂度O(n*m)，空间复杂度O(1)
1 /**
2 * 二维数组中查找
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Solution {
7
8 public boolean isExist(Integer[][] twoArray, Integer target) {
9 for (int i = 0; i < twoArray.length; i++) {
10 for (int j = 0; j < twoArray[i].length; j++) {
11 if (twoArray[i][j].equals(target)) {
12 return true;
13 }
14 }
15 }
16 return false;
17 }
18 }优点：简单暴力。
缺点：性能不是最优的，时间复杂度较高，没有充分利用题目中“有序”的条件。
解法二：时间复杂度O(n+m)，空间复杂度O(1)
1 /**
2 * 二维数组中查找
3 * @author OKevin
4 * @date 2019/5/27
5 **/
6 public class Solution {
7
8 public boolean isExist(Integer[][] twoArray, Integer target) {
9 int x = 0;
10 int y = twoArray[0].length - 1;
11 for (int i = 0; i < twoArray.length-1 + twoArray[0].length-1; i++) {
12 if (twoArray[x][y].equals(target)) {
13 return true;
14 }
15 if (twoArray[x][y] > target) {
16 y--;
17 continue;
18 }
19 if (twoArray[x][y] < target) {
20 x++;
21 }
22 }
23 return false;
24 }
25 }分析：通过举一个实例，找出规律，从右上角开始查找。
Integer[][] twoArray = new Integer[4][4];
twoArray[0] = new Integer[]{1, 2, 8, 9};
twoArray[1] = new Integer[]{2, 4, 9, 12};
twoArray[2] = new Integer[]{4, 7, 10, 13};
twoArray[3] = new Integer[]{6, 8, 11, 15};
5.替换空格
题目：将字符串中的空格替换为“20%”。
解法一：根据Java提供的replaceAll方法直接替换
1 /**
2 * 字符串空格替换
3 * @author OKevin
4 * @date 2019/5/28
5 **/
6 public class Solution {
7 public String replaceSpace(String str) {
8 return str.replaceAll(" ", "20%");
9 }
10 }这种解法没什么可说。但可以了解一下replaceAll的JDK实现。replaceAll在JDK中的实现是根据正则表达式匹配要替换的字符串。
解法二：利用空间换时间的方式替换
1 /**
2 * 字符串空格替换
3 * @author OKevin
4 * @date 2019/5/28
5 **/
6 public class Solution {
7 public String replaceSpace(String str, String target) {
8 StringBuilder sb = new StringBuilder();
9 for (char c : str.toCharArray()) {
10 if (c == ' ') {
11 sb.append(target);
12 continue;
13 }
14 sb.append(c);
15 }
16 return sb.toString();
17 }
18 }6.从尾到头打印链表
题目：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。
*由于《剑指Offer》采用C++编程语言，这题需要我们先构造出一个节点，模拟出链表的结构。
定义节点
1 /**
2 * 链表节点定义
3 * @author OKevin
4 * @date 2019/5/29
5 **/
6 public class Node {
7 /**
8 * 指向下一个节点
9 */
10 private Node next;
11 /**
12 * 表示节点的值域
13 */
14 private Integer data;
15
16 public Node(){}
17
18 public Node(Integer data) {
19 this.data = data;
20 }
21 //省略getter/setter方法
22 }解法一：利用栈先进后出的特点，遍历链表放入栈中，再从栈推出数据
1 /**
2 * 逆向打印链表的值
3 * @author OKevin
4 * @date 2019/5/29
5 **/
6 public class Solution {
7 public void tailPrint(Node head) {
8 Stack<Node> stack = new Stack<>();
9 while (head != null) {
10 stack.push(head);
11 head = head.getNext();
12 }
13 while (!stack.empty()) {
14 System.out.println(stack.pop().getData());
15 }
16 }
17 }这种解法“不幸”地借助了额外的空间。
解法二：既然使用栈的结构，实际上也就可以使用递归的方式逆向打印链表
1 /**
2 * 逆向打印链表的值
3 * @author OKevin
4 * @date 2019/5/29
5 **/
6 public class Solution {
7 public void tailPrint(Node head) {
8 if (head.getNext() != null) {
9 tailPrint(head.getNext());
10 }
11 System.out.println(head.getData());
12 }
13 }使用递归虽然避免了借助额外的内存空间，但如果链表过长，递归过深易导致调用栈溢出。
测试程序：
1 /**
2 * @author OKevin
3 * @date 2019/5/29
4 **/
5 public class Main {
6 /**
7 * 1->2->3->4->5
8 * @param args
9 */
10 public static void main(String[] args) {
11 Node node1 = new Node(1);
12 Node node2 = new Node(2);
13 Node node3 = new Node(3);
14 Node node4 = new Node(4);
15 Node node5 = new Node(5);
16 node1.setNext(node2);
17 node2.setNext(node3);
18 node3.setNext(node4);
19 node4.setNext(node5);
20
21 Node head = node1;
22
23 Solution solution = new Solution();
24 solution.tailPrint(head);
25 }
26 }本文例子完整源码地址：https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword