Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)

简介: 这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。

冒泡排序

思想
相邻的元素两两比较,较大的数下沉,较小的数冒起来,这样一趟比较下来,最大(小)值就会排列在一端。整个过程如同气泡冒起,因此被称作冒泡排序。

import random
from visual import visualizer

def maopaoSort(arr):
    return maopao(arr,len(arr)-1)

def maopao(num,n):
    for i in range(n):
        #对前一个的数据与后一个的数据进行比较
        for j in range(n):
            if num[j+1]<num[j]:
                visualizer.draw_bars(num, j, j + 1, len(num))
                num[j],num[j+1]=num[j+1],num[j]
    return num

if __name__ == '__main__':
    date = list(range(1, 101))
    random.shuffle(date)
    visualizer.t.bgcolor('black')
    maopaoSort(date)
    visualizer.t.done()

快速排序

思想
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可以对这两部分记录继续进行排序,以达到整个系列有序。
具体代码

import random
from visual import visualizer

def quicksort(nums):
    quicksorthelper(nums,0,len(nums)-1)
    return nums

def quicksorthelper(nums,startidex,rightidex):
    # 如果列表中只有一个元素或者不存在的话
    if startidex>=rightidex:return
    # 找出第一个元素为初始值
    pivotidex=startidex
    privovalue=nums[pivotidex]
    # 以第二个元素为左指针
    left=startidex+1
    # 以第最后元素为右指针
    right=rightidex
    while left<=right:
        # 如果左指针指向的元素大于初始值大于右指针的元素,则说明左指针的值应该和右指针进行替换
        if nums[left]>privovalue>nums[right]:
            visualizer.draw_bars(nums, left, right, len(nums))
            nums[left],nums[right]=nums[right],nums[left]
        # 如果左指针的元素小于等于初始值,则不需要替换,只需要将左指针往右移动一位
        if nums[left]<=privovalue:
            left+=1
        # 如果右指针的元素大于等于初始值,则不需要替换,只需要将右指针往左移动一位
        if nums[right]>=privovalue:
            right-=1
    # 调换初始指针和右指针的元素位置,完成一次快速排序
    nums[right],nums[pivotidex]=nums[pivotidex],nums[right]
    visualizer.draw_bars(nums, pivotidex, right, len(nums))
    # 每一次递归操作都需要去额外的开辟存储空间,为了尽可能降低空间复杂度
    # 需要先判断左右列表的长短,先对短的进行快速排序,在对长的进行快速排序即可。
    leftlength=right-startidex
    rightlength=rightidex-right
    if leftlength<rightlength:
        quicksorthelper(nums,startidex,right-1)
        quicksorthelper(nums,right+1,rightidex)
    else:
        quicksorthelper(nums,right+1,rightidex)
        quicksorthelper(nums,startidex,right-1)

if __name__ == '__main__':
    date = list(range(1, 101))
    random.shuffle(date)
    visualizer.t.bgcolor('black')
    quicksort(date)
    visualizer.t.done()

归并排序

思想
并指将两个或两个以上的有序数表合并成一个新的有序表
步骤

  1. 将序列中带排序数字分为若干组,每个数字分为一组
  2. 将若干个组两两合并,保证合并后的组是有序的
  3. 重复第二步操作直到只剩下一组,排序完成
import random
from visual import visualizer
def merge(nums,left,mid,right):
    new_nums=[]
    l,r=left,mid+1
    while l<=mid and r<=right:
        if nums[l]<nums[r]:
            new_nums.append(nums[l])
            visualizer.draw_bars(nums,l,r,len(nums))
            l+=1
        else:
            new_nums.append(nums[r])
            visualizer.draw_bars(nums,l,r,len(nums))
            r+=1
    while l<=mid:
        new_nums.append(nums[l])
        visualizer.draw_bars(nums, l, r, len(nums))
        l+=1
    while r<=right:
        new_nums.append(nums[r])
        visualizer.draw_bars(nums, l, r, len(nums))
        r+=1
    nums[left:right+1]=new_nums

def merge_sort(nums,left,right):
    if left<right:
        mid=(left+right)//2
        merge_sort(nums,left,mid)
        merge_sort(nums,mid+1,right)
        merge(nums,left,mid,right)
        visualizer.draw_bars(nums, -1, -1, len(nums))

def run(nums):
    l,r=0,len(nums)-1
    return merge_sort(nums,l,r)

if __name__ == '__main__':
    date=list(range(1,101))
    random.shuffle(date)
    visualizer.t.bgcolor('black')
    run(date)
    visualizer.t.done()

插入排序

思想
将给定元素分为两组,开始第一个元素分为一组,后面的元素分为一组,然后通过不断遍历后面的元素不断插入到前面合适的位置。

# 原理:将给定元素分为两组,开始第一个元素分为一组,后面的元素分为一组,然后通过不断遍历后面的元素不断插入到前面合适的位置
import random
from visual import visualizer
# 0(n^2)Time | O(1) Space
# stable
def insert_arr(a):
    for i in range(len(a)):
        j=i
        while j>0 and a[j]<a[j-1]:
            visualizer.draw_bars(a,j,j-1,len(a))
            a[j],a[j-1]=a[j-1],a[j]
            j-=1
    return a

if __name__ == '__main__':
    date=list(range(1,101))
    random.shuffle(date)
    visualizer.t.bgcolor('black')
    insert_arr(date)
    visualizer.t.done()

桶排序

思想
将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序。

import random

def Tongsort(x):
    # 找到数组的最大值和最小值
    # 方法1
    maxvalue,minvalue=x[0],x[0]
    for i in range(1,len(x)):
        if x[i]>maxvalue:
            maxvalue=x[i]
        if x[i]<minvalue:
            minvalue=x[i]
    # 方法2
    # maxvalue,minvalue=max(x),min(x)

    # 计算桶的数量
    bucketnum=(maxvalue-minvalue)//3+1
    bucket=[[]for i in range(bucketnum)]
    # 根据数值对桶进行划分
    for i in x:
        bucket[i//3].append(i)

    # 针对每一个桶使用快速排序
    for b in bucket:
        quicksorthelper(b,0,len(b)-1)
    x.clear()
    for i in bucket:
        x.extend(i)
    return x

def quicksorthelper(nums,startidex,rightidex):
    # 如果列表中只有一个元素或者不存在的话
    if startidex>=rightidex:return
    # 找出第一个元素为初始值
    pivotidex=startidex
    privovalue=nums[pivotidex]
    # 以第二个元素为左指针
    left=startidex+1
    # 以第最后元素为右指针
    right=rightidex
    while left<=right:
        # 如果左指针指向的元素大于初始值大于右指针的元素,则说明左指针的值应该和右指针进行替换
        if nums[left]>privovalue>nums[right]:
            nums[left],nums[right]=nums[right],nums[left]
        # 如果左指针的元素小于等于初始值,则不需要替换,只需要将左指针往右移动一位
        if nums[left]<=privovalue:
            left+=1
        # 如果右指针的元素大于等于初始值,则不需要替换,只需要将右指针往左移动一位
        if nums[right]>=privovalue:
            right-=1
    # 调换初始指针和右指针的元素位置,完成一次快速排序
    nums[right],nums[pivotidex]=nums[pivotidex],nums[right]
    # 每一次递归操作都需要去额外的开辟存储空间,为了尽可能降低空间复杂度
    # 需要先判断左右列表的长短,先对短的进行快速排序,在对长的进行快速排序即可。
    leftlength=right-startidex
    rightlength=rightidex-right
    if leftlength<rightlength:
        quicksorthelper(nums,startidex,right-1)
        quicksorthelper(nums,right+1,rightidex)
    else:
        quicksorthelper(nums,right+1,rightidex)
        quicksorthelper(nums,startidex,right-1)

if __name__ == '__main__':
    date=list(range(1,11))
    random.shuffle(date)
    b=Tongsort(date)
    print(b)

选择排序

思想
第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,继续放在起始位置知道未排序元素个数为0。

#基本原理:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,继续放在起始位置知道未排序元素个数为0
import random
from visual import visualizer
# 时间复杂度
# 空间复杂度
# 是否稳定

def Selectsort(a):
    # 将每一轮的最小值的索引找出来,并放入序列的起始位置
    for i in range(len(a)-1):
        # key
        start_idex=i
        for j in range(i+1,len(a)):
            # 为了找更小的值
            visualizer.draw_bars(a, i, j, len(a))
            if a[start_idex]>a[j]:
                start_idex=j
        # start_idex为我们选出来的最小值索引,i为每一轮的初始值,就进行相应替换即可
        a[start_idex],a[i]=a[i],a[start_idex]
        visualizer.draw_bars(a, i, start_idex, len(a))
    return a

if __name__ == '__main__':
    date=list(range(1,20))
    random.shuffle(date)
    visualizer.t.bgcolor('black')
    Selectsort(date)
    visualizer.t.done()

练习-基础难度

451. Sort Characters By Frequency (Medium)

桶排序的变形题。
题目描述
给定一个字符串 s ,根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案,返回其中任何一个。
输入输出样例

输入: s = "tree"
输出: "eert"
解释: 'e'出现两次,'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外,"eetr"也是一个有效的答案。

具体代码

"""
解题1:通过桶排序来做
执行用时:56 ms, 在所有 Python 提交中击败了35.11%的用户
内存消耗:28.6 MB, 在所有 Python 提交中击败了5.34%的用户
"""
def frequencySort(s):
    # 统计各元素的频率
    dic=dict()
    for i in s:
        dic[i]=dic.get(i,0)+1
    # 设置桶的数量
    buckets=[[]for _ in range(len(s)+1)]
    for  key,value in dic.items():
        buckets[value].append(key)
    res=""
    for j in range(len(s),-1,-1):
        if buckets[j]:
            if len(buckets[j])!=1:
                for k in buckets[j]:
                    res+=''.join(k*j)
            else:
                res += ''.join(buckets[j] * j)
    return res

"""
解题2:直接调用Counter进行计算
执行用时:44 ms, 在所有 Python 提交中击败了60.44%的用户
内存消耗:14.9 MB, 在所有 Python 提交中击败了76.00%的用户
"""
from collections import Counter
def frequencySort1(s):
    a=Counter(s).most_common()
    res=''
    for k,v in a:
        res+=''.join(k*v)
    return res

if __name__ == '__main__':
    s = "tree"
    a=frequencySort1(s)
    print(a)

练习-进阶难度

75. Sort Colors (Medium)

很经典的荷兰国旗问题,考察如何对三个重复且打乱的值进行排序。
题目描述
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
输入输出样例

输入:nums = [2,0,2,1,1,0]
输出:[0,0,1,1,2,2]

具体代码

"""
解题1:
执行用时: 12ms, 在所有 Python 提交中击败了94.81的用户
内存消耗: 12.8MB, 在所有 Python 提交中击败了94.34的用户
"""

def sortColors(nums):
    sum_0,sum_1=0,0
    for num in nums:
        if num==0:
            sum_0+=1
        elif num==1:
            sum_1+=1

    for i in range(len(nums)):
        if i<sum_0:
            nums[i]=0
        elif i<(sum_0+sum_1):
            nums[i]=1
        else:
            nums[i]=2
    return nums

if __name__ == '__main__':
    nums = [2, 0, 2, 1, 1, 0]
    result = sortColors(nums)
    print(result)
目录
相关文章
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第四章:和你一起你轻松刷题(Python)
这篇博客是关于LeetCode上使用Python语言解决二分查找问题的刷题笔记,涵盖了从基础到进阶难度的多个题目及其解法。
18 0
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第三章:和你一起你轻松刷题(Python)
本文是关于LeetCode算法题的刷题笔记,主要介绍了使用双指针技术解决的一系列算法问题,包括Two Sum II、Merge Sorted Array、Linked List Cycle II等,并提供了详细的题解和Python代码实现。
15 0
|
2月前
|
算法 C++ 索引
Leecode 101刷题笔记之第二章:和你一起你轻松刷题(Python)
本文是关于LeetCode 101刷题笔记的第二章,主要介绍了使用Python解决贪心算法题目的方法和实例。
11 0
|
Python
Leecode加法题目3个 每日练习 Python实现(2)
Leecode加法题目3个 每日练习 Python实现
102 0
Leecode加法题目3个 每日练习 Python实现(2)
|
人工智能 前端开发 Python
Leecode加法题目3个 每日练习 Python实现(1)
Leecode加法题目3个 每日练习 Python实现
128 0
Leecode加法题目3个 每日练习 Python实现(1)
|
17天前
|
存储 数据挖掘 开发者
Python编程入门:从零到英雄
在这篇文章中,我们将一起踏上Python编程的奇幻之旅。无论你是编程新手,还是希望拓展技能的开发者,本教程都将为你提供一条清晰的道路,引导你从基础语法走向实际应用。通过精心设计的代码示例和练习,你将学会如何用Python解决实际问题,并准备好迎接更复杂的编程挑战。让我们一起探索这个强大的语言,开启你的编程生涯吧!
|
23天前
|
机器学习/深度学习 人工智能 TensorFlow
人工智能浪潮下的自我修养:从Python编程入门到深度学习实践
【10月更文挑战第39天】本文旨在为初学者提供一条清晰的道路,从Python基础语法的掌握到深度学习领域的探索。我们将通过简明扼要的语言和实际代码示例,引导读者逐步构建起对人工智能技术的理解和应用能力。文章不仅涵盖Python编程的基础,还将深入探讨深度学习的核心概念、工具和实战技巧,帮助读者在AI的浪潮中找到自己的位置。
|
23天前
|
机器学习/深度学习 数据挖掘 Python
Python编程入门——从零开始构建你的第一个程序
【10月更文挑战第39天】本文将带你走进Python的世界,通过简单易懂的语言和实际的代码示例,让你快速掌握Python的基础语法。无论你是编程新手还是想学习新语言的老手,这篇文章都能为你提供有价值的信息。我们将从变量、数据类型、控制结构等基本概念入手,逐步过渡到函数、模块等高级特性,最后通过一个综合示例来巩固所学知识。让我们一起开启Python编程之旅吧!
|
23天前
|
存储 Python
Python编程入门:打造你的第一个程序
【10月更文挑战第39天】在数字时代的浪潮中,掌握编程技能如同掌握了一门新时代的语言。本文将引导你步入Python编程的奇妙世界,从零基础出发,一步步构建你的第一个程序。我们将探索编程的基本概念,通过简单示例理解变量、数据类型和控制结构,最终实现一个简单的猜数字游戏。这不仅是一段代码的旅程,更是逻辑思维和问题解决能力的锻炼之旅。准备好了吗?让我们开始吧!
|
10天前
|
Python
Python编程入门:从零开始的代码旅程
本文是一篇针对Python编程初学者的入门指南,将介绍Python的基本语法、数据类型、控制结构以及函数等概念。文章旨在帮助读者快速掌握Python编程的基础知识,并能够编写简单的Python程序。通过本文的学习,读者将能够理解Python代码的基本结构和逻辑,为进一步深入学习打下坚实的基础。