xXxYOLOxXx

xXxYOLOxXx

LeetCode病历表

Posted on Edited on In

做课程项目的时候发现自己对算法一无所知
刷刷题吧

两数之和

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力搜索，没啥好说的

1
2
3
4
5
6
7
class Solution:
	def twoSum(self, nums: List[int], target: int) -> List[int]:
		length = len(nums)
		for index1 in range(length):
			for index2 in range(index1+1, length):
				if nums[index1] + nums[index2] == target:
					return([index1, index2])

后来想了一下，可以从奇偶相加规律的角度进行优化

Odd+Odd=EvenOdd + Odd = Even
Odd+Even=OddOdd + Even = Odd
Even+Even=EvenEven + Even = Even

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
	def twoSum(self, nums: List[int], target: int) -> List[int]:
		odd = []
		even = []
		for index1 in nums: # 奇偶数分类
			if index1 % 2 == 0:
				even.append(index1)
			else:
				odd.append(index1)
		len_odd = len(odd)
		len_even = len(even)
		if target % 2 == 0: # 偶数
			if len_odd > 1:
				for index1 in range(len_odd):
					for index2 in range(index1+1, len_odd):
						if odd[index1] + odd[index2] == target:
							idx = nums.index(odd[index1])
							return([idx, nums.index(odd[index2], idx+1)])
			if len_even > 1:
				for index1 in range(len_even):
					for index2 in range(index1+1, len_even):
						if even[index1] + even[index2] == target:
							idx = nums.index(even[index1])
							return([idx, nums.index(even[index2], idx+1)])
		else: # 奇数
			for index1 in range(len_odd):
				for index2 in range(len_even):
					if odd[index1] + even[index2] == target:
						return([nums.index(odd[index1]), nums.index(even[index2])])

执行时间直接降了一半

两数相加

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字0之外，这两个数都不会以0开头。

示例 1：

1
2
3
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

1
2
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

1
2
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# Definition for singly-linked list.
# class ListNode:
#   def __init__(self, val=0, next=None):
#	   self.val = val
#	   self.next = next
class Solution:
	def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
		temp_node = ListNode()
		head = temp_node
		overflow = False
		while True: # 两个链表同步部分
			temp_node.val = l1.val + l2.val
			if overflow == True:
				overflow = False
				temp_node.val += 1
			if temp_node.val >= 10:
				overflow = True
				temp_node.val %= 10
			if l1.next != None and l2.next != None:
				temp_node.next = ListNode()
				l1 = l1.next
				l2 = l2.next
				temp_node = temp_node.next
			else:
				break
		if l1.next == None and l2.next == None: # 两个链表同时结束
			if overflow == True:
				temp_node.next = ListNode()
				temp_node = temp_node.next
				temp_node.val = 1
				overflow == False
			return(head)
		else: # 一个链表提前结束
			if l1.next != None:
				while True:
					l1 = l1.next
					temp_node.next = ListNode()
					temp_node = temp_node.next
					temp_node.val = l1.val
					if overflow == True:
						overflow = False
						temp_node.val += 1
					if temp_node.val >= 10:
						overflow = True
						temp_node.val %= 10
					if l1.next == None:
						break
			elif l2.next != None:
				while True:
					l2 = l2.next
					temp_node.next = ListNode()
					temp_node = temp_node.next
					temp_node.val = l2.val
					if overflow == True:
						overflow = False
						temp_node.val += 1
					if temp_node.val >= 10:
						overflow = True
						temp_node.val %= 10
					if l2.next == None:
						break
			if overflow == True: # 额外进位
				temp_node.next = ListNode()
				temp_node = temp_node.next
				temp_node.val = 1
				overflow == False
			return(head)

几个坑有点麻烦

  1. 两个链表长度不同，还得分l1、l2两种情况
  2. 进位，基本每一步计算都要检测进位
  3. 额外进位，两个二位数加出来一个三位数

无重复字符的最长子串

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是"wke"，所以其长度为 3。
	 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。

示例 4:

1
2
输入: s = ""
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
	def lengthOfLongestSubstring(self, s: str) -> int:
		length = len(s)
		if length == 0:
			return(0)
		elif length == 1:
			return(1)
		else:
			sub_len = 0
			for index1 in range(length):
				for index2 in range(index1+1, length):
					if s[index2] in s[index1:index2]:
						temp_len = index2 - index1
						if temp_len > sub_len:
							sub_len = temp_len
						break
					if index2 == length - 1:
						temp_len = index2 + 1 - index1
						if temp_len > sub_len:
							sub_len = temp_len
			return(sub_len)

依旧暴力搜索，有几个坑

  1. 空串
  2. 单字符
  3. 子串结尾与母串结尾相同

寻找两个正序数组的中位数

给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。

示例 1：

1
2
3
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

1
2
3
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：

1
2
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

1
2
输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

1
2
输入：nums1 = [2], nums2 = []
输出：2.00000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
class Solution:
	def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
		new_list = nums1 + nums2
		new_list.sort()
		length = len(new_list)
		if length % 2 == 1:
			mid_num = new_list[(length - 1)//2]
		else:
			mid_num = (new_list[(length)//2 - 1] + new_list[(length)//2]) / 2
		return(mid_num)

list().sort() yyds

最长回文子串

给你一个字符串s，找到s中最长的回文子串。

示例 1：

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

1
2
输入：s = "cbbd"
输出："bb"

示例 3：

1
2
输入：s = "a"
输出："a"

示例 4：

1
2
输入：s = "ac"
输出："a"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	def longestPalindrome(self, s: str) -> str:
		length = len(s)
		if length == 1:
			return(s)
		else:
			sub_str = ""
			sub_len = 0
			for index1 in range(length):
				for index2 in range(length-1, index1-1, -1):
					if s[index2] == s[index1] and s[index1:index2+1] == s[index1:index2+1][::-1]:
						temp_len = index2 + 1 - index1
						if temp_len > sub_len:
							sub_len = temp_len
							sub_str = s[index1:index2+1]
						break
			return(sub_str)

看到"ccc"这个测试数据人都傻了
换个角度思考，逆向搜寻字符串就好解决这事了

Z 字形变换

将一个给定字符串s根据给定的行数numRows，以从上往下、从左到右进行Z字形排列。

比如输入字符串为"PAYPALISHIRING"行数为3时，排列如下：

1
2
3
P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

1
string convert(string s, int numRows);

示例 1：

1
2
输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

1
2
3
4
5
6
7
输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P	 I	N
A   L S  I G
Y A   H R
P	 I

示例 3：

1
2
输入：s = "A", numRows = 1
输出："A"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zigzag-conversion
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
	def convert(self, s: str, numRows: int) -> str:
		if numRows == 1:
			return(s)
		length = len(s)
		forward = True
		y = -1
		lst = []
		for _ in range(numRows):
			lst.append("")
		for index in range(0, length):
			if forward == True:
				y += 1
				lst[y] += s[index]
				if y == numRows-1:
					forward = False
			else:
				y -= 1
				lst[y] += s[index]
				if y == 0:
					forward = True
		result = ""
		for _ in lst:
			result += _
		return(result)

一开始各种算形状的周期、余数、重复次数
然后拿这些玩意算矩阵宽度
再造一个二维列表当矩阵
看到用时超过11%，内存超过7%就知道自己在犯病了

直接把这个题想象成一维的来回扫描模型就好多了

整数反转

给你一个32位的有符号整数x，返回将x中的数字部分反转后的结果。

如果反转后整数超过32位的有符号整数的范围[−231,231−1][-2^{31}, 2^{31} - 1]，就返回0。

假设环境不允许存储64位整数（有符号或无符号）。

示例 1：

1
2
输入：x = 123
输出：321

示例 2：

1
2
输入：x = -123
输出：-321

示例 3：

1
2
输入：x = 120
输出：21

示例 4：

1
2
输入：x = 0
输出：0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
	def reverse(self, x: int) -> int:
		temp = []
		negative = False
		if x < 0:
			negative = True
			x = - x
		while x != 0:
			temp.append(x % 10)
			x //= 10
		cnt = 0
		num = 0
		for _ in range(-1, -len(temp)-1, -1):
			num += temp[_] * pow(10, cnt)
			cnt += 1
		if negative == True and num <= pow(2,31):
			num = -num
			return(num)
		elif negative == False and num <= pow(2,31) - 1:
			return(num)
		else:
			return(0)

挨个模10取余数丢列表
然后反向读列表就行
速度不错，但是内存太高了

字符串转换整数 (atoi)

请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的atoi函数）。

函数myAtoi(string s)的算法如下：

  • 读入字符串并丢弃无用的前导空格
  • 检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  • 读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
  • 将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
  • 如果整数数超过32位有符号整数范围[−231,231−1][-2^{31}, 2^{31} - 1]，需要截断这个整数，使其保持在这个范围内。具体来说，小于−231-2^{31}的整数应该被固定为−231-2^{31}，大于231−12^{31}-1的整数应该被固定为231−12^{31}-1。
  • 返回整数作为最终结果。

注意：
本题中的空白字符只包括空格字符’ '。
除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

示例1：

1
2
3
4
5
6
7
8
9
10
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
		 ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
		 ^
第 3 步："42"（读入 "42"）
		   ^
解析得到整数 42 。

由于 “42” 在范围[−231,231−1][-2^{31}, 2^{31} - 1]内，最终结果为 42 。

示例2：

1
2
3
4
5
6
7
8
9
10
输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
			^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
			 ^
第 3 步："   -42"（读入 "42"）
			   ^
解析得到整数 -42 。

由于 “-42” 在范围[−231,231−1][-2^{31}, 2^{31} - 1]内，最终结果为 -42 。

示例3：

1
2
3
4
5
6
7
8
9
10
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
		 ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
		 ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
			 ^
解析得到整数 4193 。

由于 “4193” 在范围[−231,231−1][-2^{31}, 2^{31} - 1]内，最终结果为 4193 。

示例4：

1
2
3
4
5
6
7
8
9
10
输入：s = "words and 987"
输出：0
解释：
第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
		 ^
第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
		 ^
第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
		 ^
解析得到整数 0 ，因为没有读入任何数字。

由于 0 在范围[−231,231−1][-2^{31}, 2^{31} - 1]内，最终结果为 0 。

示例5：

1
2
3
4
5
6
7
8
9
10
输入：s = "-91283472332"
输出：-2147483648
解释：
第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
		 ^
第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
		  ^
第 3 步："-91283472332"（读入 "91283472332"）
					 ^
解析得到整数 -91283472332 。

由于 -91283472332 小于范围[−231,231−1][-2^{31}, 2^{31} - 1]的下界，最终结果被截断为−231-2^{31} = -2147483648 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
def myAtoi(self, s: str) -> int:
	s = s.strip()
	length = len(s)
	flag = True
	if length == 0 or s[0] not in "+-0123456789":
		return(0)
	if s[0] == "+":
		s = s[1:]
	elif s[0] == "-":
		flag = False
		s = s[1:]
	num_list = []
	for _ in s:
		if _ in "0123456789":
			num_list.append(_)
		else:
			break
	num_sum = 0
	index = 0
	for _ in range(-1, -len(num_list)-1, -1):
		num_sum += int(num_list[_]) * pow(10, index)
		index += 1
	if flag == True:
		if num_sum <= pow(2, 31) - 1:
			return(num_sum)
		else:
			return(pow(2, 31) - 1)
	elif num_sum <= pow(2, 31):
		return(-num_sum)
	else:
		return(-pow(2, 31))

和整数反转那题思路差不多
无非多做几个检测罢了

回文数

给你一个整数x，如果x是一个回文整数，返回true；否则，返回false。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121是回文，而123不是。

示例 1：

1
2
输入：x = 121
输出：true

示例2：

1
2
3
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

1
2
3
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

示例 4：

1
2
输入：x = -101
输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
class Solution:
	def isPalindrome(self, x: int) -> bool:
		if x < 0:
			return(False)
		string = str(x)
		if string == string[::-1]:
			return(True)
		else:
			return(False)

当字符串来处理挺方便的
就是有点占内存

正则表达式匹配

给你一个字符串s和一个字符规律p，请你来实现一个支持'.'和'\*'的正则表达式匹配。

  • ‘.’ 匹配任意单个字符
  • ‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
示例 1：

1
2
3
输入：s = "aa" p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。

示例 2:

1
2
3
输入：s = "aa" p = "a*"
输出：true
解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例3：

1
2
3
输入：s = "ab" p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4：

1
2
3
输入：s = "aab" p = "c*a*b"
输出：true
解释：因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5：

1
2
输入：s = "mississippi" p = "mis*is*p*."
输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
class Solution:
	def isMatch(self, s: str, p: str) -> bool:
		import re
		length = len(s)
		result = re.match(p, s)
		if result != None and result.span()[1] == length:
			return(True)
		else:
			return(False)

属实不会去写正则的匹配规则
直接re.match梭哈了

盛最多水的容器

给你n个非负整数a1,a2,...,anaa_1, a_2, ..., a_na ，每个数代表坐标中的一个点(i,ai)。在坐标内画n条垂直线，垂直线i的两个端点分别为(i,ai)和(i, 0)。找出其中的两条线，使得它们与x轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器。

示例 1：

1
2
3
输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为49。

示例 2：

1
2
输入：height = [1,1]
输出：1

示例 3：

1
2
输入：height = [4,3,2,1,4]
输出：16

示例 4：

1
2
输入：height = [1,2,1]
输出：2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
	def maxArea(self, height) -> int:
		length = len(height)
		area = 0
		h = 0
		index1 = 0
		index2 = length - 1
		for _ in range(length):
			if height[index1] >= height[index2]:
				h = height[index2]
				index2 -= 1
			else:
				h = height[index1]
				index1 += 1
			temp = h * (index2 + 1 - index1)
			if temp > area:
				area = temp
		return(area)

自己逻辑都还没理清楚，代码就能跑了
一开始想二维查找梭哈，然后死在一个长度5000的列表上了
旧症复发了属于是
然后开始用一维的角度去思考
AB分别为初始值在列表两端的下标，两边往中间回缩（中间往两边跑也行）
A大就挪B，反之亦然

整数转罗马数字

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

1
2
3
4
5
6
7
8
字符		数值
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:

1
2
输入:num = 3
输出: "III"

示例2:

1
2
输入:num = 4
输出: "IV"

示例3:

1
2
输入:num = 9
输出: "IX"

示例4:

1
2
3
输入:num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例5:

1
2
3
输入:num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/integer-to-roman
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution:
	def intToRoman(self, num: int) -> str:
		num_list = []
		while num != 0:
			num_list.append(num % 10)
			num //= 10
		result = ""
		for _ in range(len(num_list)):
			if _ == 0:
				if num_list[_] == 0:
					continue
				elif num_list[_] <= 3:
					result = "I" * num_list[_] + result
				else:
					diff = num_list[_] - 5
					mod = num_list[_] % 5
					if diff == -1:
						result =  "IV" + result
					elif mod < 4:
						result = "V" + "I" * mod + result
					else:
						result = "IX" + result
			elif _ == 1:
				if num_list[_] == 0:
					continue
				elif num_list[_] <= 3:
					result = "X" * num_list[_] + result
				else:
					diff = num_list[_] - 5
					mod = num_list[_] % 5
					if diff == -1:
						result = "XL" + result
					elif mod < 4:
						result = "L" + "X" * mod + result
					else:
						result = "XC" + result
			elif _ == 2:
				if num_list[_] == 0:
					continue
				elif num_list[_] <= 3:
					result = "C" * num_list[_] + result
				else:
					diff = num_list[_] - 5
					mod = num_list[_] % 5
					if diff == -1:
						result = "CD" + result
					elif mod < 4:
						result = "D" + "C" * mod + result
					else:
						result = "CM" + result
			elif _ == 3:
				result = "M" * num_list[_] + result
		return(result)

一个挺中庸的解决方案
为了解决问题而解决问题

罗马数字转整数

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

1
2
3
4
5
6
7
8
字符		数值
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到 3999 的范围内。
示例1:

1
2
输入:"III"
输出: 3

示例2:

1
2
输入:"IV"
输出: 4

示例3:

1
2
输入:"IX"
输出: 9

示例4:

1
2
3
输入:"LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例5:

1
2
3
输入:"MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/roman-to-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
class Solution:
	def romanToInt(self, s: str) -> int:
		length = len(s)
		number = 0
		if s[0] == "M":
			_ = 0
			while s[_] == "M":
				_ += 1
				if _ == length:
					break
			s = s[_:]
			number += 1000 * _
			length -= _
			if length == 0:
				return(number)
		if s[0] == "C":
			if length == 1:
				number += 100
				length -= 1
			elif s[1] == "M":
				number += 900
				length -= 2
				s = s[2:]
			elif s[1] == "D":
				number += 400
				length -= 2
				s = s[2:]
			else:
				_ = 0
				while s[_] == "C":
					_ += 1
					if _ == length:
						break
				s = s[_:]
				number += 100 * _
				length -= _
			if length == 0:
				return(number)
		if s[0] == "D":
			number += 500
			length -= 1
			s = s[1:]
			if length == 0:
				return(number)
			_ = 0
			if s[_] == "C":
				while s[_] == "C":
					_ += 1
					if _ == length:
						break
			s = s[_:]
			number += 100 * _
			length -= _
			if length == 0:
				return(number)
		if s[0] == "X":
			if length == 1:
				number += 10
				length -= 1
			elif s[1] == "C":
				number += 90
				length -= 2
				s = s[2:]
			elif s[1] == "L":
				number += 40
				length -= 2
				s = s[2:]
			else:
				_ = 0
				while s[_] == "X":
					_ += 1
					if _ == length:
						break
				s = s[_:]
				number += 10 * _
				length -= _
			if length == 0:
				return(number)
		if s[0] == "L":
			number += 50
			length -= 1
			s = s[1:]
			if length == 0:
				return(number)
			_ = 0
			if s[_] == "X":
				while s[_] == "X":
					_ += 1
					if _ == length:
						break
			s = s[_:]
			number += 10 * _
			length -= _
			if length == 0:
				return(number)
		if s[0] == "I":
			if length == 1:
				number += 1
				length -= 1
			elif s[1] == "X":
				number += 9
				length -= 2
				s = s[2:]
			elif s[1] == "V":
				number += 4
				length -= 2
				s = s[2:]
			else:
				_ = 0
				while s[_] == "I":
					_ += 1
					if _ == length:
						break
				s = s[_:]
				number += 1 * _
				length -= _
			if length == 0:
				return(number)
		if s[0] == "V":
			number += 5
			length -= 1
			s = s[1:]
			if length == 0:
				return(number)
			_ = 0
			if s[_] == "I":
				while s[_] == "I":
					_ += 1
					if _ == length:
						break
			s = s[_:]
			number += 1 * _
			length -= _
			if length == 0:
				return(number)

实在想不出啥好的算法了
只能摆烂了

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串""。

示例 1：

1
2
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

1
2
3
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
	def longestCommonPrefix(self, strs: List[str]) -> str:
		length = 0
		if len(strs) == 1:
			return(strs[0])
		if "" in strs:
			return("")
		while True:
			for _ in range(1, len(strs)):
				if not strs[_].startswith(strs[0][:length]):
					return(strs[0][:length-1])
			if length == len(strs[0]):
				return(strs[0])
			length += 1

懒得写匹配
直接用startswith了

三数之和

给你一个包含n个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得a + b + c = 0 ？请你找出所有和为0且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

1
2
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

1
2
输入：nums = []
输出：[]

示例 3：

1
2
输入：nums = [0]
输出：[]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
	def threeSum(self, nums: List[int]) -> List[List[int]]:
		nums.sort()
		length = len(nums)
		if length < 3:
			return([])
		neg_count = 0
		for _ in nums:
			if _ < 0:
				neg_count += 1
			elif _ == 0:
				neg_count += 1
				break
		if neg_count == 0 or nums[-1] < 0:
			return([])
		result = []
		for _ in range(0, neg_count):
			c = -nums[_]
			a = _ + 1
			b = length - 1
			while a < b:
				if nums[a] + nums[b] == c:
					temp = [-c, nums[a], nums[b]]
					if temp not in result:
						result.append(temp)
					a += 1
					b -= 1
				elif nums[a] + nums[b] > c:
					b -= 1
				elif nums[a] + nums[b] < c:
					a += 1
		return(result)

实在想不出来咋做，看了下别人的题解
三个数之和为0在除了三个数都为0的情况下，至少有一个负数的存在
遍历所有的负数，两个下标分别指向c的下一位与结尾
通过a+b与-c的关系来移动a、b

最接近的三数之和

给定一个包括n个整数的数组nums和一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例：

1
2
3
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class Solution:
	def threeSumClosest(self, nums: List[int], target: int) -> int:
		length = len(nums)
		if length < 3:
			return([])
		nums.sort()
		if target >= 0:
			if target < nums[0]:
				return(nums[0] + nums[1] + nums[2])
			neg_count = 0
			for _ in nums:
				if _ < target:
					neg_count += 1
				elif _ == target:
					neg_count += 1
					break
			sub = 9999
			result = 0
			for _ in range(0, neg_count):
				c = -nums[_]
				a = _ + 1
				b = length - 1
				while a < b:
					if sub == 0:
						break
					if nums[a] + nums[b] == c + target:
						result = target
						sub = 0
						break
					elif nums[a] + nums[b] > c + target:
						temp = abs(nums[a] + nums[b] - c - target)
						if temp < sub:
							sub = temp
							result = nums[a] + nums[b] - c
						b -= 1
					elif nums[a] + nums[b] < c + target:
						temp = abs(nums[a] + nums[b] - c - target)
						if temp < sub:
							sub = temp
							result = nums[a] + nums[b] - c
						a += 1
			return(result)
		elif target < 0:
			nums = nums[::-1]
			print(nums)
			if target > nums[0]:
				return(nums[0] + nums[1] + nums[2])
			neg_count = 0
			for _ in nums:
				if _ > target:
					neg_count += 1
				elif _ == target:
					neg_count += 1
					break
			sub = 9999
			result = 0
			for _ in range(0, neg_count):
				c = -nums[_]
				a = _ + 1
				b = length - 1
				while a < b:
					if sub == 0:
						break
					if nums[a] + nums[b] == c + target:
						result = target
						sub = 0
						break
					elif nums[a] + nums[b] > c + target:
						temp = abs(nums[a] + nums[b] - c - target)
						if temp < sub:
							sub = temp
							result = nums[a] + nums[b] - c
						a += 1
					elif nums[a] + nums[b] < c + target:
						temp = abs(nums[a] + nums[b] - c - target)
						if temp < sub:
							sub = temp
							result = nums[a] + nums[b] - c
						b -= 1
			return(result)

跟上一题差不多的思路，加了点变化罢了
分了target正负两种情况来处理
但是写得太拉了

算法就图一乐，收收心干安服辣

EOF