共计 4584 个字符，预计需要花费 12 分钟才能阅读完成。
题目 1. 两数之和
*
办法 1，暴力求解，2 层循环，工夫复杂度 O(n^2)，空间复杂度 O(1)
public int[] twoSum(int[] nums, int target) {int[] res = new int[2];
for(int i=0;i<nums.length;i++){for(int j=i+1;j<nums.length;j++){if((nums[j]+nums[i]) == target){res[0]=i;
res[1]=j;
return res;
}
}
}
throw new IllegalArgumentException("No two sum solution");
}大多数人都能间接想到的方法，然而有没有方法 <font color=red>“高大上”</font> 一点呢
办法 2，应用 map，<font color=red>“一次遍历”</font>
咱们晓得 map 可能提供一种 key-value 的对应关系，当咱们确定了
target 以及组成 target 中的一个元素的时候，便有了 target-nums[i] 与 nums[j]
之间的对应关系了，于是咱们就有了
public int[] twoSum(int[] nums, int target) {int[] res = new int[2];
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<nums.length;i++){map.put(nums[i],i);
if(map.get(target-nums[i]) != null && map.get(target-nums[i])!=i) {res[0]=map.get(target-nums[i]);
res[1]=i;
return res;
}
}
throw new IllegalArgumentException("No two sum solution");
}然而这里有一个问题，咱们晓得 map 的 key 是不能反复的，这里呈现了
一种非凡状况须要思考，那就是当两个值雷同的元素呈现时，这里的
map 就会异样，如下图。
所以咱们这里须要把 put 操作放在上面，以防这种非凡状况，同时咱们再对
以上的代码做下优化，比方 if 判断的条件能够改为 map.containsKey，并
在 return 时间接 new 一个数组，不在独自初始化一个。便有了如下 AC 代码：
public int[] twoSum(int[] nums, int target) {int[] res = new int[2];
for(int i=0;i<nums.length;i++){for(int j=i+1;j<nums.length;j++){if((nums[j]+nums[i]) == target){res[0]=i;
res[1]=j;
return res;
}
}
}
throw new IllegalArgumentException("No two sum solution");
}最初，我来解释下为什么下面的“高大上”和“一次遍历”是带引号的，
外表上咱们利用的 map 的属性，get 和 containskey 简化了咱们的代码，
但相熟 map 的敌人都晓得，这两个轮子实际上是通过 map 外部的
getNode 来实现的，其外部应用了 while 循环来实现，所以事实上
咱们的代码在工夫复杂度上还是 O(n^2)，并且你还耗费了肯定的
建设 map 的哈希构造的工夫。<font color=red> 这就通知咱们，不是用了轮子就代表了
高效率，一方面要理解轮子，一方面要具体问题具体分析，灵活运用 </font>
题目 7. 整数反转
** 如果数据范畴给的比拟宽松的话，应用 stringBuilder
的 reverse 这个轮子也是能够的，然而这里做出了限度
，为避免溢出问题应用数学的办法解决 **
具体的防溢出判断能够看 LeetCode 上大佬的思路，这里不献丑了
在不思考溢出问题的状况下，简略演绎下就是，咱们能够通过不停的
取模与取余的操作来获取到一个 n 位数的每一位数字，有了这些，
咱们就能实现将他翻转。比方 123 这个数字，利用 while 循环我顺次
去除了 1，2，3，再在 while 外部应用 ((310)+2)10+ 1 便可轻松解决，
工夫复杂度为 O(n)（n 为 int 数值 x 的长度）
public int reverse(int x) {
int ans = 0;
while (x != 0) {
int pop = x % 10;
if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7))
return 0;
if (ans < Integer.MIN_VALUE / 10 || (ans == Integer.MIN_VALUE / 10 && pop < -8))
return 0;
ans = ans * 10 + pop;
x /= 10;
}
return ans;
} 题目 9. 回文数
不应用 reverse 这个轮子，那就还是用数学方法来解决，
首先依据题干给的例子，正数 pass，而后开端为 0 的数字 pass，
毕竟没有数字是 0 结尾的嘛。
解决完这两种非凡状况，咱们来思考下个别状况。既然是回文数，
那必定能够翻转嘛，不能翻转的必定不是回文数。
在上一题中咱们介绍了数学的反转办法，这里正好用到。
public boolean isPalindrome(int x) {if(x<0 || (x%10==0 && x!=0))
return false;
int res = 0;
int y = x;
while(x!=0){
res = res*10+x%10;
x = x/10;
}
return res==y;
}有了上一题的教训，咱们疾速的写出了翻转的办法。你可能会问，上一题中咱们思考了
溢出的状况，那么这题呢? 能想到这一点阐明你和我一样谨严（手动滑稽）。
** 事实上咱们这里并不需要放心溢出的问题，因为家喻户晓，int 只有 4 字节 32 位字符，
溢出的话并不代表 int 无奈示意，只是会做截取，而这个截取的值必定与原值不同，
就如下图一样 **。
题目 13. 罗马数字转整数
第一反馈是找法则 <font color=red>
IV = 5 -1 =（-1）*1 +5 = 4
VI = 5 + 1 = 5 + 1*1 = 6
XL = 50 – 10 = (-1)*10 + 50 = 40
LX = 50 + 10 = 50 + (1)*10 = 60
<font>
咱们发现，<font color=red> 如果右边的值比左边的小，则做减法，否则就是加法。</font>
于是咱们能够 for 循环做一次遍历，从第二个元素开始，每一个都跟
前一个元素比拟大小，判断加减。有个细节需注意，咱们是在第二个节点
时才判断对第一个节点的加减，因而当跳出循环时，开端元素没有加进去,
因为最初一位元素没有左边一位，因而最初一位元素必然做加法。
public int romanToInt(String s) {
int sum = 0;
char[] c = s.toCharArray();
int previous = judgeSize(c[0]);
for(int i = 1;i < c.length; i ++) {int next = judgeSize(c[i]);
if(previous < next) {sum = sum -previous;} else {sum = sum + previous;}
previous = next;
}
sum = sum + previous;
return sum;
}
private int judgeSize(char ch) {switch(ch) {
case 'I':
return 1;
case 'V':
return 5;
case 'X':
return 10;
case 'L':
return 50;
case 'C':
return 100;
case 'D':
return 500;
case 'M':
return 1000;
default:
return 0;
}
}这里的 switch 也能够用 HashMap 实现映射关系的存储，然而效率上
可能存在肯定消，毕竟建哈希表的工夫也不是天上掉下来的嘛。
工夫复杂度为 O(n)（n 为罗马数字的长度）
题目 14. 最长公共前缀
还是从例子中找思路
**flower，flow，flight
能够得出最长公共前缀为 fl
不过咱们能够看出，如果只有前两个元素，则后果是 flow
在看上面的例子
flower，flow，flight，fow
则最长公共前缀变成了 f **
<font color=red> 以此类推，第一个元素和第二个元素的最长公共前缀，肯定蕴含
或等于（前提是公共前缀存在）第二个元素和第三个元素的前缀 </font>
因而，咱们能够先把第一个元素给取出来，作为最长公共前缀（即本身与本身匹配）
而后在与第二个元素逐字符匹配，能够获取这两个元素的最长公共前缀，
再将后果与第三个元素一一匹配，能够取得前三个元素的最长公共前缀
以此类推, 直至结尾（或后果为空们则间接返回）就能够得出最终后果
public String longestCommonPrefix(String[] strs) {if (strs.length == 0)
return "";
String res = strs[0];
for (int i = 1; i < strs.length; i++) {
int j = 0;
for (; j < res.length() && j < strs[i].length(); j++) {if (!(res.charAt(j) == strs[i].charAt(j))) {break;}
}
res = res.substring(0, j);
if ("".equals(res))
return res;
}
return res;
}工夫复杂度为 O(mn)（n 为数组长度，m 为数组中每个字符串均匀长度）
题目 20. 无效的括号
** 左右括号的对应关系第一反馈是联想到了 key-value 的关系映射。
利用栈的先进后出性能完满解决。
首先，奇数长度字符串先必定不合乎，pass。再来个别状况，
每次遇到左括号就压入，遇到右括号就取出栈顶元素判断是否是
与此右括号对应的左括号（此对应关系利用 hashmap 实现），如不对应
则阐明不合乎，pass。最初，因为左右对应，最初的栈应该是空的，
如果遍历完一次之后栈不空，则阐明有括号未匹配上，pass。**
public boolean isValid(String s) {if (s.length() % 2 == 1) {return false;}
HashMap<Character, Character> brackets = new HashMap<Character, Character>();
brackets.put(')','(');
brackets.put('}','{');
brackets.put(']','[');
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);
if (brackets.containsKey(ch)) {if (stack.isEmpty() || stack.peek() != brackets.get(ch)) {return false;}
stack.pop();} else {stack.push(ch);
}
}
return stack.isEmpty();}复杂度为 O(n^2)（deque 外部的 getNode 也是用了 while 实现，因而为 n *n）
