LeetCode
1. Two Sum¶
class Solution: # (1)
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]
2025/03/26
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
2. Add Two Numbers¶
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution: # (1)
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
current = dummy
carry = 0
while l1 or l2 or carry:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
sum = val1 + val2 + carry
carry = sum // 10
current.next = ListNode(sum % 10)
current = current.next
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next
- 2025/03/27
# Remark: 思想一致
def create_linked_list(values):
dummy = ListNode()
current = dummy
for val in values:
current.next = ListNode(val)
current = current.next
return dummy.next
l1 = create_linked_list([2, 4, 3])
l2 = create_linked_list([5, 6, 4])
while l1:
print(l1.val) # 2\n 4\n 3
l1 = l1.next
// typedef struct ListNode {
// int val;
// struct ListNode* next;
// } ListNode;
// 避免一直写struct, 直接用typedef
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
dummy->next = NULL;
ListNode* current = dummy;
int carry = 0;
while (l1 || l2 || carry) {
int a = l1 ? l1->val : 0;
int b = l2 ? l2->val : 0;
int sum = a + b + carry;
carry = sum / 10;
current->next = (ListNode*)malloc(sizeof(ListNode));
current->next->val = sum % 10;
current->next->next = NULL;
current = current->next;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
ListNode* result = dummy->next;
free(dummy); // 避免内存泄漏
return result;
}
// Remark: 思想一致
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->val = val;
newNode->next = NULL;
return newNode;
}
ListNode* createList(int* nums, int size) {
ListNode* dummy = createNode(0);
ListNode* current = dummy;
for (int i = 0; i < size; i++) {
current->next = createNode(nums[i]);
current = current->next;
}
return dummy->next;
}
int main() {
int nums[] = {2, 4, 3};
int nums[] = {5, 6, 4};
ListNode* l1 = createList(nums, 3);
ListNode* l2 = createList(nums, 3);
ListNode* result = addTwoNumbers(l1, l2);
free(l1);
free(l2);
free(result);
return 0;
}
3. Longest Substring Without Repeating Characters¶
class Solution: # (1) 运行提交笑嘻嘻，一看击败百分七🤡
def lengthOfLongestSubstring(self, s: str) -> int:
countset = []
for num, i in enumerate(s):
count = 1
ls = [i]
for j in range(num+1, len(s)):
if s[j] not in ls:
ls.append(s[j])
count += 1
else:
break
countset.append(count)
if countset == []:
return 0
else:
return max(countset)
- 2025/03/27
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
window_chars = set()
n = len(s)
left = 0
max_len = 0
for right in range(n):
while s[right] in window_chars:
window_chars.remove(s[left])
left += 1
window_chars.add(s[right])
max_len = max(max_len, right - left + 1)
return max_len
4. Median of Two Sorted Arrays¶
# 合并排序秒了，但合并时间复杂度为O(m+n), 排序采用Timsort算法，时间复杂度变为O((m+n)log(m+n))
class Solution: # (1)
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
combine = sorted(nums1 + nums2)
n = len(combine)
if n % 2 == 0:
output = (combine[int(n/2 - 1)] + combine[int(n/2)]) / 2
else:
output = combine[n//2]
return output
- 2025/03/27
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def getKthElement(k):
"""
- 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较
- 这里的 "/" 表示整除
- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个
- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个
- 取 pivot = min(pivot1, pivot2)，两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) + (k/2-1) <= k-2 个
- 这样 pivot 本身最大也只能是第 k-1 小的元素
- 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums1 数组
- 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 "删除"，剩下的作为新的 nums2 数组
- 由于我们 "删除" 了一些元素（这些元素都比第 k 小的元素要小），因此需要修改 k 的值，减去删除的数的个数
"""
index1, index2 = 0, 0
while True:
# 特殊情况
if index1 == m:
return nums2[index2 + k - 1]
if index2 == n:
return nums1[index1 + k - 1]
if k == 1:
return min(nums1[index1], nums2[index2])
# 正常情况
newIndex1 = min(index1 + k // 2 - 1, m - 1)
newIndex2 = min(index2 + k // 2 - 1, n - 1)
pivot1, pivot2 = nums1[newIndex1], nums2[newIndex2]
if pivot1 <= pivot2:
k -= newIndex1 - index1 + 1
index1 = newIndex1 + 1
else:
k -= newIndex2 - index2 + 1
index2 = newIndex2 + 1
m, n = len(nums1), len(nums2)
totalLength = m + n
if totalLength % 2 == 1:
return getKthElement((totalLength + 1) // 2)
else:
return (getKthElement(totalLength // 2) + getKthElement(totalLength // 2 + 1)) / 2
5. Longest Palindromic Substring¶
class Solution: # (1)
def longestPalindrome(self, s: str) -> str:
n = len(s)
if n == 0:
return ""
maxlen = 1
maxstring = s[0]
for i in range(n):
# 奇数长度回文
l, r = i, i
while l >= 0 and r < n and s[l] == s[r]:
if r - l + 1 > maxlen:
maxlen = r - l + 1
maxstring = s[l:r+1]
l -= 1
r += 1
# 偶数长度回文
l, r = i, i+1
while l >= 0 and r < n and s[l] == s[r]:
if r - l + 1 > maxlen:
maxlen = r - l + 1
maxstring = s[l:r+1]
l -= 1
r += 1
return maxstring
- 2025/03/28
6. ZigZag Conversion¶
class Solution: # (1)
def convert(self, s: str, numRows: int) -> str:
if numRows == 1:
return s
output = []
n = len(s)
gap = numRows + (numRows - 2) # 完整“Z”字形的列间距
for row in range(numRows):
i = row
while i < n:
output.append(s[i])
# 处理中间行（非首尾行）
if row != 0 and row != numRows - 1:
j = i + gap - 2*row
if j < n:
output.append(s[j])
i += gap
return "".join(output)
- 2025/03/28
class Solution: # 真是甜菜🤏
def convert(self, s: str, numRows: int) -> str:
if numRows < 2:
return s
res = ["" for _ in range(numRows)]
i, flag = 0, -1
for c in s:
res[i] += c
if i == 0 or i == numRows - 1:
flag = -flag
i += flag
return "".join(res)
7. Reverse Integer¶
class Solution: # (1)
def reverse(self, x: int) -> int:
if x > 0:
s = reversed(str(x))
result = int("".join(s))
elif x == 0:
result = 0
else:
s = reversed(str(x)[1:])
result = int("-" + "".join(s))
if result < -2**31 or result > 2**31 - 1:
return 0
else:
return result
2025/03/29
class Solution:
def reverse(self, x: int) -> int:
INT_MIN, INT_MAX = -2**31, 2**31 - 1
sign = -1 if x < 0 else 1
x_abs = abs(x)
reversed_num = 0
while x_abs != 0:
digit = x_abs % 10
x_abs = x_abs // 10
# 检查反转后的数字是否可能溢出
if sign == 1 and (reversed_num > (INT_MAX - digit) // 10):
return 0
if sign == -1 and (reversed_num > (abs(INT_MIN) - digit) // 10):
return 0
reversed_num = reversed_num * 10 + digit
reversed_num *= sign
return reversed_num
8. ASCII to Integer (atoi)¶
INT_MAX = 2**31 - 1
INT_MIN = -2**31
class Solution: # (1) 基本方法if else判断的shit mountain 就不写了，太烂了
def myAtoi(self, s: str) -> int:
automation = Automation()
for c in s:
automation.read(c)
return automation.sign * automation.ans
class Automation:
def __init__(self):
self.state = "start"
self.sign = 1
self.ans = 0
self.table = {
"start" : ["start", "signed", "in_number", "end"],
"signed" : ["end", "end", "in_number", "end"],
"in_number" : ["end", "end", "in_number", "end"],
"end" : ["end", "end", "end", "end"]
}
def get_col(self, c):
if c.isspace():
return 0
if c == "+" or c == "-":
return 1
if c.isdigit():
return 2
return 3
def read(self, c):
self.state = self.table[self.state][self.get_col(c)]
if self.state == "in_number":
self.ans = self.ans * 10 + int(c)
self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
elif self.state == "signed":
self.sign = 1 if c == "+" else -1
2025/03/31
class Solution:
def myAtoi(self, s: str) -> int:
return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)
^: start of string
[\+\-]: a single character of: +, -
?: zero or one
+: one or more
\d: Any digit
For more information: regex101
9. Palindrome Number¶
class Solution: # (1)
def isPalindrome(self, x: int) -> bool:
# 反转一半数字法
# 特殊情况
# 当x<0时，x不是回文数
# 当数字的最后一位是0时，除非这个数字是0，否则都不满足回文性
if x < 0 or (x % 10 == 0 and x != 0):
return False
revertednumber = 0
while x > revertednumber:
revertednumber = revertednumber * 10 + x % 10
x = x // 10
# 当数字长度为奇数时，我们可以通过revertednumber // 10去除处于中间位置的数字
# 例如，当输入为12321时，在while循环的末尾我们可以得到 x = 12, revertednumber = 123
# 因此我们可以将中位数字去除
return x == revertednumber or x == revertednumber // 10
- 2025/04/01
10. Regular Expression Matching¶
class Solution: # (1) index非常绕，然后还有动态规划的思想，多琢磨吧
def isMatch(self, s: str, p: str) -> bool:
m, n = len(s) + 1, len(p) + 1
dp = [[False] * n for _ in range(m)]
dp[0][0] = True
# 初始化首行
for j in range(2, n, 2):
dp[0][j] = dp[0][j - 2] and p[j - 1] == "*"
# 状态转移
for i in range(1, m):
for j in range(1, n):
if p[j - 1] == "*": # 当前字符为*时
if dp[i][j - 2]:
dp[i][j] = True
elif dp[i - 1][j] and s[i - 1] == p[j - 2]:
dp[i][j] = True
elif dp[i - 1][j] and p[j - 2] == ".":
dp[i][j] = True
else: # 当前字符不为*时
if dp[i - 1][j - 1] and s[i - 1] == p[j - 1]:
dp[i][j] = True
elif dp[i - 1][j - 1] and p[j - 1] == ".":
dp[i][j] = True
return dp[-1][-1]
- 2025/04/01
多看多想：k神图解
11. Container With Most Water¶
class Solution: # (1) 指针移动的基本原则是短板动。本题目为贪心算法的一种
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
res = 0
while left < right:
area = (right - left) * min(height[left], height[right])
res = max(res, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return res
- 2025/04/03
12. Integer to Roman¶
class Solution:
VALUE_SIMPLES = [
(1000, "M")，
(900, "CM"),
(500, "D"),
(400, "CD"),
(100, "C"),
(90, "XC"),
(50, "L"),
(40, "XL"),
(10, "X"),
(9, "IX"),
(5, "V"),
(4, "IV"),
(1, "I"),
]
def intToRoman(self, num: int) -> str:
roman = list()
for value, symbol in Solution.VALUE_SIMPLES:
while num >= value:
num -= value
roman.append(symbol)
if num == 0:
break
return "".join(roman)
class Solution:
def intToRoman(self, num: int) -> str: # 1 <= num <= 3999
REF = [
["I", "II", "III", "IV", "V", "VI", "VII","VIII", "IX"],
["X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],
["C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],
["M", "MM", "MMM"]
]
digit = 0
flag = 0
s = ""
for i in range(3, -1, -1):
num = num - digit * flag
flag = 10**i
digit = num // flag
if digit == 0:
continue
else:
s = s + REF[i][digit - 1]
return s