Python：每日一题 374
今天的题目：数组 arr 包含 0 ~ len(arr) - 1 间的所有整数（不重复）。
将这个数组分割成几个 “块”，并将这些块分别进行排序。
之后再连接起来，使得连接的结果和按升序排序后的原数组相同。
求最多能将数组分成多少块。
示例 1：
输入：arr =
输出：1
解释：将数组分成 2 块或者更多块，都无法得到所需的结果。例如，分成 , 的结果是 ，这不是有序数组。
示例 2：
输入：arr =
输出：4
解释：可以把它分成两块，例如 , 。然而，分成 , , , 块数是最多的。
{:10_298:}欢迎大家一起答题！{:10_298:} 本帖最后由 TJBEST 于 2020-4-13 16:50 编辑
先来个简单的，后面看看有没有好办法
def fun374(arr):
M = len(arr)
result = 0
hasBeenIn = 0
while hasBeenIn < M:
tempMax = arr
rest = tempMax + 1 - hasBeenIn
for num in arr:
if num <= tempMax:
rest -= 1
else:
rest = rest + (num - tempMax) - 1
tempMax = num
if rest == 0:
break
result += 1
hasBeenIn = tempMax + 1
return result 本帖最后由 TJBEST 于 2020-4-13 15:30 编辑
第二个方法，用的求和公式。但是不知道速度如何？超时我想应该不会 O(n)的复杂度
def fun374(arr):
def inner(num):
return num*(num+1)//2
result = 0
index = 0
total = 0
for num in arr:
total += num
if total == inner(index):
result += 1
index += 1
return result 占楼 TJBEST 发表于 2020-4-13 14:08
@zltzlt 题有问题 分成【4】【3】【2】【1】【0】不可以吗？
我觉得此题改为最少可能更 ...
分成,,,,之后，连起来是，并没有按降序排列 为什么不能用其他语言答题啊{:10_266:} 本帖最后由 kinkon 于 2020-4-13 16:13 编辑
def f374(arr):
cout = 1
for i in range(1, len(arr)):
m, n = max(arr[:i]), min(arr)
if m < n:
cout = cout + 1
return cout
def f374(arr):
cout, num = 0, arr
for i, val in enumerate(arr):
if val > num:
num = val
if num == i:
cout = cout + 1
return cout 永恒的蓝色梦想 发表于 2020-4-13 14:14
分成,,,,之后，连起来是，并没有按降序排列
好的，没看全题 冰河星云 发表于 2020-4-13 14:16
为什么不能用其他语言答题啊
你可以去力扣答 本帖最后由 kinkon 于 2020-4-13 14:44 编辑
例2感觉也有个问题，为什么要分成 , 得4块，不分成, 得5块
看错了，必须要升序啊
如果碰到【2,3,2,3,4】是不是算 0？ kinkon 发表于 2020-4-13 14:32
例2感觉也有个问题，为什么要分成 , 得4块，不分成, 得5块
看错了，必 ...
数组 arr 包含 0 ~ len(arr) - 1 间的所有整数（不重复）应该是不重复的 TJBEST 发表于 2020-4-13 14:48
数组 arr 包含 0 ~ len(arr) - 1 间的所有整数（不重复）应该是不重复的
对对，没认真审题啊，谢谢 本帖最后由 March2615 于 2020-4-13 14:58 编辑
写完啦 感觉是这几天最不费脑子的了
def daily374(arr: list) -> int:
# 解题思路
# 大小为i的数应该在arr处
# -> 遍历arr，如果index处max(arr[:index+1])是index则可以将前面分块
# -> ->
# -> ->
max_value = ans = 0
for index, value in enumerate(arr):
max_value = max(max_value, value)
if max_value == index:
ans += 1
return ans
顺便思考了一下如果有重复的情况（稍微复杂了一点，但有了思路就很好写了）
# 如果arr可以重复呢
def daily374_1(arr: list) -> int:
# 解题思路
# arr > arr时需要排序 -> 遍历arr，记录下最大值
# 如 -> -> 分成三块
# 有个问题： -> -> -> wrong
# 解决方法：
# 左边的最大值一定小于右边的最小值，找到符合的进行分段后继续对右边操作
# -> ->
copy_arr = arr[:]
ans = i =0
while i < len(copy_arr)-1:
i += 1
left, right = max(copy_arr[:i]), min(copy_arr)
if left <= right:
ans += 1
copy_arr = copy_arr
i = 0
return ans + 1# +1是最后一块
不过感觉效率不会太高，while应该可以优化的 本帖最后由 sunrise085 于 2020-4-14 13:55 编辑
不带有分块的
def fun374(list1):
l=len(list1)-1
result=1
t=list1.index(0)
while t<l:
if t!=0:
if max(list1[:t])>t:
return 0
result+=1
t=list1.index(t+1)
return result
list1=
print(fun374(list1))
带有分块的
def fun374(list1):
list2=[]
l=len(list1)-1
result=1
t=list1.index(0)
m=0
while t<l:
if t!=0:
if max(list1[:t])>t:
return 0
result+=1
list2.append(list1)
m=t+1
t=list1.index(t+1)
list2.append(list1)
print(list2)
return result
list1=
print(fun374(list1)) kinkon 发表于 2020-4-13 14:32
例2感觉也有个问题，为什么要分成 , 得4块，不分成, 得5块
看错了，必 ...
我认为是分成两块
->
因为第一块排序后是，加上后面的是符合题意的 March2615 发表于 2020-4-13 15:43
我认为是分成两块
->
因为第一块排序后是，加上后面的 ...
嗯嗯，总感觉理解题意比做题还难啊 def f(arr):
n = 0
count = len(arr)
brr = list(range(len(arr)))
while n<len(arr):
if brr != arr:
for a in range(n+1,len(arr)):
if sorted(arr) == brr:
count = count-(a-n)
n = a
break
n += 1
return count 挑战一行代码：
def f374(arr):
return )==i*(i-1)/2 for i in range(1,len(arr))].count(1)+1 kinkon 发表于 2020-4-13 14:32
例2感觉也有个问题，为什么要分成 , 得4块，不分成, 得5块
看错了，必 ...
不可能分成 0 块 难度评级：简单
要素分析：比较
代码：
def solve(arr:list,which:bool=False)->int:
how = []
l = len(arr)
for i in range(1,l-1):
if max(arr[(how[-1]-1 if how else 0):i])<min(arr):
how.append(i+1)
else:
how.append(l)
res = len(how)
if which:
how.insert(0,0)
for i in range(1,res):
print(arr:how],end=',')
else:
print(arr:])
return res
if __name__ == '__main__':
print('示例1 输出：',solve())
print('示例2 输出：',solve(,1))