【数据结构与算法】之哈希系表系列-20240128

本文主要是介绍【数据结构与算法】之哈希系表系列-20240128，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

这里写目录标题

一、13. 罗马数字转整数
二、141. 环形链表
三、160. 相交链表
四、202. 快乐数
五、205. 同构字符串

一、13. 罗马数字转整数

简单
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如，罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。

示例 1:
输入: s = “III”
输出: 3

示例 2:
输入: s = “IV”
输出: 4

示例 3:
输入: s = “IX”
输出: 9

示例 4:
输入: s = “LVIII”
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:
输入: s = “MCMXCIV”
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

def func(s):dic = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}res = 0for i in range(1, len(s)):if dic[s[i]] > dic[s[i - 1]]:res = res - dic[s[i - 1]]else:res = res + dic[s[i - 1]]return res + dic[s[-1]]s = "LVIII"
print(func(s))

二、141. 环形链表

简单
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

思路：
使用快慢指针：
若无环，那么fast指针会先执行null
若有环，fast和slow迟早会在环中相遇

class Solution:def func141(self,head,pos):if not head or head.next == None:return Falsefast=headslow=headwhile fast and fast.next:fast=fast.next.nextslow=slow.nextif fast == slow:return Truereturn False

三、160. 相交链表

在这里插入图片描述

class Solution:def getIntersetionNode(self,headA,headB):d={}while headA:d[headA]=headAheadA=headA.nextwhile headB:if d.get(headB):return headBheadB=headB.nextreturn None

四、202. 快乐数

简单
相关标签
相关企业
编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
如果这个过程结果为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：
输入：n = 2
输出：false

class Solution:def calculate(self, n: int):sum = 0for i in range(len(str(n))):sum += int(str(n)[i]) ** 2return sumdef ishappy(self, n: int):record = set()res = self.calculate(n)while res != 1:if res in record:return Falserecord.add(res)res = self.calculate(res)return Trues = Solution()
n = 2
print(s.ishappy(n))

五、205. 同构字符串

简单
给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:
输入：s = “egg”, t = “add”
输出：true

示例 2：
输入：s = “foo”, t = “bar”
输出：false

示例 3：
输入：s = “paper”, t = “title”
输出：true

class Solution:def func205(self,s,t):d={}for i in range(len(s)):if s[i] not in d:if t[i] in d.values():return Falseelse:d[s[i]]=t[i]else:if d[s[i]]!=t[i]:return Falsereturn True
s = "paper"
t = "title"
r=Solution()
print(r.func205(s, t))