KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

A message containing letters from A-Z can be encoded into numbers using the following mapping:

<pre>'A' -> "1" 'B' -> "2" ... 'Z' -> "26" </pre>

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

  • "AAJF" with the grouping (1 1 10 6)
  • "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The test cases are generated so that the answer fits in a 32-bit integer.

Example 1:

<pre>Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12). </pre>

Example 2:

<pre>Input: s = "226" Output: 3 Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). </pre>

Example 3:

<pre>Input: s = "06" Output: 0 Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). </pre>

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zero(s).

</div>

题目大意：

数字1-26可以解码成A-Z字母。给定一串数字，求解码方法数。

解题思路：

求种数是DP和DFS，这题有递归关系，所以考虑用DP。类似于Fibonacci数列和LeetCode 070 Climbing Stairs，但此题带限制条件

递归式：

1
dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26

解题步骤：

利用DP五点注意事项

注意事项：

  1. 不合法的情况为空字符和含0. 这是求个数，根据DP知识点(数值到个数DP模板)，dp[0] = 1, 但这与题目空字符要求不同，所以特别处理。至于单个含0在循环中处理'0' < s[i - 1] <= '9'
  2. 验证单位范围[1, 9], 双位范围[10, 26]才加入到结果中。由于dp长度只多了一位而递归式含两个前状态，所以要验证i >= 2

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings(self, s: str) -> int:
	if not s:
		return 0
	dp = [0] * (len(s) + 1)
	dp[0] = 1
	for i in range(1, len(dp)):
		if '0' < s[i - 1] <= '9':
			dp[i] = dp[i - 1]
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			dp[i] += dp[i - 2]
	return dp[-1]

算法分析：

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

O(1)空间算法II解题思路：

类似于Fibonacci数列和LeetCode 070 Climbing Stairs，由于涉及到两个前状态，所以用两个变量来节省空间

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
# dp[i] = dp[i-1] + dp[i-2] if 0 < s[i-1] <= 9, 10 <= s[i-2:i] <= 26
def numDecodings2(self, s: str) -> int:
	if not s:
		return 0
	first, second = 1, 1
	for i in range(1, len(s) + 1):
		res = 0
		if '0' < s[i - 1] <= '9':
			res = second
		if i >= 2 and '10' <= s[i - 2: i] <= '26':
			res += first
		first, second = second, res
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

<pre>Input: p = [1,2,3], q = [1,2,3] Output: true </pre>

Example 2:

<pre>Input: p = [1,2], q = [1,null,2] Output: false </pre>

Example 3:

<pre>Input: p = [1,2,1], q = [1,1,2] Output: false </pre>

Constraints:

  • The number of nodes in both trees is in the range [0, 100].
  • -10<sup>4</sup> <= Node.val <= 10<sup>4</sup>

</div>

题目大意：

判断二叉树是否相等

解题思路：

类似于Leetcode 101 Symmetric Tree但稍简单, easy题

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
	if not p and not q:
		return True
	if not p or not q:
		return False
	return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

<pre>Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] </pre>

Example 2:

<pre>Input: numRows = 1 Output: [[1]] </pre>

Constraints:

  • 1 <= numRows <= 30

</div>

题目大意：

给定n行，产生n行的杨辉三角

解题思路：

用DP按照定义生成，其实类似于Fibonacci数列，不过是二维的，而不是一维。

解题步骤：

N/A

注意事项：

  1. 初始值为[1]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def generate(self, numRows: int) -> List[List[int]]:
	path, res = [1], []
	res.append(path)
	for i in range(1, numRows):
		next_level = []
		for j in range(1, len(path)):
			next_level.append(path[j - 1] + path[j])
		next_level.insert(0, 1)
		next_level.append(1)
		path = next_level
		res.append(list(path))
	return res

算法分析：

时间复杂度为<code>O(numRows<sup>2</sup>)</code>，空间复杂度O(1)

Posted on Edited on Disqus:

LeetCode

<div>

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

<pre>Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. </pre>

Example 2:

<pre>Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. </pre>

Example 3:

<pre>Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome. </pre>

Constraints:

  • 1 <= s.length <= 2 * 10<sup>5</sup>
  • s consists only of printable ASCII characters.

</div>

题目大意：

求含非字母数字的字符串是否回文，字符串含空格，冒号等. Easy题

双指针解题思路(推荐)：

回文首先考虑用相向双指针

解题步骤：

N/A

注意事项：

  1. 比较时，要转换成小写
  2. 外循环left < right条件要复制到内循环中

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def isPalindrome(self, s: str) -> bool:
	left, right = 0, len(s) - 1
	while left < right:
		while left < right and not s[left].isalnum():
			left += 1
		while left < right and not s[right].isalnum():
			right -= 1
		if s[left].lower() != s[right].lower():
			return False
		left += 1
		right -= 1
	return True

算法分析：

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

reverse法算法II解题思路：

reverse字符串比较

注意事项：

  1. 比较时，要转换成小写

Python代码：

1
2
3
4
5
6
def isPalindrome2(self, s: str) -> bool:
	res = ''
	for char in s:
		if char.isalpha() or char.isdigit():
			res += char.lower()
	return True if res == res[::-1] else False

算法分析：

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

Posted on Edited on Disqus:

LeetCode 128 Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

<pre>Input: [100, 4, 200, 1, 3, 2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. </pre>

题目大意：

给出一个未排序的整数数组，找出最长的连续元素序列的长度。
如： 给出[100, 4, 200, 1, 3, 2]，最长的连续元素序列是[1, 2, 3, 4]。返回它的长度：4。

解题思路：

这是连通问题，如果用排序方法，很容易，但时间复杂度为O(nlogn)。考虑改进，因为连通集，容易想到HashMap，把每个元素加入到其中，
然后对每个元素进行相邻查找。相邻查找就是以此元素为中心，向上向下在Map查找，从而得到此元素的最大连续序列长度。查找过的元素
在Map中删除，以免重复计算。

第二遍

注意事项：

  1. 先把所有数放入set，然后遍历每个数+1和-1删除。
  2. 删除时候一定要在n+=1和n-=1之前删除

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestConsecutive(self, nums: List[int]) -> int:
	nums_set, res = set(nums), 0
	for i in range(len(nums)):
		count, n = 1, nums[i] + 1
		while n in nums_set:
			count += 1
			nums_set.remove(n)
			n += 1
		n = nums[i] - 1
		while n in nums_set:
			count += 1
			nums_set.remove(n)
			n -= 1
		res = max(res, count)
	return res

注意事项：

  1. 加入set之后的元素不能再内循环中删除，因为外循环是遍历每一个数，可能会遍历到删除的数，正确做法是用map的value来记录是否访问过。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def longestConsecutive(self, nums: List[int]) -> int:
	num_set = collections.Counter(nums)
	res = 0
	for n in nums:
		if num_set[n] == 0:
			continue
		max_len = 1
		num_set[n] = 0
		i = n + 1
		while i in num_set:
			num_set[i] = 0
			max_len += 1
			i += 1
		i = n - 1
		while i in num_set:
			num_set[i] = 0
			max_len += 1
			i -= 1
		res = max(res, max_len)
	return res

注意事项：

  1. Java中在for循环中不能修改hashSet，所以只能用HashMap且value存boolean替代。HashMap表示此Map还是否含有该元素。

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
26
27
28
public int longestConsecutive(int[] nums) {
	int result = 0;
	HashMap<Integer,Boolean> hm = new HashMap<Integer,Boolean>();
	for(int i : nums)
		hm.put(i, true);
	
	Iterator it = hm.keySet().iterator();
	while(it.hasNext()){
		int key = (int)it.next();
		int i = key+1;
		int count = 1;
		while(hm.containsKey(i) && hm.get(i)){
			count++;
			hm.put(i, false);
			i++;
		}
		i = key-1;
		while(hm.containsKey(i) && hm.get(i)){
			count++;
			hm.put(i, false);
			i--;
		}
		if(count>result)
			result = count;
	}
	return result;
		
}

算法分析：

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

Free mock interview