KK's blog

LeetCode 104 Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

**Input:** root = [3,9,20,null,null,15,7]
**Output:** 3

Example 2:

**Input:** root = [1,null,2]
**Output:** 2

Example 3:

**Input:** root = []
**Output:** 0

Example 4:

**Input:** root = [0]
**Output:** 1

Constraints:

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

题目大意：

求二叉树高度。

解题思路：

公式dfs(root)=1+max(dfs(root.left),dfs(root.right))

Python代码：

1
2
3
4

def maxDepth(self, root: TreeNode) -> int:
	if not root:
		return 0
	return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

算法分析：

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

LeetCode 2073 Time Needed to Buy Tickets

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

题目大意：

排队买票，每个人都有不同的票数需求。每人每次只能买一张，买完后重新排队。买一张票需要1秒，求第k个人买票的总时间。

解题思路：

一开始按照题目要求老老实实每个元素减一，按照流程计算，但效率较低。考虑若所有人票数大于0，每轮计算结果是一样的：
当前排队人数乘以排队的人中的最小票数。当最小票数人离队后，公式会改变。如此循环直到第k个人票数也变成0为止。

解题步骤：

1. 求最小值
2. 计算票数
3. 更新人数，继续循环
4. 结果减去排在第k个人后的人数

注意事项：

1. 结果要减去排在第k个人后的还在排队的人数（tickets数不为负数，可以等于0，因为是同时在同一轮买到足够票）。

Python代码：

1
2
3
4
5
6
7
8
9
10

def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
	sum, ppl, min_tickets = 0, len(tickets), 0
	while tickets[k] > 0:
		min_tickets = min(t for t in tickets if t > 0)
		sum += min_tickets * ppl
		tickets = [t - min_tickets for t in tickets]
		ppl -= tickets.count(0)

	after_k = [i for i in range(k + 1, len(tickets)) if tickets[i] >= 0]
	return sum - len(after_k)

算法分析：

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

LeetCode 275 H-Index II

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i<sup>th</sup> paper and citations is sorted in an ascending order, return compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index.

You must write an algorithm that runs in logarithmic time.

Example 1:

**Input:** citations = [0,1,3,5,6]
**Output:** 3
**Explanation:** [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

**Input:** citations = [1,2,100]
**Output:** 2

Constraints:

• n == citations.length
• 1 <= n <= 10<sup>5</sup>
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

题目大意：

一个人的学术文章有n篇分别被引用了n次及以上，那么H指数就是n

解题思路：

数组有序，论文数从小到大有序(符合引用次数的论文数从右向左递减)，引用次数由小到大排序，所以只要从右向左遍历数组，数值和索引相交的值就是所求。

解题步骤：

二分法可提高效率，用的是

注意事项：

1. 此题是寻找单一目标，所以等号可以并入任一个if statement，但循环出来后，start必须先比较，因为贪婪法，下标越向左，越容易获得更大的结果。从这一意义上看，此题接近于first_position

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def hIndex(self, citations: List[int]) -> int:
	if citations is None or len(citations) == 0:
		return 0
	start, end = 0, len(citations) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if citations[mid] >= len(citations) - mid:
			end = mid
		else:
			start = mid
	if citations[start] >= len(citations) - start:
		return len(citations) - start
	if citations[end] >= len(citations) - end:
		return len(citations) - end
	return 0

算法分析：

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

LeetCode 007 Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2<sup>31</sup>, 2<sup>31</sup> - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

**Input:** x = 123
**Output:** 321

Example 2:

**Input:** x = -123
**Output:** -321

Example 3:

**Input:** x = 120
**Output:** 21

Example 4:

**Input:** x = 0
**Output:** 0

Constraints:

• -2<sup>31</sup> <= x <= 2<sup>31</sup> - 1

题目大意：

反转整数中的数字。

数学法解题思路：

用数学方法每位取余，余数左移。另一种方法是转成字符串然后用字符串反转的方法。

与Java的区别：

1. 不需要定义long，因为Python3所有int默认都是long
2. 反转str一行完成，非常简洁

注意事项：

1. 负值
2. 溢出

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def reverse(self, x: int) -> int:
	res, is_negative = 0, False
	if x < 0:
		is_negative = True
		x = -x
	while x > 0:
		digit = x % 10
		res = res * 10 + digit
		x //= 10
	if res > pow(2, 31) - 1:
		return 0
	if is_negative:
		res = -res
	return res

字符串法解题思路：

转为字符串，然后反转。

1
2
3
4
5
6
7
8
9

def reverse(self, x: int) -> int:
	res, is_negative = 0, False
	if x < 0:
		is_negative = True
		x = -x
	res = int(str(x)[::-1])
	if res > pow(2, 31) - 1:
		return 0
	return -res if is_negative else res

算法分析：

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

LintCode 683 Word Break III

Input:
“CatMat”
[“Cat”, “Mat”, “Ca”, “tM”, “at”, “C”, “Dog”, “og”, “Do”]
Output: 3
Explanation:
we can form 3 sentences, as follows:
“CatMat” = “Cat” + “Mat”
“CatMat” = “Ca” + “tM” + “at”
“CatMat” = “C” + “at” + “Mat”

Input:
“a”
[]
Output: 0

题目大意：

一个字符串s，被“字典集合”（wordDict）中的单词拼接而成的可能性种数。

解题思路：

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

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

注意事项：

1. 将两个输入都转换成小写。
2. dp[n+1]而不是dp[n]，而for循环从1开始。
3. 递归中dp[i]用+操作符。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public int wordBreak3(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	Set<String> lowerDict = new HashSet<>();
	for(String c : dict)
		lowerDict.add(c.toLowerCase());
	dict = lowerDict;
	s = s.toLowerCase();
	
	int[] dp = new int[s.length() + 1];
	dp[0] = 1;
	
	// dp[i][j] = sum(dp[i][k] * isWord(s[k,j])), i=0..n-1, j=i..n-1
	// dp[0][n-1] = sum(dp[0][k] * isWord(s[k,n-1]))
	// dp[n] = sum(dp[k] * isWord(s[k,n]))
	for(int i = 1; i <= s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k, i)) ? 1 : 0); 
		}
	}
	return dp[s.length()];
}

算法分析：

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

这道题一开始走过一些弯路，首先我觉得类似于Catalan算法，左右半部都是子问题，但其实这属于单边问题。所以写了以下算法：

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public int wordBreak3_wrong(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	// dp[i][j] = sum(dp[i][k] * dp[k][j])
	int[][] dp = new int[s.length() + 1][s.length() + 1];
	
	// use "ab" as an example
	for(int len = 1; len <= s.length(); len++) {
		for(int i = 0; i < s.length() - len + 1; i++) {
			for(int j = i + 1; j < i + len; j++) {
				//"a","b"
				dp[i][i+len] += dp[i][j] * dp[j][i+len];    		
			}
			//"ab"
			if(dict.contains(s.substring(i, i+len)))
				dp[i][i+len]++;
			
		}
	}
	return dp[0][s.length()];
}

但这个方法会有重复解，比如
“abc”, “a”,”b”,”c”
-> dp["ab"] * dp["c"] = 1
-> dp["a"] * dp["bc"] = 1
所以解重复，因为这问题是单边子问题而不是Catalan问题。
更改版本为单边子问题，一开始用dp[n]导致初始化稍复杂，其实初始化可以并入到递归式，只要用dp[n+1]即可。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public int wordBreak32(String s, Set<String> dict) {
	if(s == null || "".equals(s))
		return 0;
	
	int[] dp = new int[s.length()];
	for(int i = 0; i < s.length(); i++)
		dp[i] = dict.contains(s.substring(0, i + 1)) ? 1 : 0;

	for(int i = 0; i < s.length(); i++) {
		for(int k = 0; k < i; k++) {
			dp[i] += dp[k] * (dict.contains(s.substring(k + 1, i + 1)) ? 1 : 0); 
		}
	}
	return dp[s.length() - 1];
}