[LeetCode] Recover Binary Search Tree

Analysis:

Use in-order traversal to find the disorder node pairs.

  • If there is one pair: that means the swap nodes are adjacent.
  • If ther are two pair: they are not next to each other.

Finally swap them by value. This is not the optimal solution. BTW

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

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
class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        if root is None: return

        vec = []
        prev = None
        node1, node2 = None,None
        p = root

        count = 0
        while len(vec) > 0 or p is not None:
            if p is not None:
                vec.append(p)
                p = p.left
            else:
                p = vec.pop()
                if prev is None:
                    prev = p
                else:
                    if prev.val > p.val:
                        count += 1
                        if node1 is None:
                            node1 = prev
                            node2 = p
                        elif count > 1:
                            node2 = p
                prev = p
                p = p.right

        node1.val, node2.val = node2.val, node1.val

展开全文 >>

[LeetCode] Implement Queue using Stacks

Analysis:

There should be two stacks, one for push and one for pop.

Rule 1: always push items into the store stack
Rule 2: pop from the pop stack, and if not, we should pop from store stack and push them into pop stack
Average time is O(1), since if one-time pop takes O(k), then the next k-time actions only take O(1).

Time Complexity:

  • O(1)

Space Complexity：

  • O(n)

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
import collections

class Queue(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.exStack = collections.deque()
        self.storeStack = collections.deque()

    def push(self, x):
        """
        :type x: int
        :rtype: nothing
        """
        self.storeStack.append(x)

    def pop(self):
        """
        :rtype: nothing
        """
        if len(self.exStack) == 0:
            for x in xrange(len(self.storeStack)):
                self.exStack.append(self.storeStack.pop())
        if len(self.exStack) > 0:
            self.exStack.pop()


    def peek(self):
        """
        :rtype: int
        """
        if len(self.exStack) == 0:
            for x in xrange(len(self.storeStack)):
                self.exStack.append(self.storeStack.pop())
        if len(self.exStack) > 0:
            return self.exStack[-1]
        else:
            return 0

    def empty(self):
        """
        :rtype: bool
        """
        return len(self.exStack) == 0 and len(self.storeStack) == 0

展开全文 >>

[LeetCode] Minimum Window Substring

Analysis:

Use left pointer and right pointer to narrow down .
and skip the word exceed the boundary of the word

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

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(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        strMap = collections.defaultdict()
        for c in t:
            if c not in strMap:
                strMap[c] = 1
            else:
                strMap[c] += 1

        maxleft, maxright = 0, 0
        l, r = 0, 0
        leng, curlen = len(t), 0
        minlen = sys.maxint
        while r < len(s):
            if s[r] in strMap:
                if strMap[s[r]] > 0:
                    curlen += 1
                strMap[s[r]] -= 1
                if curlen >= leng:
                    while l < r:
                        if s[l] in strMap:
                            if strMap[s[l]] == 0:
                                break
                            strMap[s[l]] += 1
                        l += 1
                    if minlen > r-l:
                        minlen = r-l
                        maxleft, maxright = l, r+1
            r += 1

        return s[maxleft:maxright]

展开全文 >>

[LeetCode] Word Break

Analysis:

We use extra visited array to depict whether the word can be splitted at the length of i.
and skip the word exceed the boundary of the word

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

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
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        if len(s) == 0: return False

        size = len(s)
        visited = [0 for i in xrange(size+1)]
        visited[0] = 1
        for i in xrange(size):
            if visited[i] == 0:
                continue
            for word in wordDict:
                leng = len(word)
                if i + leng > size:
                    continue
                if s[i:i+leng] == word:
                    visited[i+leng] = 1

        return visited[size] == 1

展开全文 >>

Quick Sort

C++ Recursive:

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
void quickSort(int arr[], int left, int right) {
      int i = left, j = right;
      int tmp;
      int pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

展开全文 >>

[LeetCode] Increasing Triplet Subsequence

Analysis:

We maintain two lists, a store list and a list for candidates, both of them are all limited to 2 elements, then we update the candidate list first, because we don’t know if it is the final anser.

Time Complexity:

  • O(n)

Space Complexity：

  • O(1)

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
class Solution(object):
    def increasingTriplet(self, nums):
		"""
		:type nums: List[int]
		:rtype: bool
		"""
		if len(nums) < 3:
			return False

		curlist, candilist = [], []
		for i in xrange(len(nums)):
			if len(curlist) < 2:
				if len(curlist) < 1:
					curlist.append(nums[i])
				elif nums[i] < curlist[0]:
					curlist[0] = nums[i]
				elif nums[i] > curlist[0]:
					curlist.append(nums[i])
					candilist = list(curlist)
			else:
				if nums[i] > curlist[-1]:
					return True
				else:
					if nums[i] <= candilist[0]:
						candilist[0] = nums[i]
					elif nums[i] < candilist[1]:
						candilist[1] = nums[i]
						curlist = list(candilist)
		return False

展开全文 >>

[LeetCode] Serialize and Deserialize Binary Tree

Analysis:

Since this is not a complete binary search tree, we cannot use the index to dertermine the position of the child nodes.
use the preorder traversal to store the information

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:


    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if root is None:
            return ""
        valist = []
        def doit(node):
            if node is None:
                 valist.append('#')
            else:
                valist.append(str(node.val)) 
                doit(node.left)
                doit(node.right)

        doit(root)
        return ' '.join(valist)


    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        leng = len(data)
        if leng == 0:
            return None

        vals = iter(data.split())

        def doit():
            val = next(vals)
            if val == '#':
                return None
            curNode = TreeNode(int(val))
            curNode.left = doit()
            curNode.right = doit()
            return curNode
        return doit()




        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

展开全文 >>

[LeetCode] Surrender Regions

Analysis:

we must use breadth first traversal, otherwise the recursion stack depth will be exceeded.
use touchWall flag to determine whether this area can be marked

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

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
class Solution(object):
	def bfs(self, board, row, col, visited):
		toFlip = []
		touchWall = False

		height, width = len(board), len(board[0])
		bfsStore = collections.deque([(row, col)])
		def getNextNode(i, j):
			if i > 0 and board[i-1][j] == 'O' and visited[i-1][j] == 0: bfsStore.append((i-1, j))
			if i < height-1 and board[i+1][j] == 'O' and visited[i+1][j] == 0: bfsStore.append((i+1, j))
			if j > 0 and board[i][j-1] == 'O' and visited[i][j-1] == 0: bfsStore.append((i, j-1))
			if j < width-1 and board[i][j+1] == 'O' and visited[i][j+1] == 0: bfsStore.append((i, j+1))

		while len(bfsStore) > 0:
			tmprow, tmpcol = bfsStore.popleft()
			if tmprow == 0 or tmprow == height-1 or tmpcol == 0 or tmpcol == width-1:
				touchWall = True

			if visited[tmprow][tmpcol] == 0:
				visited[tmprow][tmpcol] = 1
				toFlip.append((tmprow, tmpcol))
				getNextNode(tmprow, tmpcol)

		if touchWall == False:
			for x, y in toFlip:
				board[x][y] = 'X'
	def solve(self, board):
		"""
		:type board: List[List[str]]
		:rtype: void Do not return anything, modify board in-place instead.
		"""
		if len(board) == 0 or len(board[0]) == 0:
			return

		height, width = len(board), len(board[0])

		visited = [[0 for i in xrange(width)] for j in xrange(height)]
		for i in xrange(height):
			for j in xrange(width):
				if visited[i][j] == 0 and board[i][j] == 'O':
					self.bfs(board, i, j, visited)

展开全文 >>

[LeetCode] Verify Preorder Serialization of a Binary Tree

Analysis

  • Stack can be used here to store the elements, one ‘#’ for one element and two ‘#’. And check if there is one ‘#’ remains in the stack, which means this is a valid pre-order

Time Complexity

  • O(n)

Space Comlexity

  • O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def isValidSerialization(self, preorder):
        """
        :type preorder: str
        :rtype: bool
        """
        store = collections.deque()

        for item in preorder.split(','):
        	store.append(item)
        	while len(store) > 2 and store[-1] == '#' and store[-2] == '#' and store[-3] != '#':
    			store.pop()
    			store.pop()
    			store[-1] = '#'

    	return len(store) == 1 and store[0] == '#'

展开全文 >>

[LeetCode] Longest Increasing Path in a Matrix

Analysis:

memorization should be used here to reduce the uneccessary traversal. Remember to check the boundry of the matrix

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

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
class Solution(object):
    def dfs(self, matrix, i, j, rowcount, colcount, stormap):
        if stormap[i][j] > 0:
            return stormap[i][j]

        if i > 0 and matrix[i][j] < matrix[i-1][j]:
            stormap[i][j] = max(stormap[i][j], self.dfs(matrix, i-1, j, rowcount, colcount, stormap))
        if i < rowcount-1 and matrix[i][j] < matrix[i+1][j]:
            stormap[i][j] = max(stormap[i][j], self.dfs(matrix, i+1, j, rowcount, colcount, stormap))
        if j > 0 and matrix[i][j] < matrix[i][j-1]:
            stormap[i][j] = max(stormap[i][j], self.dfs(matrix, i, j-1, rowcount, colcount, stormap))
        if j < colcount - 1 and matrix[i][j] < matrix[i][j+1]:
            stormap[i][j] = max(stormap[i][j], self.dfs(matrix, i, j+1, rowcount, colcount, stormap))

        stormap[i][j] += 1
        return stormap[i][j]

    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if len(matrix) == 0:
            return 0
        rowcount, colcount = len(matrix), len(matrix[0])
        stormap = [[0 for x in xrange(colcount)] for x in xrange(rowcount)]

        maxlen = 0

        for i in xrange(rowcount):
            for j in xrange(colcount):
                maxlen = max(maxlen, self.dfs(matrix, i, j, rowcount, colcount, stormap))

        return maxlen

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

Martyn's Playground