KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       
       1
      / \
     2   3

Return 6.

题目大意：

给定一棵二叉树，寻找最大路径和。路径指的是从任意起始节点出发沿着父亲-孩子链接到达某个终止节点的节点序列。路径不一定要穿过根节点。

DFS解题思路(推荐)：

DFS搜索，二叉树的题。步骤主要是考虑

  1. 空指针
  2. 一个node情况或多个node情况（可合并）
    多个node情况下（比如3个节点），有4种情况下含根节点的和：左子树+根节点，右子树+跟节点，根节点，左子树+根节点+右子树。这些情况包含了所有可能的和的情况。但值得注意的是，前三种
    情况可以是子问题的解，也就是它返回值将成为此根节点父亲的左或右子树的解，但第四种情况例外，因为此情况形成的路径与根节点父亲并不在一条路径上。所以此情况应在全局变量中比较
    并不能作为返回值。
    gmax = max {return max{val,left+val,right+val} or left+val+right}

注意事项：

  1. 4种情况: root， root + left, root + right, left + root + right, 不要漏掉最后一种left_sum + root.val + right_sum
  2. 全局最大值作为返回值，初始值为负无穷float(‘-inf’)。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def maxPathSum(self, root: TreeNode) -> int:
	_, path_gsum = self.dfs(root)
	return path_gsum

def dfs(self, root: TreeNode) -> int:
	if not root:
       return float('-inf'), float('-inf')
	left_sum, left_gsum = self.dfs(root.left)
	right_sum, right_gsum = self.dfs(root.right)
	max_path_sum = max(left_sum + root.val, right_sum + root.val, root.val)
	max_path_gsum = max(max_path_sum, left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

算法II迭代解题思路：

由上述算法看出，属于后序遍历，因为先left, right, 再计算root。所以用后序遍历模板。然后定义dp[root]为以root为结束点的最大路径值，这与上题也一样。
递归式为

1
dp[node] = max(dp[node.left] + node.val, dp[node.right] + node.val, node.val)

res为全局最大值，也和上述一致
max_path_sum = dp[node]
res = left_gsum, right_gsum

注意事项：

  1. occurrence先加再比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def maxPathSum2(self, root: TreeNode) -> int:
	it, stack, res = root, [], float('-inf')
	dp = collections.defaultdict(int)
	while it:
		stack.append((it, 0))
		it = it.left

	while stack:
		node, occurrence = stack.pop()
		occurrence += 1 # remember
		if occurrence == 2:
			dp[node] = max(dp[node.left] + node.val, dp[node.right] + node.val, node.val)
			res = max(res, dp[node], dp[node.left] + node.val + dp[node.right])
			continue
		else:
			stack.append((node, occurrence))
		if node.right:
			n = node.right
			while n:
				stack.append((n, 0))
				n = n.left
	return res

Follow-up

若path的起始点均为叶子节点

解题思路：

叶子节点要返回值，gsum为无穷小。修改max_path_sum和max_path_gsum公式，不含单独root以及gsum不含以root为终点的路径。
还有路径可能不存在

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxPathSum_fromleaf2leaf(self, root: TreeNode) -> int:
	path_sum, path_gsum = self.dfs_leaf(root)
	return path_gsum if path_gsum != float('-inf') else None

def dfs_leaf(self, root: TreeNode) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_leaf(root.left)
	right_sum, right_gsum = self.dfs_leaf(root.right)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

Follow-up 2

若path的起始点均为叶子节点且只能从某些特定的叶子节点出发和结束

解题思路：

同上，只不过加入条件root.val in endnodes

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxPathSum_fromSpecificNodes(self, root: TreeNode, endnodes) -> int:
	path_sum, path_gsum = self.dfs_end_nodes(root, set(endnodes))
	return path_gsum if path_gsum != float('-inf') else None

def dfs_end_nodes(self, root: TreeNode, endnodes) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right and root.val in endnodes:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_end_nodes(root.left, endnodes)
	right_sum, right_gsum = self.dfs_end_nodes(root.right, endnodes)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

Follow-up 3

若path的起始点可为任意节点且只能从某些特定的叶子节点出发和结束

解题思路：

若起始节点为非叶子节点，注意将表达式修改为原始表达式。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxPathSum_fromSpecificNodes2(self, root: TreeNode, endnodes) -> int:
	path_sum, path_gsum = self.dfs_end_nodes2(root, set(endnodes))
	return path_gsum if path_gsum != float('-inf') else None

def dfs_end_nodes2(self, root: TreeNode, endnodes) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right and root.val in endnodes:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_end_nodes2(root.left, endnodes)
	right_sum, right_gsum = self.dfs_end_nodes2(root.right, endnodes)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	if root.val in endnodes:
		max_path_sum = max(max_path_sum, root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	if root.val in endnodes:
		max_path_gsum = max(max_path_gsum, max_path_sum)
	return max_path_sum, max_path_gsum

注意事项：

  1. 4种情况
  2. 定义全局变量来比较最大值，因为左到右情况不能返回。全局变量初始值为负无穷。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int gsum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root){
	gsum = 0;
	int a = max(root);
	return gsum;
}
public int max(TreeNode root){
	if(root==null)
		return 0;
	int lmax = max(root.left);
	int rmax = max(root.right);
	int sum = Math.max(Math.max(lmax, rmax)+root.val,root.val);
	gsum = Math.max(Math.max(gsum, sum), lmax+root.val+rmax);
	return sum;
}

算法分析：

两种方法时间复杂度为O(n)，n为节点数。空间复杂度为O(h)，h为二叉树高度。

相关题目：

LeetCode 112 Path Sum
LeetCode 124 Binary Tree Maximum Path Sum

Posted on Edited on Disqus:

Input - (“mon 10:00 am”, mon 11:00 am)
Output - [11005, 11010, 11015…11100]
Output starts with 1 if the day is monday, 2 if tuesday and so on till 7 for sunday
Append 5 min interval times to that till the end time
So here it is 10:05 as first case, so its written as 11005
2nd is 10:10 so its written as 11010

题目大意：

DD的面经题，给定开始时间和结束时间，求5分钟的间隔时间，注意要round to 5min

解题思路：

由于非10进制，所以开一个类来计算进制

解题步骤：

N/A

注意事项：

  1. 实现lt函数
  2. 12am, 12pm要mod 12
  3. (0 if parts[2] == ‘am’ else 12)加括号
  4. 开始时间到到5分钟端点，结束时间加1分钟，由于只实现了lt

Python代码：

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
DAY_DICT = {'mon': 1, 'tue': 2, 'wed': 3, 'thu': 4, 'fri': 5, 'sat': 6, 'sun': 7}
class Solution(TestCases):

    def get_intervals(self, start, end) -> List:
        start_time = Time(start)
        end_time = Time(end)
        if start_time.min % 5 > 0:
            start_time.add(5 - start_time.min % 5)
        end_time.add(1)
        res = []
        while start_time < end_time:
            res.append(start_time.get_numeric())
            start_time.add(5)
        return res


class Time:

    def __init__(self, time):
        parts = time.split(' ')
        day = DAY_DICT[parts[0]]
        time_parts = parts[1].split(':')
        hour = int(time_parts[0]) % 12 + (0 if parts[2] == 'am' else 12) # remember paren (0 ...12), and % 12
        self.day = day
        self.hour = hour
        self.min = int(time_parts[1])

    def __lt__(self, other):
        if self.day < other.day or (self.day == other.day and self.hour < other.hour) or \
                (self.day == other.day and self.hour == other.hour and self.min < other.min):
            return True
        else:
            return False

    def get_numeric(self):
        return self.day * 10000 + self.hour * 100 + self.min

    def add(self, mins):
        self.min += mins
        if self.min == 60:
            self.min = 0
            self.hour += 1
        if self.hour == 24:
            self.hour = 0
            self.day += 1
        if self.day == 7:
            self.day = 0

算法分析：

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

Posted on Edited on Disqus:

[
[“3234.html”, “xys.html”, “7hsaa.html”], // user1
[“3234.html”, “sdhsfjdsh.html”, “xys.html”, “7hsaa.html”] // user2
]

输出两个user的最长连续且相同的访问记录。

题目大意：

求连续最长子数组

解题思路：

类似于LeetCode 1143先求最长公共子字符串。

LeetCode 1143 Longest Common Subsequence, 求最长公共子字符串
Karat 002 Longest Common Continuous Subarray 一样的题目，结果类型不同：最长长度和结果

不同之处在于：

  1. 由于是连续，所以递归只有相同的情况，其他情况为0。
  2. 答案不是最后一位，而是全局最值

递归式为

1
2
dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
         = 0

解题步骤：

N/A

注意事项：

  1. 递归只有一种情况
  2. 答案需求全局

Python代码：

1
2
3
4
5
6
7
8
9
10
11
# dp[i][j] = dp[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1]
#          = 0
def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(len(text1) + 1)]
	res = 0
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				res = max(res, dp[i][j])
	return res

优化空间：

1
2
3
4
5
6
7
8
9
def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(2)]
	res = 0
	for i in range(1, len(text1) + 1):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
				res = max(res, dp[i % 2][j])
	return res

回到原题，输入是列表而不是字符串，但原理一样。还有需要输出公共结果，而不是数字

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def longestCommonContinuousSubarray(self, history1, history2):
	dp = [[0 for _ in range(len(history2) + 1)] for _ in range(len(history1) + 1)]
	max_len, res = 0, []
	for i in range(1, len(dp)):
		for j in range(1, len(dp[0])):
			if history1[i - 1] == history2[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
				if dp[i][j] > max_len:
					max_len = dp[i][j]
					res = history1[i - dp[i][j]:i]
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.



You may assume the two numbers do not contain any leading zero, except the number 0 itself.



 


Example 1:



Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.


Example 2:



Input: l1 = [0], l2 = [0]
Output: [0]


Example 3:



Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]


 


Constraints:




  • The number of nodes in each linked list is in the range [1, 100].

  • 0 <= Node.val <= 9

  • It is guaranteed that the list represents a number that does not have leading zeros.


题目大意：

数位链表(从最低位到最高位)相加

算法思路：

类似于merge sort

注意事项：

  1. 其中一个可能较长，所以主循环出来后还要继续循环较长的链表，类似于merge sort
  2. 所有链表遍历完后，carry可能还会是1，要加一个if语句特别处理

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
	fake_head = ListNode(0)
	carry = 0
	it, it2, it_res = l1, l2, fake_head
	while it or it2:
		value = carry
		if it:
			value += it.val
			it = it.next
		if it2:
			value += it2.val
			it2 = it2.next
		carry = 1 if value >= 10 else 0
		value %= 10
		it_res.next = ListNode(value)
		it_res = it_res.next
	if carry == 1:
		it_res.next = ListNode(1)
	return fake_head.next

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

Input: s = “1 + 1”
Output: 2


Example 2:

Input: s = “ 2-1 + 2 “
Output: 3


Example 3:

Input: s = “(1+(4+5+2)-3)+(6+8)”
Output: 23


Constraints:

`1 <= s.length <= 3 105*sconsists of digits,‘+’,‘-‘,‘(‘,‘)’, and‘ ‘. *srepresents a valid expression. *‘+’is **not** used as a unary operation (i.e.,“+1”and“+(2 + 3)”is invalid). *‘-‘could be used as a unary operation (i.e.,“-1”and“-(2 + 3)”` is valid).
There will be no two consecutive operators in the input. Every number and running calculation will fit in a signed 32-bit integer.

题目大意：

实现字符串加减，但有括号。

算法思路：

括号题优先考虑用Stack。这里Stack不能只存数，因为括号前可以是正负，所以将这个信息以+1或-1也压入栈（栈不能混合字符和数字）
所以用一个stack，num是一个数，res是括号内的累积结果。num在处理完每一个数都要重设，res和sign在处理完每个括号都要重设。

运用模板，代码中含五种情况：空格，运算符，数字，左右括号。左括号将res和sign入栈，右括号将res和sign出栈，计算结果存在res

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

注意事项：

  1. 括号前可以是正负，所以将这个信息以+1或-1也压入栈
  2. 左括号无论前面是正负都要入栈
  3. num在处理完每一个数都要重设，res和sign在处理完每个括号都要重设

Python代码：

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
29
30
31
32
33
# 1-(2+3)+(4+5)
# 1+2+3
def calculate(self, s: str) -> int:
	res, num, stack, sign = 0, 0, [], 1
	s += '+'
	for char in s:
		if char == ' ':
			continue
		if char.isdigit():
			num = num * 10 + int(char)
		if char == '+':
			res += sign * num
			sign = 1
			num = 0
		if char == '-':
			res += sign * num
			sign = -1
			num = 0
		if char == '(':
			stack.append(res) # [-4+]
			stack.append(sign) #
			sign = 1
			res = 0
		if char == ')':
			res += sign * num # 9
			prev_sign = stack.pop() # +
			tmp = stack.pop() # -4
			res = tmp + prev_sign * res # -4 +9
			# sign = 1 next one will be +-, so num = 0 and sign doesn't matter
			num = 0
		# else:
		 #   res += char
	return res

算法分析：

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

Free mock interview