解题思路来源于网络和 awesome-java-leetcode
本菜鸟以小白的眼光去解释大神的思路。
Easy
1.Two Sum
Given an array of integers, return indices（index 的复数） of the two numbers such that they add up to a specific（具体的、特定的） target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题意为：给定一个整数数组，从中找到两个数字使它们相加等于一个值，最后得到两个数字在数组中的下标。
class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0; i < length; i++){
// 如果map存在和当前数相加等于目标值的数，说明这两个数满足了条件
if(map.containsKey(nums[i])){
// 取出该数在 map 中的下标，同时也是它在 nums 中的下标，因为下文放入了
// 另外取出当前循环的值的下标，因为该下标表示的值满足条件
return new int[]{map.get(nums[i]),i};
}
// map 储存目标减去数组中的值
map.put(target - nums[i],i);
}
return null;
}
}
7.Reverse Integer
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
Input: 123
Output: 321
Example 2:
Input: -123
Output: -321
Example 3:
Input: 120
Output: 21
Note:
Assume we are dealing with an environment which could only hold integers within the 32-bit signed integer range. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
题意为：给定一个32位整型数，返回它的逆序整型数。Note：当它的逆序整型数溢出的话，那么就返回 0。
思路 0：
class Solution {
public int reverse(int x) {
// 先用一个long类型来保存数据
long r = 0;
while(x != 0){
// 第一次循环：取 x 的最小位并赋值给 r，比如 123 先取余数 3
// 第二次循环：让上次取的余数*10变为首位，当前 x=12 因为x/=10并且x是整数类型，再次取余数 2
// 循环提升末位，并不断添加最小位
r = r * 10 + x % 10;
x /= 10;
}
// 判断如果范围溢出返回0
if(r < Integer.MIN_VALUE || r > Integer.MAX_VALUE){
return 0;
}else{
return (int)r;
}
}
}
简化后写法：
class Solution {
public int reverse(int x) {
long res = 0;
for(; x != 0; x /= 10){
res = res*10 + x%10;
}
return res < Integer.MIN_VALUE || res > Integer.MAX_VALUE ? 0 : (int)res;
}
}
9.Palindrome Number
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
Could negative integers be palindromes? (ie, -1)
If you are thinking of converting the integer to string, note the restriction of using extra space.
You could also try reversing an integer. However, if you have solved the problem "Reverse Integer", you know that the reversed integer might overflow. How would you handle such case?
There is a more generic way of solving this problem.
题意为：判断一个有符号整型数是否是回文，也就是逆序过来的整数和原整数相同。负整数肯定不是，逆序过后符号放后了。
解 0：
class Solution {
// 没什么好说的，把整数倒过来判定
public boolean isPalindrome(int x) {
if(x < 0) return false;
int num = 0;
int copyX = x;
while(copyX > 0){
num = num * 10 + copyX % 10;
copyX/=10;
}
return num == x;
}
}
解 1：
class Solution {
public boolean isPalindrome(int x) {
// 循环一半和不判定10的倍数
if (x < 0 || (x != 0 && x % 10 == 0)) return false;
int halfReverseX = 0;
while (x > halfReverseX) {
halfReverseX = halfReverseX * 10 + x % 10;
x /= 10;
}
return halfReverseX == x || halfReverseX / 10 == x;
}
}
13. Roman to Integer
Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.
题意为：给定一个罗马数字，转换为整数 Integer。
范围为 1 - 3999.
百度百科罗马数字介绍：
罗马数字是阿拉伯数字传入之前使用的一种数码。罗马数字采用七个罗马字母作数字、即Ⅰ（1）、X（10）、C（100）、M（1000）、V（5）、L（50）、D（500）。记数的方法：
- 相同的数字连写，所表示的数等于这些数字相加得到的数，如 Ⅲ=3；
- 小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，如 Ⅷ=8、Ⅻ=12；
- 小的数字（限于 Ⅰ、X 和 C）在大的数字的左边，所表示的数等于大数减小数得到的数，如 Ⅳ=4、Ⅸ=9；
- 在一个数的上面画一条横线，表示这个数增值 1,000 倍，如
等于5000。
class Solution {
public int romanToInt(String s) {
// 先把所有罗马英文字母添加到Map
Map<Character,Integer> map = new HashMap<>();
map.put('I',1);
map.put('V',5);
map.put('X',10);
map.put('L',50);
map.put('C',100);
map.put('D',500);
map.put('M',1000);
int length = s.length();
int sum = map.get(s.charAt(length - 1));
// 拿最后一个字母跟前一个相比如果小就需要减，否则加
for(int i = length - 2;i >= 0; i--){
if(map.get(s.charAt(i)) < map.get(s.charAt(i + 1))){
sum -= map.get(s.charAt(i));
}else{
sum += map.get(s.charAt(i));
}
}
return sum;
}
}
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
题意为：给定一个字符串数组，得出数组中这些字符串的公共开头字符串。比如 "leeta" 和 "leetb" 的公共开头为 "leet"。
解题思路 0：
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
// 遍历字符数组，用来跟首个元素作对比
for (int i = 1; i < strs.length; i++)
// 因为 prefix 就是首个字符串，所以把首个排除
while (strs[i].indexOf(prefix) != 0) {
// 如果后面的字符串不是以 prefix 开头的，就减小 prefix 的长度
prefix = prefix.substring(0, prefix.length() - 1);
// 如果最后没有公共字符串，返回 ""
if (prefix.isEmpty()) return "";
}
return prefix;
}
解题思路 1：
出最短的那个字符串的长度minLen，然后在0...minLen的范围比较所有字符串，如果比较到有不同的字符，那么直接返回当前索引长度的字符串即可，否则最后返回最短的字符串即可。
class Solution {
public String longestCommonPrefix(String[] strs) {
int len = strs.length;
if (len == 0) return "";
int minLen = 0x7fffffff; // 0x7FFFFFFF 是long int的最大值
for (String str : strs) minLen = Math.min(minLen, str.length());
for (int j = 0; j < minLen; ++j)
for (int i = 1; i < len; ++i)
if (strs[0].charAt(j) != strs[i].charAt(j))
return strs[0].substring(0, j);
return strs[0].substring(0, minLen);
}
}
