#携程0830后端笔试

1.奇变偶

def judge(x):
    cur=list(x)
    n=len(cur)
    flag=False
    for i in range(n-1):
        if cur[i] in '02468':
            cur[i],cur[n-1]=cur[n-1],cur[i]
            flag=True
            break
    if not flag:
        return -1
    else:
        cur=''.join(cur)
        return int(cur)


q = int(input())
for i in range(q):
    x = input()
    if int(x) % 2 == 0:
        print(int(x))
    else:
        res = judge(x)
        print(res)

2.给定字符串计算拼接的最大得分，'you'->score: 2, 'oo'->score:1

q=int(input())
for i in range(q):
    a,b,c=list(map(int,input().split()))
    yc=min(a,b,c)
    oc=b-yc
    if oc>=1:
        print(2*yc+oc-1)
    else:
        print(2*yc)

3.rgb三色树，求满足条件的切割边的数量

思路：并查集

class UF:
    def __init__(self,n):
        self.parent={}
        self.size={}
        self.count=0
        for i in range(1,n+1):
            self.parent[i]=i
            self.size[i]=1
            self.count+=1

    def find(self,x):
        while(x!=self.parent[x]):
            x=self.parent[x]
        return x

    #将x纳入y
    def union(self,x,y):
        rootx=self.find(x)
        rooty=self.find(y)
        if rootx==rooty:
            return
        self.parent[rootx]=rooty
        self.size[rooty]+=self.size[rootx]
        self.count-=1

    def connected(self,x,y):
        if self.find(x)==self.find(y):
            return True
        else:
            return False

if __name__=='__main__':
    # 一一列举
    # 判断去掉edges[i]后，是否满足要求
    def judge(edges, i):
        uf = UF(n)
        x, y = edges[i]
        for j in range(n - 1):
            if j != i:
                uf.union(edges[j][0], edges[j][1])
        rootx = uf.find(x)
        rooty = uf.find(y)
        if uf.size[rootx] < 3 or uf.size[rooty] < 3:
            return False
        else:
            list1=[]
            list2=[]
            for i in range(1,n+1):
                if uf.connected(i,x):
                    list1.append(nums[i-1])
                else:
                    list2.append(nums[i-1])
            for c in 'rgb':
                if c not in list1:
                    return False
                if c not in list2:
                    return False
            return True

    n = int(input())
    nums = input()

    # 去掉一条边后，两部分的结点数量都要大于2
    edges=[]
    for i in range(n - 1):
        i, j = list(map(int, input().split()))
        edges.append([i,j])

    res=0
    for i in range(n - 1):
        if judge(edges, i):
            res+=1
    print(res)

4.平滑数列

思路：修改平滑值对应的左端点或右端点，然后更新平滑值。断点位于中间时，修改端点会影响两个差值；端点位于两侧时，修改端点仅影响一个差值。

#返回平滑值及其对应原数组中的右端点
def getMax(nums):
    maxv=-1
    n=len(nums)
    for i in range(1,n):
        cur=abs(nums[i]-nums[i-1])
        if cur>maxv:
            maxv=cur
            ridx=i
    return maxv,ridx

if __name__=='__main__':
    n=int(input())
    nums=list(map(int,input().split()))
    # 平滑值为nums[idx],nums[idx-1]差的绝对值
    maxv,idx=getMax(nums)
    # 修改平滑值的前一个数或后一个数
    #修改平滑值的左端点，即nums[idx-1]
    tmp=nums[idx-1]
    if idx==1:
        nums[idx-1]=nums[idx]
    else:
        nums[idx-1]=(nums[idx-2]+nums[idx])//2
    curmv, _ = getMax(nums)
    maxv=min(maxv,curmv)
    nums[idx-1]=tmp

    # 修改平滑值的右端点,即nums[idx]
    if idx==n-1:
        nums[idx]=nums[idx-1]
    else:
        nums[idx]=(nums[idx-1]+nums[idx+1])//2
    curmv,_=getMax(nums)
    maxv=min(maxv,curmv)
    print(maxv)

#携程笔试##携程#