3. Longest Substring Without Repeating Characters
用map存儲(chǔ)每個(gè)字符以及字符所在的位置纹磺，同時(shí)定義了一個(gè)標(biāo)記位馋袜，標(biāo)記當(dāng)前的不重復(fù)字符串是從哪開始的沛硅，標(biāo)記為同時(shí)滿足兩個(gè)條件才會(huì)變動(dòng)，當(dāng)前的map中包含當(dāng)前的字符查坪，當(dāng)前字符在字典中的位置位于標(biāo)記位后面
class Solution {
public int lengthOfLongestSubstring(String s) {
int maxlength = 0;
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
int firstplace = 0;
for(int i = 0; i< s.length();i++){
if((!map.containsKey(s.charAt(i))) || (map.get(s.charAt(i)) < firstplace)){
maxlength = Math.max(maxlength,i-firstplace + 1);
}
else{
firstplace = map.get(s.charAt(i)) + 1;
}
map.put(s.charAt(i),i);
}
return maxlength;
}
}
5. Longest Palindromic Substring
class Solution {
public String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
}
14. Longest Common Prefix
從第一個(gè)字符串肪跋，遍歷所有的字符串歧蒋。兩兩比較找到公共前綴。
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length==0 || strs[0]=="")
return "";
String prefix = strs[0];
for(int i=1;i<strs.length;i++){
while(strs[i].indexOf(prefix)!=0){
prefix = prefix.substring(0,prefix.length()-1);
if(prefix=="") return "";
}
}
return prefix;
}
}
20. Valid Parentheses
這里用到一個(gè)小trick州既，當(dāng)遇到括號(hào)的前面一部分時(shí)谜洽，我們push進(jìn)去的是后一部分，這樣就不需要進(jìn)行復(fù)雜的判斷了吴叶。
class Solution {
public boolean isValid(String s) {
if(s==null || s.length()==0)
return true;
Stack<Character> stack = new Stack<Character>();
char[] t = s.toCharArray();
for(int i=0;i<t.length;i++){
if(t[i]=='(')
stack.push(')');
else if(t[i]=='{')
stack.push('}');
else if(t[i]=='[')
stack.push(']');
else
if(stack.isEmpty() || stack.pop()!=t[I])
return false;
}
return stack.isEmpty();
}
}
22. Generate Parentheses
定義兩個(gè)標(biāo)志阐虚，然后進(jìn)行回溯。第一個(gè)標(biāo)記記錄當(dāng)前還剩下的左括號(hào)的數(shù)量蚌卤，第二個(gè)標(biāo)記記錄當(dāng)前右括號(hào)的數(shù)量实束。如果剩余左括號(hào)，則可以添加左括號(hào)逊彭，如果右括號(hào)的數(shù)量大于左括號(hào)的數(shù)量咸灿，也可以添加右括號(hào)。
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
if(n<1)
return res;
backtracking(res,n,n,"");
return res;
}
public static void backtracking(List<String> res,int leftn,int rightn,String single){
if(leftn==0 && rightn==0)
res.add(single);
if(leftn > 0)
backtracking(res,leftn-1,rightn,single+"(");
if(rightn > leftn)
backtracking(res,leftn,rightn-1,single+")");
}
}
43. Multiply Strings
class Solution {
public String multiply(String num1, String num2) {
int m = num1.length();
int n = num2.length();
int[] res = new int[m+n];
for(int i=m-1;i>=0;i--){
for(int j=n-1;j>=0;j--){
int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
int p1 = i + j + 1;
int p2 = i + j;
mul += res[p1];
res[p1] = mul%10;
res[p2] += mul / 10;
}
}
String resstr = "";
int i = 0;
while(i<res.length && res[i]==0){
I++;
}
for(;i<res.length;i++){
resstr = resstr + res[I];
}
return resstr==""?"0":resstr;
}
}
67. Add Binary
從兩個(gè)數(shù)的后面往前加侮叮，同時(shí)用一個(gè)標(biāo)記為避矢，表示進(jìn)位。
class Solution {
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();
}
}
72. Edit Distance
動(dòng)態(tài)規(guī)劃
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length()+1][word2.length()+1];
if(word1==null && word2==null) return 0;
else if(word1==null) return word2.length();
else if(word2==null) return word1.length();
for(int i=0;i<word2.length()+1;i++)
dp[0][i] = i;
for(int j=0;j<word1.length()+1;j++)
dp[j][0] = j;
for(int i=1;i<word1.length()+1;i++){
for(int j=1;j<word2.length()+1;j++){
if(word1.charAt(i-1)==word2.charAt(j-1))
dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1] + 1),dp[i-1][j-1]);
else
dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1] + 1),dp[i-1][j-1] + 1);
}
}
return dp[word1.length()][word2.length()];
}
}
344. Reverse String
其實(shí)有現(xiàn)成的函數(shù)囊榜，不過(guò)將就著寫個(gè)棧吧谷异。
class Solution {
public String reverseString(String s) {
if(s==null)
return null;
Stack<String> stack = new Stack<String>();
for(int i=0;i<s.length();I++)
stack.push(s.substring(i,i+1));
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pop());
}
return sb.toString();
}
}
383. Ransom Note
用一個(gè)map保存下maganize中出現(xiàn)過(guò)字符及次數(shù)。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
char[] t = magazine.toCharArray();
for(int i=0;i<t.length;i++){
if(map.containsKey(t[I]))
map.put(t[i],map.get(t[i]) + 1);
else
map.put(t[i],1);
}
char[] s = ransomNote.toCharArray();
for(int i=0;i<s.length;i++){
if(!map.containsKey(s[I]))
return false;
if(map.get(s[i])==1)
map.remove(s[I]);
else
map.put(s[i],map.get(s[i])-1);
}
return true;
}
}
387. First Unique Character in a String
也是用一個(gè)map保存下每個(gè)字符出現(xiàn)的次數(shù)锦聊。
class Solution {
public int firstUniqChar(String s) {
Map<Character,Integer> map = new HashMap<Character,Integer>();
char[] charArr = s.toCharArray();
for(int i=0;i<charArr.length;i++){
if(map.containsKey(charArr[i])){
map.put(charArr[i],map.get(charArr[i]) + 1);
}
else{
map.put(charArr[i],1);
}
}
for(int i=0;i<charArr.length;i++){
if(map.get(charArr[i])==1)
return I;
}
return -1;
}
}
459. Repeated Substring Pattern
從一半的長(zhǎng)度開始歹嘹，不斷減少串的長(zhǎng)度，并判斷串是否重復(fù)出現(xiàn)孔庭。
class Solution {
public boolean repeatedSubstringPattern(String s) {
if(s==null)
return false;
int n = s.length();
int len = n / 2;
while(len >= 1){
if(n % len == 0){
String ab = s.substring(0,len);
boolean flag = true;
for(int i=1;i<n/len;i++){
if(!s.substring(len * i,len * (i + 1)).equals(ab)){
flag = false;
break;
}
}
if(flag) return flag;
}
len --;
}
return false;
}
}
520. Detect Capital
用兩個(gè)標(biāo)記位尺上，一個(gè)記錄小寫字母出現(xiàn)的次數(shù)材蛛，一個(gè)記錄大寫字母出現(xiàn)的次數(shù)，最后判斷是否滿足給出的三個(gè)條件即可
class Solution {
public boolean detectCapitalUse(String word) {
int bigcnt = 0;
int smallcnt = 0;
char[] t = word.toCharArray();
for(int i=0;i<t.length;i++){
if(t[i] >= 'a' && t[i] <= 'z')
smallcnt += 1;
else if(t[i] >= 'A' && t[i] <= 'Z')
bigcnt += 1;
else
return false;
}
if(bigcnt == word.length() || smallcnt == word.length())
return true;
else if(bigcnt == 1 && word.charAt(0) >= 'A' && word.charAt(0) <='Z')
return true;
else
return false;
}
}
539. Minimum Time Difference
這個(gè)題目先排序怎抛，然后排序之后比較相鄰的兩個(gè)點(diǎn)之前卑吭，然后最后比較第一個(gè)元素和最后一個(gè)元素。
class Solution {
public int findMinDifference(List<String> timePoints) {
int min = Integer.MAX_VALUE;
Collections.sort(timePoints,new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
String[] time1 = o1.split(":");
String[] time2 = o2.split(":");
int result1 = Integer.parseInt(time1[0]) * 60 + Integer.parseInt(time1[1]);
int result2 = Integer.parseInt(time2[0]) * 60 + Integer.parseInt(time2[1]);
return result1 - result2;
}
});
for(int i = 0; i < timePoints.size() - 1; i ++){
String[] time1 = timePoints.get(i).split(":");
String[] time2 = timePoints.get(i+1).split(":");
int result1 = Integer.parseInt(time1[0]) * 60 + Integer.parseInt(time1[1]);
int result2 = Integer.parseInt(time2[0]) * 60 + Integer.parseInt(time2[1]);
if(min >= result2 - result1) min = result2 - result1;
}
String[] time1 = timePoints.get(0).split(":");
String[] time2 = timePoints.get(timePoints.size() - 1).split(":");
int result1 = Integer.parseInt(time1[0]) * 60 + Integer.parseInt(time1[1]);
int result2 = Integer.parseInt(time2[0]) * 60 + Integer.parseInt(time2[1]);
if(min >= result2 - result1) min = result2 - result1;
if(min >= result1 + 24* 60 - result2) min = result1 + 24* 60 - result2;
return min;
}
}
