代码编织梦想

前言

  • 阴天睡得还挺舒服,9点半才醒,用刷题开启美好新一天!

141. 环形链表 - 力扣(LeetCode)

  • 哈希表

    • set存走过的节点,走到重复的就有环
    • class Solution:
          def hasCycle(self, head: Optional[ListNode]) -> bool:
              seen = set()  # 哈希集合
              # seen = {}  # 哈希字典
              cur = head
              while cur:
                  if cur in seen:  # 有重复的节点则有环
                      return True
                  seen.add(cur)  # 直接存节点
                  # seen[cur] = True  # 将节点作为键,值设为True
                  cur = cur.next
              return False
  • 快慢指针

    • 快指针追上慢指针就有环
    • class Solution:
          def hasCycle(self, head: Optional[ListNode]) -> bool:
              slow = fast = head  # 乌龟和兔子同时从起点出发
              while fast and fast.next:
                  slow = slow.next  # 乌龟走一步
                  fast = fast.next.next  # 兔子走两步
                  if fast == slow:  # 兔子追上乌龟(套圈),说明有环
                      return True
              return False  # 访问到了链表末尾,无环

142. 环形链表 II - 力扣(LeetCode)

  • 快慢指针

    • 快慢指针追到相同,再从终点出发和slow一起走到相同即为入环处
    • class Solution:
          def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
              fast = slow = head
              while fast and fast.next:
                  fast = fast.next.next
                  slow = slow.next
                  if slow == fast:  # 快慢指针相遇,s走了nb,f走了2nb
                      fast = head  # 入口处需要a+nb,s已经走了nb
                      while fast != slow:  # 同时走a就可到达入口
                          fast = fast.next
                          slow = slow.next
                      return fast
              return None

21. 合并两个有序链表 - 力扣(LeetCode)

  • 迭代法

    • 用虚拟头结点prehead,用precur向下遍历,最后再接上剩下的
    • class Solution:
          def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
              prehead = ListNode(-1)
              precur = prehead
              while list1 and list2:
                  if list1.val <= list2.val:  # 把较小值接到precur后面
                      precur.next = list1
                      list1 = list1.next
                  else:
                      precur.next = list2
                      list2 = list2.next
                  precur = precur.next  # 记得让precur前进
              # 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
              precur.next = list1 if list1 else list2
              return prehead.next
  • 递归法

    • class Solution:
          def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
              if list1 is None:
                  return list2
              if list2 is None:
                  return list1
              if list1.val < list2.val:
                  list1.next = self.mergeTwoLists(list1.next, list2)
                  return list1
              else:
                  list2.next = self.mergeTwoLists(list2.next, list1)
                  return list2

 2. 两数相加 - 力扣(LeetCode)

  • 模拟——转数字

    • class Solution:
          def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
              # 链表转化为数字
              def getNum(head):
                  num = 0
                  flag = 1
                  while head != None:
                      num += head.val * flag
                      head = head.next
                      flag *= 10
                  return num
              # 计算和    
              twoSum = getNum(l1) + getNum(l2)
              # 和为0直接返回0节点
              if twoSum == 0:
                  return ListNode(0)
              # 循环生成新链表
              head = cur = ListNode(-1)
              while twoSum != 0:
                  cur.next = ListNode(twoSum % 10)
                  cur = cur.next
                  twoSum //= 10  # 整除
              return head.next
  • 模拟——进位

    • 用s作为进位,有l1或l2或s不为0循环,s计算相加,接节点,更新s和l1l2
    • class Solution:
          def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
              # 创建一个结点值为 None 的头结点, dummy 和 p 指向头结点, dummy 用来最后返回, p 用来遍历
              dummy = p = ListNode(None)          
              s = 0               # 初始化进位 s 为 0
              while l1 or l2 or s:
                  # 如果 l1 或 l2 存在, 则取l1的值 + l2的值 + s(s初始为0, 如果下面有进位1, 下次加上)
                  s += (l1.val if l1 else 0) + (l2.val if l2 else 0)  
                  p.next = ListNode(s % 10)       # p.next 指向新链表, 用来创建一个新的链表
                  p = p.next                      # p 向后遍历
                  s //= 10                        # 有进位情况则取模, eg. s = 18, 18 // 10 = 1
                  l1 = l1.next if l1 else None    # 如果l1存在, 则向后遍历, 否则为 None
                  l2 = l2.next if l2 else None    # 如果l2存在, 则向后遍历, 否则为 None
              return dummy.next   # 返回 dummy 的下一个节点, 因为 dummy 指向的是空的头结点, 下一个节点才是新建链表的后序节点
  • 递归——进位

    • class Solution:
          def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
              def dfs(l, r, i):
                  # 终止条件:都为空节点且进位为0
                  if not l and not r and not i: return None
                  s = (l.val if l else 0) + (r.val if r else 0) + i
                  node = ListNode(s % 10)  # 当前节点
                  node.next = dfs(l.next if l else None, r.next if r else None, s // 10) # 接上递归链表
                  return node
              return dfs(l1, l2, 0)

19. 删除链表的倒数第 N 个结点 - 力扣(LeetCode)

  • 双指针

    • class Solution:
          def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
              dummy = ListNode(0, head)  # 直接创建虚拟头节点
              fast = slow = dummy  # 双指针
              # 快指针先走
              while n != 0:
                  fast = fast.next
                  n -= 1
              # 双指针一起走直到fast到底
              while fast.next != None:
                  fast = fast.next
                  slow = slow.next
              # 删除节点
              slow.next = slow.next.next
              return dummy.next

 24. 两两交换链表中的节点 - 力扣(LeetCode)

  • 模拟 ​​​​​

    • 一开始cur指向dummy比较方便,循环一次后cur还是指向前一个
    • class Solution:
          def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
              dummy = ListNode(0, head)
              cur = dummy
              while cur.next and cur.next.next:
                  pre = cur
                  cur = cur.next
                  temp = cur.next.next
                  pre.next = cur.next  # 步骤1
                  pre.next.next = cur  # 步骤2
                  cur.next = temp      # 步骤3
              return dummy.next
  • 递归

    • 前两个结点互换再接后面递归,0/1个结点结束递归
    • class Solution:
          def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
              # 终止条件:如果剩0/1个节点,无法交换,直接返回
              if not head or not head.next:
                  return head
              # 交换头两个结点
              newhead = head.next
              head.next = self.swapPairs(newhead.next)  # 接上后面交换好的结果
              newhead.next = head
              return newhead

后言

  • 明天估计是不开组会的,今天猛猛刷了6道题!知识能进脑子的感觉真爽啊! 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_56077562/article/details/136205114

【力扣hot100】刷题笔记day1-爱代码爱编程

前言 既然打算年后去找算法的实习,所以之后想直接改用python刷hot100了(新坑芜湖~),在B站大学找到这个刷题教程,先快速过一遍里面提到的python语法 Python数组 # 创建数组 a = [] # 添加元素,O(1) a.append(1) a.append(2) a.append(3) # [1, 2, 3] # 插入元素,O(

【力扣hot100】刷题笔记day14-爱代码爱编程

前言 又是新的一周,快乐的周一,快乐地刷题,今天把链表搞完再干活! 114. 二叉树展开为链表 - 力扣(LeetCode) 前序遍历 class Solution: def flatten(self, root: Optional[TreeNode]) -> None: if not root:

【力扣hot100】刷题笔记day7-爱代码爱编程

前言 身边同学已经陆陆续续回来啦,舍友都开始投简历了,我也要加油啦!刷完hot100就投! 73. 矩阵置零 - 力扣(LeetCode) 标记数组:空间复杂度O(m+n) class Solution: def setZeroes(self, matrix: List[List[int]]) -> None:

【力扣hot100】刷题笔记day2-爱代码爱编程

前言 hot100!开刷!不熟悉python就cv大法先,理清楚思路更重要 哈希 1. 两数之和 - 力扣(LeetCode) 暴力法 能过,遍历两遍求和是否为target class Solution(object): def twoSum(self, nums, target): n = len(nums)

【力扣hot100】刷题笔记day11-爱代码爱编程

前言 科研不顺啊......又不想搞了,随便弄弄吧,多花点时间刷题,今天开启二叉树! 94. 二叉树的中序遍历 - 力扣(LeetCode) 递归 # 最简单递归 class Solution: def inorderTraversal(self, root: TreeNode) -> List[int]: i

【力扣hot100】刷题笔记day20-爱代码爱编程

前言 今天学习了一句话“自己如果不努力,屎都吃不上热乎的”,话糙理不糙,与君共勉 35. 搜索插入位置 - 力扣(LeetCode) 二分查找 class Solution: def searchInsert(self, nums: List[int], target: int) -> int: n = len

【力扣hot100】刷题笔记day6-爱代码爱编程

前言 今天是社畜开工第一天,刷题刷题刷题💪 53. 最大子数组和 - 力扣(LeetCode) 贪心法 连续子数组累加和小于零就重新累加,【代码随想录】刷题笔记Day34-CSDN博客 class Solution: def maxSubArray(self, nums: List[int]) -> in

leetcode 1319.连通网络的操作次数-爱代码爱编程

思路:DFS(连通块) 其实一开始的时候,并不知道这道题的精髓在哪,总想着,啊?这怎么用图论的思想做啊? 细细思考之后,这道题还是比较有意思的,需要有一定的数据结构基础。 这里让我们求最少连接的操作次数。我们其实可以把这些点统统看成是连通块。 例如第一个例子,0,1,2是不是连在一块了?3是不是独立成一块?也就是说,这个例子里面,有两个连通块。我们

贪心 -爱代码爱编程

  目录 力扣860.柠檬水找零 力扣2208.将数组和减半的最少操作次数 力扣179.最大数 力扣376.摆动序列 贪心策略,局部最优->全局最优 1.把解决问题的过程分为若干步骤 2.解决每一步的时候,都选择当前看起来“最优秀的”解法 3.希望能够得到全局最优解 例子1:找零问题 50-4=46  -&g

leetcode 235. 二叉搜索树的最近公共祖先-爱代码爱编程

LeetCode 235. 二叉搜索树的最近公共祖先 1、题目 题目链接:235. 二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T

每日5题day7 -爱代码爱编程

每一步向前都是向自己的梦想更近一步,坚持不懈,勇往直前! 第一题:31. 下一个排列 - 力扣(LeetCode) 注意这道题的处理逻辑,我们应该走最右边的数i开始,向左遍历找到小于他的数j,然后交换,一定要注意交换后右边序列(j所在位置的后一位)也要满足是升序(因为刚刚已经完成升序了,每次升一点,所有子序列就要满足是最小升序,如果看文字太抽象,请

【力扣hot100】刷题笔记day3-爱代码爱编程

前言 以撒真是一不小心就玩太久了,终于解锁骨哥嘞,抓紧来刷题,今天是easy双指针! 283. 移动零 - 力扣(LeetCode) 一个指针遍历找非0,一个指针用于把0换到后面 class Solution(object): def moveZeroes(self, nums): pre = 0 # 用于交换前面的0

【力扣hot100】刷题笔记day5-爱代码爱编程

前言 回学校了,荒废了半天之后打算奋发图强猛猛刷题,找实习!赚钱!! 560. 和为 K 的子数组 - 力扣(LeetCode) 前缀法 + 哈希表 这个题解解释比官方清晰,截个图方便看,另一个题解的代码简洁计算前缀和并统计前缀和个数,遇到相减为k的情况就把前面个数加上 class Solution: def subarraySum(