---恢复内容开始-
67. Add Binary
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".
思路：这道题不好从后往前遍历，还是从前往后遍历，但用个方法处理一下。此时应检查是否还有另一个字符串没有被遍历完。
若发现存在则继续遍历。遍历完两个字符串后，还需检查进位是否为 0，若进位不为 0，还要加上进位。
public class AddBinary { public String addBinary(String a, String b) { if (a == null || b == null || a.length() == 0 || b.length() == 0) return null; int aLen = a.length(); int bLen = b.length(); StringBuilder sb = new StringBuilder(); int carry = 0; int i = 0; for (; i < aLen && i < bLen; i++) { int sum = (a.charAt(aLen - 1 - i) - '0') + (b.charAt(bLen - 1 - i) - '0') + carry; sb.insert(0, sum % 2); carry = sum / 2; } while (i < aLen) { int sum = (a.charAt(aLen - 1 - i) - '0') + carry; sb.insert(0, sum % 2); carry = sum / 2; i++; } while (i < bLen) { int sum = (b.charAt(bLen - 1 - i) - '0') + carry; sb.insert(0, sum % 2); carry = sum / 2; i++; } if (carry != 0) sb.insert(0, carry); return sb.toString(); } }
293.Flip Game
You are playing the following Flip Game with your friend: Given a string that contains only these two characters:+ and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.
Write a function to compute all possible states of the string after one valid move.
For example, given s = "++++", after one move, it may become one of the following states:
[
"--++",
"+--+",
"++--"
]
If there is no valid move, return an empty list [].
思路：该题不难，判断有没有连续的两个＋＋号即可。
public List<String> generatePossibleNextMoves(String s) { List<String> list = new ArrayList<>(); for (int i = 0; i < s.length() - 1; i++) { if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') { list.add(s.substring(0, i) + "--" + s.substring(i + 2)); } } return list; } }
408. Valid Word Abbreviation
Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.
A string such as “word” contains only the following valid abbreviations:
[“word”, “1ord”, “w1rd”, “wo1d”, “wor1”, “2rd”, “w2d”, “wo2”, “1o1d”, “1or1”, “w1r1”, “1o2”, “2r1”, “3d”, “w3”, “4”]
Notice that only the above abbreviations are valid abbreviations of the string “word”. Any other string is not a valid abbreviation of “word”.
Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.
思路：我们使用双指针分别指向两个单词的开头，循环的条件是两个指针都没有到各自的末尾，
如果指向缩写单词的指针指的是一个数字的话，如果当前数字是0，返回false，因为数字不能以0开头，
然后我们要把该数字整体取出来，所以我们用一个while循环将数字整体取出来，
然后指向原单词的指针也要对应的向后移动这么多位数。如果指向缩写单词的指针指的是一个字母的话，
那么我们只要比两个指针指向的字母是否相同，不同则返回false，相同则两个指针均向后移动一位，参见代码如下：
public class ValidWordAbbreviation { public boolean validWordAbbreviation(String word, String abbr) { int i = 0, j = 0, start = -1; while (i < word.length() && j < abbr.length()) { if (Character.isDigit(abbr.charAt(j))) { if (start == -1) { start = j; if (abbr.charAt(j) - '0' == 0) { return false; } } if (j == abbr.length() - 1) { int num = Integer.parseInt(abbr.substring(start, j + 1)); i += num; } j++; } else { if (start != -1) { int num = Integer.parseInt(abbr.substring(start, j)); i += num; start = -1; } else { if (word.charAt(i) == abbr.charAt(j)) { i++; j++; } else { return false; } } } } if (i == word.length() && j == abbr.length()) return true; else return false; } }
383. Ransom Note
Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.
Each letter in the magazine string can only be used once in your ransom note.
You may assume that both strings contain only lowercase letters.
canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
思路：利用hashmap去存储magazine中的字符，每次出现相同的字符就加1，然后去遍历ransom中的，出现一次相同的就减1，
直到为负值，或者ransom出现了magazine中没有存储过的值。
public class RansomNote { public boolean canConstruct(String ransomNote, String magazine) { Map<Character, Integer> map = new HashMap<>(); for (int i = 0; i < magazine.length(); i++) { if (map.containsKey(magazine.charAt(i))) { map.put(magazine.charAt(i), map.get(magazine.charAt(i)) + 1); } else { map.put(magazine.charAt(i), 1); } } for (int i = 0; i < ransomNote.length(); i++) { if (map.containsKey(ransomNote.charAt(i))) { int temp = map.get(ransomNote.charAt(i)); temp--; if (temp < 0) { return false; } map.put(ransomNote.charAt(i), temp); } else { return false; } } return true; } }
345. Reverse Vowels of a String
Write a function that takes a string as input and reverse only the vowels of a string.
Example 1:
Given s = "hello", return "holle".
Example 2:
Given s = "leetcode", return "leotcede".
Note:
The vowels does not include the letter "y".
public class Solution { public String reverseVowels(String s) { int left=0; int right=s.length()-1; char[] a=s.toCharArray(); String vowels = "aeiouAEIOU"; while(left<right) { while(left<right && !vowels.contains(a[left]+"")) { left++; } while(left<right && !vowels.contains(a[right]+"")) { right--; } if(left<right) { char temp=s.charAt(left); a[left]=a[right]; a[right]=temp; } left++; right--; } return new String(a); } }
344. Reverse String
Write a function that takes a string as input and returns the string reversed.
Example:
Given s = "hello", return "olleh".
public class Solution { public String reverseString(String s) { int left=0; int right=s.length()-1; char[] c=s.toCharArray(); while(left<right) { char temp=c[right]; c[right]=c[left]; c[left]=temp;; left++; right--; } return new String(c); } }
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.
思路：要求把罗马数字转换为整数。倒序从右判断，重点判断4，40，和400的情况处理。
public class Solution { public int romanToInt(String s) { int res = 0; for (int i = s.length() - 1; i >= 0; i--) { char c = s.charAt(i); switch (c) { case 'I': res += (res >= 5 ? -1 : 1); break; case 'V': res += 5; break; case 'X': res += 10 * (res >= 50 ? -1 : 1); break; case 'L': res += 50; break; case 'C': res += 100 * (res >= 500 ? -1 : 1); break; case 'D': res += 500; break; case 'M': res += 1000; break; } } return res; } }
12. Integer to Roman
Given an integer, convert it to a roman numeral.
Input is guaranteed to be within the range from 1 to 3999.
public class IntegertoRoman { public String intToRoman(int num) { int n[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}; String r[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}; String s = ""; for(int i = 0; num > 0; num %= n[i], ++ i) { for(int j = 0, k = num / n[i]; j < k; ++ j) { s += r[i]; } } return s; } }
14. Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
思路：找到字符串数组的最长的公共前缀，利用个下标比较或者利用indexof,这里提供indexof的写法。
public class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length==0) { return ""; } for(int i=0;i<strs.length;i++) { while(strs[i].indexOf(strs[0])!=0) { strs[0]=strs[0].substring(0,strs[0].length()-1); } } return strs[0]; } }
434. Number of Segments in a String
Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.
Please note that the string does not contain any non-printable characters.
Example:
Input: "Hello, my name is John"
Output: 5
思路：其实这个题就是检测空白的地方。有两种思路，第一种先用trim处理头尾的空格。然后用split("\s+")去处理中间的空白部分
补充一下：String[] split(String regex)根据给定的正则表达式的匹配来拆分此字符串。 \s表示空格,回车,换行等空白符
＋ 表示一个或者多个的意思。split("\s+") 按空格,制表符，等进行拆分（也就是说它是按空白部分进行拆分，
不管这个空白使用什么操作留下的,提如空格键 tab键
而split(" +") 按空格进行拆分（也就是说只有按空格键流出来的空白才会是拆分的一句
此处提供两种思路
public int countSegments(String s) { int cnt = 0; int i = 0; for (i = 0; i < s.length(); i++) { if (i == 0 && s.charAt(i) != ' ') { cnt++;//如果第一个值不为空 } if (i > 0 && s.charAt(i - 1) == ' ' && s.charAt(i) != ' ') { cnt++;// 如果当前不是空格,而前一个是空格,+1 } } return cnt; }
public int countSegmentsII(String s) { s=s.trim(); if(s.length()==0){ return 0; } return s.split("\s+").length; }
459. Repeated Substring Pattern
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.
Example 1:
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba"
Output: False
Example 3:
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
思路：自字符串一定能够被整除，我们从这点出发，从两个子字符串开始查找，注意后面比较的时候可以不用stringbuffer，
可以利用一个for循环来比较后几段是否一样。
public class RepeatedSubstringPattern { public boolean repeatedSubstringPattern(String str) { for (int i = str.length() / 2; i >= 1; i--) { if (str.length() % i == 0) { String substr = str.substring(0, i); int size = str.length() / i; int j; for (j = 1; j < size; j++) {// 巧妙避开stringbuffer，如果不满足条件就跳出循环， // 继续寻找新的自字符串长度，如果最后满足，那么一定符合下面 // j＝＝size那个条件，但注意j要放在外面定义，要不是局部变量 if (!substr.equals(str.substring(i * j, i + i * j))) { break; } } if (j == size) { return true; } } } return false; } }
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
思路：典型的用栈的题，先用hashmap将字符处理一下，然后寻找即可，最后要注意查看栈是否为空
public class ValidParentheses { public boolean isValid(String s) { Map<Character, Character> map = new HashMap<>(); map.put('(', ')'); map.put('[', ']'); map.put('{', '}'); Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { if (map.keySet().contains(s.charAt(i))) { stack.push(s.charAt(i)); } else { if (!stack.isEmpty() && s.charAt(i) == map.get(stack.peek())) { stack.pop(); } else { return false; } } } return stack.isEmpty(); } }
28. Implement strStr()
Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
思路：这道题给了我们两个字符串，haystack和needle，让我们判断needle是否是haystack的子字符串，如果是，返回起始的索引位置
如果不是，返回－1.起始这道题利用indexof直接解决，但估计是想让我们变相实现下indexof，所以这里两种解法都写一下。
public int strStr(String haystack, String needle) { return haystack.indexOf(needle); }
public class Solution { public int strStr(String haystack, String needle) { for(int i=0;;i++) { for(int j=0;;j++) { if(j==needle.length()) { return i; } if(j+i==haystack.length()) { return -1; } if(haystack.charAt(i+j)!=needle.charAt(j)) { break; } } } } }
157.Read N Characters Given Read4
The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note: The read function will only be called once for each test case.
思路：用一个临时数组，存放每次read4读到字符，再用一个指针标记buf数组目前存储到的位置，然后将这个临时数组的内容存到buf相应的位置就行了。
这里需要注意两个corner case：1.如果本次读到多个字符，但是我们只需要其中一部分就能完成读取任务时，我们要拷贝的长度是本次读到的个数和剩余所需个数中较小的
2.如果read4没有读满4个，说明数据已经读完，这时候对于读到的数据长度，因为也可能存在我们只需要其中一部分的情况，所以要返回总所需长度和目前已经读到的长度的较小
public class ReadNCharactersGivenReadFour extends Reader4{ public int read(char[] buf, int n) { for(int i=0;i<n;i+=4) { char[] temp=new char[4]; int length=read4(temp); // 将临时数组拷贝至buf数组，这里拷贝的长度是本次读到的个数和剩余所需个数中较小的 System.arraycopy(temp, i, buf, i, Math.min(length, n-i)); // 如果读不满4个，说明已经读完了，返回总所需长度和目前已经读到的长度的较小的 if(length<4) { return Math.min(i+length, n); } } // 如果循环内没有返回，说明读取的字符是4的倍数 return n; } }
158.Read N Characters Given Read4 II - Call multiple times
The API: int read4(char *buf) reads 4 characters at a time from a file.
The return value is the actual number of characters read. For example, it returns 3 if there is only 3 characters left in the file.
By using the read4 API, implement the function int read(char *buf, int n) that reads n characters from the file.
Note: The read function may be called multiple times.
思路：因为要调用多次，这里又多了一些corner case：
第一次调用时，如果read4读出的多余字符我们要先将其暂存起来，这样第二次调用时先读取这些暂存的字符
第二次调用时，如果连暂存字符都没读完，那么这些暂存字符还得留给第三次调用时使用
所以，难点就在于怎么处理这个暂存字符。因为用数组和指针控制对第二种情况比较麻烦，且这些字符满足先进先出，所以我们可以用一个队列暂存这些字符。这样，只要队列不为空，就先读取队列。
public class ReadNCharactersGivenRead4II extends Reader4{ Queue<Character> remain = new LinkedList<Character>(); public int read(char[] buf, int n) { int i = 0; // 队列不为空时，先读取队列中的暂存字符 while(i < n && !remain.isEmpty()){ buf[i] = remain.poll(); i++; } for(; i < n; i += 4){ char[] tmp = new char[4]; int len = read4(tmp); // 如果读到字符多于我们需要的字符，需要暂存这些多余字符 if(len > n - i){ System.arraycopy(tmp, 0, buf, i, n - i); // 把多余的字符存入队列中 for(int j = n - i; j < len; j++){ remain.offer(tmp[j]); } // 如果读到的字符少于我们需要的字符，直接拷贝 } else { System.arraycopy(tmp, 0, buf, i, len); } // 同样的，如果读不满4个，说明数据已经读完，返回总所需长度和目前已经读到的长度的较小的 if(len < 4) return Math.min(i + len, n); } // 如果到这里，说明都是完美读取，直接返回n return n; } }