KK's blog

LeetCode

<div>

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Note: You must not use any built-in BigInteger library or convert the inputs to integer directly.

Example 1:

<pre>Input: num1 = "2", num2 = "3" Output: "6" </pre>

Example 2:

<pre>Input: num1 = "123", num2 = "456" Output: "56088" </pre>

Constraints:

• 1 <= num1.length, num2.length <= 200
• num1 and num2 consist of digits only.
• Both num1 and num2 do not contain any leading zero, except the number 0 itself.

</div>

题目大意：

求字符串乘法结果

解题思路：

模拟小学乘法

解题步骤：

N/A

注意事项：

1. 模拟小学乘法，开一个大小为len(num1) + len(num2)的整数数组，内外循环计算每位结果。这位可能是大于20的数，如20, 30..。计算前先反转输入，得到最后结果后也反转。
2. 结果要消除前缀0，但注意0乘以0的情况会返回空，所以要特别处理。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12

def multiply(self, num1: str, num2: str) -> str:
	digits = [0] * (len(num1) + len(num2))
	num1, num2 = num1[::-1], num2[::-1]
	for i in range(len(num1)):
		for j in range(len(num2)):
			digits[i + j] += int(num1[i]) * int(num2[j])
	carry, res = 0, ''
	for i in range(len(digits)):
		n = digits[i] + carry
		carry = n // 10
		res += str(n % 10)
	return '0' if res[::-1].lstrip('0') == '' else res[::-1].lstrip('0')

算法分析：

时间复杂度为O(n)，空间复杂度O(1)

LeetCode 044 Wildcard Matching

<div>

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*'.

<pre>'?' Matches any single character. '*' Matches any sequence of characters (including the empty sequence). </pre>

The matching should cover the entire input string (not partial).

Note:

• s could be empty and contains only lowercase letters a-z.
• p could be empty and contains only lowercase letters a-z, and characters like <font face="monospace">?</font> or *.

Example 1:

<pre>Input: s = "aa" p = "a" Output: false Explanation: "a" does not match the entire string "aa". </pre>

Example 2:

<pre>Input: s = "aa" p = "" Output: true Explanation: '' matches any sequence. </pre>

Example 3:

<pre>Input: s = "cb" p = "?a" Output: false Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'. </pre>

Example 4:

<pre>Input: s = "adceb" p = "ab" Output: true Explanation: The first '' matches the empty sequence, while the second '' matches the substring "dce". </pre>

Example 5:

<pre>Input: s = "acdcb" p = "a*c?b" Output: false </pre>

</div>

题目大意：

通配符外卡匹配问题，有特殊字符"*"和"?"，其中"?" 能代替任何字符，"*"能代替任何字符串。

解题思路：

这是经典题。两字符串匹配题基本就是DP而且知道子问题答案可以推导下一个。

1. 定义dp[i][j]为字符串s[i-1]和p[j-1]是否能匹配。
2. 递归式为

   1 2	dp[i][j] = dp[i-1][j-1] && (p[j-1] == ? || s[i-1] == p[j-1]) if p[j-1] != \* dp[i-1][j] || dp[i][j-1] if p[j-1] == \*

   第一种情况为非*，通配一样字符或?
   第二种情况为*，如果通配就是只移动s，dp[i-1][j]。若不通配（通配完）就只移动p。
3. 方向为从左到右，从上到下。初始值为dp[0][0] = true。以及若s为空，p为多个*时候，dp[0][j]=true。

注意事项：

1. 递归式含*不匹配情况dp[i][j-1]，容易忽略。
2. 初始化s为空，p为多个*。根据递归式来写，i=0时，递归式只剩下dp[i][j-1]。将i = 0带入到内外循环代码实现即可(先写内外循环)
3. 模板问题： dp初始化先col再row； i循环到len(dp)而不是len(s); 用到p时候是p[i - 1]而不是p[i]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

def isMatch(self, s: str, p: str) -> bool:
	dp = [[False for _ in range(len(p) + 1)] for _ in range(len(s) + 1)] # remember p then s
	dp[0][0] = True
	for j in range(1, len(dp[0])):
		if p[j - 1] == '*':
			dp[0][j] = dp[0][j - 1]
	for i in range(1, len(dp)): # remember len(dp) not len(s)
		for j in range(1, len(dp[0])):
			if p[j - 1] != '*': # remember j-1 not j
				dp[i][j] = dp[i - 1][j - 1] and (s[i - 1] == p[j - 1] or p[j - 1] == '?')
			else:
				dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
	return dp[-1][-1]

注意事项：

1. 递归式含*不匹配情况dp[i][j-1]，我写的时候忽略了。
2. 初始化s为空，p为多个*。此情况其实与递归式符合，因为i=1开始，所以i=0的时候，dp[i-1][j]为负值省去，
   只取dp[i][j-1]。
3. 一开始写的corner case并入到递归式处理。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public boolean isMatch(String s, String p) {
	//if(s.isEmpty() && p.isEmpty())
		//return true;
	//if(!s.isEmpty() && p.isEmpty())
		//return false;
	//if(s.isEmpty() && !p.isEmpty() && isAllStars(p))
		//return true;
	//if(s.isEmpty() && !p.isEmpty())
		//return false;
	
	boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
	dp[0][0] = true;
	for(int j = 1; j < dp[0].length; j++)
		// remember empty s can match any prefix *** character in p making sure dp[0][j] = true
		if(p.charAt(j-1) == '*')
			dp[0][j] = dp[0][j-1];
	for(int i = 1; i < dp.length; i++)
		for(int j = 1; j < dp[0].length; j++)
			dp[i][j] = (dp[i-1][j-1] && (p.charAt(j-1) == '?' || s.charAt(i-1) == p.charAt(j-1)))
			// miss dp[i][j-1] means no match on *
			|| ((dp[i-1][j] || dp[i][j-1]) && p.charAt(j-1) == '*'); 
	return dp[dp.length -1][dp[0].length - 1];
}

算法分析：

时间复杂度为O(n*m)，空间复杂度为O(n*m)。

LeetCode 173 Binary Search Tree Iterator <div>

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Example:

<pre>BSTIterator iterator = new BSTIterator(root); iterator.next(); // return 3 iterator.next(); // return 7 iterator.hasNext(); // return true iterator.next(); // return 9 iterator.hasNext(); // return true iterator.next(); // return 15 iterator.hasNext(); // return true iterator.next(); // return 20 iterator.hasNext(); // return false </pre>

Note:

• next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.
• You may assume that next() call will always be valid, that is, there will be at least a next smallest number in the BST when next() is called.

</div>

题目大意：

实现BST的Iterator

算法思路：

参照KB中BST的非递归中序遍历。将其分拆为初始化以及去掉stack不为空的循环分别为所求。

注意事项：

1. 初始化，将root所有左节点加入到stack。先写next，出栈栈顶节点，将它的右儿子的所有左节点入栈。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class BSTIterator(TestCases):

    def __init__(self, root: TreeNode):
        self.stack = []
        it = root
        while it:
            self.stack.append(it)
            it = it.left

    def next(self) -> int:
        node = self.stack.pop()
        if node.right:
            n = node.right
            while n:
                self.stack.append(n)
                n = n.left
        return node.val

    def hasNext(self) -> bool:
        return True if self.stack else False

Java代码：

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

Stack<TreeNode> s = new Stack<>();
public L173BinarySearchTreeIterator(TreeNode root) {
	TreeNode head = root;
	while(head != null) {
		s.push(head);
		head = head.left;
	}
}

// Recommended
public int next2() {
	TreeNode node = s.pop(); 
	if(node.right != null) {// left node has been visited
		TreeNode n = node.right; 
		while(n != null) {
			s.push(n);
			n = n.left;
		}
	}
	return node.val;

}

/** @return whether we have a next smallest number */
public boolean hasNext() {
	return !s.isEmpty();
} 

算法分析：

next的平均时间复杂度(amortized complexity)为O(1)，n为字符串长度，空间复杂度O(logn)。

LeetCode 272 Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.
• You may assume k is always valid, that is: _k_≤ total nodes.
• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

<pre>Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

4

/
2 5 /
1 3

Output: [4,3]</pre>

Follow up:
Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

题目大意：

找BST中给定目标的最接近的k个值。

解题思路：

首先观察得到最接近的节点一定在二叉树的搜索路径上的节点的其中一个。这样可以分成两组
前驱节点和后驱节点（比target大），加入到两个stack中，由BST的iterator可以知道这两个
stack的越靠近栈首就越接近target，所以出栈的一定是最接近target的。只要比较两栈首元素
即可。如果某个节点出栈要找其儿子节点填充。找前驱节点和后驱节点的方法是相反的。这里可
参照KB的BST非递归中序遍历。

注意事项：

1. 找最接近target的节点，不用判断左右儿子是否为空，因为若为空，表示root更接近。大于target的放入successors，否则是predecessors
2. 然后判断两栈首谁大，谁大的就获得相应的比它远离target的节点入栈。如predecessors是左节点的所有右儿子。

Python代码：

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

def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
	predecessors, successors = [], []
	it = root
	while it:
		if target < it.val:
			successors.append(it)
			it = it.left
		else:
			predecessors.append(it)
			it = it.right
	res = []
	while k > 0:
		if predecessors and (not successors or target - predecessors[-1].val < successors[-1].val - target):
			node = predecessors.pop()
			if node.left:
				n = node.left
				while n:
					predecessors.append(n)
					n = n.right
			res.append(node.val)
		else:
			node = successors.pop()
			if node.right:
				n = node.right
				while n:
					successors.append(n)
					n = n.left
			res.append(node.val)
		k -= 1
	return res

注意事项：

1. target - preOrder.peek().val < postOrder.peek().val - target的条件前
   记得加上!preOrder.isEmpty()

Java代码：

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

public List<Integer> closestKValues(TreeNode root, double target, int k) {
	List<Integer> res = new ArrayList<>();
	if(root == null)
		return res;
	Stack<TreeNode> preOrder = new Stack<>();
	Stack<TreeNode> postOrder = new Stack<>();
	findTargetAndPopulateStacks(preOrder, postOrder, root, target);
	
	while(k-- > 0) {
		if(postOrder.isEmpty() || (!preOrder.isEmpty() && 
				target - preOrder.peek().val < postOrder.peek().val - target))
			getPredecessor(preOrder, res);
		else 
			getSuccessor(postOrder, res);
	}
	return res;
}

void findTargetAndPopulateStacks(Stack<TreeNode> preOrder, Stack<TreeNode> postOrder, 
		TreeNode root, double target) {
	TreeNode node = root;
	while(node != null) {
		if(node.val < target) { 
			preOrder.push(node);
			node = node.right;
		}
		else {
			postOrder.push(node);
			node = node.left;
		}
	}
}

void getSuccessor(Stack<TreeNode> postOrder, List<Integer> res) {
	TreeNode node = postOrder.pop();
	res.add(node.val);
	if(node.right != null) {
		TreeNode n = node.right;
		while(n != null) {
			postOrder.push(n);
			n = n.left;
		}
	}
}

void getPredecessor(Stack<TreeNode> preOrder, List<Integer> res) {
	TreeNode node = preOrder.pop();
	res.add(node.val);
	if(node.left != null) {
		TreeNode n = node.left;
		while(n != null) {
			preOrder.push(n);
			n = n.right;
		}
	}
}

算法分析：

时间复杂度为O(k + logn)，空间复杂度O(logn)。

LeetCode

<div>

Design an iterator to flatten a 2D vector. It should support the next and hasNext operations.

Implement the Vector2D class:

• Vector2D(int[][] vec) initializes the object with the 2D vector vec.
• next() returns the next element from the 2D vector and moves the pointer one step forward. You may assume that all the calls to next are valid.
• hasNext() returns true if there are still some elements in the vector, and false otherwise.

Example 1:

<pre>Input ["Vector2D", "next", "next", "next", "hasNext", "hasNext", "next", "hasNext"] [[[[1, 2], [3], [4]]], [], [], [], [], [], [], []] Output [null, 1, 2, 3, true, true, 4, false]

Explanation Vector2D vector2D = new Vector2D([[1, 2], [3], [4]]); vector2D.next(); // return 1 vector2D.next(); // return 2 vector2D.next(); // return 3 vector2D.hasNext(); // return True vector2D.hasNext(); // return True vector2D.next(); // return 4 vector2D.hasNext(); // return False </pre>

Constraints:

• 0 <= vec.length <= 200
• 0 <= vec[i].length <= 500
• -500 <= vec[i][j] <= 500
• At most 10<sup>5</sup> calls will be made to next and hasNext.

Follow up: As an added challenge, try to code it using only iterators in C++ or iterators in Java.

</div>

题目大意：

实现二维Vector的Iterator

解题思路：

用两个指针

解题步骤：

N/A

注意事项：

1. 单一Vector可以是空，所以next要循环找到非空的vector
2. next要col_id加一

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Vector2D(TestCases):

    def __init__(self, vec: List[List[int]]):
        self.vec = vec
        self.row_id = 0
        self.col_id = 0

    def next(self) -> int:
        if self.hasNext():
            val = self.vec[self.row_id][self.col_id]
            self.col_id += 1 # remember
            return val
        return None

    def hasNext(self) -> bool:
        while self.row_id < len(self.vec) and self.col_id == len(self.vec[self.row_id]): # remember while coz []
            self.row_id += 1
            self.col_id = 0
        if self.row_id == len(self.vec):
            return False
        else:
            return True

算法分析：

每个操作时间复杂度为O(V/N)或O(1)，空间复杂度O(1), N为所有数，V为vector数，O(N + V)/N. O(1)如果vector都不会空