算法急救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。

相关文章

python管理工具之conda安装部署及使用详解

python管理工具之conda安装部署及使用详解

《python管理工具之conda安装部署及使用详解》这篇文章详细介绍了如何安装和使用conda来管理Python环境,它涵盖了从安装部署、镜像源配置到具体的conda使用方法,包括创建、激活、安装包... 目录pytpshheraerUhon管理工具：conda部署+使用一、安装部署1、 下载2、 安装3
阅读更多...
Python进阶之Excel基本操作介绍

Python进阶之Excel基本操作介绍

《Python进阶之Excel基本操作介绍》在现实中,很多工作都需要与数据打交道,Excel作为常用的数据处理工具,一直备受人们的青睐,本文主要为大家介绍了一些Python中Excel的基本操作,希望... 目录概述写入使用 xlwt使用 XlsxWriter读取修改概述在现实中，很多工作都需要与数据打交
阅读更多...
使用Python实现在Word中添加或删除超链接

使用Python实现在Word中添加或删除超链接

《使用Python实现在Word中添加或删除超链接》在Word文档中,超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能,本文将为大家介绍一下Python如何实现在Word中添加或... 在Word文档中，超链接是一种将文本或图像连接到其他文档、网页或同一文档中不同部分的功能。通过添加超
阅读更多...
Python MySQL如何通过Binlog获取变更记录恢复数据

Python MySQL如何通过Binlog获取变更记录恢复数据

《PythonMySQL如何通过Binlog获取变更记录恢复数据》本文介绍了如何使用Python和pymysqlreplication库通过MySQL的二进制日志（Binlog）获取数据库的变更记录... 目录python mysql通过Binlog获取变更记录恢复数据1.安装pymysqlreplicat
阅读更多...
利用Python编写一个简单的聊天机器人

利用Python编写一个简单的聊天机器人

《利用Python编写一个简单的聊天机器人》这篇文章主要为大家详细介绍了如何利用Python编写一个简单的聊天机器人,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 使用 python 编写一个简单的聊天机器人可以从最基础的逻辑开始，然后逐步加入更复杂的功能。这里我们将先实现一个简单的
阅读更多...
Java 字符数组转字符串的常用方法

Java 字符数组转字符串的常用方法

《Java字符数组转字符串的常用方法》文章总结了在Java中将字符数组转换为字符串的几种常用方法,包括使用String构造函数、String.valueOf()方法、StringBuilder以及A... 目录1. 使用String构造函数1.1 基本转换方法1.2 注意事项2. 使用String.valu
阅读更多...
基于Python开发电脑定时关机工具

基于Python开发电脑定时关机工具

《基于Python开发电脑定时关机工具》这篇文章主要为大家详细介绍了如何基于Python开发一个电脑定时关机工具,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. 简介2. 运行效果3. 相关源码1. 简介这个程序就像一个“忠实的管家”，帮你按时关掉电脑，而且全程不需要你多做
阅读更多...
Python实现高效地读写大型文件

Python实现高效地读写大型文件

《Python实现高效地读写大型文件》Python如何读写的是大型文件,有没有什么方法来提高效率呢,这篇文章就来和大家聊聊如何在Python中高效地读写大型文件,需要的可以了解下... 目录一、逐行读取大型文件二、分块读取大型文件三、使用 mmap 模块进行内存映射文件操作（适用于大文件）四、使用 pand
阅读更多...
python实现pdf转word和excel的示例代码

python实现pdf转word和excel的示例代码

《python实现pdf转word和excel的示例代码》本文主要介绍了python实现pdf转word和excel的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价... 目录一、引言二、python编程1，PDF转Word2，PDF转Excel三、前端页面效果展示总结一
阅读更多...
Python xmltodict实现简化XML数据处理

Python xmltodict实现简化XML数据处理

《Pythonxmltodict实现简化XML数据处理》Python社区为提供了xmltodict库,它专为简化XML与Python数据结构的转换而设计,本文主要来为大家介绍一下如何使用xmltod... 目录一、引言二、XMLtodict介绍设计理念适用场景三、功能参数与属性1、parse函数2、unpa
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2