【好书推荐】《剑指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
持续更新,敬请关注公众号
这是一个能给程序员加buff的公众号 (coderbuff)
上一篇: 媳妇儿没事儿总爱看吃播