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