Monday, November 30, 2015

[leetcode]Longest Substring Without Repeating Characters 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        int start = 0;
        int longest = 0;
        HashMap<Character, Integer> lookup = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++){
            char cur = s.charAt(i);
            if (lookup.containsKey(cur) && lookup.get(cur) >= start){
                start = lookup.get(cur)+1;
            }
            lookup.put(cur, i);
            longest = Math.max(longest, i-start+1);
        }
        return longest;
    }
}
Posted by at No comments:

[leetcode]Interleaving String 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length()+s2.length() != s3.length()) return false;
        boolean lookup[] = new boolean[s2.length()+1];
        lookup[0] = true;
        for (int i = 1; i < lookup.length; i++){
            lookup[i] = lookup[i-1] && (s2.charAt(i-1) == s3.charAt(i-1));
        }
        for (int i = 1; i < s1.length()+1; i++){
            lookup[0] = lookup[0] && (s1.charAt(i-1) == s3.charAt(i-1));
            for (int j = 1; j < lookup.length; j++){
                lookup[j] = (lookup[j-1] && s2.charAt(j-1) == s3.charAt(j+i-1)) ||
                            (lookup[j] && s1.charAt(i-1) == s3.charAt(j+i-1));
            }
        }
        return lookup[lookup.length-1];
    }
}
Posted by at No comments:

[leetcode]Longest Palindromic Substring 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public String longestPalindrome(String s) {
        boolean isPalindrome[][] = new boolean[s.length()][s.length()];
        int maxStart = 0;
        int maxEnd = 0;
        for (int i = 0; i < s.length(); i++) isPalindrome[i][i] = true;
        for (int i = 1; i < s.length(); i++){
            for (int j = 0; j < s.length()-i; j++){
                isPalindrome[j][j+i] = s.charAt(j) == s.charAt(j+i) && (i <= 1 || isPalindrome[j+1][j+i-1]);
                if (isPalindrome[j][j+i] && i+1 > maxEnd-maxStart){
                    maxStart = j;
                    maxEnd = j+i;
                }
            } 
        }
        return s.substring(maxStart, maxEnd+1);
    }
}
Posted by at No comments:

[leetcode]Longest Valid Parentheses

用charAt()一直超时 改成char array竟然过了... 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int longestValidParentheses(String s) {
        int longest = 0;
        Stack<Integer> stack = new Stack<Integer>();
        char array[] = s.toCharArray();
        for (int i = 0; i < array.length; i++){
            if (array[i] == ')' &&
                !stack.isEmpty() && array[stack.peek()] != ')'){
                stack.pop();
                if (stack.isEmpty()){
                    longest = Math.max(longest, i+1);
                }else{
                    longest = Math.max(longest, i-stack.peek());
                }
            }else{
                stack.push(i);
            }
        }
        return longest;
    }
}
Posted by at No comments:

Sunday, November 29, 2015

[leetcode]Multiply Strings 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Solution {
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0")) return "0";
        String result = "0";
        for (int i = num1.length()-1,  tailZero = 0; i >= 0; i--, tailZero++){
            int current = num1.charAt(i)-'0';
            int carry = 0;
            String temp = "";
            for (int j = num2.length()-1; j >= 0; j--){
                int v2 = num2.charAt(j)-'0';
                int digit = (v2*current+carry)%10;
                carry = (v2*current+carry)/10;
                temp = digit+temp;
            }
            if (carry != 0) temp = carry+temp;
            temp = temp + getZeros(tailZero);
            result = add(result, temp);
        }
        return result;
    }
    
    private String getZeros(int n){
        String result = "";
        for (int i = 0; i < n; i++){
            result += "0";
        }
        return result;
    }
    
    private String add(String num1, String num2){
        int i = num1.length()-1;
        int j = num2.length()-1;
        int carry = 0;
        String result = "";
        while (i >= 0 || j >= 0){
            int v1 = i >= 0?num1.charAt(i--)-'0':0;
            int v2 = j >= 0?num2.charAt(j--)-'0':0;
            int digit = (v1+v2+carry)%10;
            carry = (v1+v2+carry)/10;
            result = digit+result;
        }
        if (carry == 1) result = "1"+result;
        return result;
    }
}
Posted by at No comments:

[leetcode]Basic Calculator II 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Solution {
    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        List<String> list = new LinkedList<String>();
        String prev = "";
        int i = 0;
        while(i<s.length()){
            char current = s.charAt(i);
            if (current == '*' || current == '/'){
                int numberEnd = nextNumberRange(s, i+1);
                int op2 = Integer.valueOf(s.substring(i+1, numberEnd));
                list.add(doMath(current, Integer.valueOf(list.remove(list.size()-1)), op2)+"");
                i = numberEnd;
            }else if (current == '+' || current == '-'){
                list.add(current+"");
                i++;
            }else{
                int numberEnd = nextNumberRange(s, i);
                list.add(s.substring(i, numberEnd));
                i = numberEnd;
            }
        }
        if (list.isEmpty()) return 0;
  
        while (list.size()!=1){
            int op1 = Integer.valueOf(list.remove(0));
            char op = list.remove(0).charAt(0);
            int op2 = Integer.valueOf(list.remove(0));
            list.add(0,doMath(op, op1, op2)+"");
        }
        return Integer.valueOf(list.remove(0));
    }
    
    private int doMath(char op, int op1, int op2){
        if (op == '*') return op1*op2;
        if (op == '/') return op1/op2;
        if (op == '-') return op1-op2;
        return op1+op2;
    }
    
    
    private int nextNumberRange(String s, int starting){
        while (starting < s.length()){
            char current = s.charAt(starting);
            if (current == '*' || current == '/' 
                ||current == '-' || current == '+'){
                return starting;        
            }
            starting++;
        }
        return starting;
    }
}
Posted by at No comments:

[leetcode]Zigzag conversion 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) return s;
        String[] temp = new String[numRows];
        Arrays.fill(temp, "");
        int updown = 1;
        int current = 0;
        int curRow = 0;
        while (current < s.length()){
            temp[curRow] += s.charAt(current++);
            if (curRow == numRows-1){
                updown = -1;
            }else if (curRow == 0){
                updown = 1;
            }
            curRow += updown;
        }
        String result = "";
        for (int i = 0; i < temp.length; i++) result+=temp[i];
        return result;
    }
}
Posted by at No comments:

[leetcode]Valid Palindrom

上一段神code 
1
2
s=s.toLowerCase().replaceAll("[^a-z0-9]", "");
return new StringBuilder(s).reverse().toString().equals(s);
简练！ 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
    public boolean isPalindrome(String s) {
        int left = 0;
        int right = s.length()-1;
        while (left < right){
            char leftC = Character.toLowerCase(s.charAt(left));
            char rightC = Character.toLowerCase(s.charAt(right));
            boolean leftValid = validCheck(leftC);
            boolean rightValid = validCheck(rightC);
            if(!leftValid){
                left++;
            }
            if(!rightValid){
                right--;
            }
            if (leftValid && rightValid){
                if (leftC != rightC) return false;
                left++;
                right--;
            }
        }
        
        return true;
    }
    
    
    boolean validCheck(char a){
        return Character.isAlphabetic(a) || Character.isDigit(a);
    }
}
Posted by at No comments:

[leetcode]Read N Characters Given Read4 II - Call multiple times 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    List<Character> last = new LinkedList<Character>();
    public int read(char[] buf, int n) {
        int total = 0;
        int fromFour = 4;
        char temp[] = new char[4];
        while (total < n && fromFour == 4){
            fromFour = read4(temp);
            for (int i = 0; i < fromFour; i++){
                last.add(temp[i]);
            }
            total+= fromFour;
        }
        int size = last.size();
        for (int i = 0; i < n && i < size; i++, count++){
            buf[i] = last.remove(0);
        }
        return Math.min(n, size);
    }
}
Posted by at No comments:

Saturday, November 28, 2015

[leetcode] Group anagrams 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<List<String>>();
        HashMap<String, List<String>> lookup = new HashMap<String, List<String>>();
        Arrays.sort(strs);
        for (int i = 0; i < strs.length; i++){
            char[]label = strs[i].toCharArray();
            Arrays.sort(label);
            String key = String.valueOf(label);
            if (!lookup.containsKey(key)){
                lookup.put(key, new ArrayList<String>());  
            }
            lookup.get(key).add(strs[i]);
        }
     
        return new ArrayList<List<String>>(lookup.values());
    }
}
Posted by at No comments:

[leetcode]Scramble String

DP想老半天都想不到。。看答案也不太明解 要是面试问这个 我也就认了.. 用recursion加剪枝吧
f(n) = 2[f(1) + f(n-1)] +2[f(2) + f(n-2)] … + 2[f(n/2) + f(n/2+1)]. 易推得f(n+1) = 3(fn), 故f(n) = O(3^n)。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        if (s1.length() == 1) return s1.equals(s2);
        if (s1.equals(s2)) return true;
        
        int lookup[] = new int[26];
        for (int i = 0; i < s1.length(); i++){
            lookup[s1.charAt(i)-'a']++;
            lookup[s2.charAt(i)-'a']--;
        }
        for (int i = 0; i < 26; i++){
            if (lookup[i] != 0) return false;
        }
        
        for (int i = 1; i < s1.length(); i++){
            if (isScramble(s1.substring(0, i), s2.substring(0, i))
                &&isScramble(s1.substring(i), s2.substring(i))){
                return true;
            }
            if (isScramble(s1.substring(0, i), s2.substring(s2.length()-i))
                &&isScramble(s1.substring(i), s2.substring(0, s2.length()-i))){
                return true;        
            }
        }
        
        return false;
    }
}
Posted by at No comments:

[leetcode]Add Binary

Potential improvement, 用1个loop, out of bound 用expression赋值0, 还有不需要用Integer value of 直接减一减就好了 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public String addBinary(String a, String b) {
        if (a == null || a.equals("")) return b;
        if (b == null || b.equals("")) return a;
        int i = a.length()-1;
        int j = b.length()-1;
        int carry = 0;
        String result = "";
        while (i >= 0 && j >= 0){
            int v1 = Integer.valueOf(a.charAt(i--)+"");
            int v2 = Integer.valueOf(b.charAt(j--)+"");
            int sum = (v1+v2+carry)%2;
            carry = (v1+v2+carry)/2;
            result = sum+result;
        }
        
        while (i>=0){
            int v1 = Integer.valueOf(a.charAt(i--)+"");
            int sum = (v1+carry)%2;
            carry = (v1+carry)/2;
            result = sum+result;
        }
        
        while (j>=0){
            int v2 = Integer.valueOf(b.charAt(j--)+"");
            int sum = (v2+carry)%2;
            carry = (v2+carry)/2;
            result = sum+result;
        }
        if (carry == 1){
            result = "1"+result;
        }
        
        return result;
    }
}
Posted by at No comments:

[leetcode]One Edit Distance 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public boolean isOneEditDistance(String s, String t) {
        if (s == null) return t == null;
        if (t == null) return s == null;
        if (s.equals(t)) return false;
        if (Math.abs(s.length()-t.length())>1) return false;
        if (s.length() < t.length()) return isOneEditDistance(t, s);
        boolean findDiff = false;
        for (int i = 0; i < s.length()-1&&!findDiff; i++){
            if (s.charAt(i) != t.charAt(i)){
               findDiff = true;
               if (s.length() == t.length()){
                   t = t.substring(0,i)+s.charAt(i)+t.substring(i+1, t.length());
               }else{
                   t = t.substring(0,i)+s.charAt(i)+t.substring(i, t.length());
               }
            }
        }
        if (findDiff) return s.equals(t);
        return s.substring(0, s.length()-1).equals(t.substring(0, s.length()-1));
    }
}
Posted by at No comments:

Friday, November 27, 2015

[leetcode] Encode and Decode String

收录一个更加简单的方法（同样思想） 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        StringBuilder sb = new StringBuilder();
        for(String s : strs) {
            sb.append(s.length()).append('/').append(s);
        }
        return sb.toString();
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        List<String> ret = new ArrayList<String>();
        int i = 0;
        while(i < s.length()) {
            int slash = s.indexOf('/', i);
            int size = Integer.valueOf(s.substring(i, slash));
            ret.add(s.substring(slash + 1, slash + size + 1));
            i = slash + size + 1;
        }
        return ret;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
public class Codec {

    // Encodes a list of strings to a single string.
    public String encode(List<String> strs) {
        if (strs == null || strs.size() == 0) return "#-1#";
        String header = "#";
        for (int i = 0; i < strs.size(); i++){
            header = header+strs.get(i).length()+",";
        }

        header = header.substring(0, header.length()-1)+"#";
        String body = "";
        for (int i = 0; i < strs.size(); i++){
            body += strs.get(i);
        }
        return header+body;
    }

    // Decodes a single string to a list of strings.
    public List<String> decode(String s) {
        int[]lengths = readHeader(s);
        List<String> result = new ArrayList<String>();
        if (lengths[0] == -1) return result;
        int starting = lengths[lengths.length-1];
        for (int i = 0; i < lengths.length-1; i++){
            if (lengths[i] == 0){
                result.add("");
            }else{
                result.add(s.substring(starting, starting+lengths[i]));
            }
            starting += lengths[i];
        }
        return result;
    }
    
    int[] readHeader(String s){
        int i = 2;
        for (; i < s.length() && s.charAt(i) != '#'; i++);
        String header = s.substring(1, i);
        String[]temp = header.split(",");
        int[]result = new int[temp.length+1];
        for (int j = 0; j < temp.length; j++){
            result[j] = (new Integer(temp[j])).intValue();
        }
        result[result.length-1] = i+1;//starting index
        return result;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(strs));
Posted by at No comments:

[leetcode]Longest common prefix 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        String result = "";
        int travel = findShortest(strs);
        char current;
        boolean findDiff = false;
        for (int i = 0; i < travel && !findDiff; i++){
            findDiff = false;
            current = strs[0].charAt(i);
            for (int j = 1; j < strs.length && !findDiff; j++){
                if (current != strs[j].charAt(i)) findDiff = true;
            }
            if (!findDiff) result+=current;
        }
           
        return result;
    }
    
    int findShortest(String[] strs){
        if (strs == null || strs.length == 0) return 0;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < strs.length; i++){
            min = Math.min(min, strs[i].length());
        }
        return min;
    }
}
Posted by at No comments:

[leetcode] Count and Say 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public String countAndSay(int n) {
        String trigger = "1";
        for (int i = 1; i < n; i++){
            trigger = getNumber(trigger);
        }
        
        return trigger;
    }
    
    private String getNumber(String n){
        if (n.equals("")) return "";
        char prev = 'a';
        int count = 0;
        String result = "";
        for (int i = n.length()-1; i >= 0; i--){
            char current = n.charAt(i);
            if (current == prev){
                count++;
            }else{
                if (prev != 'a'){
                    result = ""+count+prev+result;
                }
                prev = current;
                count = 1;
            }
        }
        
        if (prev != 'a' && count > 0){
            result = ""+count+prev+result;
        }
        
        return result;
    }
}
Posted by at No comments:

[leetcode]Letter Combinations of a Phone Number

实现题 妙的地方在于做一个lookup 的string array 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public List<String> letterCombinations(String digits) {
        String[] lookup = {"  ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> result = new ArrayList<String>();
        List<String> middle = new ArrayList<String>();
        for (int i = 0; i < digits.length(); i++){
            int number = digits.charAt(i) - '0';
            String temp = lookup[number];
            for(int j = 0; j < temp.length(); j++){
                if (result.isEmpty()){
                    middle.add(temp.charAt(j)+"");
                }else{
                    for(String prev: result){
                        middle.add(prev+temp.charAt(j));
                    }
                }
            }
            List<String>tempList = middle;
            middle = result;
            result = tempList;
            middle.clear();
        }
        return result;
    }
}
Posted by at No comments:

[leetcode]Valid Parentheses 


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public boolean isValid(String s) {
        Stack<Character> lookup = new Stack<Character>();
        for (int i = 0; i < s.length(); i++){
            char temp = s.charAt(i);
            if (isFaceRight(temp)) lookup.push(temp);
            else{
                if (lookup.isEmpty() || lookup.peek() != match(temp))
                    return false;
                lookup.pop();
            }
        }
        return lookup.isEmpty();
    }
    
    private boolean isFaceRight(char a){
        return a == '(' || a == '{' || a == '[';
    }
    
    private char match(char a){
        if (a == ')') return '(';
        if (a == '}') return '{';
        return '[';
    }
}
Posted by at No comments:

[leetcode]Length of Last Word 

1
2
3
4
5
6
7
8
public class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();
        if (s.equals("")) return 0;
        String[]get = s.split(" ");
        return get[get.length-1].length();
    }
}
Posted by at No comments:

[leetcode] group Shifted Strings 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public List<List<String>> groupStrings(String[] strings) {
        List<List<String>> result = new ArrayList<List<String>>();
        for (int i = 0; i < strings.length; i++){
            String temp = strings[i];
            boolean found = false;
            for (int j = 0; j < result.size() && !found; j++){
                found = isSameGroup(temp, result.get(j).get(0));
                if (found){
                    result.get(j).add(temp);
                }
            }
            if (!found){
                ArrayList<String> list = new ArrayList<String>();
                list.add(temp);
                result.add(list);
            }
        }
        for (int i = 0; i < result.size(); i++) Collections.sort(result.get(i));
        return result;
    }
    
    private boolean isSameGroup(String c, String d){
        if (c.length() != d.length()) return false;
        if (c.length() == 0) return true;
        int difference = (c.charAt(0) - d.charAt(0)) %26;
        difference = difference < 0?difference+26:difference;
        for (int i = 1; i < c.length(); i++){
            int localDiff = (c.charAt(i) - d.charAt(i)) %26;
            localDiff = localDiff < 0?localDiff+26:localDiff;
            if (localDiff != difference) return false;
        }
        return true;
    }
}
Posted by at No comments:

[leetcode]Read N Characters Given Read4 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* The read4 API is defined in the parent class Reader4.
      int read4(char[] buf); */

public class Solution extends Reader4 {
    /**
     * @param buf Destination buffer
     * @param n   Maximum number of characters to read
     * @return    The number of characters read
     */
    public int read(char[] buf, int n) {
        int sum = 0;
        char[] temp = new char[4];
        int readNum = 4;
        while (sum < n && readNum == 4){
            readNum = read4(temp);
            for (int i = 0; i < readNum && sum < n; i++){
                buf[sum++] = temp[i];
            }
        }
        return sum;
    }
}
Posted by at No comments:

[leetcode]Reverse Words in a String II

这里的妙处是把每个单词都先翻转 然后整个翻转 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public void reverseWords(char[] s) {
        int current = 0;
        for (int i = 0; i < s.length; i++){
            if (i == s.length-1||s[i+1] == ' '){
                reverse(s, current, i);
                current = i+2;
            }
        }
        reverse(s, 0, s.length-1);
    }
    
    private void reverse(char[]s, int start, int end){
        while (start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;
            end--;
            start++;
        }
    }
}
Posted by at No comments:

[leetcode] Longest Substring with At Most Two Distinct Characters 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        if (s == null || s.length() == 0) return 0;
        if (s.length() == 1) return 1;
        char c1 = s.charAt(0);
        char c2 = s.charAt(1);
        int i1 = 0;
        int i2 = 0;
        int length = 2;
        for (int i = 2; i < s.length(); i++){
            char current = s.charAt(i);
            if (current != c1 && current != c2){
                c1 = current;
                c2 = s.charAt(i-1);
                i1 = i;
                i2 = i-1;
                while (i2 >= 0&&s.charAt(i2) == c2){
                    i2--;
                }
                i2++;
            }
            length = Math.max(length, i-Math.min(i1, i2)+1);
        }
        return length;
    }
}
Posted by at No comments:

[leetcode]Generate Parentheses 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public List<String> generateParenthesis(int n) {
        if (n < 0) return result;
        rec(n, 0, "");
        return result;
    }
    
    List<String> result = new ArrayList<String>();
    private void rec(int available, int unmatch, String fromUpper){
        if (available == 0){
            for (int i = 0; i < unmatch; i++) fromUpper += ")";
            result.add(fromUpper);
            return;
        }
        String addOn = "";
        for (int i = 0; i <= unmatch; i++){
            rec(available-1, unmatch-i+1, fromUpper+addOn+"(");
            addOn += ")";
        }
    }
}
Posted by at No comments:

Thursday, November 26, 2015

[leetcode]Best Time to Buy and Sell stock series 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int currentMin = prices[0];
        int result = 0;
        for (int i = 1; i < prices.length; i++){
            result = Math.max(result, prices[i]-currentMin);
            currentMin = Math.min(currentMin, prices[i]);
        }
        
        return result;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int currentStart = 0;
        int currentEnd = 0;
        int sum = 0;
        for (int i = 1; i < prices.length; i++){
            if (prices[i] < prices[i-1]){
                sum += (prices[currentEnd]-prices[currentStart]);
                currentStart = currentEnd = i;
            }else{
                currentEnd = i;
            }
        }
        sum += (prices[currentEnd]-prices[currentStart]);
        return sum;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) return 0;
        int[] profit = new int[prices.length];
        int[] profit_r = new int[prices.length];
        findMaxI(prices, profit);
        findMaxII(prices, profit_r);
        int max = 0;
        for (int i = 0; i < prices.length; i++){
            max = Math.max(profit[i]+profit_r[i], max);
        }
        return max;
    }
    
    private void findMaxII(int[]prices, int profit[]){
        int currentMax = prices[prices.length-1];
        int last = profit[prices.length-1];
        for (int i = prices.length-2; i >= 0; i--){
            profit[i] += Math.max(profit[i+1], currentMax-prices[i]);
            currentMax = Math.max(prices[i], currentMax);
        }
        return;
    }
    
    private void findMaxI(int[]prices, int profit[]){
        int currentMin = prices[0];
        for (int i = 1; i < prices.length; i++){
            profit[i] = Math.max(profit[i-1], prices[i]-currentMin);
            currentMin = Math.min(prices[i], currentMin);
        }
        return;
    }
}
Posted by at No comments:

Wednesday, November 25, 2015

[leetcode] Maximum Product 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int maxProduct(int[] nums) {
        int prePos = 1;
        int preNeg = 1;
        int max = Integer.MIN_VALUE;
        int singleMax = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++){
            singleMax = Math.max(nums[i], singleMax);
            if (nums[i] > 0){
                prePos = prePos*nums[i];
                preNeg = (preNeg*nums[i] < 0)?preNeg*nums[i]:1;
                max = Math.max(max, prePos);
            }else if (nums[i] < 0){
                if (preNeg*nums[i] > 0) max = Math.max(max, preNeg*nums[i]);
                int temp = prePos;
                prePos = (preNeg*nums[i] > 0)?preNeg*nums[i]:1;
                preNeg = temp*nums[i];
            }else{
                prePos = preNeg = 1;
            }
        }

        return Math.max(singleMax, max);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxProduct(int A[], int n) {
        if(n<=0) return 0;
        int ret, curMax, curMin;
        ret = curMax = curMin = A[0];
        for(int i=1; i<n; i++) {
            int temp = curMax;
            curMax = max(max(curMax*A[i], curMin*A[i]),A[i]);
            curMin = min(min(temp*A[i], curMin*A[i]),A[i]);
            ret = max(ret, curMax);
        }
        return ret;
    }
};
Posted by at No comments:
Subscribe to: Posts (Atom)