面试题-算法-LeetCode-精选TOP面试题

注： 以下题目都是根据 LeetCode App上的顺序，按照由易到难排列(与其他列表有重复的题目就略过了)

350、两个数组的交集II

点击看答案

1. hashmap 记录第一个数组每个元素出现次数，再遍历第二个数组 2. 先给两个数组排序，再遍历**

自己写的时候的问题：Integer 写错、HashMap<Integer,Integer> 在 int times = get(key) 的时候，要注意判空

LeetCode

412、Fizz Buzz，写一个程序，输出从 1 到 n 数字的字符串表示。1. 如果 n 是3的倍数，输出“Fizz”；2. 如果 n 是5的倍数，输出“Buzz”；3.如果 n 同时是3和5的倍数，输出 “FizzBuzz”。

点击看答案

计算 n%3==0 及 n%5==0 的 boolean 值。之后分别输出

自己写的时候的问题：canDivid3 的时候，应该使用遍历的下标i ，而不是传入的参数n %3 == 0

LeetCode

13、 罗马数字转整数

点击看答案

前一个数比后一个数小

自己写的时候的问题：map写成了 HashMap<String,Integer> ，应该是 HashMap<Character,Integer>，还有，throw 抛出异常的时候，应该要有new关键字，即 throw new IllegalArgumentException(“error input!”);

LeetCode

387、字符串中的第一个唯一字符，给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1

点击看答案

第一次遍历，次数存放在HashMap中，第二次遍历，找到第一个不重复的。

自己写的时候的问题：无

LeetCode

28、实现 strStr()，给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例：

输入: haystack = "hello", needle = "ll"
输出: 2

点击看答案

只有第一个字符匹配上才需要比较

自己写的时候的问题：haystack = “” 且 needle = “” 时，我返回了 -1，应该是 0，还有计算String的长度应该是 str.length() ,而不是 str.leng ,不过数组倒是可以这样做 arr.length

LeetCode

38、外观数列

点击看答案

读懂题目很重要，递归

自己写的时候的问题：throw 要 new ！

LeetCode

69、x的平方根，计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去，如8的平方根是 2.28…，则结果取2即可

点击看答案

我自己的写法，没有考虑数字越界：

public static int mySqrt(int x) {
    if(x < 0){
        throw new IllegalArgumentException("error input!");
    }

    if(x == 0 || x == 1){
        return x;
    }

    int result = 0;
    for(int i = 1;i * i <= x; i++){
        System.out.println("i = " + i);
        result = i;
    }

    return result;

}

其他数字都对，但是如果输入 2147395600 ，则在 i= 46340 时，i就已经是结果了，但是这里的循环条件还是会继续执行，这时候 i= 46341 时，就超出 int 的取值范围越界了，因此不对。如果非要用这种方法去实现，可以在 for 语句里面加个条件： i * i > 0 。因为Java 中的int型数据是有符号数，最高位表示符号，越界的时候，最高位变成1了，也就是变成负数，所以这个条件在刚发生越界的时候就不满足了，就能得到正确的结果。

使用二分查找法要注意几点：首先 (a/2)² > a ，则可以解出来正整数解是 a > 4，即在 a > 4的情况下 a/2 > 根号a 是必然的，再综合 1,2,3,4 这几个特殊数字，我们可以得出，a开根号的值在 [1,a/2] 这种闭合区间。还有，开根号这里可能会有小数，但是我们只要返回正数，所以可以要求 front == tail ，最后是返回tail的值，要注意。

LeetCode

371、两整数之和，不使用运算符 + 和 -，计算两个整数 a、b之和

点击看答案

异或求出普通位相加，与操作求出进位

自己写的时候的问题：a 要暂存 无进位结果，我写的时候忘了暂存了。因为无进位结果 + 进位 还有可能产生进位，所以要有 while 循环。

LeetCode

283、移动零，给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

点击看答案

2个指针，1次遍历

自己写的时候的问题：无

LeetCode

1、两数之和，给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

点击看答案

使用 HashMap 辅助

自己写的时候的问题：无

LeetCode

101、对称二叉树,给定一个二叉树，检查它是否是镜像对称的

点击看答案

递归判断

自己写的时候的问题：要懂递归啊，这是乱写成功的。不会递归时，把条件列出来，估计就有思路了。

LeetCode

108(还未写)、将有序数组转换为二叉搜索树，将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树

点击看答案

二叉树遍历

LeetCode

118、杨辉三角，给定一个非负整数numRows，生成杨辉三角的前numRows行

点击看答案

按照描述的方法，暴力解就好

自己写的时候的问题：自己想的 for语句，依次生成前面的行

LeetCode

125、验证回文串，给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

点击看答案

自己写的时候的问题：自己写的感受还是使用双指针，效率高，转小写，然后去掉无关的符号这种操作效率太低。注意Character的方法 toLowerCase()、 isDigit() 和 isLetter() 就可以了。

[LeetCode](https://leetcode-cn.com/problems/valid-palindrome/solution/java-da-dao-zhi-jian-6xing-by-rabbitzhao/）

268、缺失数字，给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

点击看答案

1. 数组中所有数字异或，结果再与 0n 异或，得到的结果就是缺失的那个数字(因为相同的数字异或结果为0) 2. 0n 这些数字的和-数组所有数字的和 = 缺失的数字

自己写的时候的问题：自己写的时候，感觉使用 异或 操作简单方便。

LeetCode

171、Excel 表序列号，给定一个Excel表格中的列名称，返回其相应的列序号。如：A -> 1，B -> 2，Z -> 26，AA -> 27，AB -> 28

点击看答案

我们常用的 10 进制数字，0~9 共 10 个数字。题目A-Z，26个字母，所以是26进制，故，AB= 26 + 2 = 28**

自己写的时候的问题：看做26进制的数字，从字符串尾部开始遍历，计算每个char所在位的 base ，要注意输入小写字母，所以要统一转为小写去比较。

LeetCode

172、 阶乘后的零，给定一个整数 n，返回 n! 结果尾数中零的数量，你算法的时间复杂度应为 O(log n)

点击看答案

可以转换为n的质因数中5的个数

自己写的时候的问题：*自己写的时候，使用for循环(从 5 到 n，每次进5) 的方式来计算5的个数，结果超时，虽然放在 IntelliJ 中运行结果是对的。因此，应该使用更高效的方式， n /= 5; result += n; *。

[LeetCode](https://leetcode-cn.com/problems/factorial-trailing-zeroes/solution/xiang-xi-tong-su-de-si-lu-fen-xi-by-windliang-3/）

189、旋转数组，给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

点击看答案

首先能想到的是：新建一个数组，然后将原数组中的数字按照旋转后的顺序放到新数组 ，其次就是：首先将整个数组旋转，再分别旋转前面部分和后面部分

自己写的时候的问题：写了3次，旋转3次是没问题，关键是处理好 k > nums.length 的情况。

LeetCode

190、(还未写)颠倒二进制位,颠倒给定的 32 位无符号整数的二进制位。

点击看答案

每次取1位反转

LeetCode

191、位1的个数，编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数

点击看答案

n&(n-1) 或者 一直往右移

自己写的时候的问题：无符号数有点难，还么有完全理解。while 条件写成 n > 0 ，应该要写成 n != 0。

LeetCode

198、打家劫舍,小偷计划偷窃沿街的房屋。每间房内都藏有一定的现金，但如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额

点击看答案

奇偶，然后选较大

自己写的时候的问题：求偶数和的时候，先计算当前偶数和，再与奇数和比较，计算当前偶数和的最终值

LeetCode

202、快乐数，判断一个数是不是快乐数。一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。

点击看答案

快慢指针用来终止无限循环

自己写的时候的问题：主要是要细心，自己写的时候写成 result = temp * temp ,应该是 result += temp * temp

LeetCode

204、计数质数，统计所有小于非负整数 n 的质数的数量。（质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。）

点击看答案

质数的判断：for (int i = 2; i * i <= n; i++)

自己写的时候的问题：最优解暂时有点难理解，还是先只要注意 i * i <= n 这样的优化方式吧

LeetCode

234、回文链表，判断链表是否是回文链表

点击看答案

1、反转链表，对比反转后和原链表是否相同 2、链表值复制到数组中，再采用前后双指针

自己写的时候的问题：写得很完美，第一步，快慢指针找到中间节点 第二步、反转中间节点之后的部分 第三步、对比前半部分和反转后的后半部分

LeetCode

326、3的幂，给定一个整数，写一个函数来判断它是否是 3 的幂次方。

点击看答案

1、不断求余，不断除以3，看结果 2、转换成3进制，看是不是前面1个1，后面全是0

自己写的时候的问题：老老实实一直除以 3 ，但是，要注意数字 0 ，否则 n % 3 == 0 会进入死循环

LeetCode

242、有效的字母异位词，给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

点击看答案

大小26的数组，两个字符串遍历每个字符，s遍历就在相应下标+1，而遍历t时在相应下标-1

自己写的时候的问题：只有小写字母，所以用数组实现了，不难

LeetCode