biweekly-contest-23

[TOC]

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def countLargestGroup(self, n: int) -> int:
# {sum: [n1, n2], }
d = {}
for i in range(1, n+1):
_sum = 0
t = i
while t:
_sum += t%10
t = int(t/10)
if _sum not in d:
d[_sum] = [i]
else:
d[_sum].append(i)
result = 0
m = 0
for i in d.values():
if len(i)==m:
result += 1
elif len(i) > m:
result = 1
m = len(i)
return result

2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def canConstruct(self, s: str, k: int) -> bool:
if len(s)<k:
return False
if len(s)==k:
return True
# 单数,双数 个数 x, y
# 前提:len(s)=x+2y>k
# 要求:x<=k
l = []
for i in s:
if i in l:
l.remove(i)
else:
l.append(i)
if len(l) <= k:
return True
return False

3

事后看一两三四五的解法,做出来的

https://www.bilibili.com/video/BV1Ae411x7fa/?p=1

LeetCode 考的是智商吧

求距离时不要用 根号,反之把半径平方即可比较,否则会很慢

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def d(self, x1, y1, x2, y2):
return (x1-x2)**2+(y1-y2)**2

def checkOverlap(self, r: int, x: int, y: int, x1: int, y1: int, x2: int, y2: int) -> bool:
# 圆心在矩形内
if x1 <= x <= x2 and y1 <= y <= y2:
return True
# 圆心到上下两边的距离
if x1 <= x <= x2 and min(abs(y1-y), abs(y2-y))<=r:
return True
# 圆心到左右两边的距离
if y1 <= y <= y2 and min(abs(x1-x), abs(x2-x))<=r:
return True
# # 圆心到四点的距离
if min(self.d(x, y, x1, y1), self.d(x, y, x1, y2), self.d(x, y, x2, y1), self.d(x, y, x2, y2)) <= r*r:
return True
return False

另一种思路:

将矩形扩大后判断圆心是否在里面,接着判断圆心到四个顶点的距离是否不大于 r

其实这就是上面解法的另一种解释

5DRCiebSaBYI8Gu

4

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def maxSatisfaction(self, satisfaction: List[int]) -> int:
# 1. sort
# 2. 找到第一个让 sum 为负数的位置, 移动中将 sum 加到 result 中
satisfaction.sort(reverse=True)
_sum = 0
result = 0
for i in satisfaction:
_sum += i
if _sum<0:
break
result += _sum
return result
# 推荐文章
  1.biweekly-contest-22
  2.面试题 01.07 旋转矩阵
  3.chrome 插件
  4.biweekly-contest-23
  5.weekly-contest-180

评论


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