首页 > 顺丰8.29 算法 python 2AC
头像
jett201903252126953
编辑于 2020-08-29 17:00
+ 关注

顺丰8.29 算法 python 2AC

提前批面试体验太查,选择题就瞎做做,20分钟

第一题用python没有大数问题,贼简单,不用写字符串加法和除法,3分钟

import sys

line = sys.stdin.readline().strip()
values = list(map(int,line.split()))

n,m = values

line = sys.stdin.readline().strip()
a = list(map(int,line.split()))

tmp = n

for i in range(m):
    tmp += a[i]
    tmp = tmp//2

print(tmp)

第二题 用了些标志位,能够写出来,但是不简洁,复杂度为O(N),贪心算法

import sys

while True:
    line = sys.stdin.readline().strip()
    if not line:
        break
    n = list(map(int, line.split()))
    n = n[0]

    line = sys.stdin.readline().strip()
    a = list(map(int, line.split()))

    dp = [1] * n

    pre_num_flag = 0 if a[0] == -1 else 1
    pre_num = a[0]
    pre_d_flag = 0
    pre_d = 0
    mid_ne_one = 1

    for i in range(1,n):
        if not pre_num_flag:
            if a[i] == -1:
                dp[i] = dp[i-1]
            else:
                pre_num_flag = 1
                pre_num = a[i]
                dp[i] = dp[i-1]
        elif pre_num_flag:
            if a[i] == -1:
                mid_ne_one += 1
                dp[i] = dp[i-1]
            else:
                if not pre_d_flag:
                    if (a[i] - pre_num) % mid_ne_one == 0:
                        pre_d = (a[i] - pre_num) // mid_ne_one
                        pre_d_flag = 1
                        pre_num = a[i]
                        mid_ne_one = 1
                        dp[i] = dp[i-1]
                    else:
                        pre_num_flag = 1
                        pre_num = a[i]
                        pre_d_flag = 0
                        mid_ne_one = 1
                        dp[i] = dp[i-1] + 1
                elif pre_d_flag:
                    if (a[i] - pre_num) % mid_ne_one == 0 and pre_d == (a[i] - pre_num) // mid_ne_one:
                        pre_num = a[i]
                        mid_ne_one = 1
                        dp[i] = dp[i-1]
                    else:
                        pre_d_flag = 0
                        pre_num_flag = 1
                        pre_num = a[i]
                        mid_ne_one = 1
                        dp[i] = dp[i-1] + 1
    print(dp[-1])




全部评论

(5) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐