Q1:分橘子问题

问题描述

​ 班级里有n名同学从前到后排成一排，且已经得知了这些同学的成绩，其中第i名同学的成绩是ai。班主任想根据同学们上个阶段的绩来评定发橙子的数量。为了激励成绩优秀同学，发橙子时需要满足如下要求;

1. ​ 相邻同学中成绩好的同学的橙子必须更多。若相邻的同学成绩一样,则它们分到的数量必须平等。
2. ​ 每个同学至少分配一个橙子

​ 由于预算有限，班主任希望在符合要求的情况下发出尽可能少的橙子。,至少需要准备多少橙子呢?

输入格式

第一行是一个整数n,表示学生数量。 接下来一行有n个整数,第i个整数a,表示第i个同学的成绩,

输出格式

输出答案,也就是需要最少准备多少个橙子。

输入输出样例

输入 5 3 4 5 4 3 输出 9

样例1解释

​ 每位同学拿到的橙子的数量分别是1,2,3,2.1,所以至少需要准备9个

​ 数据规模与约定

​ 保证1<n≤10^6,0<ai<10。

思路

初始数组list

第一步先进行填充

while循环，==当比左边的同学分数高，并且橙子没有比左边同学多，或者比右边同学高，但橙子没有比右边同学多==的情况，给他分一个橙子，继续循环

第一轮：

第二轮：

第三轮：

第四轮：

遍历结束，返回sum(list)-2

代码

n = int(input())
l = list(map(int,input().split()))
l.insert(0,20)
l.insert(n+1,20)
nums = [1 for _ in range(n+2)]
index = 1
while index <= n:
    if (l[index] > l[index-1] and nums[index]<=nums[index-1]) or (l[index]>l[index+1]and nums[index]<=nums[index+1]):
        nums[index] += 1
        index = 1
    index += 1
print(sum(nums)-2)

分析

时间复杂度O(n²)，空间复杂度O(n)

Q2:从第几天开始不会再有树死亡?

问题描述

​ 在一个花园中有一些树，每棵树都经过了杀虫处理，分别被喷洒了不同数量的杀虫剂。

​ 当每天结束时，如果某棵树的杀虫剂含量比它左边的树的高，那么它会死去。 ​ 你会被告知每棵树的杀虫剂的初始含量。计算在第几天之后不再会有植物死去。

例子

​ p=[3,6,2,7,5] ​ 在第一天和第二天,第1和第3颗树死亡,剩下的树为p = [3,2,5]。在第2天，第3颗树也死亡,剩下的树为p=[3,2]。

​ 现在没有树比它左边的树的杀虫剂含量高了,所以结果为第2天。

输入

一个整型一维数组: N int p[n]

输出

从第几天开始不会再有树死亡

思路

第一步：填充左侧max(list)+1

第二步：遍历列表，寻找大于左侧的树，注意要更新list的长度

第一轮

第二轮

第三轮

由于此时并没有树被杀死，退出循环，day = 2

代码

l = list(map(int,input().split()))
# 填充
l.insert(0,max(l)+1)
l.insert(len(l),max(l)+1)
day = 1
while True:
    index = 1
    n = len(l)-2
    sign = False
    while index <= n:
        if l[index]>l[index-1]:
            sign = True
            l.pop(index)
            n = len(l)-2
        index += 1
    if not sign:
        break
    day += 1
print(day-1)

Q3:链表区间翻转

问题描述

​ 将一个节点数为size链表m位置到n位置之间的区间反转，要求时间复杂度O(n)

例如:

​ 给出的链表为1→2→3→4→5→NULL,m=2,n=4返回1→4→3→2→5→NULL.

​ 数据范围：链表长度0<size<1000,O<mnssize,链表中每个节点的值满足|val |<1000要求:时间复杂度O(n)

示例1

输入: {1,2,3,4,5},2,4

输出: {1,4,3,2,5}

示例2

输入: {5},1,1

输出: {5}

思路

做的时候感觉编链表麻烦了点，取巧做了个列表翻转。

代码

s = input()
s = s.replace("{","")
s = s.replace("}","")
l = s.split(",")
start = int(l[len(l)-2])-1
end = int(l[len(l)-1])-1
for i in range(start, (start + end - 1) // 2 + 1):
    tmp = l[i]
    l[i] = l[start + end - i]
    l[start + end - i] = tmp

print("{",end='')
print(l[0],end='')
for ss in l[1:len(l)-2]:
    print(",",end='')
    print(ss,end='')
print("}")

Q4:版本比较

问题描述

​ 问题比较简单，就是两个版本号比较大小。

输入：

"1.0.1","1.0.11"

输出：

-1

输入：

"1.0.012","1.0.12"

输出：

0

输入：

"2.1.0","1.12.1"

输出：

1

思路

对输入进行转化后变成一个int的list，记下来逐一比较即可

代码

def fun(l1,l2):
    min_len = min(len(l1),len(l2))
    for i in range(min_len):
        if int(l1[i]) > int(l2[i]):
            return 1
        elif int(l1[i]) < int(l2[i]):
            return -1
    if len(l1) > len(l2):
        return 1
    elif len(l1) < len(l2):
        return -1
    else:
        return 0

s1,s2 = input().split(",")
s1 = s1[1:-1]
s2 = s2[1:-1]
l1 = s1.split(".")
l2 = s2.split(".")


print(fun(l1,l2))