Friday, November 27, 2015

[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)