Q1: The problem of dividing oranges

Problem Description

​ There are n students in the class lined up in a row from front to back, and the grades of these students have been known, and the grade of the i-th student is ai. The head teacher wants to assess the number of oranges given by the students based on their previous grades. In order to motivate outstanding students, the following requirements need to be met when giving out oranges;

1. ​ There must be more oranges for students with good grades in neighboring students. If adjacent students have the same grades, they must be assigned an equal number.
2. ​ Each student is assigned at least one orange

​ Due to budget constraints, the homeroom teacher wanted to give out as few oranges as possible. , at least how many oranges do you need to prepare?

input format

The first line is an integer n, representing the number of students.
The next line contains n integers, the ith integer a, which represents the grade of the ith student,

output format

Output the answer, that is, how many oranges need to be prepared at least.

Input and output example

enter
5
3 4 5 4 3
output
9

Example 1 Explanation

​ The number of oranges each student gets is 1, 2, 3, 2.1, so at least 9 oranges need to be prepared

​ Data scale and conventions

​ Guarantee 1<n≤10^6,0<ai<10.

ideas

initial array list

list	3	4	5	4	3
nums	1	1	1	1	1

The first step is to fill

list	20	3	4	5	4	3	20
nums	1	1	1	1	1	1	1

while loop, when the score is higher than the student on the left, and there are no more oranges than the classmate on the left, or higher than the classmate on the right, but there are no more oranges than the classmate on the right, give him an orange and continue the loop

first round:

list	20	3	4	5	4	3	20
nums	1	1	2	1	1	1	1

second round:

list	20	3	4	5	4	3	20
nums	1	1	2	2	1	1	1

Third round:

list	20	3	4	5	4	3	20
nums	1	1	2	3	1	1	1

Fourth round:

list	20	3	4	5	4	3	20
nums	1	1	2	3	2	1	1

End of traversal, return sum(list)-2

code

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)

analyze

Time complexity O(n²), space complexity O(n)

Q2: From what day will no more trees die?

Problem Description

​ There are some trees in a garden, and each tree has been treated with insecticides and sprayed with different amounts of insecticides.

At the end of each day, a tree will die if it has higher levels of pesticides than the tree to its left.
​ You will be told the initial level of pesticides for each tree. Calculate the number of days after which no more plants will die.

example

​ p=[3,6,2,7,5]
​ On the first and second days, the 1st and 3rd trees die, and the remaining trees are p = [3,2,5]. On day 2, the 3rd tree also dies, and the remaining tree is p=[3,2].

​ Now no tree has more pesticides than the tree to its left, so the result is day 2.

enter

A one-dimensional array of integers:
N
int p[n]

output

No more trees will die from the first few days

ideas

list	3	6	2	7	5

Step 1: Fill the left max(list)+1

list	8	3	6	2	7	5

Step 2: Traverse the list to find the tree larger than the left, pay attention to update the length of the list

first round

list	8	3	2	5

second round

list	8	3	2

third round

Since no tree has been killed at this time, exit the loop, day = 2

code

l = list(map(int,input().split()))
# filling
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: Linked list interval flip

Problem Description

​ Reverse the interval between the m position and the n position of a linked list whose number of nodes is size, which requires time complexity O(n)

E.g:

​ The given linked list is 1→2→3→4→5→NULL,m=2,n=4 returns 1→4→3→2→5→NULL.

​ Data range: the length of the linked list is 0<size<1000, O<mnssize, the value of each node in the linked list meets the requirements of |val |<1000: time complexity O(n)

Example 1

enter:
{1,2,3,4,5},2,4

output:
{1,4,3,2,5}

Example 2

enter:
{5},1,1

output:
{5}

ideas

When I did it, I felt that it was a bit troublesome to compile a linked list, so I made a list flip.

code

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: Version comparison

Problem Description

The problem is relatively simple, that is, the two version numbers are relatively large.

enter:

"1.0.1","1.0.11"

output:

-1

enter:

"1.0.012","1.0.12"

output:

0

enter:

"2.1.0","1.12.1"

output:

1

ideas

Convert the input into a list of ints, write down and compare them one by one

code

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))