解題思路來源于網(wǎng)絡(luò)和 awesome-java-leetcode
本菜鳥以小白的眼光去解釋大神的思路良哲。
Easy
1.Two Sum
Given an array of integers, return indices（index 的復(fù)數(shù)） 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].
題意為：給定一個整數(shù)數(shù)組，從中找到兩個數(shù)字使它們相加等于一個值，最后得到兩個數(shù)字在數(shù)組中的下標(biāo)谨朝。
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存在和當(dāng)前數(shù)相加等于目標(biāo)值的數(shù)，說明這兩個數(shù)滿足了條件
if(map.containsKey(nums[i])){
// 取出該數(shù)在 map 中的下標(biāo)抽碌，同時也是它在 nums 中的下標(biāo)旺订，因為下文放入了
// 另外取出當(dāng)前循環(huán)的值的下標(biāo)，因為該下標(biāo)表示的值滿足條件
return new int[]{map.get(nums[i]),i};
}
// map 儲存目標(biāo)減去數(shù)組中的值
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位整型數(shù)赠摇，返回它的逆序整型數(shù)固逗。Note：當(dāng)它的逆序整型數(shù)溢出的話，那么就返回 0藕帜。
思路 0：
class Solution {
public int reverse(int x) {
// 先用一個long類型來保存數(shù)據(jù)
long r = 0;
while(x != 0){
// 第一次循環(huán)：取 x 的最小位并賦值給 r烫罩，比如 123 先取余數(shù) 3
// 第二次循環(huán)：讓上次取的余數(shù)*10變?yōu)槭孜唬?dāng)前 x=12 因為x/=10并且x是整數(shù)類型洽故，再次取余數(shù) 2
// 循環(huán)提升末位贝攒，并不斷添加最小位
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.
題意為：判斷一個有符號整型數(shù)是否是回文，也就是逆序過來的整數(shù)和原整數(shù)相同时甚。負整數(shù)肯定不是隘弊，逆序過后符號放后了哈踱。
解 0：
class Solution {
// 沒什么好說的，把整數(shù)倒過來判定
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) {
// 循環(huán)一半和不判定10的倍數(shù)
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.
題意為：給定一個羅馬數(shù)字梨熙，轉(zhuǎn)換為整數(shù) Integer开镣。
范圍為 1 - 3999.
百度百科羅馬數(shù)字介紹：
羅馬數(shù)字是阿拉伯?dāng)?shù)字傳入之前使用的一種數(shù)碼。羅馬數(shù)字采用七個羅馬字母作數(shù)字咽扇、即Ⅰ（1）邪财、X（10）、C（100）肌割、M（1000）卧蜓、V（5）、L（50）把敞、D（500）弥奸。記數(shù)的方法：
- 相同的數(shù)字連寫，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)奋早，如 Ⅲ=3盛霎；
- 小的數(shù)字在大的數(shù)字的右邊，所表示的數(shù)等于這些數(shù)字相加得到的數(shù)耽装，如 Ⅷ=8愤炸、Ⅻ=12；
- 小的數(shù)字（限于 Ⅰ掉奄、X 和 C）在大的數(shù)字的左邊规个，所表示的數(shù)等于大數(shù)減小數(shù)得到的數(shù)，如 Ⅳ=4姓建、Ⅸ=9诞仓；
- 在一個數(shù)的上面畫一條橫線，表示這個數(shù)增值 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.
題意為：給定一個字符串?dāng)?shù)組涣狗，得出數(shù)組中這些字符串的公共開頭字符串谍婉。比如 "leeta" 和 "leetb" 的公共開頭為 "leet"。
解題思路 0：
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
// 遍歷字符數(shù)組镀钓，用來跟首個元素作對比
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的范圍比較所有字符串，如果比較到有不同的字符，那么直接返回當(dāng)前索引長度的字符串即可措译，否則最后返回最短的字符串即可别凤。
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);
}
}
