笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 130

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

Binary Prefix Divisible By 5

原题地址 https://leetcode.com/contest/weekly-contest-130/problems/binary-prefix-divisible-by-5/

Given an array A of 0s and 1s, consider N_i: the i-th subarray from A[0] to A[i] interpreted as a binary number (from most-significant-bit to least-significant-bit.)

Return a list of booleans answer, where answer[i] is true if and only if N_i is divisible by 5.

Example 1:

1
2
3
4
Input: [0,1,1]
Output: [true,false,false]
Explanation:
The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10. Only the first number is divisible by 5, so answer[0] is true.

Example 2:

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

Example 3:

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

Example 4:

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

Note:

  1. 1 <= A.length <= 30000
  2. A[i] is 0 or 1

没什么好说的,一位位构造然后模5看余数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def prefixesDivBy5(self, A):
"""
:type A: List[int]
:rtype: List[bool]
"""
acc = 0
res = []

for i in A:
acc = (acc << 1) + i
res.append(acc % 5 == 0)

return res

Convert to Base -2

原题地址 https://leetcode.com/contest/weekly-contest-130/problems/convert-to-base-2/

Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).

The returned string must have no leading zeroes, unless the string is “0”.

Example 1:

1
2
3
Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2

Example 2:

1
2
3
Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

Example 3:

1
2
3
Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4

Note:

  1. 0 <= N <= 10^9

先把N转成二进制数,从低到高第i位为2^i前系数,当i为奇数时,如果保持当前系数为原来的1不变,则比与同表示法下-2进制数多了2*2^i,需要向前进一位到2^(i+1)的系数。可以在原二进制数上先留出两个前导0,然后从低位开始进行如上的进位计算,最后注意去掉多余的前导0,特别是当N=0时保留一位0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def baseNeg2(self, N):
"""
:type N: int
:rtype: str
"""
res = [0, 0] + map(int, (bin(N)[2:]))
n = len(res)
s = 0
for i in range(n):
s, res[n - 1 - i] = divmod(res[n - 1 - i] + s, 2)
if i % 2 == 1 and res[n - 1 - i]:
s = 1

while res and not res[0]:
res.pop(0)

return ''.join(map(str, res or [0]))

Next Greater Node In Linked List

原题地址 https://leetcode.com/contest/weekly-contest-130/problems/next-greater-node-in-linked-list/

We are given a linked list with head as the first node. Let’s number the nodes in the list: node_1, node_2, node_3, ... etc.

Each node may have a next larger value: for node_i, next_larger(node_i) is the node_j.val such that j > i, node_j.val > node_i.val, and j is the smallest possible choice. If such a j does not exist, the next larger value is 0.

Return an array of integers answer, where answer[i] = next_larger(node_{i+1}).

Note that in the example inputs (not outputs) below, arrays such as [2,1,5] represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.

Example 1:

1
2
Input: [2,1,5]
Output: [5,5,0]

Example 2:

1
2
Input: [2,7,4,3,5]
Output: [7,0,5,5,0]

Example 3:

1
2
Input: [1,7,5,1,9,2,5,1]
Output: [7,9,9,9,0,5,0,0]

Note:

  1. 1 <= node.val <= 10^9 for each node in the linked list.
  2. The given list has length in the range [0, 10000].

单调栈的基础问题,除了这里链表不能直接用索引寻址,所以压栈的时候需要把索引和值一起放进去,遇到大于栈顶元素的值就不断弹栈到栈顶大于当前值为止。

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
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None


class Solution(object):
def nextLargerNodes(self, head):
"""
:type head: ListNode
:rtype: List[int]
"""
res = []
stack = []
i = 0
p = head

while p:
res.append(0)
while stack and stack[-1][1] < p.val:
res[stack.pop()[0]] = p.val
stack.append((i, p.val))
p = p.next
i += 1

return res

Number of Enclaves

原题地址 https://leetcode.com/contest/weekly-contest-130/problems/number-of-enclaves/

Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)

A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.

Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.

Example 1:

1
2
3
4
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation:
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.

Example 2:

1
2
3
4
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation:
All 1s are either on the boundary or can reach the boundary.

Note:

  1. 1 <= A.length <= 500
  2. 1 <= A[i].length <= 500
  3. 0 <= A[i][j] <= 1
  4. All rows have the same size.

这题反而真的没什么好说的,从边界开始bfs找到所有可以访问的1,然后从所有的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
class Solution(object):
def numEnclaves(self, A):
"""
:type A: List[List[int]]
:rtype: int
"""
n, m = len(A), len(A[0])
seen = set()
ones = 0

def dfs(x, y):
seen.add((x, y))
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
if 0 <= x + dx < n and 0 <= y + dy < m and A[x + dx][y + dy] and (x + dx, y + dy) not in seen:
dfs(x + dx, y + dy)

for i in range(n):
for j in range(m):
if A[i][j] == 1:
ones += 1

for i in range(m):
if A[0][i] and A[0][i] not in seen:
dfs(0, i)
if A[-1][i] and A[-1][i] not in seen:
dfs(n - 1, i)

for i in range(n):
if A[i][0] and A[i][0] not in seen:
dfs(i, 0)
if A[i][-1] and A[i][-1] not in seen:
dfs(i, m - 1)

return ones - len(seen)