LeetCode 100道题目和答案（面试必备）（一）

1.两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

class Solution {public int[] twoSum(int[] nums, int target) {int n = nums.length;for (int i = 0; i < n; ++i) {for (int j = i + 1; j < n; ++j) {if (nums[i] + nums[j] == target) {return new int[]{i, j};}}}return new int[0];}
}
方法二：哈希表
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N)O(N) 降低到 O(1)O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();for (int i = 0; i < nums.length; ++i) {if (hashtable.containsKey(target - nums[i])) {return new int[]{hashtable.get(target - nums[i]), i};}hashtable.put(nums[i], i);}return new int[0];}
}

2.回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。

答案：

class Solution {public boolean isPalindrome(int x) {// 特殊情况：// 如上所述，当 x < 0 时，x 不是回文数。// 同样地，如果数字的最后一位是 0，为了使该数字为回文，// 则其第一位数字也应该是 0// 只有 0 满足这一属性if (x < 0 || (x % 10 == 0 && x != 0)) {return false;}int revertedNumber = 0;while (x > revertedNumber) {revertedNumber = revertedNumber * 10 + x % 10;x /= 10;}// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。return x == revertedNumber || x == revertedNumber / 10;}
}

3.罗马数字转整数

方法一：模拟
思路
通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。
若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。
class Solution {Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{put('I', 1);put('V', 5);put('X', 10);put('L', 50);put('C', 100);put('D', 500);put('M', 1000);}};public int romanToInt(String s) {int ans = 0;int n = s.length();for (int i = 0; i < n; ++i) {int value = symbolValues.get(s.charAt(i));if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {ans -= value;} else {ans += value;}}return ans;}
}

4.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

class Solution {public String longestCommonPrefix(String[] strs) {if (strs == null || strs.length == 0) {return "";}String prefix = strs[0];int count = strs.length;for (int i = 1; i < count; i++) {prefix = longestCommonPrefix(prefix, strs[i]);if (prefix.length() == 0) {break;}}return prefix;}public String longestCommonPrefix(String str1, String str2) {int length = Math.min(str1.length(), str2.length());int index = 0;while (index < length && str1.charAt(index) == str2.charAt(index)) {index++;}return str1.substring(0, index);}
}

public static String re(String[] str){if(str.length==0){return "";}String str1=str[0];for (int i = 1; i < str.length; i++) {str1 = bj(str1, str[i]);if (str1.length()==0){break;}//当第一个没有比对上时，直接用break结束循环，减少时间。}if (str1.length()==0){return "";}return str1;
}private static String bj(String str2, String str3) {int min = Math.min(str2.length(), str3.length());int index=0;while (index<min&&str2.charAt(index)==str3.charAt(index)){index++;}//用while比for循环次数更少return str2.substring(0,index);
}public static void main(String[] args) {String[] str=new String[]{"moyon","molon","moxue"};String result = re(str);System.out.println(result);
}

5.删除有序数组中的重复项

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

答案：

解法： 双指针
首先注意数组是有序的，那么重复的元素一定会相邻。
要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。
考虑用 2 个指针，一个在前记作 p，一个在后记作 q，算法流程如下：
1.比较 p 和 q 位置的元素是否相等。
如果相等，q 后移 1 位
如果不相等，将 q 位置的元素复制到 p+1 位置上，p 后移一位，q 后移 1 位
重复上述过程，直到 q 等于数组长度。
返回 p + 1，即为新数组长度。public int removeDuplicates(int[] nums) {if(nums == null || nums.length == 0) return 0;int p = 0;int q = 1;while(q < nums.length){if(nums[p] != nums[q]){nums[p + 1] = nums[q];p++;}q++;}return p + 1;
}

6.移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

答案

方法一：双指针
思路及算法由于题目要求删除数组中等于val 的元素，因此输出数组的长度一定小于等于输入数组的长度，我们可以把输出的数组直接写在输入数组上。可以使用双指针：右指针 right 指向当前将要处理的元素，左指针 left 指向下一个将要赋值的位置。如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；如果右指针指向的元素等于val，它不能在输出数组里，此时左指针不动，右指针右移一位。整个过程保持不变的性质是：区间 [0,left) 中的元素都不等于val。当左右指针遍历完输入数组以后，left 的值就是输出数组的长度。这样的算法在最坏情况下（输入数组中没有元素等于 val，左右指针各遍历了数组一次。class Solution {public int removeElement(int[] nums, int val) {int n = nums.length;int left = 0;for (int right = 0; right < n; right++) {if (nums[right] != val) {nums[left] = nums[right];left++;}}return left;}
}
另一种写法：
class Solution {public int removeElement(int[] nums, int val) {int ans = 0;for(int num: nums) {if(num != val) {nums[ans] = num;ans++;}}return ans;}
}方法二：双指针优化
思路如果要移除的元素恰好在数组的开头，例如序列 [1,2,3,4,5][1,2,3,4,5]，当 val 为 11 时，我们需要把每一个元素都左移一位。注意到题目中说：「元素的顺序可以改变」。实际上我们可以直接将最后一个元素 55 移动到序列开头，取代元素 11，得到序列 [5,2,3,4][5,2,3,4]，同样满足题目要求。这个优化在序列中 val 元素的数量较少时非常有效。实现方面，我们依然使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。算法如果左指针 left 指向的元素等于 val，此时将右指针 right 指向的元素复制到左指针 left 的位置，然后右指针 right 左移一位。如果赋值过来的元素恰好也等于 val，可以继续把右指针 right 指向的元素的值赋值过来（左指针left 指向的等于 val 的元素的位置继续被覆盖），直到左指针指向的元素的值不等于 val 为止。当左指针 left 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。class Solution {public int removeElement(int[] nums, int val) {int left = 0;int right = nums.length;while (left < right) {if (nums[left] == val) {nums[left] = nums[right - 1];right--;} else {left++;}}return left;}
}

7.字符串出现位置

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 ，如果needle字符串为空，则返回0。

public static int strStr(String haystack, String needle) {if (needle.equals("")){return 0;}int index=needle.length();for(int i=0;index<haystack.length();i++,index++){String temp=haystack.substring(i,index);if (temp.equals(needle)){return 1;}}return -1;
}public static void main(String[] args) {String a="hello";String b="ll";int num = strStr(a, b);System.out.println(num);
}

8.搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

答案：

「二分查找」作为一种基础算法，本不该很难，所以希望借这道题的讲解和大家谈谈如何学习算法：「二分查找」就那么几行代码，我们完全有理由充分掌握它，而不可以用记忆模板、背例题的方式；
「二分查找」虽然看起来有很多种写法，「递归」和「非递归」，「非递归」又有好几种写法：while (left <= right)、while (left < right)、while (left + 1 < right)。但核心的思想就一个：逐渐缩小问题规模。我们在学习和练习的时候需要 首先着眼于掌握算法的思想，而不该去纠结二分的几种写法的区别和细节，这样会让自己更乱；
在面对问题的时候，应该将主要精力放在 如何分析，利用单调性（绝大多数二分查找问题利用的是单调性，也有一些例外）或者题目本身蕴含的可以逐渐缩小问题规模的特性解决问题，而不应该纠结在「二分查找」该怎么写。
class Solution {public int search(int[] nums, int target) {int len = nums.length;int left = 0;int right = len - 1;// 在 [left..right] 里查找 targetwhile (left <= right) {// 为了防止 left + right 整形溢出，写成这样int mid = left + (right - left) / 2;if (nums[mid] == target) {return mid;} else if (nums[mid] > target) {// 下一轮搜索区间：[left..mid - 1]right = mid - 1;} else {// 此时：nums[mid] < target，下一轮搜索区间：[mid + 1..right]left = mid + 1;}}return -1;}
}

9.最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

答案：

一：
这道题用动态规划的思路并不难解决，比较难的是后文提出的用分治法求解，但由于其不是最优解法，所以先不列出来
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果1.假如全是负数，那就是找最大值即可，因为负数肯定越加越大。 2.如果有正数，则肯定从正数开始计算和，不然前面有负值，和肯定变小了，所以从正数开始。 3.当和小于零时，这个区间就告一段落了，然后从下一个正数重新开始计算
class Solution {public int maxSubArray(int[] nums) {int ans = nums[0];int sum = 0;for(int num: nums) {if(sum > 0) {sum += num;} else {sum = num;}ans = Math.max(ans, sum);}return ans;}
}
二：
class Solution {public int maxSubArray(int[] nums) {int pre = 0, maxAns = nums[0];for (int x : nums) {pre = Math.max(pre + x, x);maxAns = Math.max(maxAns, pre);}return maxAns;}
}

10.最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词之间用空格隔开。返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串

答案：

标签：字符串遍历
从字符串末尾开始向前遍历，其中主要有两种情况
第一种情况，以字符串"Hello World"为例，从后向前遍历直到遍历到头或者遇到空格为止，即为最后一个单词"World"的长度5
第二种情况，以字符串"Hello World "为例，需要先将末尾的空格过滤掉，再进行第一种情况的操作，即认为最后一个单词为"World"，长度为5
所以完整过程为先从后过滤掉空格找到单词尾部，再从尾部向前遍历，找到单词头部，最后两者相减，即为单词的长度
时间复杂度：O(n)，n为结尾空格和结尾单词总体长度
class Solution {public int lengthOfLastWord(String s) {int end = s.length() - 1;while(end >= 0 && s.charAt(end) == ' ') end--;if(end < 0) return 0;int start = end;while(start >= 0 && s.charAt(start) != ' ') start--;return end - start;}

11.加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头

答案：

根据题意加一，没错就是加一这很重要，因为它是只加一的所以有可能的情况就只有两种：除 99 之外的数字加一；
数字 99。
加一得十进一位个位数为 00 加法运算如不出现进位就运算结束了且进位只会是一。所以只需要判断有没有进位并模拟出它的进位方式，如十位数加 11 个位数置为 00，如此循环直到判断没有再进位就退出循环返回结果。然后还有一些特殊情况就是当出现 9999、999999 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。
class Solution {public int[] plusOne(int[] digits) {for (int i = digits.length - 1; i >= 0; i--) {digits[i]++;digits[i] = digits[i] % 10;if (digits[i] != 0) return digits;}digits = new int[digits.length + 1];digits[0] = 1;return digits;}
}

12.二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0

Integer.toBinaryString()//十进制转换为二进制形式

答案

整体思路是将两个字符串较短的用 00 补齐，使得两个字符串长度一致，然后从末尾进行遍历计算，得到最终结果。本题解中大致思路与上述一致，但由于字符串操作原因，不确定最后的结果是否会多出一位进位，所以会有 2 种处理方式：第一种，在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转
第二种，按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位class Solution {public String addBinary(String a, String b) {StringBuilder ans = new StringBuilder();int ca = 0;for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {int sum = ca;sum += i >= 0 ? a.charAt(i) - '0' : 0;sum += j >= 0 ? b.charAt(j) - '0' : 0;ans.append(sum % 2);ca = sum / 2;}ans.append(ca == 1 ? ca : "");return ans.reverse().toString();}
}

13.x的平方根

实现 int sqrt(int x) 函数。

Math.sqrt(int x)//求平方根

计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

答案：

由于计算机无法存储浮点数的精确值（浮点数的存储方法可以参考 IEEE 754，这里不再赘述），而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 x = 2147395600x=2147395600 时，的计算结果与正确值 4634046340 相差 10^{-11}10 
−11这样在对结果取整数部分时，会得到 4633946339 这个错误的结果。
因此在得到结果的整数部分 ans 后，我们应当找出 ans 与 ans+1 中哪一个是真正的答案
class Solution {public int mySqrt(int x) {if (x == 0) {return 0;}int ans = (int) Math.exp(0.5 * Math.log(x));return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;}
}

14.爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢

答案：

我们用 f(x)f(x) 表示爬到第 xx 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：f(x) = f(x - 1) + f(x - 2)
f(x)=f(x−1)+f(x−2)它意味着爬到第 xx 级台阶的方案数是爬到第 x - 1x−1 级台阶的方案数和爬到第 x - 2x−2 级台阶的方案数的和。很好理解，因为每次只能爬 11 级或 22 级，所以 f(x)f(x) 只能从 f(x - 1)f(x−1) 和 f(x - 2)f(x−2) 转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 00 级开始爬的，所以从第 00 级爬到第 00 级我们可以看作只有一种方案，即 f(0) = 1f(0)=1；从第 00 级到第 11 级也只有一种方案，即爬一级，f(1) = 1f(1)=1。这两个作为边界条件就可以继续向后推导出第 nn 级的正确结果。我们不妨写几项来验证一下，根据转移方程得到 f(2) = 2f(2)=2，f(3) = 3f(3)=3，f(4) = 5f(4)=5，……，我们把这些情况都枚举出来，发现计算的结果是正确的。
class Solution {public int climbStairs(int n) {int p = 0, q = 0, r = 1;for (int i = 1; i <= n; ++i) {p = q; q = r; r = p + q;}return r;}
}

15.合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

答案：

标签：从后向前数组遍历
因为 nums1 的空间都集中在后面，所以从后向前处理排序的数据会更好，节省空间，一边遍历一边将值填充进去
设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部，从尾部值开始比较遍历，同时设置指针 len 指向 nums1 的最末尾，每次遍历比较值大小之后，则进行填充
当 len1<0 时遍历结束，此时 nums2 中海油数据未拷贝完全，将其直接拷贝到 nums1 的前面，最后得到结果数组class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) {int len1 = m - 1;int len2 = n - 1;int len = m + n - 1;while(len1 >= 0 && len2 >= 0) {nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];}}
}

16.买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

答案：

我们需要找出给定数组中两个数字之间的最大差值（即，最大利润）。此外，第二个数字（卖出价格）必须大于第一个数字（买入价格）。形式上，对于每组 ii 和 jj（其中 j > ij>i）我们需要找出 \max(prices[j] - prices[i])max(prices[j]−prices[i])。
public class Solution {public int maxProfit(int prices[]) {int maxprofit = 0;for (int i = 0; i < prices.length - 1; i++) {for (int j = i + 1; j < prices.length; j++) {int profit = prices[j] - prices[i];if (profit > maxprofit) {maxprofit = profit;}}}return maxprofit;}
}
方法二：动态规划
思路：题目只问最大利润，没有问这几天具体哪一天买、哪一天卖，因此可以考虑使用 动态规划 的方法来解决。买卖股票有约束，根据题目意思，有以下两个约束条件：条件 1：你不能在买入股票前卖出股票；
条件 2：最多只允许完成一笔交易。
因此 当天是否持股 是一个很重要的因素，而当前是否持股和昨天是否持股有关系，为此我们需要把 是否持股 设计到状态数组中。状态定义：dp[i][j]：下标为 i 这一天结束的时候，手上持股状态为 j 时，我们持有的现金数。换种说法：dp[i][j] 表示天数 [0, i] 区间里，下标 i 这一天状态为 j 的时候能够获得的最大利润。其中：j = 0，表示当前不持股；
j = 1，表示当前持股。
注意：下标为 i 的这一天的计算结果包含了区间 [0, i] 所有的信息，因此最后输出 dp[len - 1][0]。说明：使用「现金数」这个说法主要是为了体现 买入股票手上的现金数减少，卖出股票手上的现金数增加 这个事实；
「现金数」等价于题目中说的「利润」，即先买入这只股票，后买入这只股票的差价；
因此在刚开始的时候，我们的手上肯定是有一定现金数能够买入这只股票，即刚开始的时候现金数肯定不为 00，但是写代码的时候可以设置为 0。极端情况下（股价数组为 [5, 4, 3, 2, 1]），此时不发生交易是最好的（这一点是补充说明，限于我的表达，希望不要给大家造成迷惑）。
推导状态转移方程：dp[i][0]：规定了今天不持股，有以下两种情况：昨天不持股，今天什么都不做；
昨天持股，今天卖出股票（现金数增加），
dp[i][1]：规定了今天持股，有以下两种情况：昨天持股，今天什么都不做（现金数与昨天一样）；
昨天不持股，今天买入股票（注意：只允许交易一次，因此手上的现金数就是当天的股价的相反数）。public class Solution {public int maxProfit(int[] prices) {int len = prices.length;// 特殊判断if (len < 2) {return 0;}int[][] dp = new int[len][2];// dp[i][0] 下标为 i 这天结束的时候，不持股，手上拥有的现金数// dp[i][1] 下标为 i 这天结束的时候，持股，手上拥有的现金数// 初始化：不持股显然为 0，持股就需要减去第 1 天（下标为 0）的股价dp[0][0] = 0;dp[0][1] = -prices[0];// 从第 2 天开始遍历for (int i = 1; i < len; i++) {dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);}return dp[len - 1][0];}
}

17.买卖股票的最佳时机2

给定一个数组 prices ，其中 prices[i] 是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

答案：

class Solution {public int maxProfit(int[] prices) {int ans = 0;int n = prices.length;for (int i = 1; i < n; ++i) {ans += Math.max(0, prices[i] - prices[i - 1]);}return ans;}
}

18.验证回文串

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

**说明：**本题中，我们将空字符串定义为有效的回文串。

Character.isLetterOrDigit(char ch) 确定指定的字符是否为字母或数字。

字符被认为是字母或数字，如果字符不是Character.isLetter(char ch)也不Character.isDigit(char ch) ，则返回true

toLowerCase() 方法用于将大写字符转换为小写。

答案:

最简单的方法是对字符串 ss 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一个普通的回文串即可。判断的方法有两种。第一种是使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev，只要这两个字符串相同，那么sgood 就是回文串。
class Solution {public boolean isPalindrome(String s) {StringBuffer sgood = new StringBuffer();int length = s.length();for (int i = 0; i < length; i++) {char ch = s.charAt(i);if (Character.isLetterOrDigit(ch)) {sgood.append(Character.toLowerCase(ch));}}StringBuffer sgood_rev = new StringBuffer(sgood).reverse();return sgood.toString().equals(sgood_rev.toString());}
}

19.只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

答案：

方法一：位运算
如果不考虑时间复杂度和空间复杂度的限制，这道题有很多种解法，可能的解法有如下几种。使用集合存储数字。遍历数组中的每个数字，如果集合中没有该数字，则将该数字  加入集合 ，如果集合中已经有该数字，则将该数字  从集合中删除  ，最后剩下的数字就是只出现一次的数字。使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。使用集合存储数组中出现的所有数字，并计算数组中的元素之和。由于集合保证元素无重复，因此计算集合中的所有元素之和的两倍，即为每个元素出现两次的情况下的元素之和。由于数组中只有一个元素出现一次，其余元素都出现两次，因此用集合中的元素之和的两倍减去数组中的元素之和，剩下的数就是数组中只出现一次的数字。上述三种解法都需要额外使用 O(n)O(n) 的空间，其中 nn 是数组长度。如何才能做到线性时间复杂度和常数空间复杂度呢？

class Solution {public int singleNumber(int[] nums) {int single = 0;for (int num : nums) { single ^= num;   //异或运算}return single;}
}

20.多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

答案：

方法一：哈希表
思路我们知道出现次数最多的元素大于n/2 次，所以可以用哈希表来快速统计每个元素出现的次数。算法我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。
class Solution {private Map<Integer, Integer> countNums(int[] nums) {Map<Integer, Integer> counts = new HashMap<Integer, Integer>();for (int num : nums) {if (!counts.containsKey(num)) {counts.put(num, 1);} else {counts.put(num, counts.get(num) + 1);}}return counts;}public int majorityElement(int[] nums) {Map<Integer, Integer> counts = countNums(nums);Map.Entry<Integer, Integer> majorityEntry = null;for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {majorityEntry = entry;}}return majorityEntry.getKey();}
}

答案2：

方法二：排序
思路如果将数组 nums 中的所有元素按照单调递增或单调递减的顺序排序，那么下标为n/2的元素（下标从 0 开始）一定是众数。
算法对于这种算法，我们先将 nums 数组排序，然后返回上文所说的下标对应的元素。下面的图中解释了为什么这种策略是有效的。在下图中，第一个例子是 nn 为奇数的情况，第二个例子是 nn 为偶数的情况。对于每种情况，数组下面的线表示如果众数是数组中的最小值时覆盖的下标，数组下面的线表示如果众数是数组中的最大值时覆盖的下标。对于其他的情况，这条线会在这两种极端情况的中间。对于这两种极端情况，它们会在下标为n/2的地方有重叠。因此，无论众数是多少，返回 n/2下标对应的值都是正确的。class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}

21.颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

答案：

方法一：逐位颠倒
思路将 nn 视作一个长为 3232 的二进制串，从低位往高位枚举 nn 的每一位，将其倒序添加到翻转结果 \textit{rev}rev 中。代码实现中，每枚举一位就将 nn 右移一位，这样当前 nn 的最低位就是我们要枚举的比特位。当 nn 为 00 时即可结束循环。需要注意的是，在某些语言（如 \texttt{Java}Java）中，没有无符号整数类型，因此对 nn 的右移操作应使用逻辑右移。
public class Solution {public int reverseBits(int n) {int rev = 0;for (int i = 0; i < 32 && n != 0; ++i) {rev |= (n & 1) << (31 - i);n >>>= 1;}return rev;}
}

22.判断能否形成等差数列

给你一个数字数组 arr 。

如果一个数列中，任意相邻两项的差总等于同一个常数，那么这个数列就称为 等差数列 。

如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。

答案：

方法一：模拟
class Solution {public boolean canMakeArithmeticProgression(int[] arr) {Arrays.sort(arr);for (int i = 1; i < arr.length - 1; ++i) {if (arr[i] * 2 != arr[i - 1] + arr[i + 1]) {return false;}}return true;}
}

23.位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

答案：

方法一：循环检查二进制位
思路及解法我们可以直接循环检查给定整数 n 的二进制位的每一位是否为 1。具体代码中，当检查第 i位时，我们可以让 n 与 2^i进行与运算，当且仅当 n 的第 i 位为 1 时，运算结果不为 0。
public class Solution public int hammingWeight(int n) {int ret = 0;for (int i = 0; i < 32; i++) {if ((n & (1 << i)) != 0) {ret++;}}return ret;}
}public class Solution {public int hammingWeight(int n) {int ret = 0;while (n != 0) {n &= n - 1;ret++;}return ret;}
}

24.快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

答案：

方法一：用哈希集合检测循环
算法算法分为两部分，我们需要设计和编写代码。给一个数字 nn，它的下一个数字是什么？
按照一系列的数字来判断我们是否进入了一个循环。
第 1 部分我们按照题目的要求做数位分离，求平方和。第 2 部分可以使用哈希集合完成。每次生成链中的下一个数字时，我们都会检查它是否已经在哈希集合中。如果它不在哈希集合中，我们应该添加它。
如果它在哈希集合中，这意味着我们处于一个循环中，因此应该返回 false。
我们使用哈希集合而不是向量、列表或数组的原因是因为我们反复检查其中是否存在某数字。检查数字是否在哈希集合中需要 O(1)O(1) 的时间，而对于其他数据结构，则需要 O(n)O(n) 的时间。选择正确的数据结构是解决这些问题的关键部分。class Solution {private int getNext(int n) {int totalSum = 0;while (n > 0) {int d = n % 10;n = n / 10;totalSum += d * d;}return totalSum;}public boolean isHappy(int n) {Set<Integer> seen = new HashSet<>();while (n != 1 && !seen.contains(n)) {seen.add(n);n = getNext(n);}return n == 1;}
}

25.存在重复元素

给定一个整数数组，判断是否存在重复元素。

如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。

答案：

方法一：排序
在对数字从小到大排序之后，数组的重复元素一定出现在相邻位置中。因此，我们可以扫描已排序的数组，每次判断相邻的两个元素是否相等，如果相等则说明存在重复的元素。class Solution {public boolean containsDuplicate(int[] nums) {Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 1; i++) {if (nums[i] == nums[i + 1]) {return true;}}return false;}
}
方法二：哈希表
对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。class Solution {public boolean containsDuplicate(int[] nums) {Set<Integer> set = new HashSet<Integer>();for (int x : nums) {if (!set.add(x)) {return true;}}return false;}
}

26.存在重复元素II

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 绝对值 至多为 k。

答案：

方法一 （线性搜索） 【超时】
思路
将每个元素与它之前的 k2 个元素中比较查看它们是否相等。算法这个算法维护了一个 k 大小的滑动窗口，然后在这个窗口里面搜索是否存在跟当前元素相等的元素。public boolean containsNearbyDuplicate(int[] nums, int k) {for (int i = 0; i < nums.length; ++i) {for (int j = Math.max(i - k, 0); j < i; ++j) {if (nums[i] == nums[j]) return true;}}return false;
}
方法三 （散列表） 【通过】
思路用散列表来维护这个k大小的滑动窗口。算法在之前的方法中，我们知道了对数时间复杂度的 搜索 操作是不够的。在这个方法里面，我们需要一个支持在常量时间内完成 搜索，删除，插入 操作的数据结构，那就是散列表。这个算法的实现跟方法二几乎是一样的。遍历数组，对于每个元素做以下操作：
在散列表中搜索当前元素，如果找到了就返回 true。
在散列表中插入当前元素。
如果当前散列表的大小超过了 k， 删除散列表中最旧的元素。
返回 false。public boolean containsNearbyDuplicate(int[] nums, int k) {Set<Integer> set = new HashSet<>();for (int i = 0; i < nums.length; ++i) {if (set.contains(nums[i])) return true;set.add(nums[i]);if (set.size() > k) {set.remove(nums[i - k]);}}return false;
}

27.汇总区间

给定一个无重复元素的有序整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

答案：

方法一：一次遍历
我们从数组的位置 00 出发，向右遍历。每次遇到相邻元素之间的差值大于 11 时，我们就找到了一个区间。遍历完数组之后，就能得到一系列的区间的列表。在遍历过程中，维护下标 \textit{low}low 和 \textit{high}high 分别记录区间的起点和终点，对于任何区间都有 \textit{low} \le \textit{high}low≤high。当得到一个区间时，根据 \textit{low}low 和 \textit{high}high 的值生成区间的字符串表示。当 \textit{low}<\textit{high}low<high 时，区间的字符串表示为 ``\textit{low} \rightarrow \textit{high}"‘‘low→high"；当 \textit{low}=\textit{high}low=high 时，区间的字符串表示为 ``\textit{low}"‘‘low"。
class Solution {public List<String> summaryRanges(int[] nums) {List<String> ret = new ArrayList<String>();int i = 0;int n = nums.length;while (i < n) {int low = i;i++;while (i < n && nums[i] == nums[i - 1] + 1) {i++;}int high = i - 1;StringBuffer temp = new StringBuffer(Integer.toString(nums[low]));if (low < high) {temp.append("->");temp.append(Integer.toString(nums[high]));}ret.add(temp.toString());}return ret;}
}

28.有效的字母异位词

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

答案：

方法一：排序
tt 是 ss 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 ss 和 tt 分别排序，看排序后的字符串是否相等即可判断。此外，如果 ss 和 tt 的长度不同，tt 必然不是 ss 的异位词。
class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}char[] str1 = s.toCharArray();   //将字符串转化为字符数组char[] str2 = t.toCharArray();Arrays.sort(str1);Arrays.sort(str2);return Arrays.equals(str1, str2);  //比较两个数组是否相同}
}
方法二：哈希表
从另一个角度考虑，t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母，因此我们可以维护一个长度为 26 的频次数组table，先遍历记录字符串 s 中字符出现的频次，然后遍历字符串 t，减去 table 中对应的频次，如果出现 table[i]<0，则说明 t 包含一个不在 s 中的额外字符，返回 false 即可。
class Solution {public boolean isAnagram(String s, String t) {if (s.length() != t.length()) {return false;}int[] table = new int[26];for (int i = 0; i < s.length(); i++) {table[s.charAt(i) - 'a']++;}for (int i = 0; i < t.length(); i++) {table[t.charAt(i) - 'a']--;if (table[t.charAt(i) - 'a'] < 0) {return false;}}return true;}
}

29.各位相加

给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。

答案：

除个位外，每一位上的值都是通过 (9+1) 进位的过程得到的，想一下 拨算盘进位
把整数 n 看成 n 样物品，原本是以 10 个 1 份打包的，现在从这些 10 个 1 份打包好的里面，拿出 1 个，让它们以 9 个为 1 份打包。
这样就出现了两部分的东西：
原本 10 个现在 9 个 1 份的，打包好的物品，这些，我们不用管
零散的物品，它们还可以分成：
从原来打包的里面拿出来的物品，它们的总和 =》 原来打包好的份数 =》 10进制进位的次数 =》 10 进制下，除个位外其他位上的值的总和
以 10 个 1 份打包时，打不进去的零散物品 =》 10 进制个位上的值
如上零散物品的总数，就是第一次处理 num 后得到的累加值
如果这个累加值 >9，那么如题就还需要将各个位上的值再相加，直到结果为个位数为止。也就意味着还需要来一遍如上的过程。
那么按照如上的思路，似乎可以通过 n % 9 得到最后的值
但是有1个关键的问题，如果 num 是 9 的倍数，那么就不适用上述逻辑。原本我是想得到 n 被打包成 10 个 1 份的份数+打不进 10 个 1 份的散落个数的和。通过与 9 取模，去获得那个不能整除的 1，作为计算份数的方式，但是如果可以被 9 整除，我就无法得到那个 1，也得不到个位上的数。
所以需要做一下特殊处理，(num - 1) % 9 + 1
可以这么做的原因：原本可以被完美分成 9 个为一份的 n 样物品，我故意去掉一个，那么就又可以回到上述逻辑中去得到我要的n 被打包成 10 个一份的份数+打不进 10 个一份的散落个数的和。而这个减去的 1 就相当于从，在 10 个 1 份打包的时候散落的个数中借走的，本来就不影响原来 10 个 1 份打包的份数，先拿走再放回来，都只影响散落的个数，所以没有关系。class Solution {public int addDigits(int num) {return (num - 1) % 9 + 1;}
}

30.丑数

给你一个整数 n ，请你判断 n 是否为 丑数 。如果是，返回 true ；否则，返回 false 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

答案：

方法一：数学
根据丑数的定义，00 和负整数一定不是丑数。当 n>0n>0 时，若 nn 是丑数，则 nn 可以写成 n = 2^a \times 3^b \times 5^cn=2 
a×3 
b×5 
c的形式，其中 a,b,ca,b,c 都是非负整数。特别地，当 a,b,ca,b,c 都是 00 时，n=1n=1。为判断 nn 是否满足上述形式，可以对 nn 反复除以2,3,5，直到 nn 不再包含质因数 2,3,5。若剩下的数等于 11，则说明 nn 不包含其他质因数，是丑数；否则，说明 nn 包含其他质因数，不是丑数。
class Solution {public boolean isUgly(int n) {if (n <= 0) {return false;}int[] factors = {2, 3, 5};for (int factor : factors) {while (n % factor == 0) {n /= factor;}}return n == 1;}
}

31.丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

答案：

方法一：排序
分析如果数组是有序的，那么就很容易知道缺失的数字是哪个了。算法首先我们对数组进行排序，随后我们可以在常数时间内判断两种特殊情况：0 没有出现在数组的首位，以及 nn 没有出现在数组的末位。如果这两种特殊情况都不满足，那么缺失的数字一定在 0 和 nn 之间（不包括两者）。此时我们可以在线性时间内扫描这个数组，如果某一个数比它前面的那个数大了超过 1，那么这两个数之间的那个数即为缺失的数字。
class Solution {public int missingNumber(int[] nums) {Arrays.sort(nums);// 判断 n 是否出现在末位if (nums[nums.length-1] != nums.length) {return nums.length;}// 判断 0 是否出现在首位else if (nums[0] != 0) {return 0;}// 此时缺失的数字一定在 (0, n) 中for (int i = 1; i < nums.length; i++) {int expectedNum = nums[i-1] + 1;if (nums[i] != expectedNum) {return expectedNum;}}// 未缺失任何数字（保证函数有返回值）return -1;}
}