【好书推荐】《剑指Offer》之硬技能(编程题1~6)

本文例子完整源码地址:https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword前一篇《【好书推荐】《剑指Offer》之软技能》中提到了面试中的一些软技能,简历的如何写等。《剑指Offer》在后面的章节中主要是一些编程题并配以讲解。就算不面试,这些题多做也无妨。可惜的是书中是C 实现,我又重新用Jav...

【好书推荐】《剑指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) {15singleton = 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) {15synchronized (Singleton.class) {16if (singleton == null) {17singleton = 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) {11if (!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  ) {10Integer num = array[i];11for (int j = i1; 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 
源文地址:https://www.guoxiongfei.cn/cntech/18400.html