- 两数之和
解题思路：通过新建一个字典将list中的数进行重新存储，数字作为key，索引值作为value，如果已经满足条件就返回，不满足条件就讲数据存到字典中。
#
# @lc app=leetcode id=1 lang=python3
#
# [1] Two Sum
#
# @lc code=start
class Solution:
def twoSum(self, nums, target) :
index = {}
for i, x in enumerate(nums):
if target - x in index:
return [index[target - x], i]
index[x] = i
思路：首先将两个链表中的元素存到一个string中，再将string中的元素存到列岸标中。
#
# @lc app=leetcode id=2 lang=python3
#
# [2] Add Two Numbers
#
# @lc code=start
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
num1 = ""
num2 = ""
while l1:
num1 += str(l1.val)
l1 = l1.next
while l2:
num2 += str(l2.val)
l2 = l2.next
res = str(int(num1[::-1]) + int(num2[::-1]))[::-1]
head = ListNode(res[0])
answer = head
for i in res[1:]:
node = ListNode(i)
head.next = node
head = head.next
return answer
3. Longest Substring Without Repeating Characters
思路：用一个stack来存储不重复的元素，如果遇到没有见过的直接添加进去，如果遇到了就把之前的删除掉，重新把这个加载进来。
#
# @lc app=leetcode id=3 lang=python3
#
# [3] Longest Substring Without Repeating Characters
#
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
stack = []
max_len = 0
for index, item in enumerate(s):
if item not in stack:
stack.append(item)
max_len = max(max_len , len(stack))
else:
idx = stack.index(item)
stack = stack[idx+1:]
stack.append(item)
max_len = max(max_len,len(stack))
return max_len
4 Median of Two Sorted Arrays
思路：这道题本质是一道二分搜索的题目。因为这两个是有序数组，同时时间复杂度要求。取出整个数列的中值，本质就是从两个数组中分别取出
和
个元素，同时
，所以关键是要在
两个数组中找到分割点，假设从A中选择了
个数，从B中选择
如果这时候
是小于
说明从A中选择的数目偏少，需要增加选择的数量如果
小于
表示从A中选择的数据太多，需要减少选择的数量。
image.png
image.png
class Solution:
def findMedianSortedArrays(self, nums1, nums2):
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m,n = len(nums1), len(nums2)
left_size = (m+n+1) // 2
start = 0
end = m
is_even = ((m+n) %2) == 0
while start <= end:
a_part = (start + end) // 2
b_part = left_size - a_part
aleftmax = float("-inf") if a_part == 0 else nums1[a_part - 1]
arightmin = float("inf") if a_part == m else nums1[a_part]
bleftmax = float("-inf") if b_part == 0 else nums2[b_part - 1]
brightmin = float("inf") if b_part == n else nums2[b_part]
if aleftmax <= brightmin and bleftmax <= arightmin:
if not is_even:
return max(aleftmax, bleftmax)
else:
return (max(aleftmax, bleftmax) + min(arightmin, brightmin)) / 2
elif aleftmax > brightmin:
end = a_part - 1
elif bleftmax > arightmin:
start = a_part + 1
if __name__ == '__main__':
nums1, nums2 = [1, 3], [3, 4]
solu = Solution()
print(solu.findMedianSortedArrays(nums1, nums2))
5 Longest Palindromic Substring
思路：重复利用已经计算出来的回文子串，考虑 “ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。首先考虑两个类型一种是奇数回文，另外一种是偶数回文。
这产生了一个直观的动态规划解法，我们首先初始化一字母和二字母的回文，然后找到所有三字母回文
#
# @lc code=start
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
maxl, start = 0, 0
for i in range(n):
if i-maxl >= 1 and s[i-maxl-1:i+1] == s[i-maxl-1:i+1][::-1]:
start = i - maxl - 1
maxl += 2
continue
if i - maxl >= 0 and s[i-maxl:i+1] == s[i-maxl:i+1][::-1]:
start = i - maxl
maxl += 1
return s[start: start+maxl]
6 ZigZag Conversion
思路：增加一个标志位判断是向上走还是向下走，通过取余操作实现标志位的取值，初始值应该设为-1，因为程序在开始时就会命中换符号的逻辑。
# @lc app=leetcode id=6 lang=python3
#
# [6] ZigZag Conversion
#
# @lc code=start
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows <= 1 or numRows > len(s):
return s
res = [""] * numRows
line, step = 0, -1
for c in s:
res[line] += c
if (line) % (numRows-1) == 0:
step = -step
line += step
return "".join(res)
7 Reverse Integer
思路：没啥好说的，python切片就可以搞定，唯一需要考虑的就是越界问题
# [7] Reverse Integer
#
# @lc code=start
class Solution:
def reverse(self, x: int) -> int:
x = int(str(x)[::-1]) if x >= 0 else - int(str(-x)[::-1])
return x if x < 2**31 and x >= -2**31 else 0
8 String to Integer (atoi)
思路：处理多种特殊情况
#
# @lc app=leetcode id=8 lang=python3
#
# [8] String to Integer (atoi)
#
# @lc code=start
class Solution:
def myAtoi(self, s):
"""
:type str: str
:rtype: int
"""
if len(s) == 0:
return 0
ls = list(s.strip())
if len(ls) == 0:
return 0
sign = -1 if ls[0] == '-' else 1
if ls[0] in ['-', '+']:
del ls[0]
ret, i = 0, 0
while i < len(ls) and ls[i].isdigit():
ret = ret*10 + ord(ls[i]) - ord('0')
i += 1
return max(-2**31, min(sign * ret, 2**31-1))
9 Palindrome Number
思路负数肯定不是回文数，之后再对正数和0进行判断
#
# @lc app=leetcode id=9 lang=python3
#
# [9] Palindrome Number
#
# @lc code=start
class Solution:
def isPalindrome(self, x: int) -> bool:
if x < 0:
return False
else:
if str(x) == str(x)[::-1]:
return True
else:
return False
10 Regular Expression Matching
思路：动态规划令 dp[i][j] 为string s 前i位是否匹配p的前j位，为bool类型，例如dp[1][1]为s[0]、p[0]是否匹配，初始化后剩下的判断分为以下几种情况分析：
- p[j] == s[i] 或者 p[j] == '.' #匹配成功跟前面匹配一致
dp[i+1][j+1] = dp[i][j] - p[j] == '*' 这时又分两种情况
（1）p[j-1] != s[i] #前的字符匹配0次
dp[i+1][j+1] = dp[i+1][j-1]
（2） p[j-1] == s[i] or p[j-1] != '.'
dp[i+1][j+1] = dp[i][j+1] #该字符出现多次
or dp[i+1][j+1] = dp[i+1][j] # 字符只出现一次
or dp[i+1][j+1] = dp[i+1][j-1] # 字符匹配0次
class Solution:
# @return a boolean
def isMatch(self, s, pattern):
dp = [[False] * (len(pattern)+1) for _ in range(len(s)+1)]
dp[0][0] = True
for i in range(len(pattern)):
if pattern[i] == '*' and dp[0][i-1]:
dp[0][i+1] = True
for i in range(len(s)):
for j in range(len(pattern)):
if pattern[j] == s[i] or pattern[j] == '.':
dp[i+1][j+1] = dp[i][j]
if pattern[j] == '*':
if pattern[j-1] != s[i] and pattern[j-1] != '.':
dp[i+1][j+1] = dp[i+1][j-1]
else:
dp[i+1][j+1] = (dp[i][j+1] or dp[i+1]
[j] or dp[i+1][j-1])
return dp[len(s)][len(pattern)]
