Count and Say
思路：递归求出n - 1时的字符串，然后双指针算出每个字符的次数，拼接在结果后面
public String countAndSay(int n) {
if(n == 1) return "1";
String front = countAndSay(n - 1);
int i = 0;
int j = 0;
String res = "";
int count = 0;
while(j < front.length()){
while(j < front.length() && front.charAt(i) == front.charAt(j)){
count++;
j++;
}
res = res.concat(String.valueOf(count));
res += (front.charAt(i));
count = 0;
i = j;
}
return res;
}
Add Binary
思路：当string有值时，就将数值加起来，该位置的结果为sum % 2，利用carry = sum / 2作为下一次的结果初值，拼接起来，最后翻转string
public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1, j = b.length() -1, carry = 0;
while (i >= 0 || j >= 0) {
int sum = carry;
if (j >= 0) sum += b.charAt(j--) - '0';
if (i >= 0) sum += a.charAt(i--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
if (carry != 0) sb.append(carry);
return sb.reverse().toString();
}
Mini Parser
思路：
If encounters '[', push current NestedInteger to stack and start a new one.
If encounters ']', end current NestedInteger and pop a NestedInteger from stack to continue.
If encounters ',', append a new number to curr NestedInteger, if this comma is not right after a brackets.
Update index l and r, where l shall point to the start of a integer substring, while r shall points to the end+1 of substring.
public NestedInteger deserialize(String s) {
if(s == null || s.isEmpty()) return null;
if(s.charAt(0) != '[') return new NestedInteger(Integer.parseInt(s));
int l = 0;
NestedInteger cur = null;
Stack<NestedInteger> stack = new Stack<NestedInteger>();
for(int r = 0; r < s.length(); r++){
if(s.charAt(r) == '['){
if(cur != null) stack.push(cur);
cur = new NestedInteger();
l = r + 1;
}
else if(s.charAt(r) == ','){
if(s.charAt(r - 1) != ']'){
String num = s.substring(l,r);
cur.add(new NestedInteger(Integer.parseInt(num)));
}
l = r + 1;
}
else if(s.charAt(r) == ']'){
String num = s.substring(l,r);
if(!num.isEmpty()){
cur.add(new NestedInteger(Integer.parseInt(num)));
}
if(!stack.isEmpty()){
NestedInteger p = stack.pop();
p.add(cur);
cur = p;
}
l = r + 1;
}
}
return cur;
}
Group Anagrams
思路：将每个字符串变成字符数组以后排序，将排序后相同的字符串放在一个list，形成最终结果
主要学习toCharArray Arrays.sort String.valueOf map.values()
public List<List<String>> groupAnagrams(String[] strs) {
List<List<String>> res = new ArrayList<List<String>>();
if(strs.length == 0 || strs == null) return res;
HashMap<String,ArrayList<String>> map = new HashMap<String,ArrayList<String>>();
for(int i = 0; i < strs.length; i++){
char[] c = strs[i].toCharArray();
Arrays.sort(c);
if(map.containsKey(String.valueOf(c))){
ArrayList<String> list = map.get(String.valueOf(c));
list.add(strs[i]);
}
else{
ArrayList<String> list = new ArrayList<String>();
list.add(strs[i]);
map.put(String.valueOf(c),list);
}
}
return new ArrayList<List<String>>(map.values());
}
17. Letter Combinations of a Phone Number
思路：建立数字和字符串的对应关系，回溯
public List<String> letterCombinations(String digits) {
HashMap<Integer,String> map = new HashMap<Integer,String>();
map.put(2,"abc");
map.put(3,"def");
map.put(4,"ghi");
map.put(5,"jkl");
map.put(6,"mno");
map.put(7,"pqrs");
map.put(8,"tuv");
map.put(9,"wxyz");
ArrayList<String> list = new ArrayList<String>();
for(int i = 0; i < digits.length(); i++){
list.add(map.get(digits.charAt(i) - '0'));
}
List<String> res = new ArrayList<String>();
if(digits.equals("")) return res;
dfs(res,"",list,0);
return res;
}
public void dfs(List<String> res,String ans,ArrayList<String> list,int start){
if(start == list.size()){
res.add(ans);
return;
}
for(int i = start; i < list.size(); i++){
String s = list.get(i);
for(int j = 0; j < s.length(); j++){
ans += s.charAt(j);
dfs(res,ans,list,i + 1);
ans = ans.substring(0,ans.length() - 1);
}
//强制返回第一层，否则在最后一次回溯结束以后会继续循环i++
return;
}
}
Basic Calculator II
思路：先判断第一个数的符号和开始下标，然后依次往后循环，若是数字则算出num，若是+-则入栈，是*/则直接计算后入栈，别忘了将最后一个num入栈，最后将栈中数字相加
public int calculate(String s) {
if(s == null || s.isEmpty()) return 0;
Stack<Integer> stack = new Stack<Integer>();
int num = 0;
//判断第一个数是正数还是负数
char sign = (s.charAt(0) == '-') ? '-' : '+';
int i = (sign == '-') ? 1 : 0;
while(i < s.length()){
if(Character.isDigit(s.charAt(i))){
num = num * 10 + (s.charAt(i) - '0');
}
//只有一个数的情况
if((!Character.isDigit(s.charAt(i)) && s.charAt(i) != ' ') || i == s.length() - 1){
if(sign == '+'){
stack.push(num);
}
else if(sign == '-'){
stack.push(-num);
}
else if(sign == '*'){
stack.push(stack.pop() * num);
}
else if(sign == '/'){
stack.push(stack.pop() / num);
}
sign = s.charAt(i);
num = 0;
}
i++;
}
int res = 0;
for(int j : stack){
res += j;
}
return res;
}
**91. Decode Ways
思路：用数组dp[n + 1]表示第几位的不同解码数，判断当前位数字范围和前两位数字范围，动态规划
public int numDecodings(String s) {
if(s == null || s.isEmpty()) return 0;
int[] dp = new int[s.length() + 1];
dp[0] = 1;
dp[1] = (s.charAt(0) == '0') ? 0 : 1;
for(int i = 2; i < s.length() + 1; i++){
int first = Integer.parseInt(s.substring(i - 1,i));
int second = Integer.parseInt(s.substring(i - 2,i));
if(first >= 1 && first <= 9) dp[i] += dp[i - 1];
if(second >= 10 && second <= 26) dp[i] += dp[i - 2];
}
return dp[s.length()];
}
**93. Restore IP Addresses
思路：回溯
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<String>();
if(s == null || s.isEmpty()) return res;
dfs(res,s,"",0,0);
return res;
}
//ans表示每个符合要求的solution，idx用来截取每段地址，i表示每段地址的长度，count表示第几段
public void dfs(List<String> res,String s,String ans,int idx,int count){
if(count > 4) return;
if(count == 4 && idx == s.length()){
res.add(ans);
return;
}
for(int i = 1; i < 4; i++){
if(idx + i > s.length()) break;
String str = s.substring(idx,idx + i);
if((str.charAt(0) == '0' && str.length() != 1) || (str.length() == 3 && Integer.parseInt(str) > 255)) continue;
dfs(res,s,ans + str + ((count == 3) ? "" : "."),idx + i,count + 1);
}
}
**214. Shortest Palindrome
public String shortestPalindrome(String s) {
int j = 0;
for(int i = s.length() - 1; i >= 0; i--){
if(s.charAt(i) == s.charAt(j)) j++;
}
if(j == s.length()) return s;
String str = s.substring(j);
return new StringBuffer(str).reverse().toString() + shortestPalindrome(s.substring(0,j)) + str;
}
**76. Minimum Window Substring
思路：用map存储字符和个数，利用count来控制已经出现的字符个数，然后滑动窗口计算长度
public String minWindow(String s, String t) {
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for(int i = 0; i < t.length(); i++){
if(map.containsKey(t.charAt(i))){
map.put(t.charAt(i),map.get(t.charAt(i)) + 1);
}
else{
map.put(t.charAt(i),1);
}
}
int left = 0;
int minLeft = 0;
int minLen = Integer.MAX_VALUE;
int count = 0;
//map中的value值大于0说明还有字符没找到，小于等于0说明窗口已经包含
for(int right = 0; right < s.length(); right++){
if(map.containsKey(s.charAt(right))){
map.put(s.charAt(right),map.get(s.charAt(right)) - 1);
if(map.get(s.charAt(right)) >= 0) count++;
}
while(count == t.length()){
if(minLen > right - left + 1){
minLen = right - left + 1;
minLeft = left;
}
if(map.containsKey(s.charAt(left))){
map.put(s.charAt(left),map.get(s.charAt(left)) + 1);
if(map.get(s.charAt(left)) > 0) count--;
}
left++;
}
}
return (minLen == Integer.MAX_VALUE) ? "" : s.substring(minLeft,minLeft + minLen);
}
总结
344：reverse string
8. String to Integer (atoi)：1.判空；2.除空格；3.定符号；4.算数值，判越界
383. Ransom Note：抽屉法，先将字母一个个放入，然后一个个拿出，若全都能拿出，则返回true
14. Longest Common Prefix：找出所有字符串中长度最短的，然后判断是否为所有串公共前缀，循环--
345. Reverse Vowels of a String：双指针，分别从前后找到元音字母（大小写），然后交换
20. Valid Parentheses:利用栈，若是左括号则入栈，是右括号则判断栈是否为空，然后判断栈顶元素是否为左括号，是则出栈，最后看栈是否为空
434. Number of Segments in a String：先除首尾空格后按空格分隔，结果为分隔后数组长度
28. Implement strStr()：indexOf
58. Length of Last Word:利用trim()和lastIndexOf()或者trim()和split()
468. Validate IP Address:分隔以后判断，考虑全面就行
151. Reverse Words in a String：分隔以后翻转列表
22. Generate Parentheses：利用left和right记录左括号数和右括号数，当都为0时即一个solution
273. Integer to English Words：利用三个字符串数组，递归拼接最终结果
训练
459. Repeated Substring Pattern：Repeated Substring的长度最多为原串的一半，则循环查找符合长度要求的串，看是不是Repeated Substring
**6. ZigZag Conversion:一行一行连接，找到每行下标的规律
13. Roman to Integer：用两个指针分别表示当前指向和前一个指向，注意I V X L C D M，VX前只能是I，LC前只能是X，DM前只能是C
12. Integer to Roman:利用数组列出所有组合，然后依次减，连接所有字符串
165. Compare Version Numbers：先按.分隔，然后使用巧妙的方法使两个数组长度对齐，最后利用Integer的compareTo方法得到结果
125. Valid Palindrome：使用正则表达式先将非字母数字的字符替换成“”，然后利用reverse判断
**43. Multiply Strings：s1[i] * s2[j]的结果在最终结果的res[i + j]和res[i + j + 1]位，最后去除首位的0即可
71. Simplify Path：利用栈，通过/分隔，注意用法ArrayList<String> list = new ArrayList<String>(stack); "/" + String.join("/",list)
3. Longest Substring Without Repeating Characters：利用map存储字符以及下标，利用双指针控制字符串首尾位置
**5. Longest Palindromic Substring：分两种情况，考虑结果位数是奇数和偶数，分别求解
**32. Longest Valid Parentheses：利用栈，将合理的括号都提取出来，只留下分隔的字符，然后依次计算间隔取最大，注意应该入栈字符下标，要不然不好计算间隔长度
**87. Scramble String：先判断长度和字符是否完全一致，若符合条件则要么左右子树完全一致，要么左右子树完全翻转，递归求解
**72. Edit Distance:构造int[m + 1][n + 1]表示长度为i的字符串到长度为j的字符串需要多少步，初始化以后，若字符相等则f(i,j) = f(i - 1,j - 1)，不相等则在插入、删除和替换三者大的那个加一即可
提示
String常用函数：
charAt compareTo contains concat endsWith equals indexOf(int/string) lastIndexOf(int/string) length() matches(regex) replace(char old, char new) split startsWith substring(begin, end) toCharArray toLowerCase/toUpperCase trim()
StringBuffer常用函数：
charAt indexOf lastIndexOf length() substring
append delete reverse setCharAt toString
因此需要删除、翻转、set操作应该先将string转化为StringBuffer
Arrays常用函数：
sort copyOfRange(origin[],from,to)包前不包后 asList:list.add(new ArrayList<Integer>(Arrays.asList(1,2,3)));
int string char char[] Array之间的常用用法：
int->string:String.valueOf(int) int->char:(char)(int + 48)
string->int:Integer.parseInt(string) string->char[]:string.toCharArray()
char->int:char - '0'/Character.getNumericValue(char) char->string:String.valueOf(char)
char[]->string:String.valueOf(char[])
Arrays.sort(char[])