一、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 = 0
for 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 False
fast=head
slow=head
while fast and fast.next:
fast=fast.next.next
slow=slow.next
if fast == slow:
return True
return False
三、160. 相交链表
class Solution:
def getIntersetionNode(self,headA,headB):
d={}
while headA:
d[headA]=headA
headA=headA.next
while headB:
if d.get(headB):
return headB
headB=headB.next
return 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 = 0
for i in range(len(str(n))):
sum += int(str(n)[i]) ** 2
return sum
def ishappy(self, n: int):
record = set()
res = self.calculate(n)
while res != 1:
if res in record:
return False
record.add(res)
res = self.calculate(res)
return True
s = 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 False
else:
d[s[i]]=t[i]
else:
if d[s[i]]!=t[i]:
return False
return True
s = "paper"
t = "title"
r=Solution()
print(r.func205(s, t))
