笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 92

俗话说码如其人,我突然发现我长得丑还隐藏着巨大的优势,不用花太多时间把代码特意写的优雅,能用就行,反正别人看见我长那么丑,代码也写的那么丑就没什么好奇怪的了(比如最后一题,真的懒得想优雅的解法了,能过就行)。相反美人们写的东西就要承载更多期待了。不多说了,辛苦你们阅读我丑陋的解法了:

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

Transpose Matrix

原题地址 https://leetcode.com/contest/weekly-contest-92/problems/transpose-matrix/

Given a matrix A, return the transpose of A.

The transpose of a matrix is the matrix flipped over it’s main diagonal, switching the row and column indices of the matrix.

Example 1:

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

Example 2:

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

Note:

  1. 1 <= A.length <= 1000
  2. 1 <= A[0].length <= 1000

把每列元素重新组成行就是转置。

1
2
3
4
5
6
7
class Solution(object):
def transpose(self, A):
"""
:type A: List[List[int]]
:rtype: List[List[int]]
"""
return [[A[i][j] for i in range(len(A))] for j in range(len(A[0]))]

Smallest Subtree with all the Deepest Nodes

原题地址 https://leetcode.com/contest/weekly-contest-92/problems/smallest-subtree-with-all-the-deepest-nodes/

Given a binary tree rooted at root, the depth of each node is the shortest distance to the root.

A node is deepest if it has the largest depth possible.

Return the node with the largest depth such that it contains all the deepest nodes in it’s subtree.

Example 1:

1
2
3
Input: [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation:


1
2
3
4
5
We return the node with value 2, colored in yellow in the diagram.
The nodes colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.

Note:

  1. The number of nodes in the tree will be between 1 and 500.

这样的最小子树满足两个条件

  1. 它的左右子树的高度相同
  2. 它的高度与它父结点所表示的树只相差1

可以先遍历一次整个树算出每个子树的高度,再进行BFS找到第一个同时满足这两个条件的子树。

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 subtreeWithAllDeepest(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
height={None:0}
def depth(r):
if not r:
return 0
height[r]=1+max(depth(r.left),depth(r.right))
return height[r]

q=[root]
d=depth(root)
for r in q:
if height[r.left]==height[r.right]:
return r
if r.left and height[r.left]==height[r]-1: q.append(r.left)
if r.right and height[r.right]==height[r]-1: q.append(r.right)
return root

Prime Palindrome

原题地址 https://leetcode.com/contest/weekly-contest-92/problems/prime-palindrome/

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

1
2
Input: 6
Output: 7

Example 2:

1
2
Input: 8
Output: 11

Example 3:

1
2
Input: 13
Output: 101

Note:

  1. 1 <= N <= 10^8
  2. The answer is guaranteed to exist and be less than 2 * 10^8.

我的做法比较朴素,先找到大于等于N的第一个palindrome,检查是否是质数,如果不是则找到大于这个palindrome的下一个palindrome

找到大于等于某个n的palindrome方法如下:

  1. 对于低位(对称的右半部分),如果该位值大于对称位的值,则向前进位,该位置为0
  2. 把低位置为和对称位相等的值

注意下边界情况比如N=1时应该返回2

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
import math

class Solution(object):
def primePalindrome(self, N):
"""
:type N: int
:rtype: int
"""
def is_prime(n):
i=2
while i*i<=n:
if n%i==0: return False
i+=1
return True

def palind(n):
x=str(n)
l=len(x)
for i in range(int(l/2)):
if int(x[-1-i])>int(x[i]):
return palind(n+(10-int(x[-1-i]))*(10**i))
x=list(x)
for i in range(int(l/2)):
x[-1-i]=x[i]
return int(''.join(x))

if N==1:
return 2

t=palind(N)

while not is_prime(t):
t=palind(t+1)

return t

Shortest Path to Get All Keys

原题地址 https://leetcode.com/contest/weekly-contest-92/problems/shortest-path-to-get-all-keys/

We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", …) are keys, and ("A", "B", …) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can’t walk over a lock unless we have the corresponding key.

For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.

Return the lowest number of moves to acquire all keys. If it’s impossible, return -1.

Example 1:

1
2
Input: ["@.a.#","###.#","b.A.B"]
Output: 8

Example 2:

1
2
Input: ["@..aA","..B#.","....b"]
Output: 6

Note:

  1. 1 <= grid.length <= 30
  2. 1 <= grid[0].length <= 30
  3. grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
    The number of keys is in [1, 6]. Each key has a different letter and opens exactly one lock.

有点像Shortest Path Visiting All Nodes引入一个K位二进制数state表示K个钥匙的访问状态,因为是简单的网格图,用BFS第一次在状态state下访问到坐标(x,y)时的所经历的路径长度就是(x,y,state)的最小值,因此只要对四个方向不断进行BFS,捡到钥匙的时候更新state,遇到锁时检查state能否满足开锁条件继续遍历,第一次把状态更新到获得所有钥匙时的路径长度即为最短路径长度。当然在BFS之前需要先扫描一下整个网格找到起点位置和钥匙数量。

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
class Solution(object):
def shortestPathAllKeys(self, grid):
"""
:type grid: List[str]
:rtype: int
"""
n,m=len(grid),len(grid[0])
start=(0,0)
keys=0
visited=set()
d=[(-1,0),(1,0),(0,-1),(0,1)]

for i in range(n):
for j in range(m):
if grid[i][j]=='@':
visited.add((i,j,0))
start=(i,j)
elif 'A'<=grid[i][j]<='F':
keys+=1
complete=(1<<keys)-1
q=[(start,0,0)] #((x,y),steps,state)

for ((i,j),s,state) in q:
for (dx,dy) in d:
x,y=i+dx,j+dy
if 0<=x<n and 0<=y<m:
temp_state=state
if grid[x][y]=='#':
continue
elif 'a'<=grid[x][y]<='f':
temp_state=state|(1<<ord(grid[x][y])-ord('a'))
if temp_state==complete:
return s+1
elif 'A'<=grid[x][y]<='F':
if state & (1<<ord(grid[x][y])-ord('A')) ==0:
continue

if (x,y,temp_state) not in visited:
visited.add((x,y,temp_state))
q.append(((x,y),s+1,temp_state))
return -1