- Merge k Sorted Lists 解：use dummy node, PriorityQueue, put(node.val, node) in q.
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = Nonesu
from Queue import PriorityQueue
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
dummy = ListNode(None)
curr = dummy
q = PriorityQueue()
for node in lists:
if node:
q.put((node.val, node))
while q.qsize() > 0:
curr.next = q.get()[1]
curr = curr.next
if curr.next:
q.put((curr.next.val, curr.next))
return dummy.next
Add Two Numbers
Populating Next Right Pointers in Each Node
" if(root.right!=null&&root.next!=null){
root.right.next=root.next.left;
}"
Merge Two Sorted Lists
"dummy = ListNode(0)
tmp = dummy
while l1 and l2:
if l1.val < l2.val:
tmp.next = l1
l1 = l1.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
if l1:
tmp.next = l1
else:
tmp.next = l2
return dummy.next"
Reverse Linked List
"class Solution:
def reverse(self, head):
curt = None
while head != None:
temp = head.next
head.next = curt
curt = head
head = temp
return curt"
Copy List with Random Pointer
"class Solution(object):
def copyRandomList(self, head):
""""""
:type head: RandomListNode
:rtype: RandomListNode
""""""
if head == None:
return None
mymap = {}
nHead = RandomListNode(head.label)
mymap[head] = nHead
p = head
q = nHead
while p!= None:
q.random = p.random
if p.next != None:
q.next = RandomListNode(p.next.label)
mymap[p.next] = q.next
else:
q.next = None
p = p.next
q = q.next
p = nHead
while p!= None:
if p.random != None:
p.random = mymap[p.random]
p = p.next
return nHead"
Insert into a Cyclic Sorted List
"class Solution:
# @param {ListNode} node a list node in the list
# @param {int} x an integer
# @return {ListNode} the inserted new list node
def insert(self, node, x):
# Write your code here
if node is None:
node = ListNode(x)
node.next = node
return node
p = node
prev = None
while True:
prev = p
p = p.next
if x <= p.val and x >= prev.val:
break
if (prev.val > p.val) and (x < p.val or x > prev.val):
break
if p is node:
break
newNode = ListNode(x)
newNode.next = p
prev.next = newNode
return newNode"
Delete Node in a Linked List
"def deleteNode(self, node):
""""""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
""""""
node.val = node.next.val
node.next = node.next.next"
- Copy List with Random Pointer
# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
# def __init__(self, x):
# self.label = x
# self.next = None
# self.random = None
class Solution(object):
def copyRandomList(self, head):
"""
:type head: RandomListNode
:rtype: RandomListNode
"""
if head is None:
return None
tmp = head
while tmp:
newnode = RandomListNode(tmp.label)
newnode.next = tmp.next
tmp.next = newnode
tmp = tmp.next.next
tmp = head
while tmp:
if tmp.random:
tmp.next.random = tmp.random.next
tmp = tmp.next.next
newhead = head.next
pold = head
pnew = newhead
while pnew.next:
pold.next = pnew.next
pold = pold.next
pnew.next = pold.next
pnew = pnew.next
pnew.next = None
pold.next = None
return newhead
- Palindrome Linked List
```
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def isPalindrome(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
node = None
while slow:
tmp = slow.next
slow.next = node
node = slow
slow = tmp
while node:
if node.val != head.val:
return False
node = node.next
head = head.next
return True
252. Meeting Rooms
class Solution(object): def canAttendMeetings(self, intervals): """ :type intervals: List[Interval] :rtype: bool """ intervals = sorted(intervals, key = lambda x: x.start)
stack = []
for elem in intervals:
if len(stack) == 0 or elem.start >= stack[-1].end:
stack.append(elem)
else:
return False
return len(stack) == len(intervals)
599. Minimum Index Sum of Two Lists
class Solution(object): def findRestaurant(self, list1, list2): """ :type list1: List[str] :type list2: List[str] :rtype: List[str] """ mp = {} for i, v in enumerate(list1): mp[v] = i
ans = []
best = 1e9
for j, v in enumerate(list2):
i = mp.get(v, 1e9)
if i + j < best:
best = i + j
ans = [v]
elif i + j == best:
ans.append(v)
return ans
347. Top K Frequent Elements
class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ mp = collections.defaultdict(int) for i in nums: mp[i] += 1
heap = []
for key in mp.keys():
heap.append((-mp[key], key))
heapq.heapify(heap)
topk = []
for i in xrange(0, k):
topk.append(heapq.heappop(heap)[1])
print topk
347. Top K Frequent Elements
class Solution(object): def topKFrequent(self, nums, k): """ :type nums: List[int] :type k: int :rtype: List[int] """ mp = collections.defaultdict(int) for elem in nums: mp[elem] += 1
hp = []
for key in mp:
hp.append((-mp[key], key))
heapq.heapify(hp)
topk = []
for i in range(0, k):
topk.append(heapq.heappop(hp)[1])
return topk
127. Word Ladder
sol: deque
class Solution(object): def ladderLength(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: int """ if not wordList: return 0 wordSet = set(wordList)
wordLen = len(beginWord)
q = collections.deque([(beginWord, 1)])
while q:
array = q.popleft()
currWord, currLen = array[0], array[1]
if currWord == endWord:
return currLen
else:
for i in xrange(wordLen):
part1, part2 = currWord[:i], currWord[i+1:]
for j in 'abcdefghijklmnopqrstuvwxyz':
nextWord = part1 + j + part2
if nextWord in wordSet:
q.append((nextWord, currLen+1))
wordSet.remove(nextWord)
return 0
126. Word Ladder II
class Solution(object): def findLadders(self, beginWord, endWord, wordList): """ :type beginWord: str :type endWord: str :type wordList: List[str] :rtype: List[List[str]] """ dict = set(wordList) dict.add(beginWord) dict.add(endWord)
def buildPath(path, word):
if len(preMap[word]) == 0:
result.append([word] + path)
return
path.insert(0, word)
for w in preMap[word]:
buildPath(path, w)
path.pop(0)
length = len(beginWord)
preMap = {}
for word in dict:
preMap[word] = []
result = []
cur_level = set()
cur_level.add(beginWord)
while True:
pre_level = cur_level
cur_level = set()
for word in pre_level:
dict.remove(word)
for word in pre_level:
for i in range(length):
left = word[:i]
right = word[i+1:]
for c in 'abcdefghijklmnopqrstuvwxyz':
if c != word[i]:
nextWord = left + c + right
if nextWord in dict:
preMap[nextWord].append(word)
cur_level.add(nextWord)
if len(cur_level) == 0:
return []
if endWord in cur_level:
break
buildPath([], endWord)
return result
380. Insert Delete GetRandom O(1)
class RandomizedSet(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.pos = {}
self.nums = []
def insert(self, val):
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
:type val: int
:rtype: bool
"""
if val not in self.pos:
self.nums.append(val)
self.pos[val] = len(self.nums) -1
return True
return False
def remove(self, val):
"""
Removes a value from the set. Returns true if the set contained the specified element.
:type val: int
:rtype: bool
"""
if val in self.pos:
idx, last = self.pos[val], self.nums[-1]
self.pos[last], self.nums[idx] = idx, last
self.nums.pop()
del self.pos[val]
return True
return False
def getRandom(self):
"""
Get a random element from the set.
:rtype: int
"""
import random
return self.nums[random.randint(0, len(self.nums)-1)]
Your RandomizedSet object will be instantiated and called as such:
obj = RandomizedSet()
param_1 = obj.insert(val)
param_2 = obj.remove(val)
param_3 = obj.getRandom()
Top k Largest Numbers
sol: Nlog(k), heap
import heapq
class Solution: ''' @param {int[]} nums an integer array @param {int} k an integer @return {int[]} the top k largest numbers in array ''' import heapq def topk(self, nums, k):
# Write your code here
heap = []
res = []
for num in nums:
heapq.heappush(heap, num)
if len(heap) > k:
heapq.heappop(heap)
for i in xrange(len(heap)):
res.append(heapq.heappop(heap))
return res[::-1]
Hash Function
def hashCode(self, key, HASH_SIZE):
# write your code here
ans = 0
for s in key:
ans = (ans * 33 + ord(s)) % HASH_SIZE
return ans
224. Basic Calculator
class Solution(object): def calculate(self, s): """ :type s: str :rtype: int """ res, num, sign, stack = 0, 0, 1, [] for ss in s: if ss.isdigit(): num = 10num + int(ss) elif ss in ["-", "+"]: res += signnum num = 0 sign = 1 if ss=="+" else -1 elif ss == "(": stack.append(res) stack.append(sign) sign, res = 1, 0 elif ss == ")": res += signnum res = stack.pop() res += stack.pop() num = 0 return res + num*sign
K Closest Points
sol: heappush(heap, Type(point, dist)), res[::-1]
Definition for a point.
class Point:
def init(self, a=0, b=0):
self.x = a
self.y = b
class Type: def init(self, point, dist): self.dist = dist self.point = point def cmp(self, other): if other.dist != self.dist: return other.dist - self.dist if other.point.x != self.point.x: return other.point.x - self.point.x return other.point.y - self.point.y class Solution:
# @param {Pint[]} points a list of points
# @param {Point} origin a point
# @param {int} k an integer
# @return {Pint[]} the k closest points
def kClosest(self, points, origin, k):
# Write your code here
import heapq
heap = []
for p in points:
dist = self.getD(p, origin)
heapq.heappush(heap, Type(p, dist))
if len(heap) > k:
heapq.heappop(heap)
res = []
while len(heap) > 0:
res.append(heapq.heappop(heap).point)
return res[::-1]
def getD(self, pa, pb):
return (pa.x - pb.x)**2 + (pa.y - pb.y)**2
218. The Skyline Problem
sol: heap
class Solution(object): def getSkyline(self, buildings): """ :type buildings: List[List[int]] :rtype: List[List[int]] """ import heapq def addsky(pos, hei): if sky[-1][1] != hei: sky.append([pos, hei])
sky = [[-1, 0]]
position = set([b[0] for b in buildings] + [b[1] for b in buildings])
i = 0
live = []
for t in sorted(position):
while i < len(buildings) and buildings[i][0] <= t:
heapq.heappush(live, [-buildings[i][2], buildings[i][1]])
i += 1
while live and live[0][1] <= t:
heapq.heappop(live)
h = -live[0][0] if live else 0
addsky(t, h)
return sky[1:]
Insert Delete GetRandom O(1) - Duplicates allowed
import random
class RandomizedCollection(object):
def __init__(self):
self.vals, self.idxs = [], collections.defaultdict(set)
def insert(self, val):
self.vals.append(val)
self.idxs[val].add(len(self.vals) - 1)
return len(self.idxs[val]) == 1
def remove(self, val):
if self.idxs[val]:
out, ins = self.idxs[val].pop(), self.vals[-1]
self.vals[out] = ins
if self.idxs[ins]:
self.idxs[ins].add(out)
self.idxs[ins].discard(len(self.vals) - 1)
self.vals.pop()
return True
return False
def getRandom(self):
return random.choice(self.vals)
min stack
sol: q
class MinStack(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.q = []
def push(self, x):
"""
:type x: int
:rtype: void
"""
curMin = self.getMin()
if curMin is None or x < curMin:
curMin = x
self.q.append((x, curMin))
def pop(self):
"""
:rtype: void
"""
self.q.pop()
def top(self):
"""
:rtype: int
"""
if len(self.q) == 0:
return None
else:
return self.q[len(self.q)-1][0]
def getMin(self):
"""
:rtype: int
"""
if len(self.q) == 0:
return None
else:
return self.q[len(self.q)-1][1]
```