LcTop5-0215
2020-02-15 本文已影响0人
inspiredhss
1. Two Sum
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].
class Solution:
def twoSum(self,nums,target):
map={}
for i in range(len(nums)):
if nums[i] not in map:
map[target-nums[i]]=i
else:
return i,map[nums[i]]
return -1,-1
- 差值 索引脚标；用map字典，map[value]=index;*
- 遍历一遍，存字典、或判断差值存在；map[target-nums[i]]=i;
Add Two Numbers
given two non-empty linked lists
digits are stored in reverse order
Add the two numbers and return it as a linked list.
class Solution:
def addTwoNumbers(self,l1,l2):
dummy=cur=ListNode(0)
carry=0
while l1 or l2 or carry:
if l1:
carry+=l1.val
l1=l1.next
if l2:
carry+=l2.val
l2=l2.next
cur.next=ListNode(carry%10)
cur=cur.next
carry//=10
return dummy.next
- 当前位：ListNode(carry%10);
进位：carry//=10; carry+=l.val；
链表头与新链表：dummy=cur=ListNode(0)；
Number of Islands
Given a 2d grid map of '1's (land) and '0's (water),
count the number of islands.
An island is surrounded by water;
formed by connecting adjacent lands horizontally or vertically.
assume all four edges of the grid are all surrounded by water.
class Solution:
def numIslands(self, grid):
if not grid:
return 0 # grid map=>1s&0s=>islands number=>adjacent lands
count = 0
for i in range(len(grid)): # 遍历每行
for j in range(len(grid[0])): # 每列
if grid[i][j] == '1': # Islands元素
self.dfs(grid, i, j) # 穷尽Islands路径 并标记元素
count += 1 #路径加一
return count #Islands总数
def dfs(self, grid, i, j):
if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
return #边界或路径结束
grid[i][j] = '#' #遍历的标记
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)
42. Trapping Rain Water
n: elevation map
width bar is 1
compute trap water
class Solution:
def trap(self,height):
ans=0
l,r=0,len(height)-1
l_max,r_max=0,0
while l<r:
if height[l]<height[r]:
if height[l]<l_max:
ans+=l_max-height[l]
else:
l_max=height[l]
l+=1
else:
if height[r]<r_max:
ans+=r_max-height[r]
else:
r_max=height[r]
r-=1
return ans
- 遍历一遍：获取当前柱囤水 & 总囤水；
参考柱：两端较高柱 & 较低柱；
当前柱：当前囤水 或更新较小柱；
LRU Cache
# 146. LRU Cache
# Design and implement a data structure for Least Recently Used (LRU) cache.
# support: get and put.
# get(key) -key exists in the cache: value, otherwise -1.
# put(key, value) - Set or insert the value if key is not present.
# When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
# initialized: positive capacity.
# O(1) time complexity?
# @des: LRU(最近最少使用) 缓存机制
# OrderedDict 参看 https://docs.python.org/3/library/collections.html#collections.OrderedDict
# OrderedDict是dict子类，支持dict所有方法，记住了插入key的顺序。
# 如果新条目覆盖现有条目，则原始插入位置保持不变。 删除条目并重新插入它将使其移至最后。详细介绍参见Python官方文档。
class LRUCache:
def __init__(self, capacity: int):
self.dic = collections.OrderedDict() # OrderedDict 记住了字典元素的添加顺序
self.remain = capacity # 容量 大小
def get(self, key: int) -> int:
if key not in self.dic:
return -1
v = self.dic.pop(key)
self.dic[key] = v # 被获取 刷新最近使用
return v
def put(self, key: int, value: int) -> None:
if key in self.dic:
self.dic.pop(key) # 如果字典中有先弹出 再加入
else: # 没有
if self.remain > 0: # 字典未满
self.remain -= 1 # 剩余容量 -1
else: # 字典已满 弹出最近最少使用的，最老的元素
self.dic.popitem(last = False)
'''
popitem(last=True)
removes a (key, value) pair.
LIFO if last true or FIFO if false.
'''
self.dic[key] = value
202. Happy Number
number === sum of the squares of its digits
repeat the process until the number equals 1
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
class Solution:
def isHappy(self, n: int) -> bool:
seen = set()
while n not in seen: #如果重复 则结束；
seen.add(n) #中间数添加到集合里；
n = sum([int(x) **2 for x in str(n)]) #中间数的平方和
return n == 1 #判断是否为 1
*set集合；
*while not in =>add & sum
*return n==1
Critical Connections in a Network
# 1192. Critical Connections in a Network
import collections
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
def makeGraph(connections):
graph = collections.defaultdict(list)
for conn in connections:
graph[conn[0]].append(conn[1])
graph[conn[1]].append(conn[0])
return graph
graph = makeGraph(connections)
connections = set(map(tuple, (map(sorted, connections))))
rank = [-2] * n
def dfs(node, depth):
if rank[node] >= 0:
# visiting (0<=rank<n), or visited (rank=n)
return rank[node]
rank[node] = depth
min_back_depth = n
for neighbor in graph[node]:
if rank[neighbor] == depth - 1:
continue # don't immmediately go back to parent.
# that's why i didn't choose -1 as the special value, in case depth==0.
back_depth = dfs(neighbor, depth + 1)
if back_depth <= depth:
connections.discard(tuple(sorted((node, neighbor))))
min_back_depth = min(min_back_depth, back_depth)
rank[node] = n # this line is not necessary. see the "brain teaser" section below
return min_back_depth
dfs(0, 0) # since this is a connected graph, we don't have to loop over all nodes.
return list(connections)
# 5. Longest Palindromic Substring
# string s, find the longest palindromic substring in s.
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ""
for i in range(len(s)):
# odd case, like "aba"
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# even case, like "abba"
tmp = self.helper(s, i, i+1)
if len(tmp) > len(res):
res = tmp
return res
# get the longest palindrome, l, r are the middle indexes
# from inner to outer
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
Longest Palindromic Substring
- 遍历元素 逐一判断 以当前元素为中心回文长度
# 5. Longest Palindromic Substring
# string s, find the longest palindromic substring in s.
class Solution:
def longestPalindrome(self, s: str) -> str:
res = ""
for i in range(len(s)):
# odd case, like "aba"
tmp = self.helper(s, i, i)
if len(tmp) > len(res):
res = tmp
# even case, like "abba"
tmp = self.helper(s, i, i+1)
if len(tmp) > len(res):
res = tmp
return res
# get the longest palindrome, l, r are the middle indexes
# from inner to outer
def helper(self, s, l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1
return s[l+1:r]
Merge Two Sorted Lists
# Merge Two Sorted Lists
# Input: 1->2->4, 1->3->4
# Output: 1->1->2->3->4->4
class Solution:
# iteratively
def mergeTwoLists(self, l1, l2):
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
53. Maximum Subarray
# 53. Maximum Subarray
# integer array nums,
# contiguous subarray (containing at least one number)=> largest sum
class Solution:
def maxSubArray(self,nums):
if not nums:
return 0
subSum=maxSum=nums[0]
for num in nums[1:]:
subSum=max(num,num+subSum)
maxSum=max(subSum,maxSum)
return maxSum
Valid Parentheses
# 20. Valid Parentheses
# string containing just the characters '(', ')', '{', '}', '[' and ']'
# determine if the input string is valid.
# correct order&same type
class Solution:
def isValid(self, s: str) -> bool:
stack = []
dict = {"]":"[", "}":"{", ")":"("}
for char in s:
if char in dict.values(): # 开口
stack.append(char)
elif char in dict.keys(): # 闭口 查看字典开口 同时pop出内部对
if stack == [] or dict[char] != stack.pop():
return False
else:
return False
return stack == []
class Solution:
# def twoSorted(self,nums1,nums2):
def findMedianSortedArrays(self, A, B):
l = len(A) + len(B)
if l % 2 == 1:
return self.kth(A, B, l // 2)
else:
return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2
def kth(self, a, b, k):
if not a:
return b[k]
if not b:
return a[k]
ia, ib = len(a) // 2 , len(b) // 2
ma, mb = a[ia], b[ib]
# when k is bigger than the sum of a and b's median indices
if ia + ib < k:
# if a's median is bigger than b's, b's first half doesn't include k
if ma > mb:
return self.kth(a, b[ib + 1:], k - ib - 1)
else:
return self.kth(a[ia + 1:], b, k - ia - 1)
# when k is smaller than the sum of a and b's indices
else:
# if a's median is bigger than b's, a's second half doesn't include k
if ma > mb:
return self.kth(a[:ia], b, k)
else:
return self.kth(a, b[:ib], k)
