KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

Example 1:

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.


Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.


Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.


Constraints: -2<sup>31</sup> <= x <= 2<sup>31</sup> - 1

Follow up: Could you solve it without converting the integer to a string?

题目大意：

判断是否回文数字

解题思路：

N/A

解题步骤：

N/A

注意事项：

Python代码：

1
2
def isPalindrome(self, x: int) -> bool:
	return str(x) == str(x)[::-1]

算法分析：

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

算法II解题思路：

Follow-up 不能用str，就求它的reversed数

注意事项：

  1. x是用于计算过程，所以不断变化，最后一行不能用它来与reversed的结果比较

Python代码：

1
2
3
4
5
6
7
8
def isPalindrome2(self, x: int) -> bool:
	if x < 0:
		return False
	rev, original = 0, x
	while x > 0:
		rev = rev * 10 + x % 10 # 121
		x = x // 10 # 1
	return rev == original

算法分析：

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

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)

Free mock interview