Leetcode按类型
字符串、模拟法
数组遍历框架
数组遍历框架,典型的线性迭代结构:
void traverse(int[] arr)
{
for (int i = 0; i < arr.length; i++) {
// 迭代访问 arr[i]
}
}
总结
标准数组生成字典及字典排序方法
1
2
3
4
5
6
7
8
9
ratings_dict = {}
for i in range(len(ratings)):
if ratings[i] not in ratings_dict.keys():
ratings_dict[ratings[i]] = [i]
else:
ratings_dict[ratings[i]].append(i)
# sort
ratings_sorted = dict(sorted(ratings_dict.items(), key = lambda ratings_dict:ratings_dict[0]))
print(ratings_sorted)
集合移除左半部分方法
1
2
while s[i] in lookup:
lookup.remove(s[left])
✅(1.5h) 93. 复原IP地址
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成)，整数之间用 ‘.’ 分隔。
1
2
3
4
5
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def restoreIpAddresses(self, s: str) -> List[str]:
count = []
for i in range(1,4):
for j in range(1,4):
for k in range(1,4):
for l in range(1,4):
if len(s) == i+j+k+l:
printstate = True
if int(s[:i]) < 256 and int(s[i:i+j]) < 256 and int(s[i+j:i+j+k]) < 256 and int(s[i+j+k:i+j+k+l]) < 256:
for ss in [s[:i],s[i:i+j], s[i+j:i+j+k],s[i+j+k:i+j+k+l]]:
if ss[0] == '0' and len(ss)>1:
printstate = False
if printstate == True:
count.append(s[:i] +'.'+ s[i:i+j] +'.'+ s[i+j:i+j+k] +'.'+ s[i+j+k:i+j+k+l])
print(count)
return count
1
2
3
4
5
6
from typing import List
nums = "25525511135"
solution = Solution()
result = solution.restoreIpAddresses(nums)
result
🚩(1.5h) 6. Z 字形变换
难度中等877收藏分享切换为英文接收动态反馈
将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。
比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
1
L C I R E T O E S I I G E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。
请你实现这个将字符串进行指定行数变换的函数：
1
string convert(string s, int numRows);
1
示例 1:输入: s = "LEETCODEISHIRING", numRows = 3输出: "LCIRETOESIIGEDHN"示例 2:输入: s = "LEETCODEISHIRING", numRows = 4输出: "LDREOEIIECIHNTSG"解释:L D RE O E I IE C I H NT S G
✅(1.5h) 8. 字符串转换整数 (atoi)
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
- 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
- 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
- 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
- 本题中的空白字符只包括空格字符
' '。 - 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
1
class Solution: def helper(self,s): for i, word in enumerate(s): if word not in '1234567890': return int(s[:i]) return int(s) def myAtoi(self, s: str) -> int: for i, word in enumerate(s): if word not in ' -+1234567890': return 0 elif word in '-+': if len(s) > i+1 and s[i+1] in '1234567890': res = self.helper(s[i+1:]) * -1 if word is '-' else self.helper(s[i+1:]) return max( min( res, 2147483647), -2147483648) else: return 0 elif word in '1234567890': res = self.helper(s[i:]) return max( min( res, 2147483647), -2147483648) return 0 ## 法2 正则 34% # def myAtoi(self, s: str) -> int: # return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
✅(1.5h) 12. 整数转罗马数字
罗马数字包含以下七种字符： 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 到 3999 的范围内。
1
示例 1:输入: 3输出: "III"示例 2:输入: 4输出: "IV"示例 3:输入: 9输出: "IX"示例 4:输入: 58输出: "LVIII"解释: L = 50, V = 5, III = 3.示例 5:输入: 1994输出: "MCMXCIV"解释: M = 1000, CM = 900, XC = 90, IV = 4.
✅(50m) 13. 罗马数字转整数
罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。
1
**字符** **数值** 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:输入: "III"输出: 3示例 2:输入: "IV"输出: 4示例 3:输入: "IX"输出: 9示例 4:输入: "LVIII"输出: 58解释: L = 50, V= 5, III = 3.示例 5:输入: "MCMXCIV"输出: 1994解释: M = 1000, CM = 900, XC = 90, IV = 4.
🚩(2.0h) 31. 下一个排列
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列(即升序排列)。
必须原地修改，只允许使用额外常数空间。
1
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1
算法思路：
- 将后面的大数与前面的小数字交换
- 增加幅度尽量小
- 低位交换，从后向前找 ✅
- 找尽量接近(小)的大数替换 ✅
- 重置为升序排序
1
class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ if len(nums) < 2: return 0 for i in range(len(nums)-1,0,-1): if nums[i] > nums[i-1]: nums[i:] = sorted(nums[i:]) for j in range(i, len(nums)): if nums[j] > nums[i-1]: # 找最接近的进行替换 nums[j], nums[i-1] = nums[i-1], nums[j] break return nums.sort()
1
from typing import Listnums = [1,3,2]solution = Solution()result = solution.nextPermutation(nums)result
✅(40m) 89. 格雷编码
✅(15m) 1603. 设计停车系统
##
