笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 115

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

Check Completeness of a Binary Tree

原题地址 https://leetcode.com/contest/weekly-contest-115/problems/check-completeness-of-a-binary-tree/

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes inclusive at the last level h.

Example 1:

1
2
3
Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

1
2
3
Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note:

  1. The tree will have between 1 and 100 nodes.

BFS把二叉树写成数组形式(就是input的那种形式),检查中间是否含有null即可:

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

class Solution:
def isCompleteTree(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
q = [root]
complete = False

for i in q:
if not i:
complete = True
else:
if complete:
return False
q.append(i.left)
q.append(i.right)

return True

Prison Cells After N Days

原题地址 https://leetcode.com/contest/weekly-contest-115/problems/prison-cells-after-n-days/

There are 8 prison cells in a row, and each cell is either occupied or vacant.

Each day, whether the cell is occupied or vacant changes according to the following rules:

If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can’t have two adjacent neighbors.)

We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0.

Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation:
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]

Example 2:

1
2
Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]

Note:

  1. cells.length == 8
  2. cells[i] is in {0, 1}
  3. 1 <= N <= 10^9

i位的取值取决于i-1位和i+1位是否相同,而首位和末尾除了第0天都会是0。

cells的变化以14天为一个周期,所以只需要看它对应这14天中的哪一天就可以了。当模14结果为0时对应第14天,其他则对应相应的模14余数。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def prisonAfterNDays(self, cells, N):
"""
:type cells: List[int]
:type N: int
:rtype: List[int]
"""
for n in range((N - 1) % 14 + 1):
temp = [0] * 8
for i in range(1, 7):
temp[i] = 1 ^ cells[i - 1] ^ cells[i + 1]
cells = temp
return cells

Regions Cut By Slashes

原题地址 https://leetcode.com/contest/weekly-contest-115/problems/regions-cut-by-slashes/

In a N x N grid composed of 1 x 1 squares, each 1 x 1 square consists of a /, \, or blank space. These characters divide the square into contiguous regions.

(Note that backslash characters are escaped, so a \ is represented as "\\".)

Return the number of regions.

Example 1:

1
2
3
4
5
6
7
Input:
[
" /",
"/ "
]
Output: 2
Explanation: The 2x2 grid is as follows:

Example 2:

1
2
3
4
5
6
7
Input:
[
" /",
" "
]
Output: 1
Explanation: The 2x2 grid is as follows:

Example 3:

1
2
3
4
5
6
7
8
Input:
[
"\\/",
"/\\"
]
Output: 4
Explanation: (Recall that because \ characters are escaped, "\\/" refers to \/, and "/\\" refers to /\.)
The 2x2 grid is as follows:

Example 4:

1
2
3
4
5
6
7
8
Input:
[
"/\\",
"\\/"
]
Output: 5
Explanation: (Recall that because \ characters are escaped, "/\\" refers to /\, and "\\/" refers to \/.)
The 2x2 grid is as follows:

Example 5:

1
2
3
4
5
6
7
Input:
[
"//",
"/ "
]
Output: 3
Explanation: The 2x2 grid is as follows:

Note:

  1. 1 <= grid.length == grid[0].length <= 30
  2. grid[i][j] is either '/', '\', or ' '.

把每个格子划分成顶部,左边,底部,右边四个部分,如

除了第一行的格子,其他格子的顶部都与上面邻接的格子的底部相通;除了最左边的格子,其他格子的左边部分都与左边邻接的格子的右边部分相通;如果这个格子里面没有/,那么左边和底部不会分开,右边和顶部也不会分开;如果这个格子里面没有\,那么左边和顶部不会分开,右边和底部也不会分开。

因此可以按照这个思路都这些小块进行union find,找到最后一共可以合并为多少块区域:

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
class Solution(object):
def regionsBySlashes(self, grid):
"""
:type grid: List[str]
:rtype: int
"""
parent = {}

def find(x):
if x not in parent:
parent[x] = x
y = x
while parent[y] != y:
y = parent[y]
parent[x] = y
return y

def union(x, y):
parent[find(y)] = find(x)

n = len(grid)
# 0:top 1:left 2:bottom 3:right
for i in range(n):
for j in range(n):
if i > 0:
union((i, j, 0), (i - 1, j, 2))
if j > 0:
union((i, j, 1), (i, j - 1, 3))
if grid[i][j] != '/':
union((i, j, 2), (i, j, 1))
union((i, j, 0), (i, j, 3))
if grid[i][j] != '\\':
union((i, j, 2), (i, j, 3))
union((i, j, 0), (i, j, 1))

return len(set(map(find, parent.keys())))

Delete Columns to Make Sorted III

原题地址 https://leetcode.com/contest/weekly-contest-115/problems/delete-columns-to-make-sorted-iii/

We are given an array A of N lowercase letter strings, all of the same length.

Now, we may choose any set of deletion indices, and for each string, we delete all the characters in those indices.

For example, if we have an array A = ["babca","bbazb"] and deletion indices {0, 1, 4}, then the final array after deletions is ["bc","az"].

Suppose we chose a set of deletion indices D such that after deletions, the final array has every element (row) in lexicographic order.

For clarity, A[0] is in lexicographic order (ie. A[0][0] <= A[0][1] <= ... <= A[0][A[0].length - 1]), A[1] is in lexicographic order (ie. A[1][0] <= A[1][1] <= ... <= A[1][A[1].length - 1]), and so on.

Return the minimum possible value of D.length.

Example 1:

1
2
3
4
5
Input: ["babca","bbazb"]
Output: 3
Explanation: After deleting columns 0, 1, and 4, the final array is A = ["bc", "az"].
Both these rows are individually in lexicographic order (ie. A[0][0] <= A[0][1] and A[1][0] <= A[1][1]).
Note that A[0] > A[1] - the array A isn't necessarily in lexicographic order.

Example 2:

1
2
3
Input: ["edcba"]
Output: 4
Explanation: If we delete less than 4 columns, the only row won't be lexicographically sorted.

Example 3:

1
2
3
Input: ["ghi","def","abc"]
Output: 0
Explanation: All rows are already lexicographically sorted.

Note:

  1. 1 <= A.length <= 100
  2. 1 <= A[i].length <= 100

这题实际上反而比前面的题的简单一些。如果给一个数组,让你找最少删除几列可以得到一个递增序列的数组,那么用动态规划找递增序列是很容易的事,对于任意下标i>j如果满足第i个元素大于第j个元素,那么以i位置结尾最长递增子序列长度可以更新为dp[i]=max(dp[i],dp[j]+1),找到最长递增子序列的长度以后,用数组长度减去这个长度就是需要删掉的列的数量。

这题稍微特殊在判断递增必须满足每行的元素都需要满足在行内递增,也就是需要检查是否每行元素都满足第i行的元素大于第j行的元素,那么需要找的是共同最长递增子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def minDeletionSize(self, A):
"""
:type A: List[str]
:rtype: int
"""
n = len(A[0])
dp = [1] * n
for i in range(1, n):
for j in range(i):
if all(s[j] <= s[i] for s in A):
dp[i] = max(dp[i], dp[j] + 1)
return n - max(dp)