笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 100

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

Monotonic Array

原题地址 https://leetcode.com/contest/weekly-contest-100/problems/monotonic-array/

An array is monotonic if it is either monotone increasing or monotone decreasing.

An array A is monotone increasing if for all i <= j, A[i] <= A[j]. An array A is monotone decreasing if for all i <= j, A[i] >= A[j].

Return true if and only if the given array A is monotonic.

Example 1:

1
2
Input: [1,2,2,3]
Output: true

Example 2:

1
2
Input: [6,5,4,4]
Output: true

Example 3:

1
2
Input: [1,3,2]
Output: false

Example 4:

1
2
Input: [1,2,4,5]
Output: true

Example 5:

1
2
Input: [1,1,1]
Output: true

Note:

  1. 1 <= A.length <= 50000
  2. -100000 <= A[i] <= 100000

判断单调性,似乎没什么复杂的地方。我这里把单调增和减分为两种情况进行讨论,在遇到第一对相邻且不等的数时确定增减。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def isMonotonic(self, A):
"""
:type A: List[int]
:rtype: bool
"""
mono = 0
for i in range(1, len(A)):
if A[i] > A[i - 1]:
if mono < 0:
return False
mono = 1
elif A[i] < A[i - 1]:
if mono > 0:
return False
mono = -1
return True

Increasing Order Search Tree

原题地址 https://leetcode.com/contest/weekly-contest-100/problems/increasing-order-search-tree/

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 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
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

5
/ \
3 6
/ \ \
2 4 8
/ / \
1 7 9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

1
\
2
\
3
\
4
\
5
\
6
\
7
\
8
\
9

Note:

  1. The number of nodes in the given tree will be between 1 and 100.
  2. Each node will have a unique integer value from 0 to 1000.

中序遍历一次得到从左至右所有结点的值,再根据这个结果重新组装一个新的,只有右子树的二叉树,没办法,我们没文化的人就是这个样子。

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
# 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 increasingBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
def in_order(r):
if not r:
return []
return in_order(r.left) + [r.val] + in_order(r.right)

vals = in_order(root)
res = TreeNode(vals[0])

if len(vals) == 1:
return res

p = res
for v in vals[1:]:
p.right = TreeNode(v)
p = p.right
return res

Bitwise ORs of Subarrays

原题地址 https://leetcode.com/contest/weekly-contest-100/problems/bitwise-ors-of-subarrays/

We have an array A of non-negative integers.

For every (contiguous) subarray B = [A[i], A[i+1], ..., A[j]] (with i <= j), we take the bitwise OR of all the elements in B, obtaining a result A[i] | A[i+1] | ... | A[j].

Return the number of possible results. (Results that occur more than once are only counted once in the final answer.)

Example 1:

1
2
3
4
Input: [0]
Output: 1
Explanation:
There is only one possible result: 0.

Example 2:

1
2
3
4
5
6
Input: [1,1,2]
Output: 3
Explanation:
The possible subarrays are [1], [1], [2], [1, 1], [1, 2], [1, 1, 2].
These yield the results 1, 1, 2, 1, 3, 3.
There are 3 unique values, so the answer is 3.

Example 3:

1
2
3
4
Input: [1,2,4]
Output: 6
Explanation:
The possible results are 1, 2, 3, 4, 6, and 7.

Note:

  1. 1 <= A.length <= 50000
  2. 0 <= A[i] <= 10^9

所有A[i]参与得到的或运算结果(包括A[i]),才可能继续和A[i+1]进行或运算并计入结果。那不妨用一个hashset保留在第i轮得到的结果,在i+1轮时直接计算A[i+1]与这些值的或运算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def subarrayBitwiseORs(self, A):
"""
:type A: List[int]
:rtype: int
"""
res = set()
new_res = set()
for x in A:
new_res = {x | y for y in new_res}
new_res.add(x)
res |= new_res
return len(res)

Orderly Queue

原题地址 https://leetcode.com/contest/weekly-contest-100/problems/orderly-queue/

A string S of lowercase letters is given. Then, we may make any number of moves.

In each move, we choose one of the first K letters (starting from the left), remove it, and place it at the end of the string.

Return the lexicographically smallest string we could have after any number of moves.

Example 1:

1
2
3
4
5
Input: S = "cba", K = 1
Output: "acb"
Explanation:
In the first move, we move the 1st character ("c") to the end, obtaining the string "bac".
In the second move, we move the 1st character ("b") to the end, obtaining the final result "acb".

Example 2:

1
2
3
4
5
Input: S = "baaca", K = 3
Output: "aaabc"
Explanation:
In the first move, we move the 1st character ("b") to the end, obtaining the string "aacab".
In the second move, we move the 3rd character ("c") to the end, obtaining the final result "aaabc".

Note:

  1. 1 <= K <= S.length <= 1000
  2. S consists of lowercase letters only.

K>1时,相邻元素S[i]S[i+1]可以在调到首尾后通过两次操作交换相对位置,即有一字符串xxxx[ab]xxx可以通过如下几步改变为xxxx[ba]xxx:

  • xxxx[ab]xxx
  • [ab]xxxxxxx 不断把第一位调换到末尾
  • [a]xxxxxxx[b] 把第二位调换到末尾
  • xxxxxxx[ba] 把第一位调换到末尾
  • xxxx[ba]xxx 不断把第一位调换到末尾

即相邻元素之间可以任意调换,那么等效于字符串所有字符就可以以任意顺序打乱重排,进行一次排序即可找到最小的串。

K=1时,对于每个i考虑S[i:]+S[:i]即当S[i]作为第一个字符的情况即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def orderlyQueue(self, S, K):
"""
:type S: str
:type K: int
:rtype: str
"""
if K == 1:
return min([S[i:] + S[:i] for i in range(len(S))])
else:
S = list(S)
S.sort()
return ''.join(S)