开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 手把手带你刷Leetcode力扣学习总结 -> 正文阅读

[数据结构与算法]手把手带你刷Leetcode力扣学习总结

1. 总体规划

在这里插入图片描述

2. 算法复杂度

2.1 时间复杂度

什么是时间复杂度？
算法的执行效率
算法的执行时间与算法的输入值之间的关系
常见时间复杂度案例分析

O(1):与num无关

O(n)

O(log n):2的n次方等于num。典型：二分查找

O(m+n)：循环并列，相加

O(nlogn):循环嵌套，相乘。典型：排序

O( $n^2$ )
常见时间复杂度对比

2.2 空间复杂度

什么是空间复杂度？
算法的存储空间与算法的输入值之间的关系
占空间的都是声明出来的变量
常见空间复杂度案例分析

变量是常量：O(1)

变量是array、list等，递归：O(n)
常见空间复杂度对比

时间和空间只能二选一
面试时：和面试官讲清楚
工作时：时间>空间

3. 数据结构

3.1 数组【Array】

数组：在连续的内存空间中，存储一组相同类型的元素。
在这里插入图片描述

特点： 适合读，不适合写------读多写少

3.1.1 Python常用操作

创建数组
添加或插入元素

中间添加,插入：O(n)
尾部添加，添加：O(1)
访问元素
更新元素
删除元素

remove:查找所需要的元素，然后删除，O(n)
pop(i):删除i索引的值，但剩余元素需要移位，O(n)
pop():删除最后一个，O(1)
获取数组长度
遍历数组
查找某个元素
数组排序

a.sort()，会直接改变a
sorted(a)，不会改变

3.1.2 Java常用操作

3.1.3 练习题

485 最大连续1的个数
在这里插入图片描述

283 移动零
在这里插入图片描述

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        for i in nums:
            if i==0:
                nums.remove(0)
                nums.append(0)
                
        return nums

27 移除元素
在这里插入图片描述

class Solution:
    def removeElement(self, nums, val):
        if nums is None or len(nums)==0:
            return 0
        l,r = 0, len(nums)-1
        while l<r:
            while(l<r and nums[l] != val):
                l=l+1
            while(l<r and nums[r] == val):
                r=r-1
            nums[l],nums[r] = nums[r],nums[l]
        return l if nums[l]==val else l+1

class Solution:
    def removeElement(self, nums, val):
        for i in range(len(nums)-1,-1,-1):
        if nums[i] == val:
        nums.remove(nums[i])

3.2 链表【Linked List】

在这里插入图片描述
单端链表 √
双端链表 leetcode一般不用

特点： 适合写，不适合读------读少写多

3.2.1 Python常用操作

创建链表
添加元素
访问元素
搜索元素：返回索引
更新元素
删除元素
长度

3.2.2 Java常用操作

3.2.3 练习题

203 移除链表元素
在这里插入图片描述

在这里插入图片描述

class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        while head is not None:
            if head.val == val:
                prev.next = head.next
                head = head.next
            else:
                prev = head
                head = head.next 
        return dummy.next

206 反转链表
在这里插入图片描述

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        while head is not None and head.next is not None:
            dnext = dummy.next
            hnext = head.next
            dummy.next = hnext
            head.next = hnext.next
            hnext.next = dnext

        return dummy.next

3.3 队列【Queue】

在这里插入图片描述

插入删除只能在头尾，所以时间复杂度：O(1)

3.3.1 Python常用操作

创建队列
添加元素
获取即将出队的元素
删除即将出队的元素
判断队列是否为空
队列长度
len(queue)
遍历队列

3.3.2 Java常用操作

3.3.3 练习题

933 最近的请求次数
在这里插入图片描述

class RecentCounter:

    def __init__(self):
        self.q = deque()
    def ping(self, t: int) -> int:
        self.q.append(t)
        while len(self.q)>0 and t-self.q[0]>3000:
            self.q.popleft()
        return len(self.q)

3.4 栈【Stack】

在这里插入图片描述

3.4.1 Python常用操作

创建栈
添加元素
查看栈顶元素-即将出栈的元素
删除栈顶元素
栈的大小
栈是否为空
栈的遍历

3.4.2 Java常用操作

3.4.3 练习题

20 有效的括号
在这里插入图片描述

在这里插入图片描述

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s)==0:
            return True
        stack= []
        for c in s:
            if c == "(" or c == "[" or c == "{":
                stack.append(c)
            else:
                if len(stack) == 0:
                    return False
                else:
                    temp = stack.pop()
                    if c == ")":
                        if temp != "(":
                            return False
                    elif c == "]":
                        if temp != "[":
                            return False 
                    elif c == "}":
                        if temp != "{":
                            return False   

        return True if len(stack) == 0 else False

496 下一个更大元素（栈+队列）
加粗样式
在这里插入图片描述

class Solution:
	def nextGreaterElement(self，nums1: List[int]，nums2: List[int]) -> List[int]:
		res =[]
		stack = []
		for num in nums2:
			stack.append( num)
		for num in nums1:
			temp =[]
			isFound = False
			nextMax = -1
			while ( len(stack) != 0 and not isFound ) :
				top = stack.pop()
				if top > num:
					nextMax = top
				elif top ==num :
					isFound = True
				temp.append( top)
			res.append( nextMax)
			while len(temp) != 0:
				stack.append(temp. pop( ))
		return res