首页 > 编程语言 >玩玩算法题——Episode 3

玩玩算法题——Episode 3

时间：2024-01-18 15:22:08浏览次数：39  
标签：head Episode self value 玩玩 算法 key return prev

Leetcode 2171. 拿出最少数目的魔法豆（2024-1-18每日一题）

Star Rating: 4.03

提示

给定一个正整数数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。

请你从每个袋子中拿出一些豆子（也可以不拿出），使得剩下的非空袋子中（即至少还有一颗魔法豆的袋子）魔法豆的数目相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。

请返回你需要拿出魔法豆的最少数目。

示例 1：

输入：beans = [4,1,6,5]
输出：4
解释：

  • 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。
    剩下袋子中魔法豆的数目为：[4,0,6,5]
  • 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。
    剩下袋子中魔法豆的数目为：[4,0,4,5]
  • 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。
    剩下袋子中魔法豆的数目为：[4,0,4,4]
    总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
    没有比取出 4 个魔法豆更少的方案。

示例 2：

输入：beans = [2,10,3,2]
输出：7
解释：

  • 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。
    剩下袋子中魔法豆的数目为：[0,10,3,2]
  • 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。
    剩下袋子中魔法豆的数目为：[0,10,3,0]
  • 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。
    剩下袋子中魔法豆的数目为：[0,10,0,0]
    总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
    没有比取出 7 个魔法豆更少的方案。

提示：

1 <= beans.length <= 10^5
1 <= beans[i] <= 10^5

一开始仍然没有思路 > <
先看下两个示例的操作过程：

4 1 6 5 -> 4 0 6 5 -> 4 0 4 5 -> 4 0 4 4
2 10 3 2 -> 0 10 3 2 -> 0 10 3 0 -> 0 10 0 0

我大概知道是什么样的过程了，可能是一个变形过的接雨水问题！..只不过雨水是反重力往上掉的，取出魔法豆就是在往里面放雨水
但是..它们也不完全相同

比如说，我们把第一个测试样例同时减去数组的最大值，再取相反数：

2 5 0 1 -> 2 6 0 1 -> 2 6 2 2

这样它应该就变成了一个接雨水的问题，只不过雨水的“最大高度”有所区别，一类“柱子”的最大高度是6，而另一类“柱子”的最大高度是2。
那么我们就有了一个基本思路：把数据分成两类，这两类分别以不同高度“接雨水”，使雨水的总量最小。
在上面的问题中，2 5 0 1可以分成2 0 1和5这两类，第一类以2为目标高度，第二类以6为目标高度。
如果不对数据预处理，那么如何理解呢？
4 1 6 5可以分成4 6 5和1这两类，第一类取出的豆子使第一类所有的豆子变成第一类袋子中豆子最少的袋子的数量，也就是4，第二类则全部取出豆子。
那么它实际上就是一个优化的问题了！
显然本题应该是确定一个分界，将魔法豆较少的和魔法豆较多的袋子分成两类！

那么，我们的基本思路如下：
（1）对列表进行排序；
（2）遍历列表并计算所有情况

具体要如何计算拿走的豆子呢？为了避免再次遍历列表，我们尝试一个例子：

9 8 6 4 3 2 1

假设以6为分界，那么前边拿走的豆子数就是9-6+8-6+6-6 = (9+8+6)-(6+6+6) = sum(9,8,6) - 6*3.
后边拿走的豆子数就是sum(4,3,2,1).
如果把它们再相加我们就会发现，结果实际上是:sum(list) - 6*3

那么，这样就有了一个时间复杂度为O(nlogn)的算法

class Solution(object):
    def minimumRemoval(self, beans):
        """
        :type beans: List[int]
        :rtype: int
        """
        s_beans = sorted(beans, reverse=True)  # 逆序排序，从大到小
        #print(s_beans)
        total_beans = sum(beans)  # 所有魔法豆的总数
        current_beans = 0  # 当前类的魔法豆数量
        result = sum(beans)  # 初始结果设为列表中豆子的总和
        #print(result)

        for i in range(len(beans)):
            removal = total_beans - s_beans[i] * (i+1)
            #print("removal = {}".format(removal))
            result = min(result, removal)
            #print("i={}, result={}".format(i, result))

        return result

可以看到我们的算法性能还是不错的, 256ms(100.00%)和21.60MB(50.00%)
Current: 76pp(New!)
Overall: 346pp(+62pp)

Leetcode 538 把二叉搜索树变成累加树

SR: 3.75

给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。

示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：

输入：root = [0,null,1]
输出：[1,null,1]
示例 3：

输入：root = [1,0,2]
输出：[3,3,2]
示例 4：

输入：root = [3,2,4,1]
输出：[7,9,4,10]

看起来这道题和二叉树这种数据结构比较相关！
我大概知道这是个什么过程啦！不过要如何做呢？

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

应该要对二叉搜索树从大到小遍历，维护一个部分和，然后累加就可以啦~
也就是说本题的关键是二叉搜索树从大到小遍历是个什么意思？！

我们知道，二叉搜索树的中序遍历是一个正序排序的过程，那么如果是逆中序遍历，是不是就是从大到小的遍历过程了呢？

接下来，我们来试一试！
先写一个最基本的二叉树中序遍历的代码，变成逆中序

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        convertBST(root.right)
        #convertBST(root)
        convertBST(root.left)

然后做一点点修改

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
sum = 0
class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root.right is not None:
            root.convertBST(root.right)
        sum += root.val
        root.val = sum
        if root.left is not None:
            root.convertBST(root.left)

似乎这样就可以啦~
不过...为什么会这样呢？
AttributeError: 'TreeNode' object has no attribute 'convertBST'
root.convertBST(root.right)
Line 15 in convertBST (Solution.py)
ret = Solution().convertBST(param_1)
Line 38 in _driver (Solution.py)
_driver()
Line 48 in (Solution.py)
原来如此...是self.convertBST..

sum = 0

class Solution(object):
    def convertBST(self, root):
        global sum #为了避免Ref before assignment错误，这里设置了全局变量
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root.right is not None:
            self.convertBST(root.right)
        sum += root.val
        root.val = sum
        if root.left is not None:
            self.convertBST(root.left)
        return root

不过我发现，在测试第二个测试用例时，仍然保留了第一个测试用例的变量！那要如何解决呢？
ChatGPT给了一种解决方式——利用self.sum

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def __init__(self):
        self.sum = 0

    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root.right is not None:
            self.convertBST(root.right)
        self.sum += root.val
        root.val = self.sum
        if root.left is not None:
            self.convertBST(root.left)
        return root

提交的时候，发现漏了一种极端情况..

class Solution(object):
    def __init__(self):
        self.sum = 0

    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if root is None:
            return root #处理root = []的情况
        if root.right is not None:
            self.convertBST(root.right)
        self.sum += root.val
        root.val = self.sum
        if root.left is not None:
            self.convertBST(root.left)
        return root

代码性能：64ms(19.12%)和17.00MB(98.53%), Score:58.825
Current: 47pp(New!)
Overall: 380pp(+34pp)

那么有办法提升Score吗？..有点不太清楚..
去看了一下题解..果然有更高端的方法！
有一个能得到71pp的解法，它能在时间复杂度为O(n)和空间复杂度为O(1)的方式，它也被称为Morris遍历，如何实现这个代码呢？

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        curr = root
        total_sum = 0
        
        while curr is not None:
            if curr.right is None:
                total_sum += curr.val
                curr.val = total_sum
                curr = curr.left
            else:
                successor = self.get_successor(curr)
                if successor.left is None:
                    successor.left = curr
                    curr = curr.right
                else:
                    successor.left = None
                    total_sum += curr.val
                    curr.val = total_sum
                    curr = curr.left
        
        return root

    def get_successor(self, node): #得到一个节点的后继节点 —— 先找右孩子，然后一直找左孩子直到左孩子为空
        successor = node.right
        while successor.left is not None and successor.left != node:
            successor = successor.left
        return successor

这是Leetcode官方给出的解析：
有一种巧妙的方法可以在线性时间内，只占用常数空间来实现中序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其反序中序遍历规则总结如下：

  1. 如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点；

  2. 如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）；

    1. 如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点；

    2. 如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点；

  3. 重复步骤 1 和步骤 2，直到遍历结束。

这样我们利用 Morris 遍历的方法，反序中序遍历该二叉搜索树，即可实现线性时间与常数空间的遍历。

作者：力扣官方题解
链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/solutions/421616/ba-er-cha-sou-suo-shu-zhuan-huan-wei-lei-jia-sh-14/
来源：力扣（LeetCode）

有点抽象...来个测试用例看看

Eg: 对下面的测试用例运行Morris遍历算法：

[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

对上面代码加了些输出条件，这样也许好理解一些：

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        curr = root
        total_sum = 0
        
        while curr is not None:
            print curr.val,
            if curr.right is None:
                total_sum += curr.val
                curr.val = total_sum
                curr = curr.left
                print("right is None")
            else:
                print("right is Not None;"),
                successor = self.get_successor(curr)
                print ("successor is %d;" % successor.val),
                if successor.left is None:
                    successor.left = curr
                    curr = curr.right
                    print("successor's left is None")
                else:
                    successor.left = None
                    total_sum += curr.val
                    curr.val = total_sum
                    curr = curr.left
                    print("successor's left is not None")
            if curr is None:
                print('NULL')
        
        return root

    def get_successor(self, node): #得到一个节点的后继节点 —— 先找右孩子，然后一直找左孩子直到左孩子为空
        successor = node.right
        while successor.left is not None and successor.left != node:
            successor = successor.left
        return successor

4 right is Not None; successor is 5; successor's left is None
6 right is Not None; successor is 7; successor's left is None
7 right is Not None; successor is 8; successor's left is None
8 right is None
7 right is Not None; successor is 8; successor's left is not None
6 right is Not None; successor is 15; successor's left is not None
5 right is None
4 right is Not None; successor is 26; successor's left is not None
1 right is Not None; successor is 2; successor's left is None
2 right is Not None; successor is 3; successor's left is None
3 right is None
2 right is Not None; successor is 33; successor's left is not None
1 right is Not None; successor is 35; successor's left is not None
0 right is None
NULL

自己在Prodrafts上用Apple Pencil模拟了一些例子...终于理解了..> <（可能我的理解能力有点太菜了..也或者有可能是别的什么原因）
算法的本质实际上是将节点的左空指针利用了起来，将左孩子构成了类似链表的结构进行遍历..

那么我们的算法性能提升到了60ms(42.65%)和15.52MB(100.00%).
不过...40ms是如何做到的呢？...

Current: 71pp(+34pp)
Overall: 401pp(+21pp)

我们看了一下那个时间acc能到100.00%的代码...它的思路大概是把中序遍历节点写成了类内函数，而不是简单递归调用convertBST(88pp)

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        global allSum
        allSum = 0
        def dfs(node):
            global allSum
            if node:
                dfs(node.right)
                allSum += node.val
                node.val = allSum
                dfs(node.left)
        
        dfs(root)
        return root

另外还有一种写法，能在44ms内运行结束，它是这样写的：(85pp)

class Solution(object):
    def convertBST(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        # 迭代
        if not root:
            return root
        cur = root
        stack = []
        pre = None
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.right
            else:
                cur = stack.pop()
                if pre:
                    cur.val += pre.val
                pre = cur
                cur = cur.left
                
        return root

它的原理如下：

  1. 初始化当前节点 cur 为根节点，定义一个栈 stack 用于迭代，初始化前一个节点 pre 为 None。
  2. 进入循环，循环条件为当前节点 cur 不为空或者栈不为空。
    • 如果当前节点 cur 不为空，将其入栈，并将当前节点移到其右子树 cur.right。
    • 如果当前节点 cur 为空，说明已经到达最右边的节点，需要出栈一个节点，即 cur = stack.pop()。
      • 在出栈的过程中，对当前节点的值进行累加操作：cur.val += pre.val，其中 pre 是前一个访问的节点。
      • 更新前一个节点 pre 为当前节点 cur。
      • 将当前节点移到其左子树 cur.left。
  3. 返回根节点 root。

这个方法的核心思想是通过迭代和栈，模拟了中序遍历的逆序过程。从最右边的节点开始，逐步处理每个节点，并更新节点的值，使其变为累加和。这样，最终的二叉搜索树就被转换成了累加树。

Leetcode 65. 有效数字

  1. 有效数字

Star Rating: 4.54

有效数字（按顺序）可以分成以下几个部分：

一个小数或者整数
（可选）一个 'e' 或 'E' ，后面跟着一个整数
小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
至少一位数字，后面跟着一个点 '.'
至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
一个点 '.' ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
至少一位数字
部分有效数字列举如下：["2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"]

部分无效数字列举如下：["abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"]

给你一个字符串 s ，如果 s 是一个有效数字 ，请返回 true 。

示例 1：

输入：s = "0"
输出：true
示例 2：

输入：s = "e"
输出：false
示例 3：

输入：s = "."
输出：false

提示：

1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

第一道Leetcode困难题~不过看起来题干似乎并不难理解
不过本题的难点是确定所有的边缘条件！.这才是最难的

class Solution:
    def isNumber(self, s: str) -> bool:

如何确定所有的边缘条件呢？或者说...找有效数字的条件容易一些，还是无效数字容易一些呢？
显然是有效数字更容易！（因为有效数字的结构是固定的）
我有一个基本的思路，也就是根据特定的边界条件，把数字划分成几个部分去判断
根据题干我们先写出能检查小数和整数的程序：

class Solution:
    def isNumber(self, s: str) -> bool:
        def isint(str):
            #检查正负号个数
            #采用异常检测的方式，将str转为int，如果成功，返回True，否则返回False

        def isdecimal(str):
            #检查正负号个数
            #采用异常检测的方式，将str转为float，如果成功，返回True，否则返回False
        
        #对字符串str,：
            #如果找到e/E，将字符串以e/E为分界分为前后两部分，如果e是最后一位，返回False
                #前面的部分：调用isdecimal(str)
                #后面的部分：调用isint(str)
                #返回isdecimal(str) and isint(str)
            #否则，寻找小数点'.'
                #如果找到，直接对整个字符串调用isdecimal(str)，返回isdecimal(str)的返回值
                #如果没找到，直接对整个字符串调用isint(str)，返回isint(str)的返回值

为了节省时间，也是直接让ChatGPT生成了一个对应的Python代码：

class Solution:
    def isNumber(self, s: str) -> bool:
        def isint(s):
            if s[0] == '+' or s[0] == '-'
                s = s[1:]
            try:
                int(s)
                return True
            except:
                return False

        def isdecimal(s):
            if s[0] == '+' or s[0] == '-'
                s = s[1:]
            try:
                float(s)
                return True
            except:
                return False
        
        e_pos = s.find('e') if 'e' in s else s.find('E')
        
        if e_pos != -1:
            if e_pos == 0 or e_pos == len(s) - 1:
                return False
            return isdecimal(s[:e_pos]) and isint(s[e_pos+1:])
        
        dot_pos = s.find('.')
        if dot_pos != -1:
            return isdecimal(s)
        
        return isint(s)

然后发现了一个特例能够让这个程序输出错误的结果，比如:'++5'，所以还是要修改下逻辑

class Solution:
    def isNumber(self, s: str) -> bool:
        def isint(s):
            if (s[0] == '+' or s[0] == '-'): 
                s = s[1:]
                if (s[0] == '+' or s[0] == '-'): #这里的逻辑修改了一下
                    return False
            try:
                int(s)
                return True
            except:
                return False

        def isdecimal(s):
            if (s[0] == '+' or s[0] == '-'):
                s = s[1:]
                if (s[0] == '+' or s[0] == '-'): #这里的逻辑修改了一下
                    return False
            try:
                float(s)
                return True
            except:
                return False
        
        e_pos = s.find('e') if 'e' in s else s.find('E')
        
        if e_pos != -1:
            if e_pos == 0 or e_pos == len(s) - 1:
                return False
            return isdecimal(s[:e_pos]) and isint(s[e_pos+1:])
        
        dot_pos = s.find('.')
        if dot_pos != -1:
            return isdecimal(s)
        
        return isint(s)

然后在测试用例'+eo'卡住了，绷不住了...string idx out of range..
因此..

class Solution:
    def isNumber(self, s: str) -> bool:
        def isint(s):
            if (s[0] == '+' or s[0] == '-'): 
                s = s[1:]
                if len(s) == 0 or (s[0] == '+' or s[0] == '-'): #这里的逻辑修改了一下
                    return False
            try:
                int(s)
                return True
            except:
                return False

        def isdecimal(s):
            if (s[0] == '+' or s[0] == '-'):
                s = s[1:]
                if len(s) == 0 or (s[0] == '+' or s[0] == '-'): #这里的逻辑修改了一下
                    return False
            try:
                float(s)
                return True
            except:
                return False
        
        e_pos = s.find('e') if 'e' in s else s.find('E')
        
        if e_pos != -1:
            if e_pos == 0 or e_pos == len(s) - 1:
                return False
            return isdecimal(s[:e_pos]) and isint(s[e_pos+1:])
        
        dot_pos = s.find('.')
        if dot_pos != -1:
            return isdecimal(s)
        
        return isint(s)

这一次终于成功啦~
成绩如下：43ms(75.38%)和16.50MB(29.19%)

Current: 96pp(New!)
Overall: 477pp(+76pp)

（所以本题的难点在于处理的方法，以及考虑所有的边缘条件！）

不过Leetcode的题解用的是有限状态机（144pp的Solution，估计是两个100.00%的解法），之后可以学习一下...不过现在暂时还用不上（可能有点像数字电路里面的时序逻辑电路了）

Leetcode 41. 缺失的整数

Star Rating: 4.60

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3
示例 2：

输入：nums = [3,4,-1,1]
输出：2
示例 3：

输入：nums = [7,8,9,11,12]
输出：1

提示：

1 <= nums.length <= 5 * 10^5
-2^31 <= nums[i] <= 2^31 - 1

本题难点在于..空间复杂度为O(1)...时间复杂度O(n)，也就是只能遍历一次列表...?（也不一定）
所以我们需要找一个合适的数据结构来为本题建模

稍微思考了一下，..这为什么让我想到了一个思修课程上讲过的经典的麦田问题...不过这是个哲学问题...
但是这题的目标显然和那个问题是不同的

为此我想到了一个可能合适的第一个版本的方法：

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        # 初始化一个空间为5*10^5的列表，元素全部置为0
        #dict = []
        for i in range(n):
            # 把dict[nums[i]]置为1
        for i in range(len(nums)+1):
            # 返回第一个0出现的位置

不过这并不是真正的常数级别时间复杂度，而是取决于题目中数字的范围...

然后ChatGPT给出了另一个版本，也就是采用了哈希表进行映射的版本

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i]-1] != nums[i]: #利用了结果不超过n+1的特性，所以nums[i]如果>=n+1可以不需要处理
                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1] #把两个数字进行交换，但并不是i和i+1进行交换，而是...
        #大概知道它的思想了，它的思想是尝试将整数放在正确的位置上，然后找到第一个不在位置上的最小整数。
        
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1
        
        return n + 1

这个似乎有点像快速排序的内部算法！..

当使用交换实现的快速排序时，我们选择数组中的一个元素作为基准值（pivot），然后通过一系列的交换操作将数组分为两个部分，使得基准值左边的元素都小于等于基准值，右边的元素都大于等于基准值。然后，对左右两个部分分别进行递归排序，最终整个数组就被排序了。

具体步骤如下：

  1. 选择一个基准值（通常是数组的第一个元素）。
  2. 定义两个指针，一个指向数组的起始位置（左指针），另一个指向数组的结束位置（右指针）。
  3. 从右到左找到第一个小于等于基准值的元素，记为 nums[right]。
  4. 从左到右找到第一个大于等于基准值的元素，记为 nums[left]。
  5. 如果 left < right，则交换 nums[left] 和 nums[right]，继续步骤 3 和步骤 4；否则，将基准值与 nums[right] 交换，此时基准值左边的元素都小于等于基准值，右边的元素都大于等于基准值。
  6. 对基准值左边的子数组和右边的子数组分别进行递归排序。

下面是一个简单的实现示例：

def quicksort(nums, low, high):
    if low < high:
        pivot_index = partition(nums, low, high)
        if low != pivot_index:
            quicksort(nums, low, pivot_index - 1)
        if pivot_index != high:
            quicksort(nums, pivot_index + 1, high)

def partition(nums, low, high):
    pivot = nums[low]
    left = low + 1
    right = high

    done = False
    while not done:
        while left <= right and nums[left] <= pivot:
            left += 1
        while left <= right and nums[right] >= pivot:
            right -= 1
        if left <= right:
            nums[left], nums[right] = nums[right], nums[left]
        else:
            done = True
    
    nums[low], nums[right] = nums[right], nums[low]
    return right

# 示例用法
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
quicksort(nums, 0, len(nums) - 1)
print(nums)

这个示例展示了采用交换实现的快速排序的基本思想。在实际应用中，还可以优化和改进算法以提高性能。

刚刚的那道题提交啦~性能还不错..
77ms(77.40%)和27.44MB(45.12%)

Current: 101pp(New!)
Overall: 554pp(+77pp)

Leetcode 146. LRU缓存

Star Rating: 4.44（应该算中等题里面比较难的了，如果是没有提示手写的话..难度直接能上到5星以上）
Star Rating +No Hint mod: 5.29

有点像osu!里面的耐力图..虽然之前做过，但是之前是依靠ChatGPT写的代码..

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1)的平均时间复杂度运行。

示例：

输入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多调用 2 * 10^5 次 get 和 put

我们所写的模版代码是这样的： （我把答案藏在几十行开外了...那我们来看一下如何去构思这道题吧！

class LRUCache:

    def __init__(self, capacity: int):


    def get(self, key: int) -> int:


    def put(self, key: int, value: int) -> None:



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

感觉理解这道题就不是一件容易的事情..虽然LRU这个方法比较好理解
首先要尝试把数据结构先写出来，然后才能考虑操作..

大概知道啦~我想这个题确实应该用一个双向链表来实现，这样时间复杂度就是O(capacity // 2).
再思考下LRU如何实现，我们就能得到这样的初始思路

class LRUCache:

    def __init__(self, capacity: int):
        #创建容量为capacity的链表，不过现在只是初始化一个头节点


    def get(self, key: int) -> int:
        #双向遍历链表，并找到对应key的值


    def put(self, key: int, value: int) -> None:
        #检查数值是否存在（所以需要调用一次get）
            #如果存在，修改这个位置的值
            #如果不存在：
                # 当前链表元素小于capacity
                    # 在尾部添加元素
                # 当前链表元素大于capacity
                    # 在头部删除元素，并在尾部添加元素

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

想试着自己把这题的代码写出来...因为这题比较重要而且有一定挑战性

class binode: #定义双向链表
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:
    def __init__(self, capacity: int):
        #创建容量为capacity的链表，不过现在只是初始化一个头节点
        self.head = binode(-1,-1) #把key和value都设置为-1,表示头节点
        self.capacity = capacity
        self.size = 0
        self.head.next = self.head
        self.head.prev = self.head

    def get(self, key: int, return_pointer = False) -> int:
        #双向遍历链表，并找到对应key的值
        rcurr = self.head
        lcurr = self.head
        while rcurr != lcurr or rcurr.prev != lcurr: #两个指针相遇的条件
            if rcurr.key == key:
                if return_pointer:
                    return rcurr.value, rcurr
                else:
                    return rcurr.value
            rcurr = rcurr.next
            if lcurr.key == key:
                if return_pointer:
                    return lcurr.value, lcurr
                else:
                    return lcurr.value
            lcurr = lcurr.prev
        if return_pointer:
            return -1,None
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        #检查数值是否存在（所以需要调用一次get）
        value, pointer = self.get(key, True)
        if value != -1:
            pointer.value = value    #如果存在，修改这个位置的值
            return
        else:
        #如果不存在：
            if self.size < self.capacity:
            # 当前链表元素小于capacity
                newnode = binode(key,value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                self.head.prev = newnode
                self.size += 1
                # 在尾部添加元素
            else:
            # 当前链表元素大于等于capacity
                curr = self.head.next
                curr.prev.next = curr.next
                curr.next.prev = curr.prev
                # 在头部删除元素，并在尾部添加元素
                newnode = binode(key,value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                head.prev = newnode

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

这个代码会TLE，这是什么原因呢？...但是这还没到大的测试用例..

我们对代码做了一点点修改，但是测试用例仍然有些问题..

class binode: #定义双向链表
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:
    def __init__(self, capacity: int):
        #创建容量为capacity的链表，不过现在只是初始化一个头节点
        self.head = binode(-1,-1) #把key和value都设置为-1,表示头节点
        self.capacity = capacity
        self.size = 0
        self.head.next = self.head
        self.head.prev = self.head
        print(self.head.value)

    def get(self, key: int, return_pointer = False) -> int:
        #双向遍历链表，并找到对应key的值
        rcurr = self.head.next 
        lcurr = self.head.prev
        if self.size == 0 and return_pointer:
            return -1, None
        elif self.size == 0:
            return -1
        meet_again = False
        while not meet_again and rcurr.prev != lcurr: #两个指针相遇的条件
            if rcurr.key == key:
                print(f"key = {rcurr.key}, value = {rcurr.value}")
                if return_pointer:
                    return rcurr.value, rcurr
                else:
                    return rcurr.value
            rcurr = rcurr.next
            if lcurr.key == key:
                print(f"key = {lcurr.key}, value = {lcurr.value}")
                if return_pointer:
                    return lcurr.value, lcurr
                else:
                    return lcurr.value
            lcurr = lcurr.prev
            if rcurr == lcurr:
                meet_again = True
        if return_pointer:
            return -1,None
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        #检查数值是否存在（所以需要调用一次get）
        _, pointer = self.get(key, True)
        if pointer != None:
            pointer.value = value    #如果存在，修改这个位置的值
            return
        else:
            #如果不存在：
            if self.size < self.capacity:
                # 当前链表元素小于capacity
                newnode = binode(key, value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                self.head.prev = newnode
                self.size += 1
                # 在尾部添加元素
            else:
                # 当前链表元素大于等于capacity
                curr = self.head.next
                curr.prev.next = curr.next
                curr.next.prev = curr.prev
                # 在头部删除元素，并在尾部添加元素
                newnode = binode(key, value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                self.head.prev = newnode

思考了一下，是因为使用过的元素没有更新它的状态！
那这样的话，思路就清晰多了：

class binode: #定义双向链表
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:
    def __init__(self, capacity: int):
        #创建容量为capacity的链表，不过现在只是初始化一个头节点
        self.head = binode(-1,-1) #把key和value都设置为-1,表示头节点
        self.capacity = capacity
        self.size = 0
        self.head.next = self.head
        self.head.prev = self.head
        print(self.head.value)

    def get(self, key: int, return_pointer = False) -> int:
        #双向遍历链表，并找到对应key的值
        rcurr = self.head.next 
        lcurr = self.head.prev
        if self.size == 0 and return_pointer:
            return -1, None
        elif self.size == 0:
            return -1
        meet_again = False
        while not meet_again and rcurr.prev != lcurr: #两个指针相遇的条件
            if rcurr.key == key:
                print(f"key = {rcurr.key}, value = {rcurr.value}")
                 # 把这个元素移动到最近使用的位置，也就是链表尾部！
                if rcurr.next != self.head:
                    # 在当前位置删除节点
                    rcurr.next.prev = rcurr.prev
                    rcurr.prev.next = rcurr.next
                    # 插入到尾部节点
                    self.head.prev.next = rcurr
                    rcurr.prev = self.head.prev
                    rcurr.next = self.head
                    self.head.prev = rcurr
                if return_pointer:
                    return rcurr.value, rcurr
                else:
                    return rcurr.value
            rcurr = rcurr.next
            if lcurr.key == key:
                print(f"key = {lcurr.key}, value = {lcurr.value}")
                # 把这个元素移动到最近使用的位置，也就是链表尾部！
                if lcurr.next != self.head:
                    # 在当前位置删除节点
                    lcurr.next.prev = lcurr.prev
                    lcurr.prev.next = lcurr.next
                    # 插入到尾部节点
                    self.head.prev.next = lcurr
                    lcurr.prev = self.head.prev
                    lcurr.next = self.head
                    self.head.prev = lcurr
                if return_pointer:
                    return lcurr.value, lcurr
                else:
                    return lcurr.value
            lcurr = lcurr.prev
            if rcurr == lcurr:
                meet_again = True
        if return_pointer:
            return -1,None
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        #检查数值是否存在（所以需要调用一次get）
        _, pointer = self.get(key, True)
        if pointer != None:
            pointer.value = value    #如果存在，修改这个位置的值
        else:
            #如果不存在：
            if self.size < self.capacity:
                # 当前链表元素小于capacity
                newnode = binode(key, value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                self.head.prev = newnode
                self.size += 1
                # 在尾部添加元素
            else:
                # 当前链表元素大于等于capacity
                curr = self.head.next
                curr.prev.next = curr.next
                curr.next.prev = curr.prev
                # 在头部删除元素，并在尾部添加元素
                newnode = binode(key, value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                self.head.prev = newnode

然后又进行了一些优化：

class binode: #定义双向链表
    def __init__(self,key,value):
        self.key = key
        self.value = value
        self.next = None
        self.prev = None

class LRUCache:
    def __init__(self, capacity: int):
        #创建容量为capacity的链表，不过现在只是初始化一个头节点
        self.head = binode(-1,-1) #把key和value都设置为-1,表示头节点
        self.capacity = capacity
        self.size = 0
        self.head.next = self.head
        self.head.prev = self.head
        #print(self.head.value)

    def traverse(self):
        curr = self.head.next
        print('[',end='')
        while curr != self.head:
            print(f"[{curr.key},{curr.value}]",end = ',')
            curr = curr.next
        print(']')

    def get(self, key: int, return_pointer = False) -> int:
        #双向遍历链表，并找到对应key的值
        rcurr = self.head.next 
        lcurr = self.head.prev
        if self.size == 0 and return_pointer:
            return -1, None
        elif self.size == 0:
            return -1
        meet_again = False
        while not meet_again and rcurr.prev != lcurr: #两个指针相遇的条件
            if rcurr.key == key:
                #print(f"key = {rcurr.key}, value = {rcurr.value}")
                 # 把这个元素移动到最近使用的位置，也就是链表尾部！
                if rcurr.next != self.head:
                    # 在当前位置删除节点
                    rcurr.next.prev = rcurr.prev
                    rcurr.prev.next = rcurr.next
                    # 插入到尾部节点
                    self.head.prev.next = rcurr
                    rcurr.prev = self.head.prev
                    rcurr.next = self.head
                    self.head.prev = rcurr
                if return_pointer:
                    return rcurr.value, rcurr
                else:
                    return rcurr.value
            if lcurr.key == key:
                #print(f"key = {lcurr.key}, value = {lcurr.value}")
                # 把这个元素移动到最近使用的位置，也就是链表尾部！
                if lcurr.next != self.head:
                    # 在当前位置删除节点
                    lcurr.next.prev = lcurr.prev
                    lcurr.prev.next = lcurr.next
                    # 插入到尾部节点
                    self.head.prev.next = lcurr
                    lcurr.prev = self.head.prev
                    lcurr.next = self.head
                    self.head.prev = lcurr
                if return_pointer:
                    return lcurr.value, lcurr
                else:
                    return lcurr.value
            if rcurr == lcurr:
                meet_again = True
            rcurr = rcurr.next #注意这里需要在rcurr == lcurr判断以后再移动指针，否则可能漏掉情况
            lcurr = lcurr.prev
        if return_pointer:
            return -1,None
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        #检查数值是否存在（所以需要调用一次get）
        _, pointer = self.get(key, True)
        if pointer != None:
            pointer.value = value    #如果存在，修改这个位置的值
        else:
            #如果不存在：
            if self.size < self.capacity:
                # 当前链表元素小于capacity
                newnode = binode(key, value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                self.head.prev = newnode
                self.size += 1
                # 在尾部添加元素
            else:
                # 当前链表元素大于等于capacity
                curr = self.head.next
                curr.prev.next = curr.next
                curr.next.prev = curr.prev
                # 在头部删除元素，并在尾部添加元素
                newnode = binode(key, value)
                self.head.prev.next = newnode
                newnode.prev = self.head.prev
                newnode.next = self.head
                self.head.prev = newnode
        #self.traverse()

现在的代码已经能正确处理所有测试用例了，不过这次在一个大的样例下超时了...那么，我们要如何优化呢？

（有点想不起来之前是怎么写的了..）

ChatGPT: 在你的代码中，你使用了一个循环双向链表来实现LRU缓存，但是对于大数据量的场景可能会导致性能问题。在每次插入或获取元素时，你都进行了双向遍历来查找目标元素，这样会导致时间复杂度为O(n)，而题目要求的是O(1)。

为了优化这个问题，可以考虑使用哈希表和双向链表结合的方式来实现LRU缓存。哈希表用于快速查找元素，双向链表用于维护元素的访问顺序。这样，每次插入或获取元素时，只需在哈希表中进行O(1)的查找，然后通过双向链表进行元素的移动。这样可以保证插入、获取和删除操作都能在O(1)的时间内完成。

以下是一个基于哈希表和双向链表的优化版本：

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}
        self.head = Node(-1, -1)  # dummy head
        self.tail = Node(-1, -1)  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def move_to_end(self, node):
        # 移动节点到双向链表尾部
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.cache:
            node = self.cache[key] #直接通过哈希表映射到链表对应的位置，而不需要遍历双向链表！
            self.move_to_end(node)
            return node.value
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_end(node)
        else:
            if len(self.cache) == self.capacity:
                # 删除双向链表头部节点和哈希表中对应的键值对
                removed_node = self.head.next
                self.head.next = removed_node.next
                removed_node.next.prev = self.head
                del self.cache[removed_node.key]

            # 插入新节点到双向链表尾部和哈希表中
            new_node = Node(key, value)
            self.cache[key] = new_node #果然如此...直接用哈希表（字典）把键映射到链表对应位置啦~
            new_node.prev = self.tail.prev
            new_node.next = self.tail
            self.tail.prev.next = new_node
            self.tail.prev = new_node

这样的设计保证了在插入、获取和删除操作中都能够在O(1)的时间内完成。
这段代码的性能还不错，达到了385ms(97.97%)和75.48MB(65.02%)

Current: 132pp(New!)
Overall: 658pp(+104pp)

标签：head,Episode,self,value,玩玩,算法,key,return,prev
From： https://www.cnblogs.com/tuffysbase/p/17972584

相关文章

  • java实现正态分布算法文心一言
    实现正态分布算法文心一言1.了解正态分布在开始实现正态分布算法之前，我们先来了解一下正态分布是什么。正态分布也被称为高斯分布，是一种常见的连续概率分布。它的概率密度函数可以用一个钟形曲线来表示，曲线的中心对应着均值，曲线的宽度对应着标准差。2.实现流程我们要实现的是......
  • 《算法竞赛》07 组合数学
    二项式定理\((a+b)^n=\sum_{i=0}^n\binomnia^ib^{n-i}\)。杨辉三角每个数对应一个组合数。卢卡斯定理\(m\)为质数时\(\binomnm\bmodp=\binom{n\bmodp}{m\bmodp}\cdot\binom{\lfloor\fracnp\rfloor}{\lfloor\fracmp\rfloor}\bmodp\)。有时候结合递归，对\(\binom{......
  • 用余弦相似度修正评分的协同过滤推荐算法
    前言今天读的这篇论文是一篇于2020年6月份发表在计算机工程与科学(ComputerEngineering&Science)上的一篇论文。论文采用评分矩阵的多种维度进行相似度比较以修正不合理评分，再用修正后的评分进行协同过滤推荐。利用MovieLens和BookCrossing数据库进行实验，结果表明：带修正评分......
  • 玩玩算法题——Episode 2
    Leetcode每日一题：最大字符串匹配数目题干如下：给你一个下标从0开始的数组words，数组中包含互不相同的字符串。如果字符串words[i]与字符串words[j]满足以下条件，我们称它们可以匹配：字符串words[i]等于words[j]的反转字符串。0<=i<j<words.length请你返回数组......
  • 贪心算法-题目1力扣455（简单题）
    力扣455，给小朋友发饼干假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j]>=g[i]，我们可以将这个饼干 j 分配......
  • 算法—差分
    1.一维差分（实质：前缀和的逆运算）给区间[l,r]中的每个数加上c：B[l]+=c,B[r+1]-=c上述操作可以免去构造一个新数组，可以直接给差分赋值2.二维差分给以(x1,y1)为左上角，(x2,y2)为右下角的子矩阵中的所有元素加上C：S[x1,y1]+=c,S[x2+1,y1]-=c,S[x1,y2+1]-=c,......
  • 2024/1/17 算法笔记
    1.欧拉质数筛功能是给一个整数n查找小于等于n的所有质数。最后使用的是prime【i】//功能：查找n内第x个质数。boolisprime[100000010];//isprime[i]=1表示:i是素数intprime[6000010],cnt=0;//prime存质数voidgetprime(intn){//筛到n也就是n以内的质数memset(is......
  • 算法笔记之图论
    打开转盘锁你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字：'0','1','2','3','4','5','6','7','8','9'。每个拨轮可以自由旋转：例如把'9'变为'0'，'0'变为......
  • 算法笔记
    1.回溯法(Backtracking)应用：组合、排列、子集等组合型问题，0/1背包问题、图的着色问题等。时空复杂度：时空复杂度较高，指数级别。时间复杂度：O(2^n)或更高，其中n是问题规模。空间复杂度：O(n)或更高，取决于递归深度。特性：通过深度优先搜索遍历解空间。需要撤销选择，回溯到上一步......
  • 学习笔记——ST算法
    ST算法ST算法是一种运用倍增来解决RMQ问题也就是区间最值问题的算法。给定一个长度为\(N\)的序列\(A\)，ST算法能在\(\mathcalO(NlogN)\)的时间预处理后，以\(\mathcalO(1)\)的时间在线回答区间最值问题。设\(F_{i,j}\)表示序列\(A\)中下标在子区间\(\left[i,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99