再次挖坑新的Java分类，这次是关于Java面试题的，每期解析十道Java面试题，这些面试题会涉及到Java的方方面面，基础知识、数据结构、各路算法、数据处理等等等，老四的目的主要是根据面试题分析解决问题的思路以及题目涉及到的Java相关知识，所有题目几乎都会敲写不成熟的解题代码供您参考，同时也希望诸君提出不足之处，互相进步。
1.判断某年度Y是否为闰年。
解析:老掉牙的Java题了，但是为什么拿出来呢?就当做是熟悉一下逻辑运算符算术运算符吧。
判断某年是否为闰年的方法是:
- 如果Y是4的倍数，且不是100的倍数，则是闰年。
- 如果Y是100的倍数，则只有当Y是400的倍数时。
最主要的就是个小算法判断，如果面试的时候，你没必要写那些”请输入”这类的语法，最主要就是体现判断的逻辑。代码如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
package com.glorze.interview.one; /** * 判断某年是否是闰年 * @ClassName IsLeapYear * @author: glorze.com * @since: 2018年3月20日 下午11:25:18 */ public class IsLeapYear { /** * 判断某年是否是闰年 * @Title: isLeapYear * @param year * @return Boolean * @author: 高老四博客 * @since: 2018年3月20日 下午11:25:35 */ public Boolean isLeapYear(Integer year) { return ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0); } public static void main(String[] args) { IsLeapYear ily = new IsLeapYear(); System.out.println(ily.isLeapYear(2016)); } } |
Java中的算术运算符:
- + 加法运算符，除此之外，它也是字符串的连接运算符
- – 减法运算符
- * 乘法运算符
- / 除法运算符 整数除以整数取整且除数不能为0，如果存在浮点数或者都是浮点数的除法结果位浮点数且0或者0.0可以作为除数，结果为正/负无穷大
- % 求余运算符 结果不一定是整数，除数也不能为0，如果存在浮点数，除数可以为0或者0.0，结果为非数NaN
- ++ 自加 单目运算符即只能操作一个操作数，不能操作常量或者表达式 符号放在操作数的左边先进行操作数自加运算 放在操作数的右边就先进行表达式的计算在进行操作数自身自加运算
- — 同自加 反过来而已
Java中的逻辑运算符:
- && 与。前后必须都为true才返回true
- & 不短路与。表达式都会计算，及时第一个条件为false
- || 或。只要有一个返回true结果就是true
- | 不短路或。表达式都会计算，存在true会返回true
- ! 非，true变成false，false变成true
- ^ 异或。两个操作数不同时返回true，相同时返回false
注意: 稍微有点编程经验的人，对这道题我们可以讲点一些”野路子”。。。我们可以在特定的情境之下利用空间换时间来解决这个问题。比如说我们事先建立一个长度3000的数组，然后把所有的年份按下标的数字对应，如果是闰年，那么该项数组的值就为1，否则就是0。这样一年判断某一年是否是闰年直接判断对应位置的数组值是否为1就好了。抛出该方法不能将未来所有的年限都存放在数组中的因素之外，这是典型的那空间换时间的思路，我们牺牲掉一些空间存储这些年份以及是否是闰年的标识，但换来的是很快能判断某一年的是否是闰年。当然直接写一个小算法和利用这种技巧哪个更合适肯定都是根据当前的业务场景决定的。
2.请编写一个函数，返回是某个整型变量(不考虑负数)的二进制位中有多少个1。
解析:其实这道题也比较古老了，但是这道题会帮助你理解计算机组成原理，二进制、移位运算等等。
我们本着优秀解题的原则，尽量让我们的程序效率更高，所以我会贴上接近较完美的代码，其余的演变代码会在源码项目包中体现。关于本题，我们最初的想法都是去循环32个数字位，存在1的话计数器就加1，这样的写法没什么错误，但是显然不是我们想要写的代码，也不是面试官想要的。第二个想法我们会想到移位运算，每次右移一位(至于为什么不除以2，我会告诉你的。)直到整数为0。但是这种方式不适合以补码形式存在负数。考虑以上两种方式解决问题的方式都不是很好，它们都占用了二进制位数的时间复杂度。那我们可以这样想，每次从最低位开始遇到的第一个1，计数器加1，清0继续。例如5的二进制是101，101&100=100，结果还有1，计数器加1继续，100&011=0，说明没有1了，计数器加1结束战斗。代码如下:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
package com.glorze.interview.one; /** * 判断整型的二进制中1的个数 * @ClassName OneOfNum * @author: glorze.com * @since: 2018年3月20日 下午11:50:35 */ public class OneOfNum { /** * 不要使用for循环，虽然不算错，但是不够优秀 * @Title: oneCount * @param number * @return Integer * @author: 高老四博客 * @since: 2018年3月20日 下午11:51:01 */ public Integer oneCount(Integer number) { int count = 0; while (number != 0) { number = number & (number - 1); count++; } return count; } public static void main(String[] args) { OneOfNum oon = new OneOfNum(); System.out.println(oon.oneCount(-5)); System.out.println(oon.oneCount(0xFF)); System.out.println(oon.oneCount(0x100)); System.out.println(oon.oneCount(7)); System.out.println(oon.oneCount(16)); System.out.println(oon.oneCount(63)); } } |
关于计算机组成原理(原码、反码、补码)老四也是特么的学的乱七八糟，不敢瞎说，自己研究去吧。
Java中的位运算符:
- & 按位与。同时为1才返回1
- | 按位或。只要有1就返回1
- ~ 按位非。取反
- ^ 按位异或。相同为0，不同为1
- << 左移运算符。如果左移n位相当于当前数的绝对值乘以2的n次方，负数补符号
- >> 右移运算符。同左移，相当于除以2的n次方。
- >>> 无符号右移运算符。即使是负数无符号右移也变成了正数。
注意(在Java中):
- 低于int类型的操作数会自动转型在进行移位运算
- 对于int类型的整型，移位数大于32的时候，移位相当于减去32的移位。如:a>>33和a>>1是一样的
- 对于long型，当移位数大于64的时候，移位数会对64取余进行移位。
- 移位计算不会改变操作数本身，只是得到一个新的运算结果。
那么在Java中为什么移位运算相对算术运算效率高一些呢?
从硬件层面上看，计算机是别的就是二进制，所以移位是人家的功能，而算术运算是在此基础上建立的。从效率层面，移位指令占两个指令周期，而算术运算占4个。同样，移位只有一个寻址，而算术运算和逻辑运算需要两次寻址，综合起来，移位效率高一些。你去看jvm源码，人家都不用的加减乘除的。。。至于我说的这些如果你感兴趣，买一本计算机组成原理看去吧，相信你不会疯掉的。
关于这道题，其实还有更变态的解法，只不过已经有点超出常规了，感觉不是学术性研究就没必要去研究了，采用分治思想(先计算每对相邻的2位中有几个1，再依次计算相邻的4位，8位，16位，32位有几个1。。。)有兴趣的自己去研究参考吧。老四老四源码包中写了三种关于本题的实现，有需要自助下载参考。最后补一下分治思想的算法图解:
3.在不使用jdk api的情况下实现字符串转整型。
解析:如果碰到这道题，面试官的本意其实不是让你把jvm的源码记下来的，但是我们的确要知道jdk是怎么实现字符串转整型的。然而在笔试题中，一般都是将字符串转为char数组，然后遍历计算得到整形数值，但是字符串的题一般都要考察边界值，各种特殊情况判断等等。比如:
- 排除第一个空格
- 允许正负符号开头
- 遇到非法字符停止转换，抛出异常或者返回默认值。
- 如果转换的字符串超出整型最大值(整数最大值2^32-1，负数最小值-2^32)也需要抛出异常或者返回默认值。
再说一下关于Integer.parseInt(s)源码，虽然jdk源码其实也是这么做的，只不过他处理的高级一些，用负数统一转换正数和负数，减少处理逻辑:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
public static int parseInt(String s， int radix) throws NumberFormatException { if (s == null) { throw new NumberFormatException("null"); } // radix代表进制，所以的Integer的默认值是10，该值要在2-36之间，否则抛异常 if (radix < Character.MIN_RADIX) { throw new NumberFormatException("radix " + radix + " less than Character.MIN_RADIX"); } if (radix > Character.MAX_RADIX) { throw new NumberFormatException("radix " + radix + " greater than Character.MAX_RADIX"); } int result = 0; boolean negative = false; int i = 0， len = s.length(); /** * limit 默认初始化为 最大正整数的 负数 ，假如字符串表示的是正数 * 那么result(在返回之前一直是负数形式)就必须和这个最大正数的负数来比较，判断是否溢出 */ int limit = -Integer.MAX_VALUE; int multmin; int digit; if (len > 0) { // 判断正负 char firstChar = s.charAt(0); if (firstChar < '0') { if (firstChar == '-') { negative = true; // 负数的情况下判断溢出 limit = Integer.MIN_VALUE; } else if (firstChar != '+') throw NumberFormatException.forInputString(s); if (len == 1) throw NumberFormatException.forInputString(s); i++; } multmin = limit / radix; /** * len:字符串的长度 * multmin初始值为最大负整数/进制数 */ while (i < len) { // 根据Character类获取当前对应字符对应进制的数字 digit = Character.digit(s.charAt(i++)， radix); if (digit < 0) { throw NumberFormatException.forInputString(s); } /** * result统一使用负值来计算 */ if (result < multmin) { throw NumberFormatException.forInputString(s); } result *= radix; if (result < limit + digit) { throw NumberFormatException.forInputString(s); } result -= digit; /** * 举例：一开始输入一个数字字符串为678，digit = 678 / 10 = 67 * result *= radix --> result = 0 ; result -= digit --> result = -6 * result *= radix --> result = -60; result -= digit --> result = -67 * result *= radix --> result = -670; result -= digit --> result = -678 * negative = false，最终结果为：678 */ } } else { throw NumberFormatException.forInputString(s); } return negative ? result : -result; } |
当然作为笔试我们不必要玩得这么高级，把基本的边界以及特殊情况和算法写对了就好，老四附不成熟的代码供参考。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
package com.glorze.interview.one; /** * 实现String转Integer 考虑各种边界以及特殊情况 * ps:这段代码里面违法字符返回默认值0，但是数字开头的字符串会返回开头的数字 * 面试的要问清各种情况编码，或者尽可能考虑的多一些 * @ClassName StringToInteger * @author: glorze.com * @since: 2018年3月24日 下午4:40:01 */ public class StringToInteger { /** * 当然你也可以完全依赖Character类完成这个算法 * @Title: stringToInteger * @param str * @return int * @author: 高老四博客 * @since: 2018年3月24日 下午4:43:05 */ public static int stringToInteger(String str) { if (str == null || str.length() == 0) { return 0; } char[] array = str.toCharArray(); long result = 0; // 判断正负符号，截取第一个出现的符号 int count = 0; // 判断空格 int num = 0; // 正负数 int flag = 1; for (int i = 0; i < array.length; i++) { Character c = array[i]; if (c >= '0' && c <= '9') { result = result * 10 + c - '0'; // 判断是否溢出 if (flag == 1 && result > Integer.MAX_VALUE) { return Integer.MAX_VALUE; } else if (flag == -1 && -result < Integer.MIN_VALUE) { return Integer.MIN_VALUE; } num++; } else if (c == ' ' && num == 0 && count == 0) { continue; } else if (c == '+' && count == 0) { count = 1; } else if (c == '-' && count == 0) { flag = -1; count = 1; } else { return (int) (flag * result); } } return (int) (flag * result); } public static void main(String[] args) { System.out.println(StringToInteger.stringToInteger("12 1aaasf1")); } } |
最后记住几个常用的ASCII码常用的转换值:大写字母A->65 小写字母a->97 大写字母Z->90 小写字母z-172 数字0-9->48-57。
4.两个数组已经升序排好，请返回一个数组，将两个数组合在一起按照升序排好。
解析:其实这道题考的是数据结构中的归并排序，关于归并排序，请参考这里，点我起飞。
5.有2个已经排序好的整数数组arr1，arr2，请编写函数，返回一个新排序数组，这个数组包括了这两个数组中的相同整数。
解析:如果本题没有给出一些限制的话，你写两个for循环也没什么大的问题。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
package com.glorze.interview.one; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 求两个数组的交集 * * @ClassName ArrayUtil * @author: glorze.com * @since: 2018年4月7日 下午4:55:39 */ public class ArrayUtil { public static void main(String[] args) { int[] array1 = { 1， 2， 3， 4， 5， 6 }; int[] array2 = { 2， 3， 4， 8 }; List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < array1.length; i++) { for (int j = 0; j < array2.length; j++) { if (array1[i] == array2[j]) { list.add(array1[i]); } } } System.out.println(Arrays.toString(list.toArray())); } } |
但是如果要求通过某些数据结构或者让你实现的效率的更高一些，你应该就不能写上面的代码了。其实这道题使用数据结构中的二分法(折半)查找效率会高。首先了解一下什么是二分法(折半查找)。
定义:二分法的前提是线性表中的记录必须是关键码有序(通常从小到大有序)，线性表必须采用顺序存储。符合题中的前提条件。折半查找(就是二分法)的基本思想:
在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功;若给定值小于中间记录的关键字，则在中间记录的左半区继续查找;若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
package com.glorze.interview.one; /** * 二分法Java实现 * @ClassName BinarySearch * @author: glorze.com * @since: 2018年4月7日 下午5:08:35 */ public class BinarySearch { /** * 二分查找法 * @Title: binarySearch * @param arr 序列 * @param key 要查找的值 * @return int * @author: 高老四博客 * @since: 2018年4月7日 下午5:08:49 */ public int binarySearch(int arr[]， int key) { int start = 0; int end = arr.length - 1; int index = -1; while (start <= end) { index = start + (end - start) / 2; if (arr[index] == key) { return arr[index]; } else if (arr[index] < key) { // 在右半区查找 start = index + 1; } else if (arr[index] > key) { end = index - 1; } } return -1; } public static void main(String[] args) { int arr[] = { 23， 25， 27， 28， 29， 35， 46， 48， 73， 84 }; BinarySearch find = new BinarySearch(); int result = find.binarySearch(arr， 48); System.out.println(result); } } |
我们能感觉到二分查找效率非常高，最快一次就找到了，时间复杂度O(logn)。不过由于折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，这样的算法已经比较好了。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。
那么这道题中，选取一个数组进行循环，通过二分法查找数组中相同的元素依次输出就可以了。由于Arrays类中已经带了二分法，我们可以直接调用。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
package com.glorze.interview.one; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 求两个数组的交集 * * @ClassName ArrayUtil * @author: glorze.com * @since: 2018年4月7日 下午4:55:39 */ public class ArrayUtil { public static void main(String[] args) { int[] array1 = { 1， 2， 3， 4， 5， 6 }; int[] array2 = { 2， 3， 4， 8 }; /* * List<Integer> list = new ArrayList<Integer>(); for (int i = 0; i < * array1.length; i++) { for (int j = 0; j < array2.length; j++) { if * (array1[i] == array2[j]) { list.add(array1[i]); } } } * System.out.println(Arrays.toString(list.toArray())); */ int len = array1.length; for (int i = 0; i < len; i++) { if (Arrays.binarySearch(array2， array1[i]) >= 0) { System.out.println(array1[i]); } } } } |
项目源码包文末自助下载。
更博不易，如果觉得文章对你有帮助并且有能力的老铁烦请捐赠盒烟钱，点我去赞助。或者扫描文章下面的微信/支付宝二维码打赏任意金额(点击”给你买杜蕾斯”)，也可扫描小站放的支付宝领红包二维码，线下支付享受优惠的同时老四也可以获得对应赏金，老四这里抱拳谢谢诸位了。捐赠时请备注姓名或者昵称，因为您的署名会出现在赞赏列表页面，您的捐赠钱财也会被用于小站的服务器运维上面，再次抱拳感谢。
资源下载
隐藏内容：******，购买后可见！
下载价格：0 G币
您需要先登录后，才能购买资源
欢迎访问高老四博客(glorze.com),本站技术文章代码均为老四亲自编写或者借鉴整合,其余资源多为网络收集,如涉及版权问题请与站长联系。如非特殊说明,本站所有资源解压密码均为:glorze.com。
