[已解决]Python：每日一题 374

阴阳神万物主

March2615 发表于 2020-4-13 15:43
我认为是分成两块
[2,3,2,3,4] -> [2,3,2,3|4]
因为第一块[2,3,2,3]排序后是[2,2,3,3]，加上后面的[4] ...

幽幽地说：这种输入超纲了呦~

whosyourdaddy

def func374(arr):
    count = 0
    key = arr[0]
    len1 = len(arr)
    for i in range(len1):
        if key>arr[i]:
            continue
        else:
            key = arr[i]
            count += 1
    return count

March2615

阴阳神万物主 发表于 2020-4-13 17:29
幽幽地说：这种输入超纲了呦~

没事
今天看着最简单就给自己找了点事做
有重复的也想了一下

zltzlt

TJBEST 发表于 2020-4-13 14:02
先来个简单的，后面看看有没有好办法

90 ms

zltzlt

TJBEST 发表于 2020-4-13 14:08
第二个方法，用的求和公式。但是不知道速度如何？超时我想应该不会 O(n)的复杂度

80 ms

阴阳神万物主

冰河星云 发表于 2020-4-13 14:16
为什么不能用其他语言答题啊

因为这是在python区啊。

l0stparadise

1. def f374(arr):
   
2.     dp = [0]*len(arr)
   
3.     dp[0] = 1
   
4.     for i in range(1,len(arr)):
   
5.         if arr[i] < arr[i-1]:
   
6.             dp[i] = dp[i - 1]
   
7.         else:
   
8.             if arr[i] > max(arr[:i]):
   
9.                 dp[i] = dp[i - 1] + 1
   
10.             else:
    
11.                 dp[i] = dp[i - 1]
    
12.     return dp[-1]

复制代码

NAMELESSONE

1. def solve(arr):
   
2.     count, mx = 0, 0
   
3.     for i in range(len(arr)):
   
4.         if arr[i] > mx:
   
5.             mx = arr[i]
   
6.         if i == mx:
   
7.             count += 1
   
8.     return count

复制代码

lucky邪神

不知道，我理解的对不对，分块，排序，重新组合后与原数组一样

1. def func(arr):
   
2.     length=len(arr)
   
3.     num=1
   
4.     index=0
   
5.     while index<length-1:
   
6.         if arr[index]<arr[index+1]:
   
7.             num +=1
   
8.         index +=1
   
9.     return num

复制代码

zltzlt

kinkon 发表于 2020-4-13 14:16

第一个超时，第二个 117 ms

zltzlt

March2615 发表于 2020-4-13 14:56
写完啦 感觉是这几天最不费脑子的了

110 ms

zltzlt

sunrise085 发表于 2020-4-13 15:22
不带有分块的

带有分块的

输入 [0, 1] 出错

zltzlt

风魔孤行者 发表于 2020-4-13 16:34

输入以下数据超时：

testcase.zip (73.62 KB, 下载次数: 3)

2020-4-14 13:26 上传

点击文件名下载附件

zltzlt

ouyunfu 发表于 2020-4-13 16:44
挑战一行代码：

输入以下数据超时：

testcase.zip (73.62 KB, 下载次数: 0)

2020-4-14 13:26 上传

点击文件名下载附件

zltzlt

阴阳神万物主 发表于 2020-4-13 17:25
难度评级：简单
要素分析：比较
代码：

解答错误

输入：[0, 1]
输出：1
预期结果：2

zltzlt

whosyourdaddy 发表于 2020-4-13 18:30
def func374(arr):
    count = 0
    key = arr[0]

解答错误

输入：[1, 2, 0, 3]
输出：3
预期结果：2

kinkon

zltzlt 发表于 2020-4-14 13:17
第一个超时，第二个 117 ms

第一个超时了？不应该啊，貌似速度应该差不多才对

sunrise085

zltzlt 发表于 2020-4-14 13:25
输入 [0, 1] 出错

修改好了，其实也就是把0在最开始的情况给漏掉了。求大佬看看运行效率

旅途Z

已修改 Orz

1. def arr_split(array):
   
2.     length = len(array)
   
3.     index = 0
   
4.     max_num = 0
   
5.     block_num = 0
   
6.     while index < length:
   
7.         for i in range(index, length):
   
8.             if array[i] > max_num:
   
9.                 max_num = array[i]
   
10.             if max_num <= index:
    
11.                 block_num += 1
    
12.                 index += 1
    
13.                 break
    
14.             else:
    
15.                 index += 1
    
16.     return block_num

复制代码

阴阳神万物主

zltzlt 发表于 2020-4-14 13:27
解答错误

输入：[0, 1]

这个修好了。

1. def solve(arr:list,which:bool=False)->int:
   
2.     how = []
   
3.     l = len(arr)
   
4.     for i in range(1,l):
   
5.         if max(arr[(how[-1]-1 if how else 0):i])<min(arr[i:]):
   
6.             how.append(i)
   
7.     else:
   
8.         how.append(l)
   
9.     res = len(how)
   
10.     if which:
    
11.         how.insert(0,0)
    
12.         for i in range(1,res):
    
13.             print(arr[how[i-1]:how[i]],end=',')
    
14.         else:
    
15.             print(arr[how[-2]:])
    
16.     return res
    
17. if __name__ == '__main__':
    
18.     print('示例1 输出：',solve([4,3,2,1,0]))
    
19.     print('示例2 输出：',solve([1,0,2,3,4],1))
    
20.     print('之前错的：',solve([0,1],1))
    

复制代码