给出题目一的试题链接如下:
这一题思路上还是比较直接的,直接按照题意检查一下对角元素和非对角元素即可。
给出python代码实现如下:
class Solution:
def checkXMatrix(self, grid: List[List[int]]) -> bool:
n = len(grid)
for i in range(n):
for j in range(n):
if i == j:
if grid[i][j] == 0:
return False
elif i + j == n-1:
if grid[i][j] == 0:
return False
else:
if grid[i][j] != 0:
return False
return True
提交代码评测得到:耗时644ms,占用内存15.1MB。
给出题目二的试题链接如下:
这一题我的思路就是一个简单的动态规划。
给出python代码实现如下:
class Solution:
def countHousePlacements(self, n: int) -> int:
MOD = 10**9 + 7
@lru_cache(None)
def dp(idx, pre):
if idx >= n:
return 1
res = 0
for i in range(4):
if i & pre == 0:
res += dp(idx+1, i)
return res % MOD
return dp(0, 0)
提交代码评测得到:耗时2850ms,占用内存473.8MB。
看了一下其他人提交的结果,发现有一个更加优雅的解法。
显然两岸的排布方式是独立的,因此,我们只需要考察一侧的可能排布方式,然后平方一下就是我们最终需要的答案。
而关于如何计算一侧的可能排布方式,其事实上恰好就是一个斐波那契数列,因此,其答案也是简单的。
摘录对应的python代码实现如下:
mod = 10**9 + 7
@lru_cache(10**5 + 1)
def fib(n):
if n <= 0:
return 1
return (fib(n - 1) + fib(n - 2)) % mod
class Solution:
def countHousePlacements(self, n: int) -> int:
return fib(n)**2 % mod
给出题目三的试题链接如下:
这一题的思路来说分两个阶段,第一阶段就是计算一个累积数组,分别即为 s 1 s_1 s1和 s 2 s_2 s2。
由此一来,我们要计算的最终答案可以表示为如下两个结果之一:
{
m
a
x
i
,
j
(
s
1
(
n
)
+
(
s
2
(
j
)
−
s
2
(
i
)
)
−
(
s
1
(
j
)
−
s
1
(
i
)
)
)
m
a
x
i
,
j
(
s
2
(
n
)
+
(
s
1
(
j
)
−
s
1
(
i
)
)
−
(
s
2
(
j
)
−
s
2
(
i
)
)
)
\left\{
改写上两式即有:
{
m
a
x
i
,
j
(
s
1
(
n
)
+
(
s
2
(
j
)
−
s
1
(
j
)
)
−
(
s
2
(
i
)
−
s
1
(
i
)
)
)
m
a
x
i
,
j
(
s
2
(
n
)
+
(
s
1
(
j
)
−
s
1
(
j
)
)
−
(
s
1
(
i
)
−
s
2
(
i
)
)
)
\left\{
因此,我们只需要维护 s 1 − s 2 s_1 - s_2 s1−s2以及 s 2 − s 1 s_2 - s_1 s2−s1的两个单调数组即可完成答案的求解。
给出python代码实现如下:
class Solution:
def maximumsSplicedArray(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
s1, s2 = [0] + list(accumulate(nums1)), [0] + list(accumulate(nums2))
res = max(s1[-1], s2[-1])
delta = [x-y for x, y in zip(s1, s2)]
s = []
for x in delta:
while s != [] and x <= s[-1]:
s.pop()
s.append(x)
res = max(res, s2[-1] + s[-1] - s[0])
delta = [x-y for x, y in zip(s2, s1)]
s = []
for x in delta:
while s != [] and x <= s[-1]:
s.pop()
s.append(x)
res = max(res, s1[-1] + s[-1] - s[0])
return res
提交代码评测得到:耗时1914ms,占用内存40.2MB。
给出题目四的试题链接如下:
这一题我放弃了,实在是没有啥很好的思路,唉……