KK's blog

LeetCode 129 Sum Root to Leaf Numbers

Posted on 2022-01-16 Disqus:

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Example 1:

Input: root = [1,2,3]
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

Example 2:

Input: root = [4,9,0,5,1]
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Constraints: The number of nodes in the tree is in the range [1, 1000].
0 <= Node.val <= 9 The depth of the tree will not exceed 10.

题目大意：

由root到叶子节点的数字组成多位数的数，求这些数的总和

解题思路：

题目提到叶子节点，所以DFS中要含叶子节点的情况

解题步骤：

N/A

注意事项：

题目提到叶子节点，所以DFS中要含叶子节点的情况。当然还要有root为空的情况，这样root.left和root.right不用非空检查，代码更简洁

Python代码：

def sumNumbers(self, root: TreeNode) -> int:
	return self.dfs(root, 0)

def dfs(self, root, path):
	if not root:
		return 0
	current = path * 10 + root.val
	if not root.left and not root.right:
		return current
	#if root.left #if root.right:
	return self.dfs(root.left, current) + self.dfs(root.right, current)

算法分析：

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

LeetCode 125 Valid Palindrome

Posted on 2022-01-16 Disqus:

LeetCode

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:

Input: s = “A man, a plan, a canal: Panama”
Output: true
Explanation: “amanaplanacanalpanama” is a palindrome.

Example 2:

Input: s = “race a car”
Output: false
Explanation: “raceacar” is not a palindrome.

Example 3:

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.

Constraints:

`1 <= s.length <= 2 10⁵*s` consists only of printable ASCII characters.

题目大意：

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

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

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

解题步骤：

N/A

注意事项：

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

Python代码：

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字符串比较

注意事项：

比较时，要转换成小写

Python代码：

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)

LeetCode 118 Pascal's Triangle

Posted on 2022-01-16 Disqus:

LeetCode

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:

Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:

Input: numRows = 1
Output: [[1]]

Constraints:

* 1 <= numRows <= 30

题目大意：

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

解题思路：

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

解题步骤：

N/A

注意事项：

初始值为[1]

Python代码：

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

算法分析：

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

LeetCode 100 Same Tree

Posted on 2022-01-16 Disqus:

LeetCode

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:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints:

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

题目大意：

判断二叉树是否相等

解题思路：

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

解题步骤：

N/A

注意事项：

Python代码：

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)

LeetCode 093 Restore IP Addresses

Posted on 2022-01-16 Disqus:

LeetCode

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

For example, "0.1.2.201" and "192.168.1.1" are valid IP addresses, but "0.011.255.245", "192.168.1.312" and "192.168@1.1" are invalid IP addresses.

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You are not allowed to reorder or remove any digits in s. You may return the valid IP addresses in any order.

Example 1:

Input: s = “25525511135”
Output: [“255.255.11.135”,”255.255.111.35”]

Example 2:

Input: s = “0000”
Output: [“0.0.0.0”]

Example 3:

Input: s = “101023”
Output: [“1.0.10.23”,”1.0.102.3”,”10.1.0.23”,”10.10.2.3”,”101.0.2.3”]

Constraints: 0 <= s.length <= 20
* s consists of digits only.

题目大意：

给定一个数字字符串，求以分解成合法IP的所有解。IP每段范围是0-255且不能有前缀0，如06

解题思路：

求所有解，所以用DFS

解题步骤：

N/A

注意事项：

用DFS模板，属于结果分组型DFS，dfs函数有k。
两个限制条件，不能含leading zero和数字范围在255内

Python代码：

def restoreIpAddresses(self, s: str) -> List[str]:
	res = []
	self.dfs(s, 0, [], res, 4)
	return res

def dfs(self, s, st, path, res, k):
	if st == len(s) and k == 0:
		res.append('.'.join(path))
		return
	if st == len(s) or k == 0:
		return
	for i in range(st, min(st + 3, len(s))):
		segment = s[st:i + 1]
		if len(segment) > 1 and segment[0] == '0': # no leading 0
			continue
		if int(segment) > 255: # remember
			continue
		path.append(segment)
		self.dfs(s, i + 1, path, res, k - 1)
		path.pop()

算法分析：

时间复杂度为O(1)，空间复杂度O(1), 由于IP固定是4个部分，每个部分最多3位，所以乘法原理第一个dot的选择有三个位置，其他两个dot如此类推，3x3x3=27