Python：每日一题 371
本帖最后由 zltzlt 于 2020-4-8 21:54 编辑今天的题目：
一个整数区间 ( a < b ) 代表着从 a 到 b 的所有连续整数（包括 a 和 b）。
给定一组整数区间 intervals，找出一个最小的集合 S，使得 S 里的元素与区间 intervals 中的每一个整数区间都至少有 2 个元素相交。
返回这个最小集合 S 的大小。
说明：S 不一定是连续整数。
示例 1：
输入：intervals = [, , , ]
输出：3
解释：最小的集合是 {2, 3, 4}。
示例 2：
输入：intervals = [, , , ]
输出：5
解释：最小的集合是 {1, 2, 3, 4, 5}。
{:10_298:}欢迎大家一起答题！{:10_298:} def f(i):
min1 = i
max1 = i
for each in i:
if each>min1:
min1 = each
if each<max1:
max1 = each
if max1-min1>=1:
return 2
else:
return min1-max1+3 本帖最后由 TJBEST 于 2020-4-9 17:00 编辑
不知道写的对不对，没有严格的证明。试了几个例子是对的
def fun371(intervals):
def inner(eachSeg):
result = 0
index = 0
M = len(eachSeg)
Tail = 0
while index < M - 1:
state = False
for innerindex in range(index+1,M):
if eachSeg > eachSeg:
state = True
else:
break
else:
innerindex += 1
if state == True:
result += 2
else:
result += 2 - Tail
if innerindex == M:
break
else:
if eachSeg == eachSeg:
Tail = 1
else:
Tail = 0
index = innerindex
else:
result += 2 - Tail
return result
sortedArr = sorted(intervals)
#第一次保留子集
M = len(sortedArr)
for index in range(M-1,0,-1):
if sortedArr == sortedArr:
del sortedArr
#第二次保留子集，并分组
Seg = []
temp = []
for each in sortedArr:
if temp != []:
N = len(temp)
for index in range(N-1,-1,-1):
if each <= temp:
del temp
else:
break
if temp == [] or each <= temp[-1]:
temp.append(each)
else:
Seg.append(temp)
temp =
else:
temp.append(each)
else:
Seg.append(temp)
#计算每一个分组的值进行叠加
result = 0
for each in Seg:
result += inner(each)
return result 例1的区间是1-5吗？返回1-3好像是最小的啊？ 本帖最后由 ouyunfu 于 2020-4-9 00:19 编辑
def f371(intervals:list)->int:
l=len(intervals)
m,n=max( for i in range(l)]),min( for i in range(l)])
return 2 if n-m>=1 else m-n+3 @zltzlt intervals 是否排好序了？ 前排 TJBEST 发表于 2020-4-8 21:23
@zltzlt intervals 是否排好序了？
不一定 本帖最后由 zltzlt 于 2020-4-9 13:19 编辑
def func371(intervals):
count = 0
newlist = sorted(intervals,key = lambda s:s)
result = [(newlist-1),newlist]
for i in range(1,len(newlist)):
for j in result:
if j <=newlist and j>=newlist:
count += 1
temp = j
if count == 2:
break
if count == 0:
result.append((newlist-1))
result.append(newlist)
if count == 1:
if temp !=newlist:
result.append(newlist)
else:
result.append(newlist-1)
count = 0
return len(result) 观摩大佬解答 {:10_245:}
def find(list1):
items = list1[:]
dic = dict()
for i in list1:
for j in range(i,i + 1):
dic.setdefault(str(j),0)
dic += 1
sort = sorted(dic,key = dic.__getitem__)
setlist =
while items:
setlist.append(sort.pop())
list1 = items[:]
for each in list1:
num = 0
eachlist = ,each + 1)]
for vol in setlist:
if vol in eachlist:
num += 1
if num == 2:
items.remove(each)
break
return len(setlist) 本帖最后由 旅途Z 于 2020-4-9 13:20 编辑
import numpy as np
import operator
def get_subset(intervals):
intervals = np.array(intervals)
interval_num = intervals.shape
left_bound = min(intervals[:, 0])
right_bound = max(intervals[:, 1])
element_dict = {}
num_dict = {}
length_list = []
return_list = []
for i in range(interval_num):
length_list.append(intervals-intervals+1)
for i in range(left_bound, right_bound+1):
for j in range(interval_num):
if intervals <= i <= intervals:
if i not in element_dict:
element_dict = []
num_dict = 0
element_dict.append(j)
num_dict += 1
sorted_element = sorted(num_dict.items(), key=operator.itemgetter(1), reverse=False)
for i in range(len(sorted_element)):
for each in element_dict]:
if length_list == 2:
return_list.append(sorted_element)
break
else:
for each in element_dict]:
length_list -= 1
return len(return_list)
本帖最后由 阴阳神万物主 于 2020-4-9 17:23 编辑
难度评级：简单
要素分析：数论
随机输入生成器，送给有需要的人：
import random
def gent(a:'区间下限'=1,b:'区间上限'=10,l:'列表长度上限'=4,n:'生成数量'=10):
for i in range(n):
yield [[(l := random.randint(a,b-1)),random.randint(l+1,b)]for j in range(0,l+1)]
解题代码：
def solve(intervals:list,how:'是否打印最小集合'=False):
sets = ,i+1))for i in intervals]
u = set()
while sets:
n = []
l = len(sets)
flg = *l
for a in range(l-1):
for b in range(a+1,l):
c = sets.intersection(sets)
if len(c)>=2:
if c not in n:n.append(c)
flg,flg = False,False
if flg:n.append(sets)
if flg[-1]:n.append(sets[-1])
if n == sets:
for each in sets:
u = u.union({each.pop(),each.pop()})
break
sets = n
if how:print(u)
return len(u)
if __name__ == '__main__':
print('示例1 输出：',solve([, , , ]))
print('示例2 输出：',solve([, , , ]))
def a371(intervals):
left = []
right = []
for i in intervals:
left.append(i)
right.append(i)
max1 = max(left)
min1 = min(right)
if max1 > min1:
print(max1 - min1 + 3)
elif max1 == min1:
print('3')
else:
print('2')
a371([, , , ])
a371([, , , ]) def f371(intervals):
a=[]
b=[]
for i in intervals:a.append(max(i))
m=min(a)
for i in intervals:b.append(min(i))
n=max(b)
print(n-m+3)
风魔孤行者 发表于 2020-4-8 20:29
解答错误
输入：[, , , , , , , , , ]
输出：7
预期结果：5 TJBEST 发表于 2020-4-8 20:43
不知道写的对不对，没有严格的证明。试了几个例子是对的
解答错误
输入：[, , , , , , , , , ]
输出：6
预期结果：5 kinkon 发表于 2020-4-8 20:48
例1的区间是1-5吗？返回1-3好像是最小的啊？
例 1 ？ ouyunfu 发表于 2020-4-8 21:06
解答错误
输入：[, , , , , , , , , ]
输出：7
预期结果：5 whosyourdaddy 发表于 2020-4-8 23:14
1480 ms
页:
[1]
2