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

2024-08-22 05:28

本文主要是介绍算法急救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

相关文章

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

MySQL字符串常用函数详解

《MySQL字符串常用函数详解》本文给大家介绍MySQL字符串常用函数,本文结合实例代码给大家介绍的非常详细,对大家学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录mysql字符串常用函数一、获取二、大小写转换三、拼接四、截取五、比较、反转、替换六、去空白、填充MySQL字符串常用函数一、

基于Python开发一个图像水印批量添加工具

《基于Python开发一个图像水印批量添加工具》在当今数字化内容爆炸式增长的时代,图像版权保护已成为创作者和企业的核心需求,本方案将详细介绍一个基于PythonPIL库的工业级图像水印解决方案,有需要... 目录一、系统架构设计1.1 整体处理流程1.2 类结构设计(扩展版本)二、核心算法深入解析2.1 自

从入门到进阶讲解Python自动化Playwright实战指南

《从入门到进阶讲解Python自动化Playwright实战指南》Playwright是针对Python语言的纯自动化工具,它可以通过单个API自动执行Chromium,Firefox和WebKit... 目录Playwright 简介核心优势安装步骤观点与案例结合Playwright 核心功能从零开始学习

Python 字典 (Dictionary)使用详解

《Python字典(Dictionary)使用详解》字典是python中最重要,最常用的数据结构之一,它提供了高效的键值对存储和查找能力,:本文主要介绍Python字典(Dictionary)... 目录字典1.基本特性2.创建字典3.访问元素4.修改字典5.删除元素6.字典遍历7.字典的高级特性默认字典

Python自动化批量重命名与整理文件系统

《Python自动化批量重命名与整理文件系统》这篇文章主要为大家详细介绍了如何使用Python实现一个强大的文件批量重命名与整理工具,帮助开发者自动化这一繁琐过程,有需要的小伙伴可以了解下... 目录简介环境准备项目功能概述代码详细解析1. 导入必要的库2. 配置参数设置3. 创建日志系统4. 安全文件名处

使用Python构建一个高效的日志处理系统

《使用Python构建一个高效的日志处理系统》这篇文章主要为大家详细讲解了如何使用Python开发一个专业的日志分析工具,能够自动化处理、分析和可视化各类日志文件,大幅提升运维效率,需要的可以了解下... 目录环境准备工具功能概述完整代码实现代码深度解析1. 类设计与初始化2. 日志解析核心逻辑3. 文件处

python生成随机唯一id的几种实现方法

《python生成随机唯一id的几种实现方法》在Python中生成随机唯一ID有多种方法,根据不同的需求场景可以选择最适合的方案,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起学习学习... 目录方法 1:使用 UUID 模块(推荐)方法 2:使用 Secrets 模块(安全敏感场景)方法

使用Python删除Excel中的行列和单元格示例详解

《使用Python删除Excel中的行列和单元格示例详解》在处理Excel数据时,删除不需要的行、列或单元格是一项常见且必要的操作,本文将使用Python脚本实现对Excel表格的高效自动化处理,感兴... 目录开发环境准备使用 python 删除 Excphpel 表格中的行删除特定行删除空白行删除含指定