Fork me on GitHub

Posted on

Linkage

https://leetcode.com/problems/search-for-a-range/description/

Code

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
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] None = {-1, -1};
        if (nums.length == 0) return None;
        
        int left = 0;
        int right = nums.length - 1;
        int mid = ( left + right ) / 2;
        while (left <= right) {
            if (nums[mid] == target) {
                return searchForRange(nums, target, mid);
            }
            if (left == right) {
                return None;
            }
            
            if (nums[mid] < target) left = mid + 1;
            if (nums[mid] > target) right = mid - 1;
            mid = ( left + right ) / 2;
        }
        
        
        return None; 
    }
    
    public int[] searchForRange(int[] nums, int target, int position) {
        int left = position;
        int right = position;
        while (left-1 >= 0 && nums[left-1] == target) {
            left -= 1;
        }
        while (right + 1 < nums.length && nums[right + 1] == target) {
            right += 1;
        }
        int[] ret = {left, right};
        return ret;
    }
    
}

Posted on

Linkage

https://leetcode.com/problems/next-permutation/description/

Code

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
class Solution {
    
    public void nextPermutation(int[] nums) {
        if (nums.length == 0 || nums.length == 1){
            return;
        }
        
        int current = nums[nums.length-1];
        int index = nums.length - 2;
        while(index >= 0 && nums[index] >= current){
            current = nums[index];
            index -= 1;
        }
        
        
        //Reverse Array directly
        if (index < 0){
            reverseArray(nums);
            return;
        }
        
        //Find the min element but larger than current itme in subarray
        int min = 100000;
        int min_index = -1;
        for(int i = index+1; i <= nums.length-1; i++) {
            if ( nums[i] > nums[index] && nums[i] < min ) {
                min = nums[i];
                min_index = i;
            }
        }
        
        
        //Swap
        int temp = nums[index];
        nums[index] = nums[min_index];
        nums[min_index] = temp;
        
        //Sor in ascending order
        Arrays.sort(nums, index+1, nums.length);
    }
    
    public void reverseArray(int[] nums){
        int[] temp = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            temp[i] = nums[nums.length-i-1];
        }
        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
        
    }
}

Posted on

Idea

The key idea for my O(n) algorithm is keeping two stacks named position_stack and height_stack while traverse. The definition of stacks is defined in following:(Pay attention the size of the two stacks should keep consistent)

Let the original height array be heights, A equal position_stack[i] , B equal height_stack[i]. This notation means the max height of the qualified rectangle starting at index A(Ending at the current cursor index) in heights is B.

Code

The stack has a little trick in my implementation. I used a sentinel node which is less then all the normal heights and indexed at -1 as the first item in the stacks, to simplify the code when handling the corner case.

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
class Solution:
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        
        lens = len(heights)
        if lens == 0:
            return 0
        
        position_stack = [-1]
        height_stack = [ -100 ]
        
        index = 0
        max_area = -1
        while index < lens:
            
            while (index < lens and heights[index] >= height_stack[-1]):
                height_stack.append(heights[index])
                position_stack.append(index)
                index += 1
                
            while len(height_stack) > 1 and index < lens and heights[index] <= height_stack[-1]:
                yet_top = height_stack.pop()
                yet_start = position_stack.pop()
                max_area = max(max_area, (index-yet_start)*yet_top )
            
            if index < lens:
                height_stack.append(heights[index])
                position_stack.append(position_stack[-1]+1) 
            
        
        while len(height_stack) > 1:
            yet_height = height_stack.pop()
            yet_start_position = position_stack.pop()
            max_area = max(max_area, (index-yet_start_position)*yet_height )
        
        return max_area

Posted on

Linkage

https://leetcode.com/problems/permutations/description/

Code

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
class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        lens = len(nums)
        if lens == 0:
            return [[]]
        
        extant_items = [ [nums[0]] ]
        for i in range(1, lens):
            extant_items = self.generate_items(extant_items, nums[i])
            
        return extant_items
            
    def generate_items(self, extant_items, new_value):
        ret = []
        for item in extant_items:
            lens = len(item)
            for index in range(lens+1):
                new_item = item[:]
                new_item.insert(index, new_value)
                ret.append( new_item )
             
        return ret

FollowUp

https://leetcode.com/problems/permutations-ii/description/

In this implementation, we need the preprocessing to the original array, which means we should count the number of each elements.

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
import java.util.HashMap;

class Solution {
    
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> retArray = new ArrayList();
        HashMap<Integer, Integer> counter = new HashMap();
        
        for (int i = 0; i < nums.length; i++) {
            Integer item = counter.get(new Integer(nums[i]));
            if ( item == null){
                 counter.put( new Integer(nums[i]), 1 );
                 continue;
            }
            counter.put( new Integer(nums[i]), item+1);
        }
        List<Integer> permutate_array = new ArrayList<Integer>();
        helper(counter, permutate_array, retArray, nums.length);
        
        return retArray;
   }
    
    
    public void helper(HashMap<Integer, Integer> counter, List<Integer> permutate_array, List<List<Integer>> retArray, int depth){
        
        if (depth == 0) {
            retArray.add(permutate_array);
            return; 
        }
    
        for(Integer i : counter.keySet() ) {
            Integer count = counter.get(i);
            if (count > 0) {
                counter.put(i, count-1);
                List<Integer> new_permutate_array = new ArrayList<Integer>( permutate_array );
                new_permutate_array.add(i);
                helper(counter, new_permutate_array, retArray, depth-1);
                counter.put(i, count);
            }
        }
    }
}

Posted on

The brutal-force way to calculate all the combination.

Linkage

https://leetcode.com/problems/combinations/description/

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        ret = []
        self.add(ret, 1, n, [], k) 
        return ret
            
    def add(self, ret, start, end, item, residual):
        if residual == 0:
            ret.append(item)
            return 
        
        for i in range(start, end-residual+2):
            new_item = item[:]
            new_item.append(i)
            self.add(ret, i+1, end, new_item, residual-1)

Posted on

Linkage

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

Analysis

In this situation, we need another item for comparison when we determine which side to do further search. In my code, we set the first item of the array as the compliment to help us compare. To be more specific, the code show the two cases which composes of all the situation.

Code

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
class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        lens = len(nums)
        if lens == 0:
            return -1
        return self.find(nums, 0, lens-1, target)
    
    def find(self, nums, left, right, target):
        
        while left <= right:
             
            middle = int ( (left + right) / 2 ) 
            if nums[middle] == target:
                return middle
            if left == right and nums[middle] != target:
                return -1
            
            ##Right sorted
            if nums[middle] < nums[0]:
                if target > nums[middle] and target < nums[0]:
                    left = middle + 1
                else:
                    right = middle - 1
            ##Left is sorted
            else:
                if target < nums[middle] and target >= nums[0]:
                    right = middle - 1
                else:
                    left = middle + 1
                
        return -1

Posted on

Decode Ways

Analysis

We should utilize the dynamic perogramming, the transfer equation is, suppose result[i] is the number of decoding ways ending at s[i]

result[i] = result[i-1] + result[i-2] (If both s[i-1~ i] and s[i] is valid)

result[i] = result[i-1] (If only s[i] is valid)

Pay attention to the corner case!!!!

Solution

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
class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        length = len(s)

        result = [1 for i in range(length+1)]
        
        if s[0] < '1' or s[0] > '9':
            return 0
        else:
            result[1] = 1 
        
        for index in range(1, length):
            one_digit_number = int(s[index])
            two_digit_number = int(s[index-1:index+1])
            if one_digit_number == 0:
                if not( two_digit_number <= 26 and two_digit_number >= 10):
                    return 0
                else:
                    result[index+1] = result[index - 1]
                    continue
            
            if two_digit_number <= 26 and two_digit_number >= 10:
                result[index+1] = result[index] + result[index-1]
                continue
                
            ##Defualt case
            result[index+1] = result[index]
                
        return result[length]

Posted on

Linkage

Implement Trie (Prefix Tree)

Reminder

1.This is a naive implementation of Trie, which do not support the delete function, furthermore, the long string which can match multiple words is also not supported.

2.The key and value of a map must be Object, the basic type like int and char is not supported.

Code

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
62
63
64
65
66
67
import java.util.HashMap;

class TrieNode {
    boolean isWord;
    HashMap<Character, TrieNode> charToTrieNode;
    public TrieNode() {
        isWord = false;
        charToTrieNode = new HashMap<Character, TrieNode>();
    }
}


public class Trie {
    
    TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode();
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        int word_len = word.length();
        TrieNode traverseNode = root;
        for (int index = 0; index < word_len; index++) {
            Character ch = word.charAt(index);
            TrieNode target = traverseNode.charToTrieNode.get(ch);
            if (target == null){
                target = new TrieNode();
                traverseNode.charToTrieNode.put(ch, target);
            }
            traverseNode = target;
        }
        traverseNode.isWord = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        int word_len = word.length();
        TrieNode traverseNode = root;
        for (int index = 0; index < word_len; index++) {
            Character ch = word.charAt(index);
            TrieNode target = traverseNode.charToTrieNode.get(ch);
            if (target == null){
                return false;
            }
            traverseNode = target;
        }
        
        return traverseNode.isWord;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        int word_len = prefix.length();
        TrieNode traverseNode = root;
        for (int index = 0; index < word_len; index++) {
            Character ch = prefix.charAt(index);
            TrieNode target = traverseNode.charToTrieNode.get(ch);
            if (target == null){
                return false;
            }
            traverseNode = target;
        }
        return true;
    }
}

Posted on

Description

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Code

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
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        return self.find_inner_k_largest(nums, 0, len(nums)-1, k)
        
    def find_inner_k_largest(self, nums, start, end, k):
        lens = end - start + 1
        if k > lens:
            return 
        if lens == 1:
            return nums[start]
        
        middle_index = self.partition(nums, start, end)
        
        if lens - (middle_index-start) == k:
            return nums[middle_index]
        
        if lens - (middle_index-start) < k:
            return self.find_inner_k_largest(nums, start, middle_index-1, k-(end-middle_index+1))
        
        
        return self.find_inner_k_largest(nums, middle_index+1, end, k)
        
        
    ## The single direction partition algorithm is easier than the bi-diretion case
    def partition(self, nums, start, end):
        segment = nums[end]
        lens = end - start + 1
        
        smaller = start - 1
        larger = start 
        while larger <= end:
            if nums[larger] <= segment:
                smaller += 1
                temp = nums[smaller]
                nums[smaller] = nums[larger]
                nums[larger] = temp
            larger += 1
            
        return smaller

Posted on

Description

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Code

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
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        INF = 100000000000
        self.len1 = len(nums1)
        self.len2 = len(nums2)
        if self.len1 == 0:
            return nums2[self.len2/2] if self.len2 % 2 else float(nums2[int(self.len2/2)-1] + nums2[int(self.len2/2)])/2 
        if self.len2 == 0:
             return nums1[self.len1/2] if self.len1 % 2 else float((nums1[int(self.len1/2)-1] + nums1[int(self.len1/2)]))/2
        
        median_index_1 = int((self.len1 - 1) / 2) 
        median_index_2 = int( (self.len1 + self.len2 + 1)/2 ) - (median_index_1+1) - 1
        
        while True:
            left_1 = -INF if median_index_1 < 0 else nums1[median_index_1] 
            right_1 = INF if median_index_1+1 >= self.len1 else nums1[median_index_1+1]
            left_2 = -INF if median_index_2 < 0 else nums2[median_index_2]
            right_2 = INF if median_index_2+1 >= self.len2 else nums2[median_index_2+1]
            if left_1 <= right_2 and left_2 <= right_1:
                if (self.len1 + self.len2) % 2 == 0:
                    print(left_1, left_2, right_1, right_2)
                    return float( max(left_1, left_2) + min(right_1, right_2) ) / 2
                else:
                    ##Since the number of left part is larger than or equal to right part
                    return max(left_1, left_2)

            if left_1 > right_2:
                median_index_1 -= 1
                median_index_2 += 1
                continue

            if left_2 > right_1:
                median_index_1 += 1
                median_index_2 -= 1
                continue

####

Remains to Do

How to prove the time scale is log(m+n)