[Обмен лицами] Вопросы по программированию на стороне Али

алгоритм
[Обмен лицами] Вопросы по программированию на стороне Али

Первый вопрос-----------------------------------------------------

Дан неупорядоченный массив положительных целых чисел, найти медиану

[мысль] Первый метод заключается в использовании идеи быстрой сортировки, а второй — в использовании кучи. Поместите код быстрой сортировки:

class solution():
    def partition(self,nums,left,right):
        key=nums[left]
        while left<right:
            while left<right and nums[right]>=key:
                right-=1
            nums[left]=nums[right]
            while left<right and nums[left]<=key:
                left+=1
            nums[right]=nums[left]
        nums[left]=key
        return left
    def func(self,nums):
        start = 0
        end= len(nums) - 1
        mid=(start+end)//2
        ind=self.partition(nums,start,end)
        while ind!=mid:
            if ind<mid:
                ind=self.partition(nums,ind+1,end)
            else:
                ind = self.partition(nums, start,ind-1)
        return nums[ind]

nums=[2,3,1,5,7,6,4]
print(solution().func(nums))

Это классический тип вопроса, подробности по ссылке:blog.CSDN.net/О, какое пальто_789/…

вопрос 2-----------------------------------------------------

Учитывая неупорядоченный массив положительных целых чисел, найдите самую длинную подпоследовательность (последовательную), которая делает нечетные и четные числа одинаковыми.

【Думаю:】

【Код】

python代码：
arr=[1,1,-1,1,1,-1,-1]
arr2=[1,-1,1,-1,1,-1,1,-1]
def func(arr):
    dp=[0 for _ in range(len(arr))]
    dp[0]=arr[0]
    max_len=0
    dic_={dp[0]:0}
    left=0
    right=0
    for i in range(1,len(arr)):
        dp[i]=dp[i-1]+arr[i]
        if dp[i] not in dic_.keys():
            dic_[dp[i]]=i
        if max_len<i-dic_[dp[i]]:
            max_len=max(max_len,i-dic_[dp[i]])
            left=dic_[dp[i]]
            right=i
    if dp[-1]==0:
        return arr
    return arr[left + 1:right + 1]
print(func(arr2))

Это вариант этого вопроса, вы можете обратиться к:Блог woohoo.cn на.com/coding-WTF/…

Категории