Python每日一练(20230331) 阶乘后的零、无重复最长子串、LRU缓存机制

简介: Python每日一练(20230331) 阶乘后的零、无重复最长子串、LRU缓存机制

1. 阶乘后的零

给定一个整数 n ,返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1:

输入:n = 3

输出:0

解释:3! = 6 ,不含尾随 0


示例 2:

输入:n = 5

输出:1

解释:5! = 120 ,有一个尾随 0


示例 3:

输入:n = 0

输出:0


提示:

  • 0 <= n <= 10^4

进阶:你可以设计并实现对数时间复杂度的算法来解决此问题吗?

出处:

https://edu.csdn.net/practice/24289744

代码:

class Solution:
    def trailingZeroes(self, n: int) -> int:
        zero_count = 0
        current_multiple = 5
        while n >= current_multiple:
            zero_count += n // current_multiple
            current_multiple *= 5
        return zero_count
# %%
s = Solution()
print(s.trailingZeroes(5))
print(s.trailingZeroes(100))

输出:

1

24

以下这种写法更简洁:

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        while n > 0:
            count += n // 5
            n //= 5
        return count

2. 无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: s = "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: s = "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: s = "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

示例 4:

输入: s = ""

输出: 0


提示:

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

出处:

https://edu.csdn.net/practice/24289745

代码:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        i = 0
        j = 0
        m = 0
        hset = {}
        while j < len(s):
            char = s[j]
            index = hset.get(char)
            if index is not None and index > i:
                i = index
            m = m if m > j - i + 1 else j - i + 1
            hset[char] = j + 1
            j += 1
        return m
# %%
s = Solution()
print(s.lengthOfLongestSubstring('abcabcbb'))
print(s.lengthOfLongestSubstring('pwwkew'))

输出:

3

3


3. LRU 缓存机制

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制(https://baike.baidu.com/item/LRU)

实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

进阶:你是否可以在 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^5getput

出处:

https://edu.csdn.net/practice/24289743

代码:

class LRUCache:
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.maxlength = capacity
        self.array = {}
        self.array_list = []
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        value = self.array.get(key)
        if value is not None and self.array_list[0] is not key:
            index = self.array_list.index(key)
            self.array_list.pop(index)
            self.array_list.insert(0, key)
        value = value if value is not None else -1
        return value
    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if self.array.get(key) is not None:
            index = self.array_list.index(key)
            self.array.pop(key)
            self.array_list.pop(index)
        if len(self.array_list) >= self.maxlength:
            key_t = self.array_list.pop(self.maxlength - 1)
            self.array.pop(key_t)
        self.array[key] = value
        self.array_list.insert(0, key)
#%%
lRUCache = LRUCache(2)
lRUCache.put(1, 1)
lRUCache.put(2, 2)
val = lRUCache.get(1)
print(val)
lRUCache.put(3, 3)
val = lRUCache.get(2)
print(val)
lRUCache.put(4, 4)
val = lRUCache.get(1)
print(val)
val = lRUCache.get(3)
print(val)
val = lRUCache.get(4)
print(val)

输出:

1

-1

-1

3

4


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
相关文章
|
14天前
|
缓存 NoSQL 关系型数据库
在Python Web开发过程中:数据库与缓存,MySQL和NoSQL数据库的主要差异是什么?
MySQL是关系型DB,依赖预定义的表格结构,适合结构化数据和复杂查询,但扩展性有限。NoSQL提供灵活的非结构化数据存储(如JSON),无统一查询语言,但能横向扩展,适用于大规模、高并发场景。选择取决于应用需求和扩展策略。
109 1
|
16天前
|
开发者 Python 容器
深入理解Python迭代器:迭代机制的核心与应用
本文介绍了Python迭代器的核心概念、工作原理和应用场景。迭代器是遍历容器类型数据结构(如列表、元组、字典和集合)的对象,遵循迭代器协议,具有记忆遍历位置和一次性特点。通过实现迭代器协议,开发者能为自定义类型定义迭代行为,实现高效处理大量数据和与其他迭代工具协同工作。迭代器与可迭代对象的区别在于,可迭代对象实现`__iter__()`方法,返回迭代器,而迭代器实现`__next__()`方法,用于逐个访问元素。理解并运用迭代器能提升Python代码的性能和可读性。
|
1月前
|
监控 算法 Java
如何确保Python的内存管理机制能够有效地工作?
【2月更文挑战第19天】【2月更文挑战第57篇】如何确保Python的内存管理机制能够有效地工作?
|
1月前
|
存储 Java Python
谈谈你对 Python 的内存管理机制的理解。
【2月更文挑战第19天】【2月更文挑战第55篇】谈谈你对 Python 的内存管理机制的理解。
|
2月前
|
编译器 Python
Python优化机制:常量折叠
Python优化机制:常量折叠
20 0
|
2月前
|
缓存 Python
给我一些具体的例子,说明如何在Python中使用缓存和释放来避免内存溢出。
给我一些具体的例子,说明如何在Python中使用缓存和释放来避免内存溢出。
14 0
|
1月前
|
Python
解释 Python 中的异常处理机制。
解释 Python 中的异常处理机制。
18 0
|
29天前
|
索引 Python
Python阶乘计算
Python阶乘计算
|
30天前
|
存储 缓存 算法
深入探究LRU缓存机制:优化内存利用与提升性能
深入探究LRU缓存机制:优化内存利用与提升性能
75 1
|
1月前
|
存储 Python
Python计算阶乘
Python计算阶乘
11 0