KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given two strings s and goal, return true if you can swap two letters in s so the result is equal to goal, otherwise, return false.

Swapping letters is defined as taking two indices i and j (0-indexed) such that i != j and swapping the characters at s[i] and s[j].

For example, swapping at indices 0 and 2 in "abcd" results in "cbad".

Example 1:

Input: s = “ab”, goal = “ba”
Output: true
Explanation: You can swap s[0] = ‘a’ and s[1] = ‘b’ to get “ba”, which is equal to goal.


Example 2:

Input: s = “ab”, goal = “ab”
Output: false
Explanation: The only letters you can swap are s[0] = ‘a’ and s[1] = ‘b’, which results in “ba” != goal.


Example 3:

Input: s = “aa”, goal = “aa”
Output: true
Explanation: You can swap s[0] = ‘a’ and s[1] = ‘a’ to get “aa”, which is equal to goal.


Constraints: 1 <= s.length, goal.length <= 2 * 10<sup>4</sup>
* s and goal consist of lowercase letters.

题目大意：

给定两字符串，交换一次使得他们相等

解题思路：

三种情况： 长度不等，完全相等（若至少有一个重复，即满足题意），两次不同

解题步骤：

N/A

注意事项：

  1. 三种情况： 长度不等，完全相等，两次不同

Python代码：

1
2
3
4
5
6
7
def buddyStrings(self, s: str, goal: str) -> bool:
	if len(s) != len(goal):
		return False
	if s == goal and len(set(s)) < len(goal): # any dups
		return True
	diff = [(a, b) for a, b in zip(s, goal) if a != b]
	return True if len(diff) == 2 and diff[0] == diff[1][::-1] else False

算法分析：

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

Posted on Edited on Disqus:

A change for two N-children tree contains:

  1. key is different
  2. value is different
  3. delete a node
  4. add a node

Problem: how many changes to convert tree A to tree B

题目大意：

DD的面经题，多少个改动可以使得existingTree变成newTree

解题思路：

DFS, 比较children，三种情况。若其中一方没有节点，就是计算节点数

解题步骤：

N/A

注意事项：

  1. 比较children，三种情况。若其中一方没有节点，就是计算节点数

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
def changeNodes(self, existingTree, newTree) -> int:
	if not existingTree and not newTree:
		return 0
	if not existingTree or not newTree:
		return self.count(existingTree) + self.count(newTree)
	res = 0 if existingTree.key == newTree.key and existingTree.val == newTree.val else 1
	existing_children_dict = self.get_children_dict(existingTree.children)
	new_tree_children_dict = self.get_children_dict(newTree.children)
	for key in existing_children_dict.keys() & new_tree_children_dict.keys(): # in both
		res += self.changeNodes(existing_children_dict[key], new_tree_children_dict[key])
	for key in existing_children_dict.keys() - new_tree_children_dict.keys(): # in existing tree not in new tree
		res += self.count(existing_children_dict[key])
	for key in new_tree_children_dict.keys() - existing_children_dict.keys():  # in new tree not in existing tree
		res += self.count(new_tree_children_dict[key])
	return res

def count(self, root):
	if not root:
		return 0
	res = 0
	for child in root.children:
		res += self.count(child)
	return 1 + res

def get_children_dict(self, children):
	key_to_node = {}
	for child in children:
		key_to_node[child.key] = child
	return key_to_node

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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:



Input: root = [3,1,4,null,2], k = 1
Output: 1


Example 2:



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


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?

题目大意：

求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



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:

    Parameter:  char[] buf4
    Returns:    int

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


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



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


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:

    Parameters:    char[] buf, int n
    Returns:    int

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


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:

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.


Example 2:

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.


Example 3:

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.


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

题目大意：

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



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:

    Parameter:  char[] buf4
    Returns:    int

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


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



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


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:

    Parameters:    char[] buf, int n
    Returns:    int

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


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:

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.


Example 2:

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.


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

题目大意：

题意类似于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)

Free mock interview