KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Given the root of a binary search tree, and an integer k, return the k<sup>th</sup> smallest value (1-indexed) of all the values of the nodes in the tree.

Example 1:

<pre>Input: root = [3,1,4,null,2], k = 1 Output: 1 </pre>

Example 2:

<pre>Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3 </pre>

Constraints:

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10<sup>4</sup>
  • 0 <= Node.val <= 10<sup>4</sup>

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

</div>

题目大意：

求BST的第k个最小元素（k从1开始）

算法思路：

N/A

注意事项：

  1. 用返回值(count, 结果). 递归右节点，用k - 1 - left_count
  2. Line 9不能用if left_val，因为left_val可能是0，用is not None

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def kthSmallest(self, root: TreeNode, k: int) -> int:
	count, val = self.dfs(root, k)
	return val

def dfs(self, root, k):
	if not root:
		return 0, None

	left_count, left_val = self.dfs(root.left, k)
	if left_val is not None: # remember if left_val is wrong
		return 0, left_val
	if left_count + 1 == k:
		return 0, root.val
	right_count, right_val = self.dfs(root.right, k - left_count - 1) # remember k-1-left_count
    if right_val is not None:
		return 0, right_val
	return left_count + 1 + right_count, right_val

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
public int kthSmallest2(TreeNode root, int k) {
	return kthSmallest2R(root, k).result;
}

public ResultType kthSmallest2R(TreeNode root, int k) {
	if (root == null)
		return new ResultType(null, 0);
	ResultType leftResult = kthSmallest2R(root.left, k);

	Integer result = leftResult.result;
	if(result != null)
		return new ResultType(result, 0);
	if(leftResult.count + 1 == k)
		return new ResultType(root.val, 0);
	
	ResultType rightResult = kthSmallest2R(root.right, k - 1 - leftResult.count);
	result = rightResult.result;
	
	return new ResultType(result, leftResult.count + 1 + rightResult.count);
}

class ResultType {
	Integer result;
	int count;
	
	public ResultType(Integer r, int c) {
		result = r;
		count = c;
	}
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters.

Method read4:

The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

<pre> Parameter: char[] buf4 Returns: int

buf4[] is a destination, not a source. The results from read4 will be copied to buf4[]. </pre>

Below is a high-level example of how read4 works:

<pre>File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a' char[] buf4 = new char[4]; // Create buffer with enough space to store characters read4(buf4); // read4 returns 4\. Now buf4 = "abcd", fp points to 'e' read4(buf4); // read4 returns 1\. Now buf4 = "e", fp points to end of file read4(buf4); // read4 returns 0\. Now buf4 = "", fp points to end of file </pre>

Method read:

By using the read4 method, implement the method read that reads n characters from file and store it in the buffer array buf. Consider that you cannot manipulate file directly.

The return value is the number of actual characters read.

Definition of read:

<pre> Parameters: char[] buf, int n Returns: int

buf[] is a destination, not a source. You will need to write the results to buf[]. </pre>

Note:

  • Consider that you cannot manipulate the file directly. The file is only accessible for read4 but not for read.
  • The read function will only be called once for each test case.
  • You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.

Example 1:

<pre>Input: file = "abc", n = 4 Output: 3 Explanation: After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3. Note that "abc" is the file's content, not buf. buf is the destination buffer that you will have to write the results to. </pre>

Example 2:

<pre>Input: file = "abcde", n = 5 Output: 5 Explanation: After calling your read method, buf should contain "abcde". We read a total of 5 characters from the file, so return 5. </pre>

Example 3:

<pre>Input: file = "abcdABCD1234", n = 12 Output: 12 Explanation: After calling your read method, buf should contain "abcdABCD1234". We read a total of 12 characters from the file, so return 12. </pre>

Constraints:

  • 1 <= file.length <= 500
  • file consist of English letters and digits.
  • 1 <= n <= 1000

</div>

题目大意：

Karat题，有一个函数read4,如此调用

1
2
buf4 = [' '] * 4
count = read4(buf4)
buf4是填充后的结果，是一个大小为4的char list
count是buf4的有数据的实际大小(4或更小，取决于是否文件最后一段是否不够4)

现在要实现这个函数 

1
def read(self, buf, n)
buf是字符列表，n是想要读取文件的大小，返回值为n或者更小，取决于是否文件大小是否小于n

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 若count为0，跳出循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def read(self, buf, n):
	i = 0
	while i < n:
		buf4 = [' '] * 4
		count = read4(buf4)
		if not count: # avoid dead loop
			break
		count = min(count, n - i)
		buf[i:] = buf4
		i += count
	return i

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.

Method read4:

The API read4 reads four consecutive characters from file, then writes those characters into the buffer array buf4.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

<pre> Parameter: char[] buf4 Returns: int

buf4[] is a destination, not a source. The results from read4 will be copied to buf4[]. </pre>

Below is a high-level example of how read4 works:

<pre>File file("abcde"); // File is "abcde", initially file pointer (fp) points to 'a' char[] buf4 = new char[4]; // Create buffer with enough space to store characters read4(buf4); // read4 returns 4\. Now buf4 = "abcd", fp points to 'e' read4(buf4); // read4 returns 1\. Now buf4 = "e", fp points to end of file read4(buf4); // read4 returns 0\. Now buf4 = "", fp points to end of file </pre>

Method read:

By using the read4 method, implement the method read that reads n characters from file and store it in the buffer array buf. Consider that you cannot manipulate file directly.

The return value is the number of actual characters read.

Definition of read:

<pre> Parameters: char[] buf, int n Returns: int

buf[] is a destination, not a source. You will need to write the results to buf[]. </pre>

Note:

  • Consider that you cannot manipulate the file directly. The file is only accessible for read4 but not for read.
  • The read function may be called multiple times.
  • Please remember to RESET your class variables declared in Solution, as static/class variables are persisted across multiple test cases. Please see here for more details.
  • You may assume the destination buffer array, buf, is guaranteed to have enough space for storing n characters.
  • It is guaranteed that in a given test case the same buffer buf is called by read.

Example 1:

<pre>Input: file = "abc", queries = [1,2,1] Output: [1,2,0] Explanation: The test case represents the following scenario: File file("abc"); Solution sol; sol.read(buf, 1); // After calling your read method, buf should contain "a". We read a total of 1 character from the file, so return 1. sol.read(buf, 2); // Now buf should contain "bc". We read a total of 2 characters from the file, so return 2. sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0. Assume buf is allocated and guaranteed to have enough space for storing all characters from the file. </pre>

Example 2:

<pre>Input: file = "abc", queries = [4,1] Output: [3,0] Explanation: The test case represents the following scenario: File file("abc"); Solution sol; sol.read(buf, 4); // After calling your read method, buf should contain "abc". We read a total of 3 characters from the file, so return 3. sol.read(buf, 1); // We have reached the end of file, no more characters can be read. So return 0. </pre>

Constraints:

  • 1 <= file.length <= 500
  • file consist of English letters and digits.
  • 1 <= queries.length <= 10
  • 1 <= queries[i] <= 500

</div>

题目大意：

题意类似于LeetCode 157 Read N Characters Given Read4，但此题唯一的区别是这个新的API: def read(self, buf, n)会被调用多次

解题思路：

因为read调用多次，所以调用read4多读了几个字符在n以外的，需要保留下来让下一次read返回到结果中，所以用queue来保存中间结果

解题步骤：

N/A

注意事项：

  1. 先将read4的结果保存在self.queue中，然后再填充到buf中，这里用到了quicksort里面partition的方法，while中只有当填充buf时i才移动，而read4时候不移动

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def __init__(self):
	self.queue = collections.deque()

def read(self, buf: List[str], n: int) -> int:
	i = 0
	while i < n:
		if self.queue:
			buf[i] = self.queue.popleft()
			i += 1
		else:
			buf4 = [' '] * 4
			count = read4(buf4)
			if not count: # avoid dead loop
				break
			self.queue.extend(buf4[:count])
	return i

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Android devices have a special lock screen with a 3 x 3 grid of dots. Users can set an "unlock pattern" by connecting the dots in a specific sequence, forming a series of joined line segments where each segment's endpoints are two consecutive dots in the sequence. A sequence of k dots is a valid unlock pattern if both of the following are true:

  • All the dots in the sequence are distinct.
  • If the line segment connecting two consecutive dots in the sequence passes through the center of any other dot, the other dot must have previously appeared in the sequence. No jumps through the center non-selected dots are allowed.
    • For example, connecting dots 2 and 9 without dots 5 or 6 appearing beforehand is valid because the line from dot 2 to dot 9 does not pass through the center of either dot 5 or 6.
    • However, connecting dots 1 and 3 without dot 2 appearing beforehand is invalid because the line from dot 1 to dot 3 passes through the center of dot 2.

Here are some example valid and invalid unlock patterns:

  • The 1st pattern [4,1,3,6] is invalid because the line connecting dots 1 and 3 pass through dot 2, but dot 2 did not previously appear in the sequence.
  • The 2nd pattern [4,1,9,2] is invalid because the line connecting dots 1 and 9 pass through dot 5, but dot 5 did not previously appear in the sequence.
  • The 3rd pattern [2,4,1,3,6] is valid because it follows the conditions. The line connecting dots 1 and 3 meets the condition because dot 2 previously appeared in the sequence.
  • The 4th pattern [6,5,4,1,9,2] is valid because it follows the conditions. The line connecting dots 1 and 9 meets the condition because dot 5 previously appeared in the sequence.

Given two integers m and n, return the number of unique and valid unlock patterns of the Android grid lock screen that consist of at least m keys and at most n keys.

Two unlock patterns are considered unique if there is a dot in one sequence that is not in the other, or the order of the dots is different.

Example 1:

<pre>Input: m = 1, n = 1 Output: 9 </pre>

Example 2:

<pre>Input: m = 1, n = 2 Output: 65 </pre>

Constraints:

  • 1 <= m, n <= 9

</div>

题目大意：

安卓开屏密码解锁种数。给定m, n是安卓的密码长度范围，求这个范围内的解码种数。1可以跳到2和4, 5, 6, 8(斜线没有通过其他数字)，但不能跳到3, 7, 9因为前提条件是这条线通过的数如2, 4, 5必须已经用过了。

解题思路：

此题属于填位法，带条件的，条件在于map中，类似于LeetCode 248 Strobogrammatic Number III 难点是理解jump keys，有16种 

1
2
3
4
5
skip[1][3] = skip[3][1] = 2;
skip[1][7] = skip[7][1] = 4;
skip[3][9] = skip[9][3] = 6;
skip[7][9] = skip[9][7] = 8;
skip[1][9] = skip[9][1] = skip[2][8] = skip[8][2] = skip[3][7] = skip[7][3] = skip[4][6] = skip[6][4] = 5;

解题步骤：

用DFS模板: def dfs(self, graph, start, visited, res), start = num

注意事项：

  1. Line 9有return，所以要去掉刚加入的visited的num

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
JUMP_KEYS = {(1,3):2, (1,7):4, (1,9):5, (2,8):5, (3,7):5, (3,1):2, (3,9):6, (4,6):5, (6,4):5, (7,1):4, (7,3):5, (7,9):8, (8,2):5, (9,7):8, (9,3):6, (9,1):5}
class Solution(TestCases):

    def dfs(self, num, m, n, visited):
        if num in visited:
            return 0
        visited.add(num)
        if len(visited) == n:
            visited.remove(num) # remember
            return 1
        res = 0
        if len(visited) >= m:
            res += 1
        for next_num in range(1, 10):
            if (num, next_num) in JUMP_KEYS and JUMP_KEYS[(num, next_num)] not in visited:
                continue
            res += self.dfs(next_num, m, n, visited)
        visited.remove(num)
        return res

算法分析：

时间复杂度为O(1)，空间复杂度O(1), 因为最多是9乘以8乘以7...

Posted on Edited on Disqus:

LeetCode

<div>

Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]

  • An expression alternates chunks and symbols, with a space separating each chunk and symbol.
  • A chunk is either an expression in parentheses, a variable, or a non-negative integer.
  • A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like "2x" or "-x".

Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.

  • For example, expression = "1 + 2 * 3" has an answer of ["7"].

The format of the output is as follows:

  • For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically.
    • For example, we would never write a term like "b*a*c", only "a*b*c".
  • Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
    • For example, "a*a*b*c" has degree 4.
  • The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed.
  • An example of a well-formatted answer is ["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"].
  • Terms (including constant terms) with coefficient 0 are not included.
    • For example, an expression of "0" has an output of [].

Example 1:

<pre>Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1] Output: ["-1*a","14"] </pre>

Example 2:

<pre>Input: expression = "e - 8 + temperature - pressure", evalvars = ["e", "temperature"], evalints = [1, 12] Output: ["-1*pressure","5"] </pre>

Example 3:

<pre>Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = [] Output: ["1ee","-64"] </pre>

Constraints:

  • 1 <= expression.length <= 250
  • expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' '.
  • expression does not contain any leading or trailing spaces.
  • All the tokens in expression are separated by a single space.
  • 0 <= evalvars.length <= 100
  • 1 <= evalvars[i].length <= 20
  • evalvars[i] consists of lowercase English letters.
  • evalints.length == evalvars.length
  • -100 <= evalints[i] <= 100

</div>

题目大意：

表达式含有若干变量evalvars及其对应值evalints，且含加减乘和括号，求结果。若变量不在evalvars就简化表达式

解题思路：

此题不需要掌握，若考到就认命好了。之前的LeetCode 224 Basic Calculator含有括号和加法已经是Hard，此题不但有括号和加减乘，还有变量，难度不止提高一个数量级。不过不可以用eval函数的条件去掉了。所以就是考察eval。 如果不含变量，直接调用eval即可求解

Python代码：

1
2
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	return eval(expression)

含变量且变量有值，就调用字典将变量替代掉，这里考到了regex替代函数re.sub

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	var_to_val = dict(zip(evalvars, evalints))

	def f(s):
		token = s.group()
		s = str(var_to_val[token] if token in var_to_val else token)
		return s

	converted_expr = re.sub(r'\w+', f, expression)
	res = eval(converted_expr)
	return res

由于变量可能没有值，所以核心思路是用dict进行计算，如x + 2，用集合求和{(x,): 1} + {(): 2}得到{('x',): 1, (): -2}，用dict来计算及保存结果

解题步骤：

  1. regex替代变量
  2. 将表达式用f包装，如(f("x") + f("8")) * (f("x") - f("8"))
  3. 实现dict的加减乘
  4. dict的计算结果转成题目所求

注意事项：

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
31
32
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
	class MyCounter(Counter):
		def __add__(self, other):
			self.update(other)
			return self

		def __sub__(self, other):
			self.subtract(other)
			return self

		def __mul__(self, other):
			product = MyCounter()
			for x in self:
				for y in other:
					xy = tuple(sorted(x + y))
					product[xy] += self[x] * other[y]
			return product

	var_to_val = dict(zip(evalvars, evalints))

	def f(s):
		token = s
		s = str(var_to_val[token] if token in var_to_val else token)
		return MyCounter({(s, ): 1}) if s.isalpha() else MyCounter({(): int(s)})

	converted_expr = re.sub(r'(\w+)', r'f("\1")', expression)
	# (f("x") + f("8")) * (f("x") - f("8"))
	res = eval(converted_expr) #
	# C({('x', 'x'): 1, ('x',): 0, (): -64})
	return ['*'.join((str(res[x]), ) + x)
			for x in sorted(res, key=lambda x: (-len(x), x))
			if res[x]]

算法分析：

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

Free mock interview