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

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
python: 多模块(.py)中全局变量的导入

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别： 当你在一个模块（文件）中使用 global 声明变量时，这个变量只在该模块的全局命名空
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...
usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。 代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2