笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 132

https://leetcode.com/contest/weekly-contest-132

Divisor Game

原题地址 https://leetcode.com/contest/weekly-contest-132/problems/divisor-game/

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there is a number N on the chalkboard. On each player’s turn, that player makes a move consisting of:

  • Choosing any x with 0 < x < N and N % x == 0.
  • Replacing the number N on the chalkboard with N - x.

Also, if a player cannot make a move, they lose the game.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example 1:

1
2
3
Input: 2
Output: true
Explanation: Alice chooses 1, and Bob has no more moves.

Example 2:

1
2
3
Input: 3
Output: false
Explanation: Alice chooses 1, Bob chooses 1, and Alice has no more moves.

Note:

  1. 1 <= N <= 1000

当遇到N=1的时候,玩家会输,这也是所有输家最后一轮面临的唯一一种可能,否则都可以通过选择x=1进入下一轮。

N=2时,一定能够使得对手面临上面的状况,那么就赢定了……

N为偶数时,一定有一个约数是奇数,减去奇数可以使得对手面临N为奇数的情况。而N为奇数时,所有约数都为奇数,轮到对手时就只可能是偶数了。也就是轮到奇数的玩家最终会一直面临N为奇数,直至最终到N=1一定会输,反之开局为偶数就会赢。

1
2
3
4
5
6
7
class Solution(object):
def divisorGame(self, N):
"""
:type N: int
:rtype: bool
"""
return N % 2 == 0

Maximum Difference Between Node and Ancestor

原题地址 https://leetcode.com/contest/weekly-contest-132/problems/maximum-difference-between-node-and-ancestor/

Given the root of a binary tree, find the maximum value V for which there exists different nodes A and B where V = |A.val - B.val| and A is an ancestor of B.

(A node A is an ancestor of B if either: any child of A is equal to B, or any child of A is an ancestor of B.)

Example 1:

1
2
3
4
5
6
7
8
9
Input: [8,3,10,1,6,null,14,null,null,4,7,13]
Output: 7
Explanation:
We have various ancestor-node differences, some of which are given below :
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Among all possible differences, the maximum value of 7 is obtained by |8 - 1| = 7.

Note:

  1. The number of nodes in the tree is between 2 and 5000.
  2. Each node will have value between 0 and 100000.

从根结点进行一次后序遍历,post_dfs返回整个树的最大值,最小值,和题中要求的有直系关系最大差值。post_dfs的具体过程为:一个结点的值val需要分别与左右子树的最值作绝对差,再与左右子树本身包含的最大绝对差比较,然后更新为以该结点为根的整个树的最大绝对差,相似的,再把这些最值与val本身比较得到整个树的最值。

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution(object):
def maxAncestorDiff(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def post_dfs(r):
if not r:
return 100001, -1, 0
l_min, l_max, l_abs_diff = post_dfs(r.left)
r_min, r_max, r_abs_diff = post_dfs(r.right)
min_v, max_v = min(l_min, r_min), max(l_max, r_max)
temp = max(l_abs_diff, r_abs_diff)
if min_v < 100001:
temp = max(temp, abs(r.val - min_v))
if max_v > -1:
temp = max(temp, abs(r.val - max_v))
return min(min_v, r.val), max(max_v, r.val), temp

_, _, res = post_dfs(root)
return res

Longest Arithmetic Sequence

原题地址 https://leetcode.com/contest/weekly-contest-132/problems/longest-arithmetic-sequence/

Given an array A of integers, return the length of the longest arithmetic subsequence in A.

Recall that a subsequence of A is a list A[i_1], A[i_2], ..., A[i_k] with 0 <= i_1 < i_2 < ... < i_k <= A.length - 1, and that a sequence B is arithmetic if B[i+1] - B[i] are all the same value (for 0 <= i < B.length - 1).

Example 1:

1
2
3
4
Input: [3,6,9,12]
Output: 4
Explanation:
The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

1
2
3
4
Input: [9,4,7,2,10]
Output: 3
Explanation:
The longest arithmetic subsequence is [4,7,10].

Example 3:

1
2
3
4
Input: [20,1,15,3,10,5,8]
Output: 4
Explanation:
The longest arithmetic subsequence is [20,15,10,5].

Note:

  1. 2 <= A.length <= 2000
  2. 0 <= A[i] <= 10000

找相对顺序不变的等差数列,还是先考虑动态规划。用dp[i][diff]表示到第i个元素为止,公差为diff的序列至多有多长。二层循环顺序遍历每一对(i,j)来更新序列长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
def longestArithSeqLength(self, A):
"""
:type A: List[int]
:rtype: int
"""
res = 1
dp = collections.defaultdict(dict)
n = len(A)

for i in range(n - 1):
for j in range(i + 1, n):
diff = A[j] - A[i]
if diff in dp[i]:
temp = dp[i][diff] + 1
else:
temp = 2
dp[j][diff] = max(dp[j].get(diff, 1), temp)
res = max(res, temp)
return res

Recover a Tree From Preorder Traversal

原题地址 https://leetcode.com/contest/weekly-contest-132/problems/recover-a-tree-from-preorder-traversal/

We run a preorder depth first search on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. (If the depth of a node is D, the depth of its immediate child is D+1. The depth of the root node is 0.)

If a node has only one child, that child is guaranteed to be the left child.

Given the output S of this traversal, recover the tree and return its root.

Example 1:

1
2
Input: "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

Example 2:

1
2
Input: "1-2--3---4-5--6---7"
Output: [1,2,5,3,null,6,null,4,null,7]

Example 3:

1
2
Input: "1-401--349---90--88"
Output: [1,401,null,349,88,90]

Note:

  1. The number of nodes in the original tree is between 1 and 1000.
  2. Each node will have a value between 1 and 10^9.

第一个数字为根结点的值。找到深度为1也就是只有一个-开始引导的子串,把这些(最多2个)子串的深度都减去1,即把所有数字之间的-都去掉一个,然后对子串递归构造成树,作为根结点的子结点。思想很简单,麻烦的字符串操作,不多说了,直接看代码。

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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None


class Solution(object):
def recoverFromPreorder(self, S):
"""
:type S: str
:rtype: TreeNode
"""
if not S:
return None
n = len(S)
start = [i for i in range(1, n) if S[i] == '-' and S[i - 1] != '-']
end = [i for i in range(n - 1) if S[i] == '-' and S[i + 1] != '-']
if not start:
return TreeNode(int(S))
root = TreeNode(int(S[:start[0]]))
children = [start[i] for i in range(len(start)) if start[i] == end[i]]
S = list(S)
for i in start:
S[i] = ''
if len(children) == 1:
l = ''.join(S[children[0]:])
r = ''
else:
l = ''.join(S[children[0]:children[1]])
r = ''.join(S[children[1]:])
root.left = self.recoverFromPreorder(l)
root.right = self.recoverFromPreorder(r)
return root