Wednesday, November 25, 2015

[leetcode]Summary Range 

 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> summaryRanges(int[] nums) {
        List<String> result = new ArrayList<String>();
        if (nums == null || nums.length == 0) return result;
        int prev = 0;
        int current = 1;
        while (current < nums.length){
            if (nums[current] != nums[current-1]+1){
                result.add(generateRange(nums[prev], nums[current-1]));
                prev = current;
            }
            current++;
        }
        result.add(generateRange(nums[prev], nums[current-1]));
        return result;
    }

    private String generateRange(int from, int to){
        return from==to?""+from:from+"->"+to;
    }
}
Posted by at No comments:

[leetcode[ Spiral Matrix

想想奇数最后一行的方向 就搞掂 
 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 List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;
        int hStart = 0;
        int hEnd = matrix[0].length-1;
        int vStart = 0;
        int vEnd = matrix.length-1;

        while (hStart < hEnd && vStart < vEnd){
            for (int i = hStart; i < hEnd; i++) result.add(matrix[vStart][i]);
            for (int i = vStart; i < vEnd; i++) result.add(matrix[i][hEnd]);
            for (int i = hEnd; i > hStart; i--) result.add(matrix[vEnd][i]);
            for (int i = vEnd; i > vStart; i--) result.add(matrix[i][hStart]);
            hStart++;
            hEnd--;
            vStart++;
            vEnd--;
        }

        if (hStart == hEnd && vStart <= vEnd){
            for (int i = vStart; i <= vEnd; i++) result.add(matrix[i][hStart]);
        }else if (vStart == vEnd && hStart <= hEnd){
            for (int i = hStart; i <= hEnd; i++) result.add(matrix[vStart][i]);
        }

        return result;
    }
}
Posted by at No comments:

[leetcode] Word Search 

 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 boolean exist(char[][] board, String word) {
        boolean visited[][] = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[i].length; j++){
                if (dfs(board, word, 0, i, j, visited)) return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int wordIndex, int i, int j, boolean[][] visited){
        if (i < 0 || i > board.length-1 || j < 0 || j > board[i].length-1 || wordIndex >= word.length()) return false;
        if (visited[i][j] || board[i][j] != word.charAt(wordIndex)) return false;
        if (wordIndex == word.length()-1 && !visited[i][j] && board[i][j] == word.charAt(wordIndex)) return true;
        boolean result = false;
        visited[i][j] = true;
        if (dfs(board, word, wordIndex+1, i-1, j, visited)||
            dfs(board, word, wordIndex+1, i+1, j, visited)||
            dfs(board, word, wordIndex+1, i, j-1, visited)||
            dfs(board, word, wordIndex+1, i, j+1, visited)){
            result = true;
        }
        visited[i][j] = false;
        return result;
    }
}
Posted by at No comments:

[leetcode] 4 Sum

就是一层一层剥下去直到变成2sum 
 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
54
55
56
57
58
59
60
61
public class Solution {
    public List<List<Integer>> kSum(int[]nums, int k, int target, int start){
        if (k == 1) return oneSum(nums, target, start);
        if (k == 2) return twoSum(nums, target, start);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = start; i <= nums.length-k; i++){
            if (i == start || nums[i] != nums[i-1]){
                List<List<Integer>> temp = kSum(nums, k-1, target-nums[i], i+1);
                for (List<Integer> list:temp){
                    list.add(0, nums[i]);
                    result.add(list);
                }
            }
        }
        return result;
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) return new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        return kSum(nums, 4, target, 0);
    }

    public List<List<Integer>> oneSum(int nums[], int target, int start){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length == 0) return result;
        for (int i = start; i < nums.length; i++){
            if (nums[i] == target){
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(nums[i]);
                result.add(temp);
                break;
            }
        }
        return result;
    }

    public List<List<Integer>> twoSum(int nums[], int target, int start){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int left = start;
        int end = nums.length-1;
        while (left < end){
            int sum = nums[left]+nums[end];
            if (sum == target){
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(nums[left]);
                temp.add(nums[end]);
                result.add(temp);
                while (left < end-1 && nums[left] == nums[left+1]) left++;
                while (left+1 < end && nums[end] == nums[end-1]) end--;
                left++;
                end--;
            }else if (sum > target){
                end--;
            }else{
                left++;
            }
        }
        return result;
    }
}
Posted by at No comments:

[leetcode] 3 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
34
35
36
37
38
39
40
41
public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for (int i = 0; i < nums.length-2; i++){
            if (i == 0 || nums[i] != nums[i-1]){
                List<List<Integer>> temp = twoSum(nums, i+1, 0-nums[i]);
                for (List<Integer> list:temp){
                    list.add(0, nums[i]);
                    result.add(list);
                }
            }
        }
        return result;
    }

    public List<List<Integer>> twoSum(int nums[], int start, int target){
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        int left = start;
        int end = nums.length-1;
        while (left < end){
            int sum = nums[left]+nums[end];
            if (sum == target){
                List<Integer> temp = new ArrayList<Integer>();
                temp.add(nums[left]);
                temp.add(nums[end]);
                result.add(temp);
                while (left < end-1 && nums[left] == nums[left+1]) left++;
                while (left+1 < end && nums[end] == nums[end-1]) end--;
                left++;
                end--;
            }else if (sum > target){
                end--;
            }else{
                left++;
            }
        }
        return result;
    }

}
Posted by at No comments:

[leetcode] Two Sum 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int result[] = new int[2];
        HashMap<Integer, Integer> lookup = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) lookup.put(nums[i],i);
        for (int i = 0; i < nums.length; i++){
            if (lookup.containsKey(target-nums[i]) && lookup.get(target-nums[i])!=i){
                result[0] = i+1;
                result[1] = lookup.get(target-nums[i])+1;
                break;
            }
        }
        return result;
    }
}
Posted by at No comments:

[leetcode]Insert Interval

方法就是跟interval没交集的时候 要是在前就push 进去 在后就hold着它，把interval push进去..然后等下一次（肯定会在下一个的前面 input的assumption) 直到loop完再补一个.. 还有merge的话就只merge 然后hold住不push因为有可能不只merge 一个

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<Interval>();
        for (Interval interval:intervals){
            if (interval.end < newInterval.start){
                result.add(interval);
            }else if (interval.start > newInterval.end){
                result.add(newInterval);
                newInterval = interval;
            }else{
                newInterval = new Interval(Math.min(interval.start, newInterval.start), Math.max(interval.end, newInterval.end));
            }
        }       
        result.add(newInterval);
        return result;
    }
}
Posted by at No comments:
Subscribe to: Posts (Atom)