Fork me on GitHub

Posted on

Description

https://leetcode.com/problems/decode-string/description/

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
37
38
39
40
41
42
43
44
class Solution(object):
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        return self.decodeFromIndex(s, 0)[1]
    
    def decodeFromIndex(self, s, index):
        ret = ""
        traverse = index
        
        while traverse < len(s):
            ret_string = ""
            number_str = ""
            number = None
            number_flag = False 
            while traverse < len(s) and ( (s[traverse] >= 'a' and s[traverse] <= 'z') or (s[traverse] >= 'A' and s[traverse] <= 'Z') ):
                ret += s[traverse]
                traverse += 1
            while traverse < len(s) and s[traverse] >= '0' and s[traverse] <= '9':
                number_flag = True
                number_str += s[traverse]
                traverse += 1
            if number_flag:
                number = int(number_str)
            
            
            if traverse < len(s) and s[traverse] == '[':
                traverse += 1
                [traverse, ret_string] = self.decodeFromIndex(s, traverse)
                
            if number:
                for i in range(number):
                    ret += ret_string
            
            print(traverse, ret_string)
            
            
            if traverse < len(s) and s[traverse] == ']':
                traverse += 1
                break
        
        return (traverse, ret)

Posted on

Decription

https://leetcode.com/problems/sliding-window-maximum/description/

Solution

Quite straightforward, use a heap to maitain the maxium and minium dynamically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.*;
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0){
            int[] ret = new int[0];
            return ret;
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for(int i = 0; i < k; i++) heap.add(nums[i]);
        int[] ret = new int[nums.length - k + 1];
        for (int newIndex = k; newIndex < nums.length; newIndex++){
            ret[newIndex - k] = heap.peek();
            heap.remove(nums[newIndex - k]);
            heap.offer(nums[newIndex]);
        }
        ret[nums.length - k] = heap.peek();
        return ret;
    }
}

Posted on

Description

https://leetcode.com/problems/largest-number/description/

Naive Solution

Write a comparactor.

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
class Solution:
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        sorted_nums = sorted(nums, cmp=self.comparator)
        
        ret = ""
        if sorted_nums[0] == 0:
            return "0"
        
        for num in sorted_nums:
            ret += str(num)
        
        return ret
    
    def comparator(self, left, right):
        if right == 0:
            return -1
        elif left == 0:
            return 1
        
        left_stack = []
        right_stack = []
        while left != 0:
            left_stack.append(left % 10)
            left = int(left / 10)
        while right != 0:
            right_stack.append(right % 10)
            right = int(right / 10)
            
        return self.compare_array(left_stack, right_stack)
        
    def compare_array(self, left_stack, right_stack):
        origin_stack = []
        while left_stack and right_stack:
            left_item = left_stack.pop()
            right_item = right_stack.pop()
            if left_item > right_item:
                return -1
            if left_item < right_item:
                return 1
            origin_stack.insert(0, left_item)
            
        if not left_stack and not right_stack:
            return 0
        
        left = left_stack if left_stack else origin_stack
        right = right_stack if right_stack else origin_stack
        return self.compare_array(left, right)

Use Build-in method nested in string comparsion

When compare which string is larger, the straight forward way is experiment, this is how things worked in this question. There is no bothering analyse why the left larger than right, but just compare it.

Posted on

Description

https://leetcode.com/problems/group-anagrams/description/

Naive Solution —— implement your own hash

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
class Solution:
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        ret = []
        word_to_list = {}
        
        for word in strs:
            ##generate the key
            has = 1
            dic = {} ##The identity of strs
            for s in word:
                if dic.get(s) is None:
                    dic[s] = 0
                dic[s] += 1
                bias = ord(s) - ord('a') + 1
                has *= bias
            fake_matched = word_to_list.get(has)
            
            if fake_matched == None:
                word_to_list[has] = [{}]
                word_to_list[has][0]["word_list"] = [word]
                word_to_list[has][0]["id"] = dic
                
            else:
                ##Found the proper item in the hash slot
                found = False
                for item in fake_matched:
                    if item["id"] == dic:
                        item["word_list"].append(word)
                        found = True
                        break
                ##Find nothing matched, means Hash conflict
                if found == False:
                    fake_matched.append({
                        "id": dic,
                        "word_list": [word]
                    })
            
        for li in word_to_list.values():
            for item in li:
                ret.append(item["word_list"])
            
        return ret

But the performance is so pool.

Sorting

Sort the word by char, then use the sorted string as key in hash table

Trade Off

Given the length of word is n

The time consuming on each item is O(n x logn) on sorting method, the one on the other method is (5*n)

If the length of the word is short, the constant item is quite large compared to the length of the word, which is the case in this question. so the your-own-hash way performance poorly.

Posted on

Description

https://leetcode.com/problems/combination-sum/description/

Solution

BFS

The naive implementation of BFS, in this algorithm, we need a lot of space to record the state, and the time spent on copying these states is tremendous.

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
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if len(candidates) == 0:
            return []
        
        new_candidates = sorted(candidates)
        ret = []
        result_stack = []
        candidate_lens = len(new_candidates)
        for index in range( 0, candidate_lens ):
            new_candidate = new_candidates[index]
            if new_candidate == target:
                ret.append([new_candidate])
            else:
                result_stack.append([ [new_candidate], index, new_candidate] )
                
        while(result_stack != []):
            new_result_stack = []
            for index in range(0, len(result_stack)):
                current_sum = result_stack[index][2]
                next_index = result_stack[index][1]
                
                ##The result stack is full
                if next_index >= candidate_lens:
                    continue    
                for inner_index in range(next_index, candidate_lens):
                    candidate = new_candidates[inner_index]
                    if current_sum + candidate < target:
                        s = result_stack[index][0][:] ##COPY
                        s.append(candidate)
                        new_item = [s, inner_index, candidate + current_sum]
                        new_result_stack.append(new_item)
                     
                    if current_sum + candidate == target:
                        s = result_stack[index][0][:]
                        s.append(candidate)
                        ret.append(s)
                        break
            result_stack = new_result_stack
        
        return ret

DFS

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
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        new_candidates = sorted(candidates)
        ret = []
        self.get_result(ret, new_candidates, [], target, 0)
        return ret
        
    def get_result(self, ret, candidates, candidates_list, remain, index):
        
        if remain < 0:
            return
        if remain == 0:
            ret.append(candidates_list[:])
            return
        
        traverse_index = index
        while(traverse_index < len(candidates) and candidates[traverse_index] <= remain):
            candidates_list.append(candidates[traverse_index])
            self.get_result(ret, candidates, candidates_list, remain - candidates[traverse_index], traverse_index)
            candidates_list.pop()            
            traverse_index += 1
      
        return

Non_Recursive Solution(DFS)

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
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        ret = []
        lens = len(candidates)
        remain = target
        stack = [[-1, target]]
        path = []
        current_index = 0
        while stack:
            item = stack[-1]
            current_index = item[0] + 1
            stack[-1][0] = current_index
            if current_index >= lens:
                if stack:
                    stack.pop()
                if path:
                    path.pop()
                continue
            remain = item[1]
            while remain >= candidates[current_index]:
                remain -= candidates[current_index]
                stack.append( [current_index, remain] )
                path.append(candidates[current_index])
                
            if remain == 0:
                ret.append(path[:])
                path.pop()
                stack.pop()
            if path:
                path.pop()
            if stack:
                stack.pop()
            
            print (path)
            print(stack)
            print()
        return ret

But the result is upsetting, the recursive method performs better than the non-recursive solution.

Posted on

Description

https://leetcode.com/problems/merge-intervals/description/

Solution

The key point here is to sort all the intervals, then we add each interval by order to merge(insert) into the new intervals.

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
# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

        
class Solution(object):
    
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        sorted_intervals = sorted(intervals, key=lambda x: x.start)
        if len(sorted_intervals) == 0 or len(sorted_intervals) == 1:
            return intervals
        
        ret = [ sorted_intervals[0] ]
        for index in range(1, len(sorted_intervals)):
            pre_start = ret[-1].start
            pre_end = ret[-1].end
            current_start = sorted_intervals[index].start
            current_end = sorted_intervals[index].end
            
            if pre_end < current_start:
                ret.append(Interval(current_start, current_end))
                continue
            ret.pop()
            new_start = pre_start
            new_end = max(pre_end, current_end)
            ret.append(Interval(new_start, new_end))        
                    
        return ret;

Posted on

Description

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Solution

The code is quite straightforward. The recursive formule is the following:

The string range from i to j can be reduced to the smaller case by two situations:

If the char at i and j is equal, then the largest prlindromic subseq is [i+1, j-1] + 2

Else, the largest prlindromic subseq is the larger value of [i+1, j], [i, j+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestPalindromeSubseq(String s) {
        int lens = s.length();
        if (lens == 0) return lens;
        int[][] matrix = new int[lens][lens];
        for (int i = 0; i < lens; i++) matrix[i][i] = 1;
        for (int i = 0; i < lens - 1; i++)
            matrix[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 2 : 1;
        
        for(int len = 3; len <= lens; len++)
            for (int start = 0; start <= lens - len; start++) {
                int end = start + len - 1;
                if (s.charAt(start) == s.charAt(end)) 
                    matrix[start][end] = matrix[start + 1][end - 1] + 2;
                else 
                    matrix[start][end] = Math.max(matrix[start][end - 1], matrix[start + 1][end]); 
        
            }
        return matrix[0][lens-1];
    }
}

Posted on

Descrpition

https://leetcode.com/problems/palindromic-substrings/description/

Solution (O(n^2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0; 
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for(int i = 0; i < s.length(); i++) { dp[i][i] = true; count += 1; }
        for(int i = 0; i < s.length() - 1; i++) if(s.charAt(i) == s.charAt(i+1) ) { dp[i][i+1] = true; count += 1; }
        for(int lens = 3; lens <= s.length(); lens++) {
            for(int left = 0; left <= s.length() - lens; left++) {
                int right = left + lens - 1;
                if (dp[left + 1][right - 1] && s.charAt(left) == s.charAt(right) ){
                    dp[left][right] = true;
                    count += 1;
                }
            }
        }
        return count;
    }
}

hash with Dichotomy(O(N*logN))

No result yet

Posted on

Description

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/

Solution

Two things need paying attention:

Using stack plus direction flag to traverse each node.
Pay attention how to instantiate a nested list
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new LinkedList<>();
        if (root == null) return ret;
        
        boolean direction = false;
        LinkedList<TreeNode> stack = new LinkedList<>();
        
        
        //Initialization
        List<Integer> firstLine = new LinkedList<>();
        firstLine.add(root.val);
        ret.add(firstLine);
        stack.add(root);
        
        while(stack.isEmpty() == false) {
            LinkedList<TreeNode> tempStack = new LinkedList<TreeNode>(stack);
            stack = new LinkedList<TreeNode>(); 
            List<Integer> localRet = new LinkedList<Integer>();
            while(tempStack.isEmpty() == false) {
                TreeNode tempNode = tempStack.removeFirst();
                if(direction == true) {
                    if(tempNode.left != null) { stack.addFirst(tempNode.left); localRet.add(tempNode.left.val); }
                    if(tempNode.right != null) { stack.addFirst(tempNode.right); localRet.add(tempNode.right.val); }
                }else{
                    if(tempNode.right != null) { stack.addFirst(tempNode.right); localRet.add(tempNode.right.val); }
                    if(tempNode.left != null) { stack.addFirst(tempNode.left); localRet.add(tempNode.left.val); }
                }
            }
            if(localRet.isEmpty() == false) ret.add(localRet);
            direction = !direction;
        }
        
        return ret;
    }
    
}

Posted on

This is a cliche problem, all I have learned is don’t forget the corner case of head node in linkedlist problem!!!!!!!!!

Descrption

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null; //corner case
        
        ListNode current = head, nextNNode = head;
        //Find the next n-th node
        while(nextNNode != null && n > 0) {
            nextNNode = nextNNode.next;
            n -= 1;
        }
        if (nextNNode == null) return head.next; //Remove the head
        
        //Traverse the remaining node
        while(nextNNode.next != null) {
            nextNNode = nextNNode.next;
            current = current.next;
        }
        current.next = current.next.next;
        return head;
    }
}