KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Example 1:



Input: root = [10,5,15,3,7,null,18], low = 7, high = 15
Output: 32
Explanation: Nodes 7, 10, and 15 are in the range [7, 15]. 7 + 10 + 15 = 32.


Example 2:



Input: root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
Output: 23
Explanation: Nodes 6, 7, and 10 are in the range [6, 10]. 6 + 7 + 10 = 23.


Constraints:

The number of nodes in the tree is in the range `[1, 2 104]. *1 <= Node.val <= 105*1 <= low <= high <= 105* AllNode.val` are unique.

题目大意：

给定[low, high]和BST，求满足条件的BST的节点和

解题思路：

Easy题，DFS，条件比较容易错

解题步骤：

N/A

注意事项：

  1. 两个条件，若root.val在范围内，加入和。若low小于root.val(这里不取等号，因为所有节点是唯一，不存在相等节点)，
    表示范围适用于左节点，同理右节点。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
	if not root:
		return 0
	res = 0
	if low <= root.val <= high:
		res += root.val
	if low < root.val:
		res += self.rangeSumBST(root.left, low, high)
	if root.val < high:
		res += self.rangeSumBST(root.right, low, high)
	return res

算法分析：

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

Posted on Disqus:

LeetCode



Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map. void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input
[“MyHashMap”, “put”, “put”, “get”, “get”, “put”, “get”, “remove”, “get”]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]


Constraints:

0 <= key, value <= 10<sup>6</sup> At most 10<sup>4</sup> calls will be made to put, get, and remove.

题目大意：

设计HashMap

LL解题思路(推荐)：

大学学到的方法，用Array实现，将key mod prime num找到index插入。难点在于冲突处理，这里用chaining方法，也就是LL

解题步骤：

N/A

注意事项：

  1. 迭代LL时候，每种方法put, get, remove都不同。put只能迭代到最后一个不能到None，因为要从尾部加入。
    get正常一个个迭代。remove要从parent也就是it.next迭代因为要删除节点。

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
33
34
35
36
37
38
39
40
41
42
43
44
class MyHashMap(TestCases):

    def __init__(self):
        self.key_space = 997
        self.buckets = [ListNode(-1, -1) for _ in range(self.key_space)]

    def put(self, key: int, value: int) -> None:
        index = key % self.key_space
        it = self.buckets[index]
        while it:
            if it.key == key:
                it.val = value
                return
            if not it.next:
                break
            it = it.next
        it.next = ListNode(key, value)

    def get(self, key: int) -> int:
        index = key % self.key_space
        it = self.buckets[index]
        while it:
            if it.key == key:
                return it.val
            it = it.next
        return -1

    def remove(self, key: int) -> None:
        index = key % self.key_space
        it = self.buckets[index]
        while it.next:
            if it.next.key == key:
                tmp = it.next
                it.next, tmp.next = it.next.next, None
                return
            it = it.next


class ListNode:

    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

算法分析：

时间复杂度为O(k)，空间复杂度O(n), k为冲突数

数组算法II解题思路：

较容易实现，remove复杂度稍差，但是最差情况也是同上

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
class MyHashMap(TestCases):

    def __init__(self):
        self.key_space = 997
        self.buckets = [[] for _ in range(self.key_space)]

    def put(self, key: int, value: int) -> None:
        index = key % self.key_space
        for i, [_key, _val] in enumerate(self.buckets[index]):
            if _key == key:
                self.buckets[index][i] = [key, value]
                return
        self.buckets[index].append([key, value])

    def get(self, key: int) -> int:
        index = key % self.key_space
        for _key, _val in self.buckets[index]:
            if _key == key:
                return _val
        return -1

    def remove(self, key: int) -> None:
        index = key % self.key_space
        for i, [_key, _val] in enumerate(self.buckets[index]):
            if _key == key:
                self.buckets[index].pop(i)
                return

算法分析：

时间复杂度为O(k)，空间复杂度O(n), k为冲突数

Posted on Disqus:

Input - (“mon 10:00 am”, mon 11:00 am)
Output - [11005, 11010, 11015…11100]
Output starts with 1 if the day is monday, 2 if tuesday and so on till 7 for sunday
Append 5 min interval times to that till the end time
So here it is 10:05 as first case, so its written as 11005
2nd is 10:10 so its written as 11010

题目大意：

DD的面经题，给定开始时间和结束时间，求5分钟的间隔时间，注意要round to 5min

解题思路：

由于非10进制，所以开一个类来计算进制

解题步骤：

N/A

注意事项：

  1. 实现lt函数
  2. 12am, 12pm要mod 12
  3. (0 if parts[2] == ‘am’ else 12)加括号
  4. 开始时间到到5分钟端点，结束时间加1分钟，由于只实现了lt

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
DAY_DICT = {'mon': 1, 'tue': 2, 'wed': 3, 'thu': 4, 'fri': 5, 'sat': 6, 'sun': 7}
class Solution(TestCases):

    def get_intervals(self, start, end) -> List:
        start_time = Time(start)
        end_time = Time(end)
        if start_time.min % 5 > 0:
            start_time.add(5 - start_time.min % 5)
        end_time.add(1)
        res = []
        while start_time < end_time:
            res.append(start_time.get_numeric())
            start_time.add(5)
        return res


class Time:

    def __init__(self, time):
        parts = time.split(' ')
        day = DAY_DICT[parts[0]]
        time_parts = parts[1].split(':')
        hour = int(time_parts[0]) % 12 + (0 if parts[2] == 'am' else 12) # remember paren (0 ...12), and % 12
        self.day = day
        self.hour = hour
        self.min = int(time_parts[1])

    def __lt__(self, other):
        if self.day < other.day or (self.day == other.day and self.hour < other.hour) or \
                (self.day == other.day and self.hour == other.hour and self.min < other.min):
            return True
        else:
            return False

    def get_numeric(self):
        return self.day * 10000 + self.hour * 100 + self.min

    def add(self, mins):
        self.min += mins
        if self.min == 60:
            self.min = 0
            self.hour += 1
        if self.hour == 24:
            self.hour = 0
            self.day += 1
        if self.day == 7:
            self.day = 0

算法分析：

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

Posted on Disqus:

LeetCode



Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2<sup>31</sup>, 2<sup>31</sup> - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “1+1”
Output: 2


Example 2:

Input: s = “6-4/2”
Output: 4


Example 3:

Input: s = “2(5+52)/3+(6/2+8)”
Output: 21


Constraints:

1 <= s <= 10<sup>4</sup> s consists of digits, '+', '-', '*', '/', '(', and ')'.
s is a *valid expression.

题目大意：

实现字符串加减乘除且有括号。

解题思路：

类似于Leetcode 227求加减乘除，这里多了括号，括号内含加减乘除，所以每对括号是一轮DFS。遇到左括号，就进入递归，遇到右括号就返回递归值

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

解题步骤：

N/A

注意事项：

  1. 不同于L227, 类似于填位法将i作为DFS参数传入，返回括号内的值以及i。i放入while循环， i += 1要加入到空格情况和循环最后
  2. 最后位加入加号要移除DFS中，放入主函数
  3. 注意处理括号情况的顺序，左括号在空格后，右括号在最后

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
33
def calculate(self, s: str) -> int:
	s += '+'
	return self.dfs(s, 0)

def dfs(self, s, i):
	res, num, stack, op = 0, 0, [], '+'
	while i < len(s):
		char = s[i]
		if char == ' ':
			i += 1
			continue
		if char == '(':
			num, i = self.dfs(s, i + 1)
		elif char.isdigit():
			num = num * 10 + int(char)
		elif op == '-':
			stack.append(-num)
		elif op == '+':
			stack.append(num) # [4+2*1]
		elif op == '*':
			prev = stack.pop()
			stack.append(prev * num)
		elif op == '/':
			prev = stack.pop()
			stack.append(int(prev / num))  # remember
		if char in '+-*/':
			num = 0
			op = char

		if char == ')':
			return sum(stack), i
		i += 1
	return sum(stack)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Design a data structure to store the strings’ count with the ability to return the strings with minimum and maximum counts.

Implement the AllOne class:

AllOne() Initializes the object of the data structure. inc(String key) Increments the count of the string key by 1. If key does not exist in the data structure, insert it with count 1.
dec(String key) Decrements the count of the string key by 1. If the count of key is 0 after the decrement, remove it from the data structure. It is guaranteed that key exists in the data structure before the decrement. getMaxKey() Returns one of the keys with the maximal count. If no element exists, return an empty string "".
getMinKey() Returns one of the keys with the minimum count. If no element exists, return an empty string "".

Example 1:

Input
[“AllOne”, “inc”, “inc”, “getMaxKey”, “getMinKey”, “inc”, “getMaxKey”, “getMinKey”]
[[], [“hello”], [“hello”], [], [], [“leet”], [], []]
Output
[null, null, null, “hello”, “hello”, null, “hello”, “leet”]

Explanation
AllOne allOne = new AllOne();
allOne.inc(“hello”);
allOne.inc(“hello”);
allOne.getMaxKey(); // return “hello”
allOne.getMinKey(); // return “hello”
allOne.inc(“leet”);
allOne.getMaxKey(); // return “hello”
allOne.getMinKey(); // return “leet”


Constraints: 1 <= key.length <= 10
key consists of lowercase English letters. It is guaranteed that for each call to dec, key is existing in the data structure.
At most `5 104calls will be made toinc,dec,getMaxKey, andgetMinKey`.

题目大意：

设计数据结构，使其支持增加或减少一个单词的频数，最大或最小单词的频数。注意最小频数不能为0

解题思路：

这个频数有点似LRU的分层思路，加入self.max_freq, 其他操作都可以实现，但是dec操作不能达到O(1), 因为若某个最小频数单词从1变成0，需要检索频率到下一个有节点的层。
改进就是要将频率的的值连起来，所以参考LRU，map的key是频率，value是node，node中含有freq，形成一个环。而node含有该频率对应的单词set，inc/dec就是将单词移动另一个node中

解题步骤：

N/A

注意事项：

  1. 与LRU区别: map的key是频率，node含有频率和单词set，数据结构加入key_to_count。LL是从最大频率到最小频率
  2. inc操作将节点从原频率node移到下一个频率node，若新node不存在，调用append_before. 然后从原频率node的单词set中删除该单词，若set为空，删除此node以及map中的entry
  3. dec与inc类似，但要注意频率变成0的情况：不移到新的node，且从key_to_count中删除该单词

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
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class AllOne(TestCases):

    def __init__(self):
        self.freq_to_node = {}
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next, self.tail.prev = self.tail, self.head
        self.key_to_count = collections.defaultdict(int)

    def inc(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.tail
        count += 1
        if count not in self.freq_to_node:
            self.freq_to_node[count] = self.append_before(old_node)
        new_node = self.freq_to_node[count]
        new_node.key_set.add(key)
        self.key_to_count[key] = count

        count -= 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count) # remember

    def dec(self, key: str) -> None:
        count = self.key_to_count[key]
        old_node = self.freq_to_node[count] if count in self.freq_to_node else self.head
        count -= 1
        if count > 0: # remember
            if count not in self.freq_to_node:
                self.freq_to_node[count] = self.append_after(old_node)
            new_node = self.freq_to_node[count]
            new_node.key_set.add(key)
            self.key_to_count[key] = count
        else:
            self.key_to_count.pop(key)

        count += 1
        if count in self.freq_to_node and key in self.freq_to_node[count].key_set:
            self.freq_to_node[count].key_set.remove(key)
            if len(self.freq_to_node[count].key_set) == 0:
                self.remove_node(self.freq_to_node[count])
                self.freq_to_node.pop(count)

    def getMaxKey(self) -> str:
        node = self.head.next
        return '' if node == self.tail else next(iter(node.key_set))

    def getMinKey(self) -> str:
        node = self.tail.prev
        return '' if node == self.head else next(iter(node.key_set))

    def append_before(self, node):
        new_node = ListNode(node.freq + 1)
        predecessor, successor = node.prev, node
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def append_after(self, node):
        new_node = ListNode(node.freq - 1)
        predecessor, successor = node, node.next
        predecessor.next, new_node.prev = new_node, predecessor
        new_node.next, successor.prev = successor, new_node
        return new_node

    def remove_node(self, node):
        predecessor, successor = node.prev, node.next
        predecessor.next, successor.prev = successor, predecessor
        node.prev, node.next = None, None


class ListNode:
    def __init__(self, freq=0, next=None, prev=None):
        self.key_set = set()
        self.freq = freq
        self.next = next
        self.prev = prev

算法分析：

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

Free mock interview