算法急救LeetCode62题-python版（2）/ 哈希表、字符串

2024-08-22 05:28
文章标签 python 算法 字符串 哈希 急救 leetcode62

本文主要是介绍算法急救LeetCode62题-python版（2）/ 哈希表、字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法急救LeetCode62题-python版（2）/ 哈希表、字符串

常考题型的迅速回顾，用于没时间刷力扣的

三：哈希表

1：242.有效的字母异位词

题目描述： 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

  • 示例1：
    输入: s = “anagram”, t = “nagaram”
    输出: true
  • 示例2：
    输入: s = “rat”, t = “car” 输出: false

说明: 你可以假设字符串只包含小写字母。

思路： 先看暴力的解法，两层for循环，同时还要记录字符是否重复出现，很明显时间复杂度是 O(n^2)。
暴力的方法这里就不做介绍了，直接看一下哈希法。数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。
需要定义一个多大的数组呢，定一个数组叫做record，大小为26 就可以了，初始化为0，因为字符a到字符z的ASCII也是26个连续的数值。

代码：

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
（版本一）
class Solution:def isAnagram(self, s: str, t: str) -> bool:record = [0] * 26for i in s:#并不需要记住字符a的ASCII，只要求出一个相对数值就可以了record[ord(i) - ord("a")] += 1for i in t:record[ord(i) - ord("a")] -= 1for i in range(26):if record[i] != 0:#record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。return Falsereturn True

# （版本二）没有使用数组作为哈希表，只是介绍defaultdict这样一种解题思路
class Solution:def isAnagram(self, s: str, t: str) -> bool:from collections import defaultdicts_dict = defaultdict(int)t_dict = defaultdict(int)for x in s:s_dict[x] += 1for x in t:t_dict[x] += 1return s_dict == t_dict

# （版本三）没有使用数组作为哈希表，只是介绍Counter这种更方便的解题思路
class Solution(object):def isAnagram(self, s: str, t: str) -> bool:from collections import Countera_count = Counter(s)b_count = Counter(t)return a_count == b_count
2：349. 两个数组的交集

题目描述： 给定两个数组，编写一个函数来计算它们的交集。

  • 示例1：
    输入:nums1=[1,2,2,1]，nums2 =[2,2]
    输出:[2]
  • 示例 2:
    输入:nums1=[4,9,5]，nums2=[9,4,9,8,4]
    输出:[9,4]
    说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

思路：
这道题目，主要要学会使用一种哈希数据结构：set（无重复数值），这个数据结构可以解决很多类似的问题。
注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。此时就要使用另一种结构体了，set 。

代码：

（版本一）使用字典和集合
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:# 使用哈希表存储一个数组中的所有元素table = {}for num in nums1:table[num] = table.get(num, 0) + 1# 使用集合存储结果res = set()for num in nums2:if num in table:res.add(num)del table[num]return list(res)	
# （版本二）使用数组
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:count1 = [0]*1001count2 = [0]*1001result = []for i in range(len(nums1)):count1[nums1[i]]+=1for j in range(len(nums2)):count2[nums2[j]]+=1for k in range(1001):if count1[k]*count2[k]>0:result.append(k)return result

# （版本三）集合
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:return list(set(nums1) & set(nums2))
3：1. 两数之和

题目描述： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

  • 示例1：
    输入:nums = [2, 7, 11, 15], target = 9
    输出:[0, 1]
    说明： nums[0] + nums[1] = 2 + 7 = 9。

思路：
什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
本题呢，就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。

代码：

（版本一）使用字典
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:records = dict()for index, value in enumerate(nums):  if target - value in records:   # 遍历当前元素，并在map中寻找是否有匹配的keyreturn [records[target- value], index]records[value] = index    # 如果没找到匹配对，就把访问过的元素和下标加入到map中return []
# （版本二）使用集合
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:#创建一个集合来存储我们目前看到的数字seen = set()             for i, num in enumerate(nums):complement = target - numif complement in seen:return [nums.index(complement), i]seen.add(num)

# （版本三）暴力法
class Solution:def twoSum(self, nums: List[int], target: int) -> List[int]:for i in range(len(nums)):for j in range(i+1, len(nums)):if nums[i] + nums[j] == target:return [i,j]

字符串

1：151.翻转字符串里的单词

题目描述： 给定一个字符串，逐个翻转字符串中的每个单词。

  • 示例1：
    输入: “the sky is blue”
    输出: “blue is sky the”
  • 示例 2：
    输入: " hello world! "
    输出: “world! hello”
    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
  • 示例 3：
    输入: “a good example”
    输出: “example good a”
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路：
这道题目可以说是综合考察了字符串的多种操作。如果不要使用辅助空间，空间复杂度要求为O(1)。
不能使用辅助空间之后，那么只能在原字符串上下功夫了。想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。
所以解题思路如下：

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转

代码：

（版本一）先删除空白，然后整个反转，最后单词反转。 因为字符串是不可变类型，所以反转单词的时候，需要将其转换成列表，然后通过join函数再将其转换成列表，所以空间复杂度不是O(1)
class Solution:def reverseWords(self, s: str) -> str:# 删除前后空白s = s.strip()# 反转整个字符串s = s[::-1]# 将字符串拆分为单词，并反转每个单词s = ' '.join(word[::-1] for word in s.split())return s

（版本二）使用双指针
class Solution:def reverseWords(self, s: str) -> str:# 将字符串拆分为单词，即转换成列表类型words = s.split()# 反转单词left, right = 0, len(words) - 1while left < right:words[left], words[right] = words[right], words[left]left += 1right -= 1# 将列表转换成字符串return " ".join(words)
2：右旋字符串

题目描述：
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k，请编写一个函数，将字符串中的后面 k 个字符移到字符串的前面，实现字符串的右旋转操作。

例如，对于输入字符串 “abcdefg” 和整数 2，函数应该将其转换为 “fgabcde”。

输入：输入共包含两行，第一行为一个正整数 k，代表右旋转的位数。第二行为字符串 s，代表需要旋转的字符串。
输出：输出共一行，为进行了右旋转操作后的字符串。

  • 示例1：
    输入:2，abcdefg
    输出:fgabcde
    数据范围：1 <= k < 10000, 1 <= s.length < 10000;

思路：
为了让本题更有意义，提升一下本题难度：不能申请额外空间，只能在本串上操作。

本题中，我们需要将字符串右移n位，字符串相当于分成了两个部分，如果n为2，符串相当于分成了两个部分。右移n位， 就是将第二段放在前面，第一段放在后面，先不考虑里面字符的顺序，是不是整体倒叙不就行了。
其实，思路就是 通过 整体倒叙，把两段子串顺序颠倒，两个段子串里的的字符在倒叙一把，负负得正，这样就不影响子串里面字符的顺序了。

代码：

  • 时间复杂度: 涉及 index 的相关操作为 O(index), 其余为 O(1)
  • 空间复杂度: O(n)
#获取输入的数字k和字符串
k = int(input())
s = input()#通过切片反转第一段和第二段字符串
#注意：python中字符串是不可变的，所以也需要额外空间
s = s[len(s)-k:] + s[:len(s)-k]
print(s)k = int(input())
s = input()print(s[-k:] + s[:-k])
3：459.重复的子字符串

题目描述： 给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

  • 示例1：
    输入: “abab”
    输出: True
    解释: 可由子字符串 “ab” 重复两次构成。
  • 示例 2:
    输入: “aba”
    输出: False
  • 示例 3:
    输入: “abcabcabcabc”
    输出: True
    解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

思路：
暴力的解法， 就是一个for循环获取 子串的终止位置， 然后判断子串是否能重复构成字符串，又嵌套一个for循环，所以是O(n^2)的时间复杂度。
怎么一个for循环就可以获取子串吗？ 至少得一个for获取子串起始位置，一个for获取子串结束位置吧。
其实我们只需要判断，以第一个字母为开始的子串就可以，所以一个for循环获取子串的终止位置就行了。 而且遍历的时候 都不用遍历结束，只需要遍历到中间位置，因为子串结束位置大于中间位置的话，一定不能重复组成字符串。
暴力的解法，这里就不详细讲解了。

代码：

（版本一）前缀法 减一
class Solution:def repeatedSubstringPattern(self, s: str) -> bool:  if len(s) == 0:return Falsenxt = [0] * len(s)self.getNext(nxt, s)if nxt[-1] != -1 and len(s) % (len(s) - (nxt[-1] + 1)) == 0:return Truereturn Falsedef getNext(self, nxt, s):nxt[0] = -1j = -1for i in range(1, len(s)):while j >= 0 and s[i] != s[j+1]:j = nxt[j]if s[i] == s[j+1]:j += 1nxt[i] = jreturn nxt
（版本二）前缀表 不减一
class Solution:def repeatedSubstringPattern(self, s: str) -> bool:  if len(s) == 0:return Falsenxt = [0] * len(s)self.getNext(nxt, s)if nxt[-1] != 0 and len(s) % (len(s) - nxt[-1]) == 0:return Truereturn Falsedef getNext(self, nxt, s):nxt[0] = 0j = 0for i in range(1, len(s)):while j > 0 and s[i] != s[j]:j = nxt[j - 1]if s[i] == s[j]:j += 1nxt[i] = jreturn nxt
（版本三）使用find
class Solution:def repeatedSubstringPattern(self, s: str) -> bool:n = len(s)if n <= 1:return Falsess = s[1:] + s[:-1] print(ss.find(s))              return ss.find(s) != -1
（版本四）暴力法
class Solution:def repeatedSubstringPattern(self, s: str) -> bool:n = len(s)if n <= 1:return Falsesubstr = ""for i in range(1, n//2 + 1):if n % i == 0:substr = s[:i]if substr * (n//i) == s:return Truereturn False

来源于代码随想录的小记，官网上有详细的解析，需要的小伙伴可以去官网看哟~

这篇关于算法急救LeetCode62题-python版（2）/ 哈希表、字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1095366。

相关文章

Conda与Python venv虚拟环境的区别与使用方法详解

Conda与Python venv虚拟环境的区别与使用方法详解

《Conda与Pythonvenv虚拟环境的区别与使用方法详解》随着Python社区的成长,虚拟环境的概念和技术也在不断发展,：本文主要介绍Conda与Pythonvenv虚拟环境的区别与使用... 目录前言一、Conda 与 python venv 的核心区别1. Conda 的特点2. Python v
阅读更多...
Python使用python-can实现合并BLF文件

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库：CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合
阅读更多...
Python使用OpenCV实现获取视频时长的小工具

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文
阅读更多...
Python中你不知道的gzip高级用法分享

Python中你不知道的gzip高级用法分享

《Python中你不知道的gzip高级用法分享》在当今大数据时代,数据存储和传输成本已成为每个开发者必须考虑的问题,Python内置的gzip模块提供了一种简单高效的解决方案,下面小编就来和大家详细讲... 目录前言：为什么数据压缩如此重要1. gzip 模块基础介绍2. 基本压缩与解压缩操作2.1 压缩文
阅读更多...
Python设置Cookie永不超时的详细指南

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法（一）
阅读更多...
Python内置函数之classmethod函数使用详解

Python内置函数之classmethod函数使用详解

《Python内置函数之classmethod函数使用详解》：本文主要介绍Python内置函数之classmethod函数使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地... 目录1. 类方法定义与基本语法2. 类方法 vs 实例方法 vs 静态方法3. 核心特性与用法(1编程客
阅读更多...
Python函数作用域示例详解

Python函数作用域示例详解

《Python函数作用域示例详解》本文介绍了Python中的LEGB作用域规则,详细解析了变量查找的四个层级,通过具体代码示例,展示了各层级的变量访问规则和特性,对python函数作用域相关知识感兴趣... 目录一、LEGB 规则二、作用域实例2.1 局部作用域（Local）2.2 闭包作用域（Enclos
阅读更多...
Python实现对阿里云OSS对象存储的操作详解

Python实现对阿里云OSS对象存储的操作详解

《Python实现对阿里云OSS对象存储的操作详解》这篇文章主要为大家详细介绍了Python实现对阿里云OSS对象存储的操作相关知识,包括连接,上传,下载,列举等功能,感兴趣的小伙伴可以了解下... 目录一、直接使用代码二、详细使用1. 环境准备2. 初始化配置3. bucket配置创建4. 文件上传到os
阅读更多...
MySQL查询JSON数组字段包含特定字符串的方法

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案（推荐）2. 模糊匹配方案参数化查询示例使用场景建议性能优
阅读更多...
Java中的雪花算法Snowflake解析与实践技巧

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2