KK's blog

每天积累多一些

0%

Posted on Edited on 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. 初始值为[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

算法分析：

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

Posted on Edited on 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 105*s` consists only of printable ASCII characters.

题目大意：

求含非字母数字的字符串是否回文，字符串含空格，冒号等. 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:

**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.

题目大意：

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

解题思路：

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

注意事项：

  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)。

Posted on Edited on Disqus:

LeetCode



You are given a 0-indexed 2D integer array questions where questions[i] = [points<sub>i</sub>, brainpower<sub>i</sub>].

The array describes the questions of an exam, where you have to process the questions in order (i.e., starting from question 0) and make a decision whether to solve or skip each question. Solving question i will earn you points<sub>i</sub> points but you will be unable to solve each of the next brainpower<sub>i</sub> questions. If you skip question i, you get to make the decision on the next question.

For example, given questions = [[3, 2], [4, 3], [4, 4], [2, 5]]: If question 0 is solved, you will earn 3 points but you will be unable to solve questions 1 and 2.
If instead, question 0 is skipped and question 1 is solved, you will earn 4 points but you will be unable to solve questions 2 and 3.

Return the maximum points you can earn for the exam.

Example 1:

Input: questions = [[3,2],[4,3],[4,4],[2,5]]
Output: 5
Explanation: The maximum points can be earned by solving questions 0 and 3.
- Solve question 0: Earn 3 points, will be unable to solve the next 2 questions
- Unable to solve questions 1 and 2
- Solve question 3: Earn 2 points
Total points earned: 3 + 2 = 5. There is no other way to earn 5 or more points.


Example 2:

Input: questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: 7
Explanation: The maximum points can be earned by solving questions 1 and 4.
- Skip question 0
- Solve question 1: Earn 2 points, will be unable to solve the next 2 questions
- Unable to solve questions 2 and 3
- Solve question 4: Earn 5 points
Total points earned: 2 + 5 = 7. There is no other way to earn 7 or more points.


Constraints: 1 <= questions.length <= 10<sup>5</sup>
questions[i].length == 2 1 <= points<sub>i</sub>, brainpower<sub>i</sub> <= 10<sup>5</sup>

题目大意：

(points, brainpower)解决一个问题得到points分，但是接下来的brainpower个问题都不能回答。求最大分数

一维DP解题思路(推荐)：

类似于LeetCode 198 House Robber，但此不再是固定的相邻不能偷，而是动态多个不能偷。
这题求最值，且数组有序访问，暴力法是多项式复杂度，所以考虑用DP。详见解法二。考虑优化算法二
首先考虑用累计dp，但是即使这样，由于前n-1个问题每个不能回答的范围都不同，并不能容易由第n-1个累计DP获得dp[n]
巧妙地利用从后往前计算，这样dp值不能回答范围包含在了已经计算的dp值中，如计算dp[3] <- dp[i + questions[3][1] + 1] + questions[3][0], 后者最大的话，当前结果也是最大，符合归纳条件。

解题步骤：

N/A

注意事项：

  1. 如哈雷彗星，限制条件是向后，所以从后往前计算
  2. 用累计DP： F[i] = max(F[i + 1], f)

Python代码：

1
2
3
4
5
6
7
8
def mostPoints(self, questions: List[List[int]]) -> int:
	dp = [0] * (len(questions) + 1)
	for i in range(len(dp) - 2, -1, -1):
		next_val = 0
		if i + questions[i][1] + 1 < len(dp):
			next_val = dp[i + questions[i][1] + 1]
		dp[i] = max(dp[i + 1], questions[i][0] + next_val)
	return dp[0]

算法分析：

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

二维DP算法II解题思路：

一开始我的思路是比较直接，此算法TLE。 dp[i]为以回答了第i个问题及之前的问题所得分数。递归式为： 

1
dp[i] = max(dp[j] + questions[i][0]) if j + questions[j][1] < i, 0 <= j < i

Python代码：

1
2
3
4
5
6
7
8
def mostPoints2(self, questions: List[List[int]]) -> int:
	dp = [0] * len(questions)
	for i in range(len(dp)):
		dp[i] = questions[i][0]
		for j in range(i):
			if j + questions[j][1] < i:
				dp[i] = max(dp[i], dp[j] + questions[i][0])
	return max(dp)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
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)

Free mock interview