KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



You are given a stream of records about a particular stock. Each record contains a timestamp and the corresponding price of the stock at that timestamp.

Unfortunately due to the volatile nature of the stock market, the records do not come in order. Even worse, some records may be incorrect. Another record with the same timestamp may appear later in the stream correcting the price of the previous wrong record.

Design an algorithm that:

Updates the price of the stock at a particular timestamp, correcting the price from any previous records at the timestamp. Finds the latest price of the stock based on the current records. The latest price is the price at the latest timestamp recorded.
Finds the maximum price the stock has been based on the current records. Finds the minimum price the stock has been based on the current records.

Implement the StockPrice class:

StockPrice() Initializes the object with no price records. void update(int timestamp, int price) Updates the price of the stock at the given timestamp.
int current() Returns the latest price of the stock. int maximum() Returns the maximum price of the stock.
int minimum() Returns the minimum price of the stock.

Example 1:

Input
[“StockPrice”, “update”, “update”, “current”, “maximum”, “update”, “maximum”, “update”, “minimum”]
[[], [1, 10], [2, 5], [], [], [1, 3], [], [4, 2], []]
Output
[null, null, null, 5, 10, null, 5, null, 2]

Explanation
StockPrice stockPrice = new StockPrice();
stockPrice.update(1, 10); // Timestamps are [1] with corresponding prices [10].
stockPrice.update(2, 5);  // Timestamps are [1,2] with corresponding prices [10,5].
stockPrice.current();     // return 5, the latest timestamp is 2 with the price being 5.
stockPrice.maximum();     // return 10, the maximum price is 10 at timestamp 1.
stockPrice.update(1, 3);  // The previous timestamp 1 had the wrong price, so it is updated to 3.
                          // Timestamps are [1,2] with corresponding prices [3,5].
stockPrice.maximum();     // return 5, the maximum price is 5 after the correction.
stockPrice.update(4, 2);  // Timestamps are [1,2,4] with corresponding prices [3,5,2].
stockPrice.minimum();     // return 2, the minimum price is 2 at timestamp 4.


Constraints: 1 <= timestamp, price <= 10<sup>9</sup>
At most 10<sup>5</sup> calls will be made in total to update, current, maximum, and minimum. current, maximum, and minimum will be called only after update has been called at least once.

题目大意：

实现一个关于股票的数据结构，可以更新时间点对应的股价，最大最小值，最新价格

解题思路：

求最大最小值容易想到用heap，但heap不支持更新，难点是怎么支持更新股价。
仍然(price, timestamp)加入到heap中，在出堆时验证

解题步骤：

N/A

注意事项：

  1. 验证堆顶： 若股价和时间不匹配(用time_to_price验证)，表示这是stale股价，不断去掉，直到验证成功为止，最后加入到堆中

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

    def __init__(self):
        self.time_to_price = {}
        self.cur_time = 0
        self.min_heap = []
        self.max_heap = []

    def update(self, timestamp: int, price: int) -> None:
        self.time_to_price[timestamp] = price
        self.cur_time = max(self.cur_time, timestamp)
        heapq.heappush(self.min_heap, (price, timestamp))
        heapq.heappush(self.max_heap, (-price, timestamp))

    def current(self) -> int:
        return self.time_to_price[self.cur_time]

    def maximum(self) -> int:
        price, timestamp = heapq.heappop(self.max_heap)
        while -price != self.time_to_price[timestamp]:
            price, timestamp = heapq.heappop(self.max_heap)
        heapq.heappush(self.max_heap, (price, timestamp))
        return -price

    def minimum(self) -> int:
        price, timestamp = heapq.heappop(self.min_heap)
        while price != self.time_to_price[timestamp]:
            price, timestamp = heapq.heappop(self.min_heap)
        heapq.heappush(self.min_heap, (price, timestamp))
        return price

算法分析：

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

Posted on Disqus:

LeetCode



You are given an m x n binary matrix grid.

In one operation, you can choose any row or column and flip each value in that row or column (i.e., changing all 0‘s to 1‘s, and all 1‘s to 0‘s).

Return true if it is possible to remove all 1‘s from grid using any number of operations or false otherwise.

Example 1:



Input: grid = [[0,1,0],[1,0,1],[0,1,0]]
Output: true
Explanation: One possible way to remove all 1’s from grid is to:
- Flip the middle row
- Flip the middle column


Example 2:



Input: grid = [[1,1,0],[0,0,0],[0,0,0]]
Output: false
Explanation: It is impossible to remove all 1’s from grid.


Example 3:



Input: grid = [[0]]
Output: true
Explanation: There are no 1’s in grid.


Constraints:

m == grid.length n == grid[i].length
1 <= m, n <= 300 grid[i][j] is either 0 or 1.

题目大意：

给定一个矩阵，每次可以flip一行或一列，求是否可以令矩阵变成全0

解题思路：

从例子找规律，
010和010属于一种类型
010和101也是同一种，每一行必须符合任何一种类型才是解

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    def removeOnes(self, grid: List[List[int]]) -> bool:
    	row_patten, row_pattern_invert = grid[0], [1 - n for n in grid[0]]
    	for i in range(1, len(grid)):
    		if grid[i] != row_patten and grid[i] != row_pattern_invert:
    			return False
    	return True

算法分析：

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

Posted on Disqus:

LeetCode



This is an interactive problem.

You are given an array of unique strings wordlist where wordlist[i] is 6 letters long, and one word in this list is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original list with 6 lowercase letters.

This function returns an integer type, representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. At the end of any number of calls, if you have made 10 or fewer calls to Master.guess and at least one of these guesses was secret, then you pass the test case.

Example 1:

Input: secret = “acckzz”, wordlist = [“acckzz”,”ccbazz”,”eiowzz”,”abcczz”], numguesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess(“aaaaaa”) returns -1, because “aaaaaa” is not in wordlist.
master.guess(“acckzz”) returns 6, because “acckzz” is secret and has all 6 matches.
master.guess(“ccbazz”) returns 3, because “ccbazz” has 3 matches.
master.guess(“eiowzz”) returns 2, because “eiowzz” has 2 matches.
master.guess(“abcczz”) returns 4, because “abcczz” has 4 matches.
We made 5 calls to master.guess and one of them was the secret, so we pass the test case.


Example 2:

Input: secret = “hamada”, wordlist = [“hamada”,”khaled”], numguesses = 10
Output: You guessed the secret word correctly.


Constraints:

1 <= wordlist.length <= 100 wordlist[i].length == 6
wordlist[i] consist of lowercase English letters. All the strings of wordlist are unique.
secret exists in wordlist. numguesses == 10

题目大意：

给定单词列表，每个单词长度为6， 其中一个为答案，每次猜一个单词。给一个API会告诉你猜的单词有多少位命中(位置,数值), 求是否可以10次内猜对

暴力法解题思路：

较直观的解法是抽第一个单词出来，然后call API, 然后再filter wordlist使得新的单词列表里的单词的命中位数也是一样的。每轮缩少范围。

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    7
    8
    def findSecretWord2(self, wordlist, master):
    	for i in range(10):
    		guess = wordlist[0]
    		res = master.guess(guess)
    		wordlist = [w for w in wordlist if self.match(w, guess) == res]

    def match(self, w1, w2):
    	return sum(i == j for i, j in zip(w1, w2))

算法分析：

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

统计频率算法II解题思路(推荐)：

上述方法跟单词个数有关，如果很多的话，就会超过10次。考虑单词长度为6，而可以猜10次。考虑用26字母存储法，也就是统计频率。统计每位的频率，然后将频率作为这一位的分数，求每个单词的总分。
一定要选择单词列表中的某个单词去猜，如果不在列表中返回为-1，这个信息没有任何作用。
选择总分最高的去猜，原理是它最具代表性，这样可以快速排除很多单词，有点类似于二分法。反之，若用频率低的单词，也就只能排除一个单词。

Python代码：

1
2
3
4
5
6
7
8
9
def findSecretWord(self, wordlist, master):
	for _ in range(10):
		char_to_count = [collections.Counter(w[i] for w in wordlist) for i in range(6)]
		guess = max(wordlist, key=lambda w: sum(char_to_count[i][char] for i, char in enumerate(w)))
		res = master.guess(guess)
		wordlist = [w for w in wordlist if self.match(w, guess) == res]

def match(self, w1, w2):
	return sum(i == j for i, j in zip(w1, w2))

算法分析：

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

Posted on Disqus:

LeetCode



You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the i<sup>th</sup> replacement operation:

1. Check if the substring sources[i] occurs at index indices[i] in the original string s.
2. If it does not occur, do nothing.
3. Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "<u>ab</u>cd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "<u>eee</u>cd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

For example, a testcase with s = "abc", indices = [0, 1], and sources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

Example 1:



Input: s = “abcd”, indices = [0, 2], sources = [“a”, “cd”], targets = [“eee”, “ffff”]
Output: “eeebffff”
Explanation:
“a” occurs at index 0 in s, so we replace it with “eee”.
“cd” occurs at index 2 in s, so we replace it with “ffff”.


Example 2:



Input: s = “abcd”, indices = [0, 2], sources = [“ab”,”ec”], targets = [“eee”,”ffff”]
Output: “eeecd”
Explanation:
“ab” occurs at index 0 in s, so we replace it with “eee”.
“ec” does not occur at index 2 in s, so we do nothing.


Constraints: 1 <= s.length <= 1000
k == indices.length == sources.length == targets.length 1 <= k <= 100
0 <= indexes[i] < s.length 1 <= sources[i].length, targets[i].length <= 50
s consists of only lowercase English letters. sources[i] and targets[i] consist of only lowercase English letters.

题目大意：

整洁题。找到位置，然后验证，最后替换

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. i是循环外的变量，所以poplate index_dict注意不能重名

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
	res = ''
	index_dict = {}
	for _i, _n in enumerate(indices):
		index_dict[_n] = _i # 0 -> 0, 2 -> 1
	i = 0
	while i < len(s):
		if i in index_dict and s[i:i + len(sources[index_dict[i]])] == sources[index_dict[i]]:
			res += targets[index_dict[i]]
			i += len(sources[index_dict[i]])
		else:
			res += s[i]
			i += 1
	return res

算法分析：

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

Posted on Disqus:

LeetCode



An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.

Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.

Example 1:

Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1  2 = 2.
- Twice the value of 3 is 3  2 = 6.
- Twice the value of 4 is 4  2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].


Example 2:

Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.


Example 3:

Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.


Constraints: 1 <= changed.length <= 10<sup>5</sup>
* 0 <= changed[i] <= 10<sup>5</sup>

题目大意：

给定一个数组，求这个数组是否可以分成两部分，后一部分的每个元素是否前一部分某元素的两倍

解题思路：

由最大值容易确定它的一半是否在数组中。所以排序后由大到小遍历。注意数组元素可能相等，所以不能用visited set来记录已用过的数，val_to_index也不支持重复，只有val_to_count支持

解题步骤：

N/A

注意事项：

  1. 用val_to_count，注意遍历时候就要减去，不要进入if才减去

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findOriginalArray(self, changed: List[int]) -> List[int]:
	if len(changed) % 2 == 1:
		return []
	changed.sort()
	res = []
	val_to_count = collections.Counter(changed)
	for i in reversed(range(len(changed))):
		if val_to_count[changed[i]] == 0:
			continue
		val_to_count[changed[i]] -= 1 # not in  if statement
		if changed[i] / 2 in val_to_count and val_to_count[changed[i] / 2] > 0:
			val_to_count[changed[i] / 2] -= 1
			res.append(int(changed[i] / 2))
	return [] if len(res) * 2 != len(changed) else res

算法分析：

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

Free mock interview