力扣周赛

[TOC]

一天一套周赛题计划

0916 weekly-contest-257

1995. 统计特殊四元组 - 力扣(LeetCode)

给你一个 下标从 0 开始 的整数数组 nums ,返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 :

nums[a] + nums[b] + nums[c] == nums[d] ,且
a < b < c < d

示例 1:

输入:nums = [1,2,3,6]
输出:1
解释:满足要求的唯一一个四元组是 (0, 1, 2, 3) 因为 1 + 2 + 3 == 6 。

简单的暴力+剪枝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def countQuadruplets(self, nums: List[int]) -> int:
n = len(nums)
res = 0
for di in reversed(range(n)):
d = nums[di]
for ai in range(di):
a = nums[ai]
if a+2>d: continue
for bi in range(ai+1, di):
b = nums[bi]
if a+b+1>d: continue
for ci in range(bi+1, di):
c = nums[ci]
if a+b+c > d: continue
if a+b+c==d:
res += 1
return res

1996. 游戏中弱角色的数量 - 力扣(LeetCode)

你正在参加一个多角色游戏,每个角色都有两个主要属性:攻击 和 防御 。给你一个二维整数数组 properties ,其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。

如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级,则认为该角色为 弱角色 。更正式地,如果认为角色 i 弱于 存在的另一个角色 j ,那么 attackj > attacki 且 defensej > defensei 。

返回 弱角色 的数量。

示例 1:

输入:properties = [[5,5],[6,3],[3,6]]
输出:0
解释:不存在攻击和防御都严格高于其他角色的角色。
示例 2:

输入:properties = [[2,2],[3,3]]
输出:1
解释:第一个角色是弱角色,因为第二个角色的攻击和防御严格大于该角色。
示例 3:

输入:properties = [[1,5],[10,4],[4,3]]
输出:1
解释:第三个角色是弱角色,因为第二个角色的攻击和防御严格大于该角色。

想到一个 nlog 的解法,做了很多优化

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
class Solution:
def numberOfWeakCharacters(self, nums: List[List[int]]) -> int:
n = len(nums)
nums.sort()
ms = [0] * n # ms[i] 表示从 i 位置开始往后的 nums[j][1] 的最大值
iis = [0] # 从左往右出现的第一个新 nums[x][0] 的 x( 1 1 1 2 2 3 的 iis 结果是 0 3 5, 分别是 1 2 3 第一次出现)

m = 0
for i in reversed(range(n)):
m = max(m, nums[i][1])
ms[i] = m

cur = nums[0][0]
for i in range(1, n):
if nums[i][0]!=cur:
iis.append(i)
cur = nums[i][0]

res = 0
iisi = 0 # 下一个比当前大的位置 iis[iisi]
for i in range(n):
if i==iis[iisi]:
iisi += 1
if iisi==len(iis): break
if ms[iis[iisi]] > nums[i][1]:
res += 1
print(i)
return res

但是比较慢,看其他人的解法,很奇妙,没有像我这样排序后遍历了3 遍,只遍历一遍维护一个最大值即可(从nums[x][0] 大的那边遍历,确保 m 是 0 比当前大的最大 1 值,为了避免相同 0 值位置的 1 值互相影响,0 和 1 位置的排序方向要相反)

这个更秒啊!

换种写法,又写了一遍

1
2
3
4
5
6
7
8
9
10
class Solution:
def numberOfWeakCharacters(self, nums: List[List[int]]) -> int:
n = len(nums)
nums.sort(key=lambda i: (-i[0], i[1]))
res = m = 0
for i in range(n):
if nums[i][1]<m:
res += 1
m = max(m, nums[i][1])
return res

时间也差不多,毕竟排序是主要的操作。但是代码短啊!

image-20210916134323386

3

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
```







## 0915 weekly-contest-258

### [2002. 两个回文子序列长度的最大乘积 - 力扣(LeetCode)](https://leetcode-cn.com/problems/maximum-product-of-the-length-of-two-palindromic-subsequences/)

给你一个字符串 s ,请你找到 s 中两个 不相交回文子序列 ,使得它们长度的 乘积最大 。两个子序列在原字符串中如果没有任何相同下标的字符,则它们是 不相交 的。

请你返回两个回文子序列长度可以达到的 最大乘积 。



感想:该暴力时就暴力

```python
# 思路:状态压缩遍历所有情况,用数组缓存是否是回文子串
class Solution:
def maxProduct(self, s: str) -> int:
n = len(s)
m = 2**n
def check(num):
bitCnt = 0
l, r = 0, n-1
while l <= r:
while l<=r and (1<<l & num)==0:
l += 1
while l<=r and (1<<r & num)==0:
r -= 1
# 这里还要检查是否是因为边界问题导致上面的循环退出
if l>r: break
if s[l]!=s[r]:
return False, 0
if l==r:
bitCnt += 1
else:
bitCnt += 2
l += 1
r -= 1
return True, bitCnt
nums = []
# 符合条件的子序列
for i in range(1, m):
b, bitCnt = check(i)
if b:
nums.append((i, bitCnt))
# print(nums)
res = 0
for i in range(len(nums)):
numi, bitCnti = nums[i]
for j in range(i):
numj, bitCntj = nums[j]
if (numi&numj)==0:
res = max(res, bitCnti*bitCntj)
return res

参考:

【XYFS】状压之后,我可就要暴力了!┗|`O′|┛ 嗷~~ - 两个回文子序列长度的最大乘积 - 力扣(LeetCode)

2003. 每棵子树内缺失的最小基因值 - 力扣(LeetCode)

# 推荐文章
  1.MYSQL45讲-笔记
  2.《Java业务开发常见错误100例》笔记
  3.django
  4.flutter
  5.elastic search

评论


:D 一言句子获取中...