浪潮校招-算法-笔经

一.石头
题目描述：
沙滩按照线型摆放着n个大小不一的球形石头，已知第i个石头的半径为ri，且不存在两个石头有相同的半径。为了使石头的摆放更加美观，现要求摆放的石头的半径从左往右依次递增。因此，需要对一些石头进行移动，每次操作可以选择一个石头，并把它放在剩下n−1个石头在最左边或最右边。问最少需要操作多少次才能将这n个石头的半径变成升序？

输入描述
第一行一个整数n，表示石头的个数。(1 <= n <= 100000) 第二行n个整数，表示从左往右石头的半径r1，r2，...，rn。(1 <= ri <= n)，且保证不存在两个不同的石头拥有相同的半径。

输出描述
最少操作次数

样例输入
5
4 1 2 5 3
样例输出
2

通过了73%

cd = int(input())
cc = list(map(int,input().split()))

def lengthOfLIS(nums):
    ls=sorted(nums)
    stack=[]
    res=[]
    for i in ls:
        cur=nums.index(i)
        if not stack:
            stack.append(cur)
        else:
            if cur>stack[-1]:
                stack.append(cur)
            else:
                res.append(len(stack))
                stack=[cur]
    return max(res)




print(cd-lengthOfLIS(cc))

二.01交替
题目描述：
给你一个长度为n的01串。现在想让你找出最长的01交替子串（子串可以不连续）比如：1010,0101是01交替的串，1101则不是。现在你可以把某一个连续的区间进行翻转，即0变1，1变0。问修改之后的最大01交替子串的长度是多少。

输入描述
输入第一行包含一个整数n （1 <= n <= 100000) 表示01串的长度。 第二行包含一个01串。

输出描述
输出一个数表示符合题意的子串长度

样例输入
8
10000011
样例输出
5

AC

n = int(input())
arr = input()
cnt = 1
for i in range(n-1):
    if arr[i] != arr[i+1]:
        cnt += 1
if cnt < n-1:
    print(cnt+2)
else:
    print(n)