leetcode刷题系列
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
版本1:超出时间限制：
class Solution(object):
def getLeastNumbers(self, arr, k):
"""
:type arr: List[int]
:type k: int
:rtype: List[int]
"""
Bucket = [0]*(max(arr)- min(arr) +1) #创建并初始化桶
for i in range(len(arr)):
#把所有的元素放入桶中，即把对应的元素+1
Bucket[arr[i]-min(arr)] += 1
temp = []
for i in range(len(Bucket)):
#取出桶中的元素
if Bucket[i] != 0:
temp += [min(arr) + i] * Bucket[i]
return temp[0:k]
运行时间有点长，其他的没毛病
class Solution(object):
def getLeastNumbers(self, arr, k):
"""
:type arr: List[int]
:type k: int
:rtype: List[int]
"""
if k > len(arr) or k <= 0:
return []
start = 0
end = len(arr) - 1
arr = self.quickSort(arr, start, end)
return arr[:k]
def partition(self,arr,low,high):
i = ( low-1 ) # 最小元素索引
pivot = arr[high]
for j in range(low , high):
# 当前元素小于或等于 pivot
if arr[j] <= pivot:
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
def quickSort(self,arr,low,high):
if low < high:
pi = self.partition(arr,low,high)
self.quickSort(arr, low, pi-1)
self.quickSort(arr, pi+1, high)
return arr
正确答案
class Solution(object):
def getLeastNumbers(self, arr, k):
"""
:type arr: List[int]
:type k: int
:rtype: List[int]
"""
# 方法一:partition方法(基于快速排序)
if k > len(arr) or k <= 0:
return []
start = 0
end = len(arr) - 1
index = self.quickSort(arr, start, end)
while index != k-1:
print(index)
if index > k-1:
end = index - 1
index = self.quickSort(arr, start, end)
if index < k-1:
start = index + 1
index = self.quickSort(arr, start, end)
return arr[:k]
def quickSort(self, arr, start, end):
low = start
high = end
temp = arr[start]
while low < high:
while low < high and arr[high] >= temp:
high -= 1
arr[low] = arr[high]
while low <high and arr[low] < temp:
low += 1
arr[high] = arr[low]
arr[low] = temp
return low
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
d={}
n=0
for i in nums:
if d.has_key(i):
tmp=d[i]
tmp.append(n)
d[i]=tmp
else :
tmp=[]
tmp.append(n)
d[i]=tmp
n+=1
for i in nums:
tmp=0
tmp=target-i
if tmp!=i and tmp in nums:
return nums.index(tmp),nums.index(i)
elif tmp==i and len(d[i])>=2:
return d[i][0],d[i][1]
else :
print 'none'
正确解法
def twoSum(nums, target):
hashmap={}
for i,num in enumerate(nums):
if hashmap.get(target - num) is not None:
return [i,hashmap.get(target - num)]
hashmap[num] = i #这句不能放在if语句之前，解决list中有重复值或target-num=num的情况
水壶问题：有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶，从而可以得到恰好 z升 的水？
顺便复习了数学中的贝祖定理
class Solution:
def canMeasureWater(self, x: int, y: int, z: int) -> bool:
if x + y < z:
return False
if x == 0 or y == 0:
return z == 0 or x + y == z
return z % math.gcd(x, y) == 0
给定整数数组 A，每次 move 操作将会选择任意 A[i]，并将其递增 1。
返回使 A 中的每个值都是唯一的最少操作次数。
class Solution(object):
def minIncrementForUnique(self, A):
"""
:type A: List[int]
:rtype: int
"""
count = [0] * 80000
for x in A:
count[x] += 1
ans = taken = 0
for x in range(80000):
if count[x] >= 2:
taken += count[x] - 1
ans -= x * (count[x] - 1)
elif taken > 0 and count[x] == 0:
taken -= 1
ans += x
return ans
给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
class Solution(object):
def middleNode(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
tmp=head
n=0
while tmp!=None:
n+=1
tmp=tmp.next
cnt=n//2 +1
tmp=head
n=0
while tmp!=None:
n+=1
if n==cnt:
return tmp
tmp=tmp.next
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
自己解答：有问题，没考虑到【2，1，1，2】的情况。
class Solution(object):
def massage(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return max(sum(nums[::2]),sum(nums[1::2]))
正确解答：动态规划（用n-1的状态更新n的状态）
class Solution(object):
def massage(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
n = len(nums)
if n == 0:
return 0
dp0, dp1 = 0, nums[0]
for i in range(1, n):
tdp0 = max(dp0, dp1) # 计算 dp[i][0]
tdp1 = dp0 + nums[i] # 计算 dp[i][1]
dp0, dp1 = tdp0, tdp1
return max(dp0, dp1)
在 N * N 的网格上，我们放置一些 1 * 1 * 1 的立方体。
每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
请你返回最终形体的表面积。
class Solution(object):
def surfaceArea(self, grid):
N = len(grid)
ans = 0
for r in xrange(N):
for c in xrange(N):
if grid[r][c]:
ans += 2
for nr, nc in ((r-1, c), (r+1, c), (r, c-1), (r,c+1)):
if 0 <= nr < N and 0 <= nc < N:
nval = grid[nr][nc]
else:
nval = 0
ans += max(grid[r][c] - nval, 0)
return ans
在一个 8 x 8 的棋盘上，有一个白色车（rook）。也可能有空方块，白色的象（bishop）和黑色的卒（pawn）。它们分别以字符 “R”，“.”，“B” 和 “p” 给出。大写字符表示白棋，小写字符表示黑棋。
车按国际象棋中的规则移动：它选择四个基本方向中的一个（北，东，西和南），然后朝那个方向移动，直到它选择停止、到达棋盘的边缘或移动到同一方格来捕获该方格上颜色相反的卒。另外，车不能与其他友方（白色）象进入同一个方格。
返回车能够在一次移动中捕获到的卒的数量。
超出了时间限制：
dx,dy=[0,1,0,-1],[1,0,-1,0]
cnt=line_x=line_y=0
for i in range(8):
if 'R' in board[i]:
line_x=i
line_y=board[i].index('R')
for i in range(4):
step=0
while True:
x=line_x+step*dx[i]
y=line_y+step*dx[i]
if x<0 or x>=8 or y<0 or y>=8 or board[x][y]=='p':
break
if board[x][y]=='.':
cnt+=1
break
step+=1
return cnt
再来一次：
class Solution(object):
def numRookCaptures(self, board):
"""
:type board: List[List[str]]
:rtype: int
"""
result=0
for i in range(len(board)):
if 'R' in board[i]:
raw = i
break
colum = board[raw].index('R')
s = ''.join(board[raw])
s = s.replace('.','')
if 'pR' in s:
result += 1
if 'Rp' in s:
result += 1
s = ''.join(i[colum] for i in board)
s = s.replace('.','')
if 'pR' in s:
result += 1
if 'Rp' in s:
result += 1
return result
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
每组都有 X 张牌。
组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
class Solution(object):
def hasGroupsSizeX(self, deck):
"""
:type deck: List[int]
:rtype: bool
"""
from fractions import gcd
vals = collections.Counter(deck).values()
return reduce(gcd, vals) >= 2
给定一个单词列表，我们将这个列表编码成一个索引字符串 S 与一个索引列表 A。
例如，如果这个列表是 ["time", "me", "bell"]，我们就可以将其表示为 S = "time#bell#" 和 indexes = [0, 2, 5]。
对于每一个索引，我们可以通过从字符串 S 中索引的位置开始读取字符串，直到 "#" 结束，来恢复我们之前的单词列表。
那么成功对给定单词列表进行编码的最小字符串长度是多少呢？
class Solution(object):
def minimumLengthEncoding(self, words):
"""
:type words: List[str]
:rtype: int
"""
word_set=set(words)
for word in words:
for k in range(1,len(word)):
word_set.discard(word[k:])
return sum(len(word)+1 for word in word_set
你现在手里有一份大小为 N x N 的『地图』（网格） grid，上面的每个『区域』（单元格）都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，你知道距离陆地区域最远的海洋区域是是哪一个吗？请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋，请返回 -1。
class Solution(object):
def maxDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
N = len(grid)
queue = []
# 将所有的陆地格子加入队列
for i in range(N):
for j in range(N):
if grid[i][j] == 1:
queue.append((i, j))
# 如果我们的地图上只有陆地或者海洋，请返回 -1。
if len(queue) == 0 or len(queue) == N * N:
return -1
distance = -1
while len(queue) > 0:
distance += 1
# 这里一口气取出 n 个结点，以实现层序遍历
n = len(queue)
for i in range(n):
r, c = queue.pop(0)
# 遍历上边单元格
if r-1 >= 0 and grid[r-1][c] == 0:
grid[r-1][c] = 2
queue.append((r-1, c))
# 遍历下边单元格
if r+1 < N and grid[r+1][c] == 0:
grid[r+1][c] = 2
queue.append((r+1, c))
# 遍历左边单元格
if c-1 >= 0 and grid[r][c-1] == 0:
grid[r][c-1] = 2
queue.append((r, c-1))
# 遍历右边单元格
if c+1 < N and grid[r][c+1] == 0:
grid[r][c+1] = 2
queue.append((r, c+1))
return distance
0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
(还是用动态规划解决的）
def f(n, m):
if n == 0:
return 0
x = f(n - 1, m)
return (m + x) % n
class Solution(object):
def lastRemaining(self, n, m):
"""
:type n: int
:type m: int
:rtype: int
"""
return f(n, m)
全局排序
class Solution(object):
def sortArray(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return self.qsort(nums)
def qsort(self,nums):
if len(nums) <= 1:
return nums
else:
pivot = nums[0]
less = [x for x in nums[1:] if x < pivot]
greater = [x for x in nums[1:] if x >= pivot]
return self.qsort(less) + [pivot] + self.qsort(greater)
有效括号字符串 定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「有效括号字符串」部分。
嵌套深度 depth 定义：即有效括号字符串嵌套的层数，depth(A) 表示有效括号字符串 A 的嵌套深度。详情参见题末「嵌套深度」部分。
class Solution(object):
def maxDepthAfterSplit(self, seq):
"""
:type seq: str
:rtype: List[int]
"""
ans=[]
d=0
for c in seq:
if c=='(':
d+=1
ans.append(d % 2)
if c==')':
ans.append(d% 2)
d-=1
return ans
根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
class Solution(object):
def gameOfLife(self, board):
"""
:type board: List[List[int]]
:rtype: None Do not return anything, modify board in-place instead.
"""
neighbor=[(1,0),(0,1),(-1,0),(0,-1),(1,1),(1,-1),(-1,-1),(-1,1)]
for i in range(len(board)):
for j in range(len(board[i])):
living_neibhbor=0
for (r,c) in neighbor:
row=r+i
col=c+j
if (row>=0 and row<len(board)) and (col>=0 and col<len(board[0])) and abs(board[row][col])==1:
living_neibhbor+=1
if (board[i][j]==1) and (living_neibhbor<2 or living_neibhbor>3):
board[i][j]=-1
if (board[i][j]==0) and (living_neibhbor==3):
board[i][j]=2
print board
for i in range(len(board)):
for j in range(len(board[i])):
if board[i][j] > 0:
board[i][j] = 1
else:
board[i][j] = 0
return board
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。
假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。
该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示：
本题中的空白字符只包括空格字符 ' ' 。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
return max(min(int(*re.findall('^[\+\-]?\d+', str.lstrip())), 2**31 - 1), -2**31)
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
超出时间限制，难受
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
if len(height)==0:
return 0
re=[]
for h in height:
re_tmp=[0] * max(height)
for j in range(h):
re_tmp[j]=1
re.append(re_tmp)
rain=0
for j in range(max(height)):
left=0
for i in range(len(height)):
if left==0 and re[i][j]==1:
left+=1
rain_tmp=0
elif left==1 and re[i][j]==0:
rain_tmp+=1
print i,j
print re[i][j],left,rain
elif left==1 and re[i][j]==1 and rain_tmp!=0 :
rain+=rain_tmp
rain_tmp=0
return rain
正确答案：
class Solution(object):
def trap(self, height):
"""
:type height: List[int]
:rtype: int
"""
n = len(height)
# 同时从左往右和从右往左计算有效面积
s1, s2 = 0, 0
max1, max2 = 0, 0
for i in range(n):
if height[i] > max1:
max1 = height[i]
if height[n - i - 1] > max2:
max2 = height[n - i - 1]
s1 += max1
s2 += max2
# 积水面积 = S1 + S2 - 矩形面积 - 柱子面积
res = s1 + s2 - max1 * len(height) - sum(height)
return res
彻底跪，只能抄答案：
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？
class dlNode:
def __init__(self, key, val, cnt=0):
self.val = [key, val, cnt]#键、值、访问次数
self.pre = None
self.nxt = None
class LFUCache:
def __init__(self, capacity: int):
self.cache = {}#通过key保存链表节点，key:node
self.c = capacity#字典容量
self.head = dlNode(1, 1, float('inf'))#头节点，定义访问次数正无穷
self.tail = dlNode(-1, -1, float('-inf'))#尾节点，定义访问次数负无穷
self.head.nxt = self.tail
self.tail.pre = self.head
def _refresh(self, node, cnt):##辅助函数，对节点node，以访问次数cnt重新定义其位置
pNode, nNode = node.pre, node.nxt #当前节点的前后节点
if cnt < pNode.val[2]:#如果访问次数小于前节点的访问次数，无需更新位置
return
pNode.nxt, nNode.pre = nNode, pNode#将前后连起来，跳过node位置
while cnt >= pNode.val[2]:#前移到尽可能靠前的位置后插入
pNode = pNode.pre
nNode = pNode.nxt
pNode.nxt = nNode.pre = node
node.pre, node.nxt = pNode, nNode
def get(self, key: int) -> int:
if self.c <= 0 or key not in self.cache:#如果容量<=0或者key不在字典中，直接返回-1
return -1
node = self.cache[key]#通过字典找到节点
_, value, cnt = node.val#通过节点得到key，value和cnt
node.val[2] = cnt+1#访问次数+1
self._refresh(node, cnt+1)#刷新位置
return value
def put(self, key: int, value: int) -> None:
if self.c <= 0:#缓存容量<=0
return
if key in self.cache:#已在字典中，则要更新其value，同时访问次数+1刷新位置
node = self.cache[key]
_, _, cnt = node.val
node.val = [key, value, cnt+1]#更新其值
self._refresh(node, cnt+1)
else:
if len(self.cache) >= self.c: #容量已满，先清除掉尾部元素
tp, tpp = self.tail.pre, self.tail.pre.pre
self.cache.pop(tp.val[0]) #从字典剔除尾节点
tpp.nxt, self.tail.pre = self.tail, tpp #首尾相连，跳过原尾节点
#新建节点，并先插入到队尾
node = dlNode(key, value)
node.pre, node.nxt = self.tail.pre, self.tail
self.tail.pre.nxt, self.tail.pre = node, node
self.cache[key] = node
self._refresh(node, 0)
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
class Solution(object):
def minDistance(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
n=len(word1)
m=len(word2)
if n*m==0:
return n+m
dp=[[0] * (m+1) for _ in range(n+1)]
for j in range(m+1):
dp[0][j]=j
for i in range(n+1):
dp[i][0]=i
for i in range(1, n + 1):
for j in range(1,m+1):
left=dp[i-1][j]+1
down=dp[i][j-1]+1
left_down=dp[i-1][j-1]
if word1[i-1]!=word2[j-1]:
left_down+=1
dp[i][j]=min(left,down,left_down)
return dp[n][m]
矩阵转置：
基于这个公式：
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
for i in range(n // 2):
for j in range((n + 1) // 2):
matrix[i][j], matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1] \
= matrix[n - j - 1][i], matrix[n - i - 1][n - j - 1], matrix[j][n - i - 1], matrix[i][j]
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。
一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），
也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，
因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？
def digitsum(n):
ans=0
while n:
ans+=n%10
n //= 10
return ans
class Solution(object):
def movingCount(self, m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
vis=set([(0,0)])
for i in range(m):
for j in range(n):
if ((i - 1, j) in vis or (i, j - 1) in vis) and digitsum(i) + digitsum(j) <= k:
vis.add((i, j))
return len(vis)
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
class Solution:
def generateParenthesis(self, n):
ans = []
def backtrack(S, left, right):
if len(S) == 2 * n:
ans.append(''.join(S))
return
if left < n:
S.append('(')
backtrack(S, left+1, right)
S.pop()
if right < left:
S.append(')')
backtrack(S, left, right+1)
S.pop()
backtrack([], 0, 0)
return ans
你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。
每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。
你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。
每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。
你的目标是确切地知道 F 的值是多少。
无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？
给定一个字符串，逐个翻转字符串中的每个单词。
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
return " ".join(reversed(s.split()))
class Solution(object):
def superEggDrop(self, K, N):
"""
:type K: int
:type N: int
:rtype: int
"""
if N==1:
return 1
dp=[[0] * (K+1) for _ in range(N+1) ]
for i in range(1,K+1):
dp[1][i]=1
ans=0
for i in range(2,N+1):
for j in range(1,K+1):
dp[i][j]=1+dp[i-1][j]+dp[i-1][j-1]
if dp[i][j]>=N:
ans=i
break
return ans
给定两条线段（表示为起点start = {X1, Y1}和终点end = {X2, Y2}），如果它们有交点，请计算其交点，没有交点则返回空值。
要求浮点型误差不超过10^-6。若有多个交点（线段重叠）则返回 X 值最小的点，X 坐标相同则返回 Y 值最小的点。
class Solution:
def intersection(self, start1: List[int], end1: List[int], start2: List[int], end2: List[int]) -> List[float]:
# 判断 (xk, yk) 是否在「线段」(x1, y1)~(x2, y2) 上
# 这里的前提是 (xk, yk) 一定在「直线」(x1, y1)~(x2, y2) 上
def inside(x1, y1, x2, y2, xk, yk):
# 若与 x 轴平行，只需要判断 x 的部分
# 若与 y 轴平行，只需要判断 y 的部分
# 若为普通线段，则都要判断
return (x1 == x2 or min(x1, x2) <= xk <= max(x1, x2)) and (y1 == y2 or min(y1, y2) <= yk <= max(y1, y2))
def update(ans, xk, yk):
# 将一个交点与当前 ans 中的结果进行比较
# 若更优则替换
return [xk, yk] if not ans or [xk, yk] < ans else ans
x1, y1 = start1
x2, y2 = end1
x3, y3 = start2
x4, y4 = end2
ans = list()
# 判断 (x1, y1)~(x2, y2) 和 (x3, y3)~(x4, y3) 是否平行
if (y4 - y3) * (x2 - x1) == (y2 - y1) * (x4 - x3):
# 若平行，则判断 (x3, y3) 是否在「直线」(x1, y1)~(x2, y2) 上
if (y2 - y1) * (x3 - x1) == (y3 - y1) * (x2 - x1):
# 判断 (x3, y3) 是否在「线段」(x1, y1)~(x2, y2) 上
if inside(x1, y1, x2, y2, x3, y3):
ans = update(ans, x3, y3)
# 判断 (x4, y4) 是否在「线段」(x1, y1)~(x2, y2) 上
if inside(x1, y1, x2, y2, x4, y4):
ans = update(ans, x4, y4)
# 判断 (x1, y1) 是否在「线段」(x3, y3)~(x4, y4) 上
if inside(x3, y3, x4, y4, x1, y1):
ans = update(ans, x1, y1)
# 判断 (x2, y2) 是否在「线段」(x3, y3)~(x4, y4) 上
if inside(x3, y3, x4, y4, x2, y2):
ans = update(ans, x2, y2)
# 在平行时，其余的所有情况都不会有交点
else:
# 联立方程得到 t1 和 t2 的值
x1,x2,x3,x4=float(x1),float(x2),float(x3),float(x4)
y1,y2,y3,y4=float(y1),float(y2),float(y3),float(y4)
t1 = (x3 * (y4 - y3) + y1 * (x4 - x3) - y3 * (x4 - x3) - x1 * (y4 - y3)) / ((x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1))
t2 = (x1 * (y2 - y1) + y3 * (x2 - x1) - y1 * (x2 - x1) - x3 * (y2 - y1)) / ((x4 - x3) * (y2 - y1) - (x2 - x1) * (y4 - y3))
# 判断 t1 和 t2 是否均在 [0, 1] 之间
if 0.0 <= t1 <= 1.0 and 0.0 <= t2 <= 1.0:
ans = [x1 + t1 * (x2 - x1), y1 + t1 * (y2 - y1)]
return ans
设计一个简化版的推特(Twitter)，可以让用户实现发送推文，关注/取消关注其他用户，能够看见关注人（包括自己）的最近十条推文。你的设计需要支持以下的几个功能：
postTweet(userId, tweetId): 创建一条新的推文
getNewsFeed(userId): 检索最近的十条推文。每个推文都必须是由此用户关注的人或者是用户自己发出的。推文必须按照时间顺序由最近的开始排序。
follow(followerId, followeeId): 关注一个用户
unfollow(followerId, followeeId): 取消关注一个用户
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/design-twitter
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Twitter(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.users=dict()
self.posts=[]
def postTweet(self, userId, tweetId):
"""
Compose a new tweet.
:type userId: int
:type tweetId: int
:rtype: None
"""
self.posts.append([userId,tweetId])
if userId not in self.users.keys():
self.users[userId]=[]
def getNewsFeed(self, userId):
"""
Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
:type userId: int
:rtype: List[int]
"""
if userId not in self.users.keys():
return
else :
idx=[userId]+self.users.get(userId)
tmp=[]
count=10
for post in self.posts[-1:-len(self.posts)-1:-1]:
if count>0:
if post[0] in idx:
tmp.append(post[1])
count-=1
return tmp
def follow(self, followerId, followeeId):
"""
Follower follows a followee. If the operation is invalid, it should be a no-op.
:type followerId: int
:type followeeId: int
:rtype: None
"""
if followerId not in self.users.keys():
self.users[followerId]=[]
self.users[followerId].append(followeeId)
else:
self.users[followerId].append(followeeId)
def unfollow(self, followerId, followeeId):
"""
Follower unfollows a followee. If the operation is invalid, it should be a no-op.
:type followerId: int
:type followeeId: int
:rtype: None
"""
if followerId not in self.users.keys():
return
elif followeeId not in self.users[followerId]:
return
else :
self.users[followerId].remove(followeeId)
# Your Twitter object will be instantiated and called as such:
# obj = Twitter()
# obj.postTweet(userId,tweetId)
# param_2 = obj.getNewsFeed(userId)
# obj.follow(followerId,followeeId)
# obj.unfollow(followerId,followeeId)
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
l1_n=0
tmp=l1
while tmp!=None:
tmp=tmp.next
l1_n+=1
## 判断l2的链表长度：
l2_n=0
tmp=l2
while tmp!=None:
tmp=tmp.next
l2_n+=1
print l1_n,l2_n
l_num=0
tmp=l1
for i in range(l1_n-1,-1,-1):
print i
l_num+=(10**i) * tmp.val
tmp=tmp.next
tmp=l2
for i in range(l2_n-1,-1,-1):
print i
l_num+=(10**i) * tmp.val
tmp=tmp.next
l_tmp=None
l_num=str(l_num)
for i in range(len(l_num)-1,-1,-1):
print i
l_re=ListNode(l_num[i])
if l_tmp==None:
pass
else :
l_re.next=l_tmp
l_tmp=l_re
return l_re
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
s1, s2 = [], []
while l1:
s1.append(l1.val)
l1 = l1.next
while l2:
s2.append(l2.val)
l2 = l2.next
ans = None
carry = 0
while s1 or s2 or carry != 0:
a = 0 if not s1 else s1.pop()
b = 0 if not s2 else s2.pop()
cur = a + b + carry
carry = cur // 10
cur %= 10
curnode = ListNode(cur)
curnode.next = ans
ans = curnode
return ans
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
m,n=len(matrix),len(matrix[0])
dp=[[0] * n for _ in range(m)]
print dp
zeros = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
print zeros
q=collections.deque(zeros)
seen=set(zeros)
while q:
i,j=q.popleft()
for ni,nj in [(i-1,j),(i,j-1),(i+1,j),(i,j+1)]:
if 0<=ni<m and 0<=nj<n and (ni,nj) not in seen:
dp[ni][nj]=dp[i][j]+1
q.append((ni,nj))
seen.add((ni,nj))
return dp
给出一个区间的集合，请合并所有重叠的区间。
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
intervals.sort(key=lambda x :x[0])
merge=[]
for l in intervals:
if not merge or merge[-1][1]<l[0]:
merge.append(l)
else :
merge[-1][1]=max(merge[-1][1],l[1])
return merge
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。
class Solution(object):
def canJump(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
n,right=len(nums),0
for i in range(n):
if i<=right:
right=max(right,i+nums[i])
if right>=n-1:
return True
return False
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
class Solution:
def maxArea(self, height: List[int]) -> int:
l, r = 0, len(height) - 1
ans = 0
while l < r:
area = min(height[l], height[r]) * (r - l)
ans = max(ans, area)
if height[l] <= height[r]:
l += 1
else:
r -= 1
return ans
由 n 个连接的字符串 s 组成字符串 S，记作 S = [s,n]。例如，["abc",3]=“abcabcabc”。
如果我们可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。例如，根据定义，"abc" 可以从 “abdbec” 获得，但不能从 “acbbe” 获得。
现在给你两个非空字符串 s1 和 s2（每个最多 100 个字符长）和两个整数 0 ≤ n1 ≤ 106 和 1 ≤ n2 ≤ 106。现在考虑字符串 S1 和 S2，其中 S1=[s1,n1] 、S2=[s2,n2] 。
请你找出一个可以满足使[S2,M] 从 S1 获得的最大整数 M 。
class Solution:
def getMaxRepetitions(self, s1: str, n1: int, s2: str, n2: int) -> int:
if n1 == 0:
return 0
s1cnt, index, s2cnt = 0, 0, 0
# recall 是我们用来找循环节的变量，它是一个哈希映射
# 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符
# 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了
# 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果
# 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组
# 循环节就是；
# - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
# - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
# 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配
# 注意 s2 要从第 index 个字符开始匹配
recall = dict()
while True:
# 我们多遍历一个 s1，看看能不能找到循环节
s1cnt += 1
for ch in s1:
if ch == s2[index]:
index += 1
if index == len(s2):
s2cnt, index = s2cnt + 1, 0
# 还没有找到循环节，所有的 s1 就用完了
if s1cnt == n1:
return s2cnt // n2
# 出现了之前的 index，表示找到了循环节
if index in recall:
s1cnt_prime, s2cnt_prime = recall[index]
# 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
pre_loop = (s1cnt_prime, s2cnt_prime)
# 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
in_loop = (s1cnt - s1cnt_prime, s2cnt - s2cnt_prime)
break
else:
recall[index] = (s1cnt, s2cnt)
# ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 pre_loop 和 in_loop
ans = pre_loop[1] + (n1 - pre_loop[0]) // in_loop[0] * in_loop[1]
# S1 的末尾还剩下一些 s1，我们暴力进行匹配
rest = (n1 - pre_loop[0]) % in_loop[0]
for i in range(rest):
for ch in s1:
if ch == s2[index]:
index += 1
if index == len(s2):
ans, index = ans + 1, 0
# S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2
return ans // n2
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
land_cnt=0
ones=[(i,j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j]=='1']
print ones
seen=set()
while len(ones)!=0:
land_cnt+=1
print 'return'
q=set()
q.add(ones[0])
while len(q)!=0:
one=q.pop()
i=int(one[0])
j=int(one[1])
if (i,j) not in seen:
if 0<=i+1<len(grid) and grid[i+1][j]=='1':
q.add((i+1,j))
if 0<=j+1<len(grid[0]) and grid[i][j+1]=='1':
q.add((i,j+1))
if 0<=i-1<len(grid) and grid[i-1][j]=='1':
q.add((i-1,j))
if 0<=j-1<len(grid[0]) and grid[i][j-1]=='1':
q.add((i,j-1))
seen.add(one)
ones=[i for i in ones if i not in seen]
return land_cnt
深度优先搜索：
把所有遍历到的1全部标记为0
class Solution:
def dfs(self, grid, r, c):
grid[r][c] = 0
nr, nc = len(grid), len(grid[0])
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
self.dfs(grid, x, y)
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
self.dfs(grid, r, c)
return num_islands
广度优先搜索
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
nr = len(grid)
if nr == 0:
return 0
nc = len(grid[0])
num_islands = 0
for r in range(nr):
for c in range(nc):
if grid[r][c] == "1":
num_islands += 1
grid[r][c] = "0"
neighbors = collections.deque([(r, c)])
while neighbors:
row, col = neighbors.popleft()
for x, y in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
neighbors.append((x, y))
grid[x][y] = "0"
return num_islands
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
class Solution(object):
def numberOfSubarrays(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
n = len(nums)
odd = [-1]
ans = 0
for i in range(n):
if nums[i] % 2 == 1:
odd.append(i)
odd.append(n)
print(odd)
for i in range(1, len(odd) - k):
ans += (odd[i] - odd[i - 1]) * (odd[i + k] - odd[i + k - 1])
return ans
网友评论