3. Longest Substring Without Repeating Characters
用map存储每个字符以及字符所在的位置，同时定义了一个标记位，标记当前的不重复字符串是从哪开始的，标记为同时满足两个条件才会变动，当前的map中包含当前的字符，当前字符在字典中的位置位于标记位后面
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
从第一个字符串，遍历所有的字符串。两两比较找到公共前缀。
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
这里用到一个小trick，当遇到括号的前面一部分时，我们push进去的是后一部分，这样就不需要进行复杂的判断了。
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
定义两个标志，然后进行回溯。第一个标记记录当前还剩下的左括号的数量，第二个标记记录当前右括号的数量。如果剩余左括号，则可以添加左括号，如果右括号的数量大于左括号的数量，也可以添加右括号。
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
从两个数的后面往前加，同时用一个标记为，表示进位。
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
动态规划
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
其实有现成的函数，不过将就着写个栈吧。
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
用一个map保存下maganize中出现过字符及次数。
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
也是用一个map保存下每个字符出现的次数。
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
从一半的长度开始，不断减少串的长度，并判断串是否重复出现。
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
用两个标记位，一个记录小写字母出现的次数，一个记录大写字母出现的次数，最后判断是否满足给出的三个条件即可
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
这个题目先排序，然后排序之后比较相邻的两个点之前，然后最后比较第一个元素和最后一个元素。
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;
}
}
网友评论