KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:



Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]


Example 2:

Input: list1 = [], list2 = []
Output: []


Example 3:

Input: list1 = [], list2 = [0]
Output: [0]


Constraints:

The number of nodes in both lists is in the range [0, 50]. -100 <= Node.val <= 100
Both list1 and list2 are sorted in *non-decreasing order.

题目大意：

合并两个LL

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. Fake Node的引入

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
	fake_head = ListNode(0)
	it, it2, it_res = list1, list2, fake_head
	while it and it2:
		if it.val <= it2.val:
			it_res.next = it
			it = it.next
			it_res = it_res.next
		else:
			it_res.next = it2
			it2 = it2.next
			it_res = it_res.next
	if it:
		it_res.next = it
	if it2:
		it_res.next = it2
	return fake_head.next

算法分析：

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

Posted on Edited on Disqus:

LeetCode 139 Word Break



Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation. You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".


Example 2:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
             Note that you are allowed to reuse a dictionary word.


Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false


题目大意：

一个字符串s，是否能够被“字典集合”（wordDict）中的单词拼接而成。

解题思路：

这是经典题。如果知道s[0:n-1)很容易知道s[0:n)是否有解，既然和子问题有关，就用DP。

  1. 定义dp[i]为字符串s[0,i)是否可以合法分解。
  2. 判断一个字符串是否可以合法分解，方案是尝试在每一位进行分解，若其中一个可分解，即有解。
    递归式为dp[i] |= dp[k] && isWord(s[k:i)), 0 <= k < i.
  3. 方向为从左到右i=0..n, 初始值为dp[0] = true.

注意事项：

  1. 初始值dp[0] = True。
  2. 递归中dp[i]用或操作符。
  3. s[j:i] in word_set不要忘记上限为i

Python代码：

1
2
3
4
5
6
7
8
9
10
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
	if not s:
		return False
	word_set = set(wordDict)
	dp = [False] * (len(s) + 1)
	dp[0] = True
	for i in range(1, len(dp)):
		for j in range(0, i):
			dp[i] |= dp[j] and s[j:i] in word_set
	return dp[len(dp) - 1]

注意事项：

  1. 将两个输入都转换成小写。
  2. 递归中dp[i]用或操作符。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean wordBreak(String s, List<String> wordDict) {
	if(s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0)
		return false;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	
	boolean[] dp = new boolean[s.length() + 1];
	dp[0] = true;
	for(int i = 1; i < dp.length; i++)
		for(int k = 0; k < i; k++) {//"a"
			dp[i] |= dp[k] && wordDictLower.contains(s.substring(k, i));
		}
	return dp[dp.length - 1];
}

算法分析：

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

算法II解题思路：

这题也可以额用DFS来解。如果可以用DP就尽量用DP，只有求所有可能性才只能用DFS而不能用DP。
这道题递归子问题dfs[:n]为子串[0:n)是否可合法拆解。对于子问题而言，需要对其范围内i=[0:st)的每个可能位置分解
dfs[:i) + word[i:st)从而求出dfs(st)的解，只有任一分解成功，dfs(st)=true，否则false。

Cache的应用场景： 如果子问题重复就要用Cache。
例如dfs(10)=dfs(9)+s[9:9] = (dfs(8) + s[8:8]) + s[9:9]
=dfs(8)+s[8:9]
dfs(8)由第一层递归第二个循环s[8:9]和第二层递归s[9:9]达到，这是重复的子问题dfs(8)。如果不cache，dfs(8)的求解
是重复的。

Cache模板：

  1. key为子问题索引st，value为子问题的解。
  2. 紧跟终结条件，若在cache中，返回子问题的解。
  3. 循环结束，将子问题的结果存于cache。

注意事项：

  1. 将两个输入都转换成小写。
  2. 递归中先查询词是否在字典中再递归。如果顺序调转就会LTE，因为这些子问题是白费的。
  3. 递归终结条件为st==0而不是st==s.length()因为子问题递归从右到左。

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
public boolean wordBreakDFS(String s, List<String> wordDict) {
	if(s == null || s.isEmpty() || wordDict == null || wordDict.size() == 0)
		return false;
	Set<String> wordDictLower = new HashSet<>();
	for(String c : wordDict)
		wordDictLower.add(c.toLowerCase());
	s = s.toLowerCase();
	Map<Integer, Boolean> cache = new HashMap<>();
	return dfs(s, wordDictLower, s.length(), cache);
}

// subproblem's answer dfs[:st)
boolean dfs(String s, Set<String> wordDict, int st, Map<Integer, Boolean> cache) {
	if(st == 0)
		return true;
	if(cache.containsKey(st))
		return cache.get(st);
	boolean re = false;
	for(int i = 0; i < st; i++) {
		if(wordDict.contains(s.substring(i, st)) && dfs(s, wordDict, i, cache))
			return true;
	}
	cache.put(st, re);
	return false;
}

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000


For example, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

Example 1:

Input: s = “III”
Output: 3
Explanation: III = 3.


Example 2:

Input: s = “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.


Example 3:

Input: s = “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.


Constraints: 1 <= s.length <= 15
s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M'). It is guaranteed that s is a valid roman numeral in the range [1, 3999].

题目大意：

罗马数组转阿拉伯数字

解题思路：

按照规则累加。有一个特别规则是需要做减法如IV。

解题步骤：

N/A

注意事项：

  1. 先加再减的方法。
  2. SYMBOL_TO_VAL的值可以哟用于判断先后顺序。

Python代码：

1
2
3
4
5
6
7
8
9
10
def romanToInt(self, s: str) -> int:
	SYMBOL_TO_VAL = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
	res, num, prev = 0, 0, ''
	for symbol in s:
		num = SYMBOL_TO_VAL[symbol]
		if prev and SYMBOL_TO_VAL[prev] < SYMBOL_TO_VAL[symbol]:
			res -= SYMBOL_TO_VAL[prev] * 2
		res += num
		prev = symbol
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Implement pow(x, n), which calculates x raised to the power n (i.e., x<sup>n</sup>).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000


Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100


Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25


Constraints:

-100.0 < x < 100.0 -2<sup>31</sup> <= n <= 2<sup>31</sup>-1
* -10<sup>4</sup> <= x<sup>n</sup> <= 10<sup>4</sup>

题目大意：

求幂

解题思路：

DFS

解题步骤：

N/A

注意事项：

  1. 保存dfs(x, n/2)的临时结果，避免重复计算
  2. n可以是0，负数

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def myPow(self, x: float, n: int) -> float:
	if n >= 0:
		return self.dfs(x, n)
	else:
		return self.dfs(1 / x, -n)

def dfs(self, x, n):
	if n == 0:
		return 1
	if n == 1:
		return x
	if n % 2 == 0:
		tmp = self.dfs(x, n / 2)
		return tmp * tmp
	else:
		tmp = self.dfs(x, (n - 1) / 2)
		return tmp * tmp * x

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given two sparse vectors, compute their dot product.

Implement class SparseVector:

SparseVector(nums) Initializes the object with the vector nums dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 10 + 03 + 00 + 24 + 30 = 8


Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 00 + 10 + 00 + 00 + 02 = 0


Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6


Constraints:

n == nums1.length == nums2.length 1 <= n <= 10^5
* 0 <= nums1[i], nums2[i] <= 100

题目大意：

稀疏数组乘法，设计类来存储且计算乘积

HashMap解题思路：

类似于Two sum，也是两种方法。HashMap的方法由于hash函数计算容易冲突，所以算法复杂度不够稳定。

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class SparseVector(TestCases):

    def __init__(self, nums: List[int]):
        self.idx_to_num = collections.defaultdict(int)
        for i, n in enumerate(nums):
            if n > 0:
                self.idx_to_num[i] = n

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        res = 0
        for i, n in vec.idx_to_num.items():
            if i in self.idx_to_num:
                res += self.idx_to_num[i] * n
        return res

算法分析：

创建时间复杂度为O(n)，计算时间复杂度为O(L)，空间复杂度O(L)，L为非0元素个数

Mergesort算法II解题思路：

初始化复杂度比较稳定

Python代码：

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

    def __init__(self, nums: List[int]):
        self.non_zero_list = []
        for i, n in enumerate(nums):
            if n > 0:
                self.non_zero_list.append((i,n))

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        i, j, res = 0, 0, 0
        while i <= len(self.non_zero_list) - 1 and j <= len(vec.non_zero_list) - 1:
            if self.non_zero_list[i][0] == vec.non_zero_list[j][0]:
                res += self.non_zero_list[i][1] * vec.non_zero_list[j][1]
                i += 1
                j += 1
            elif self.non_zero_list[i][0] < vec.non_zero_list[j][0]:
                i += 1
            else:
                j += 1
        return res

算法分析：

创建时间复杂度为O(n)，计算时间复杂度为O(L1 + L2)，空间复杂度O(L)，L为非0元素个数

Free mock interview