KK's blog

每天积累多一些

0%

Posted on Edited 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 Edited 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 Edited 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 Edited on Disqus:

LeetCode



You are asked to design a file system that allows you to create new paths and associate them with different values.

The format of a path is one or more concatenated strings of the form: / followed by one or more lowercase English letters. For example, “/leetcode" and “/leetcode/problems" are valid paths while an empty string "" and "/" are not.

Implement the FileSystem class:

bool createPath(string path, int value) Creates a new path and associates a value to it if possible and returns true. Returns false if the path already exists or its parent path doesn’t exist. int get(string path) Returns the value associated with path or returns -1 if the path doesn’t exist.

Example 1:

Input:
[“FileSystem”,”createPath”,”get”]
[[],[“/a”,1],[“/a”]]
Output:
[null,true,1]
Explanation:
FileSystem fileSystem = new FileSystem();

fileSystem.createPath(“/a”, 1); // return true
fileSystem.get(“/a”); // return 1


Example 2:

Input:
[“FileSystem”,”createPath”,”createPath”,”get”,”createPath”,”get”]
[[],[“/leet”,1],[“/leet/code”,2],[“/leet/code”],[“/c/d”,1],[“/c”]]
Output:
[null,true,true,2,false,-1]
Explanation:
FileSystem fileSystem = new FileSystem();

fileSystem.createPath(“/leet”, 1); // return true
fileSystem.createPath(“/leet/code”, 2); // return true
fileSystem.get(“/leet/code”); // return 2
fileSystem.createPath(“/c/d”, 1); // return false because the parent path “/c” doesn’t exist.
fileSystem.get(“/c”); // return -1 because this path doesn’t exist.


Constraints:

The number of calls to the two functions is less than or equal to 10<sup>4</sup> in total. 2 <= path.length <= 100
* 1 <= value <= 10<sup>9</sup>

题目大意：

设计文件系统，支持创建路径，路径含key, value

Trie解题思路：

用Trie, is_end变成key, value

解题步骤：

N/A

注意事项：

  1. 遍历用1开始，因为首个/前面是空字符串

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

    def __init__(self):
        self.head = TrieNode('')

    def createPath(self, path: str, value: int) -> bool:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                if i == len(segments) - 1: # match all the previous segments
                    it.children[segment] = TrieNode(segment)
                else:
                    return False
            it = it.children[segment]
        if it.value != -1: # exists
            return False
        it.value = value
        return True

    def get(self, path: str) -> int:
        segments = path.split('/')

        it = self.head
        for i in range(1, len(segments)):
            segment = segments[i]
            if segment not in it.children:
                return -1
            it = it.children[segment]
        return it.value

class TrieNode:

    def __init__(self, name):
        self.children = collections.defaultdict(TrieNode)  # {}
        self.name = name
        self.value = -1

算法分析：

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

算法II HashMap解题思路：

用前缀法

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class FileSystem2(TestCases):

    def __init__(self):
        self.path_to_val = defaultdict()

    def createPath(self, path: str, value: int) -> bool:

        if path == "/" or len(path) == 0 or path in self.path_to_val:
            return False

        # search from the right
        parent = path[:path.rfind('/')]
        if len(parent) > 1 and parent not in self.path_to_val:
            return False

        self.path_to_val[path] = value
        return True

    def get(self, path: str) -> int:
        return self.path_to_val.get(path, -1)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.

Return the minimum number of steps to make t an anagram of s.

An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.

Example 1:

Input: s = “bab”, t = “aba”
Output: 1
Explanation: Replace the first ‘a’ in t with b, t = “bba” which is anagram of s.


Example 2:

Input: s = “leetcode”, t = “practice”
Output: 5
Explanation: Replace ‘p’, ‘r’, ‘a’, ‘i’ and ‘c’ from t with proper characters to make t anagram of s.


Example 3:

Input: s = “anagram”, t = “mangaar”
Output: 0
Explanation: “anagram” and “mangaar” are anagrams.


Constraints:

`1 <= s.length <= 5 104*s.length == t.length*sandt` consist of lowercase English letters only.

题目大意：

通过替换字母使得两字符为同位词Anagram

解题思路：

统计某一个词的词频，遍历另一个单词，减去词频，若不够减(小于0)，就加步数

解题步骤：

N/A

注意事项：

  1. Python代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    def minSteps(self, s: str, t: str) -> int:
    	char_to_count_t = collections.Counter(t)
    	steps = 0
    	for char in s:
    		if char in char_to_count_t and char_to_count_t[char] > 0:
    			char_to_count_t[char] -= 1
    		else:
    			steps += 1
    	return steps

算法分析：

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

Free mock interview