1. Two Sum
难度: Easy
思路：用空间复杂度换取时间复杂度，字典
#for循环，从i+1开始
for j in range(i+1, len(nums)): # 不要忘记加冒号
#可以直接返回数组，循环中执行到return语句则跳出循环
return [i, j]
# enumerate() 函数用于将一个可遍历的数据对象组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
for i, num in enumerate(nums):
#新建字典
look_up = {}
#给字典添加元素
look_up[num] = i #{num: i}
2. Add Two Numbers
难度: 中等
思路：使用递归，每次计算一位相加
# 如果l1为Falsely则执行
if not l1:
# 将val1数组中的元素逆序合并成一个字符串
num1 = ''.join([str(i) for i in val1[::-1]])
#将字符串形式的数字相加，然后逆序组成新的字符串
tmp = str(int(num1) + int(num2))[::-1]
3. Longest Substring Without Repeating Characters
难度: Medium
猜想：从第一个字符开始计算它往后不重复相连字符的数量，更新这个最大值
思路：1. 贪婪算法; 2. slide window 全家桶
# 返回字典中指定键的值，如果值不在字典中返回默认值-1。
maps.get(s[i], -1)
# 获取最大值
max(a, b)
5. Longest Palindromic Substring
难度: Medium
猜想：找子字符串+回文的判定条件
思路：Manacher algorithm，马拉车算法，时间复杂度为o（n）
# S = "abba", T = "^#a#b#b#a#$"
T = '#'.join('^{}$'.format(s))
class Solution:
#Manacher algorithm
def longestPalindrome(self, s):
# Transform S into T.
# For example, S = "abba", T = "^#a#b#b#a#$".
# ^ and $ signs are sentinels appended to each end to avoid bounds checking
T = '#'.join('^{}$'.format(s))
n = len(T)
P = [0] * n
C = R = 0
for i in range (1, n-1):
P[i] = (R > i) and min(R - i, P[2*C - i]) # equals to i' = C - (i-C)
# Attempt to expand palindrome centered at i
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
# If palindrome centered at i expand past R,
# adjust center based on expanded palindrome.
if i + P[i] > R:
C, R = i, i + P[i]
# Find the maximum element in P.
maxLen, centerIndex = max((n, i) for i, n in enumerate(P))
return s[(centerIndex - maxLen)//2: (centerIndex + maxLen)//2]
6. ZigZag Conversion
难度: 中等
思路：纵向思维考虑，index从0开始，我们要一直自增直到numRows-1，此后又一直自减到0，重复执行。分别往4个子字符串里面添加字母，最后再合并成一个字符串
# 把列表合成字符串
''.join(res)
#创建n维空列表
res = [''] * numRows
7. Reverse Integer 反转整数
难度: Easy
思路：取绝对值，逆序
# 除去这行文本的最后一个字符
line[:-1]
8. String to Integer (atoi)
难度: Medium
# 移除字符串头尾指定的字符序列
str.strip()
# 返回对应的 ASCII 数值，或者 Unicode 数值
ord()
11. Container With Most Water
难度: Medium
由于ai和aj (i<j) 组成的container的面积：S(i,j) = min(ai, aj) * (j-i)
当height[left] < height[right]时，对任何left < j < right来说
1. min(height[left], height[j]) <= height[left] = min(height[left], height[right])
2. j - left < right - left
所以S(left, right) = min(height[left], height[right]) * (right-left) > S(left, j) = min(height[left], height[j]) * (j-left)
12. Integer to Roman
难度: Medium
# 第一个参数传给第二个参数“键-键值”
# 第二个参数取出其中的键([0])或键值(1])
sorted(lookup.items(), key = lambda t: t[1])
15. 3Sum
难度: Medium
- 排序
- 固定左边，如果左边重复，继续
- 左右弄边界，去重，针对不同的左右边界情况处理
# 给数组排序，升序
nums.sort()
sorted(nums)
16. 3Sum Closest
难度: Medium
float('inf') #浮点数最大值
abs() #python自带的绝对值函数，不需要numpy
while i > 0 and nums[i] == nums[i-1]:
continue
# 错误操作
# 在while循环内部必须要接能够使#得条件不满足的语句，不然会死循环
# 如果有continue，则该语句必须在continue前面
17. Letter Combinations of a Phone Number
难度: Medium
思路：定义一个迭代函数
## 字典中每一组键值对后面用逗号隔开
lookup = {
'2' : ['a', 'b', 'c'],
'3' : ['d', 'e', 'f'],
'4' : ['g', 'h', 'i'],
'5' : ['j', 'k', 'l'],
'6' : ['m', 'n', 'o'],
'7' : ['p', 'q', 'r', 's'],
'8' : ['t', 'u', 'v'],
'9' : ['w', 'x', 'y', 'z']
}
18. 4Sum
难度: Medium
思路： 迭代，可推广至NSum问题
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
l,r = 0,len(nums)-1
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results) #往数组里面添加数组
results = []
findNsum(sorted(nums), target, 4, [], results)
return results
网友评论