In [1]:
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
if n == 0 or s[0] == '0':
return 0
fn_2, fn_1, fn = 1, 1, 1
for i in range(1, n):
if s[i] == '0':
if int(s[i-1]) > 2 or int(s[i-1]) == 0:
return 0
else:
fn = fn_2
else:
fn = fn_1
if 10 < int(s[i-1] + s[i]) < 27:
fn += fn_2
fn_2, fn_1 = fn_1, fn
return fn
In [3]:
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
v, w, p = 0, int(s > ''), ''
for c in s:
v, w, p = w, (c > '0') * w + (9 < int(p + c) < 27) * v, c
return w
In [2]:
class Solution(object):
def numDecodings(self, s):
"""
:type s: str
:rtype: int
"""
Mod = 10**9 + 7
e0, e1, e2 = 1, 0, 0
for c in s:
if c == '*':
f0 = 9 * e0 + 9 * e1 + 6 * e2
f1 = e0
f2 = e0
else:
f0 = (c > '0') * e0 + e1 + (c < '7') * e2
f1 = (c == '1') * e0
f2 = (c == '2') * e0
e0, e1, e2 = f0 % Mod, f1, f2
return e0
• 怎样识别动态规划类题？ – 最优化，问方法数，不需要打印所有路径的大概率是 – 看下数据范围
• 动态规划的解题步骤： 0.考虑最后一步（怎么分解，怎么走） 直觉、解题灵感来源 1.定状态 2.写转移方程 3.初始条件、边界情况
In [1]:
## consider about it from the opposite way
class Solution:
"""
@param: l1: top-left coordinate of first rectangle
@param: r1: bottom-right coordinate of first rectangle
@param: l2: top-left coordinate of second rectangle
@param: r2: bottom-right coordinate of second rectangle
@return: true if they are overlap or false
"""
def doOverlap(self, l1, r1, l2, r2):
# write your code here
if l1.x > r2.x or l2.x > r1.x:
return False
elif l1.y < r2.y or r1.y > l2.y:
return False
else:
return True
http://www.lintcode.com/en/problem/check-word-abbreviation/
https://leetcode.com/problems/valid-word-abbreviation/description/
In [1]:
class Solution:
"""
@param: word: a non-empty string
@param: abbr: an abbreviation
@return: true if string matches with the given abbr or false
"""
def validWordAbbreviation(self, word, abbr):
# write your code here
i, n = 0, '0'
for c in abbr:
if c.isdigit():
if c == n:
return False
n += c
else:
i += int(n)
if i >= len(word) or word[i] != c:
return False
i += 1
n = '0'
return len(word[i:]) == int(n)
http://www.lintcode.com/en/problem/words-abbreviation/
In [16]:
import collections
In [24]:
class Solution:
"""
@param: dict: an array of n distinct non-empty strings
@return: an array of minimal possible abbreviations for every word
"""
def wordsAbbreviation(self, dict):
# write your code here
self.dic = {}
self.solve(dict, 0)
return map(self.dic.get, dict)
def abbr(self, word, size):
if len(word) - size <= 3:
return word
else:
return word[: size + 1] + str(len(word) - size - 2) + word[-1]
def solve(self, dict, size):
glist = collections.defaultdict(list)
for word in dict:
glist[self.abbr(word, size)].append(word)
for abbr, words in glist.items():
if len(words) == 1:
self.dic[words[0]] = abbr
else:
self.solve(words, size+1)
In [3]:
dict = ["like", "god", "internal", "me", "internet", "interval", "intension", "face", "intrusion"]
dic = {"like": "l2e", "face": "f2e"}
In [13]:
list(map(dic.get, dict))
Out[13]:
In [4]:
dic.get("like")
Out[4]:
In [18]:
def abbr(word, size):
if len(word) - size <= 3:
return word
return word[:size+1] + str(len(word) - size - 2) + word[-1]
In [20]:
glist = collections.defaultdict(list)
for word in dict:
glist[abbr(word, 0)].append(word)
In [21]:
glist
Out[21]:
In [23]:
for abbr, words in glist.items():
print(abbr, words)
In [25]:
Solu = Solution()
In [26]:
Solu.wordsAbbreviation(dict)
Out[26]:
In [27]:
list(Solu.wordsAbbreviation(dict))
Out[27]:
In [28]:
list(Solu.wordsAbbreviation(dict))
Out[28]:
https://leetcode.com/problems/generalized-abbreviation/description/
nice problem!
a letter can be represented as a word or a number, so totally 2^n possibilities.
In [17]:
class Solution(object):
def generateAbbreviations(self, word):
"""
:type word: str
:rtype: List[str]
"""
def helper(word, pos, count, cur, result):
if pos == len(word):
result.append(cur + (str(count) if count > 0 else ''))
else:
helper(word, pos + 1, count + 1, cur, result)
helper(word, pos + 1, 0, cur + (str(count) if count > 0 else '') + word[pos], result)
result = []
helper(word, 0, 0, '', result)
return result
https://leetcode.com/problems/unique-word-abbreviation/description/
In [ ]:
class ValidWordAbbr(object):
def __init__(self, dictionary):
"""
:type dictionary: List[str]
"""
self.dic = collections.defaultdict(set)
for word in dictionary:
self.dic[self.abbr(word)].add(word)
def abbr(self, word):
if len(word) <= 2:
return word
else:
return word[0] + str(len(word) -2) + word[-1]
def isUnique(self, word):
"""
:type word: str
:rtype: bool
"""
abbr = self.abbr(word)
if abbr not in self.dic:
return True
else:
return len(self.dic[abbr]) == 1 and word in self.dic[abbr]
# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)
https://leetcode.com/problems/minimum-unique-word-abbreviation/description/
In [ ]:
class Solution(object):
def minAbbreviation(self, target, dictionary):
"""
:type target: str
:type dictionary: List[str]
:rtype: str
"""
def abbr(target, num):
cur, count = '', 0
for c in target:
if num & 1 == 1:
if count:
cur += str(count)
count = 0
cur += c
else:
count += 1
num >>= 1
if count:
cur += str(count)
return cur
m, diffs = len(target), []
for word in dictionary:
if len(word) != m:
continue
bits = 0
for i, c in enumerate(word):
if target[i] != c:
bits += 2 ** i
diffs += [bits]
if not diffs:
return str(m)
abbrs = []
for i in range(2 ** m):
if all(i & d for d in diffs):
abbrs.append(abbr(target, i))
return min(abbrs, key=lambda x: len(x))
In [8]:
import operator
word = '1e4'
target = '1r2'
any(map(operator.eq, word, target))
Out[8]:
In [18]:
num = 5
num >>= 1
num
Out[18]:
In [19]:
num >> 1
Out[19]:
In [20]:
num
Out[20]:
In [12]:
diffs = []
for i in [1,2,3]:
diffs += i,
diffs
Out[12]:
In [14]:
?all
In [1]:
## straight foreward
class MovingAverage:
"""
@param: size: An integer
"""
def __init__(self, size):
# do intialization if necessary
self.idx = 0
self.sum = 0
self.list = []
self.size = size
"""
@param: val: An integer
@return:
"""
def next(self, val):
# write your code here
self.sum += val
self.idx += 1
if self.idx <= self.size:
self.list += [self.sum]
return float(self.list[-1]) / self.idx
else:
j = self.idx % self.size - 1
prev = self.list[j]
self.list[j] = self.sum
return float(self.list[j] - prev) / self.size
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param = obj.next(val)
• 如何快速求和？ 前缀和数组(dummy 0)
• 如何节省储存空间呢？ 链表/滚动
• 写滚动的技巧 先写程序最后加滚动
In [99]:
## data structure: queue
class MovingAverage(object):
def __init__(self, size):
"""
Initialize your data structure here.
:type size: int
"""
self.queue = collections.deque(maxlen=size)
self.size = size
self.sum = 0
def next(self, val):
"""
:type val: int
:rtype: float
"""
self.sum += val
if len(self.queue) == self.size:
self.sum -= self.queue.popleft()
self.queue.append(val)
return float(self.sum) / len(self.queue)
# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)
In [100]:
import collections
In [101]:
collections.deque.popleft
https://leetcode.com/problems/one-edit-distance/description/
In [21]:
class Solution(object):
def isOneEditDistance(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
m, n = len(s), len(t)
if abs(m - n) > 1:
return False
elif m < n:
return self.isOneEditDistance(t, s)
else:
for i in range(n):
if s[i] != t[i]:
if m == n:
return s[i+1:] == t[i+1:]
else:
return s[i+1:] == t[i:]
return m != n
In [22]:
s = '12dere'
n = len(s)
s[n:]
Out[22]:
https://leetcode.com/problems/read-n-characters-given-read4/description/
In [102]:
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):
class Solution(object):
def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Maximum number of characters to read (int)
:rtype: The number of characters read (int)
"""
idx = 0
while True:
buf4 = [""]*4
curr = min(read4(buf4), n-idx)
for i in range(curr):
buf[idx] = buf4[i]
idx += 1
if curr != 4 or idx == n:
return idx
In [23]:
buf4 = [""]*4
buf4
Out[23]:
https://leetcode.com/problems/read-n-characters-given-read4-ii-call-multiple-times/description/
难点：
• 如果只读3个，剩下的一个怎么处理？（读多的怎么留着给下次用？）
• Read4 这个函数只读了2个怎么办？ （读到末尾时，没有读全4个）
In [103]:
# The read4 API is already defined for you.
# @param buf, a list of characters
# @return an integer
# def read4(buf):
class Solution(object):
def __init__(self):
self.queue = []
def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Maximum number of characters to read (int)
:rtype: The number of characters read (int)
"""
idx = 0
while True:
buf4 = [""]*4
l = read4(buf4)
self.queue.extend(buf4)
curr = min(len(self.queue), n-idx)
for i in range(curr):
buf[idx] = self.queue.pop(0)
idx += 1
if curr == 0:
break
return idx
In [28]:
buf4 = [""]*4
queue1, queue2 = [], []
queue1.append(buf4)
queue2.extend(buf4)
queue1, queue2
Out[28]:
http://www.lintcode.com/zh-cn/problem/strings-serialization/
• abc def -> abc:;def:;
• ab:c def -> ab::c:;def:;
• ab:;c def -> ab::;c:;def:;
• 用‘：’表示转义，那么连接符就是’：；’ 表示‘：’本身就是‘：：’
In [114]:
class Solution:
"""
@param: strs: a list of strings
@return: encodes a list of strings to a single string.
"""
def encode(self, strs):
# write your code here
res = ''
for s in strs:
for c in s:
if c == ":":
res += "::"
else:
res += c
res += ":;"
return res
"""
@param: str: A string
@return: dcodes a single string to a list of strings
"""
def decode(self, str):
# write your code here
res = []
s = ''
i = 0
while i < len(str) - 1:
if str[i] == ":":
if str[i+1] == ";":
res += [s]
s = ''
else:
s += str[i+1]
i += 2
else:
s += str[i]
i += 1
return res
https://leetcode.com/problems/longest-absolute-file-path/description/
In [26]:
len("dir/subdir2/subsubdir2/file2.ext")
Out[26]:
In [27]:
s = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"
In [31]:
s.splitlines()
Out[31]:
In [32]:
line = '\t\tfile.ext'
line.lstrip('\t')
Out[32]:
In [115]:
class Solution(object):
def lengthLongestPath(self, input):
"""
:type input: str
:rtype: int
"""
maxlen = 0
pathlen = {0:0}
for line in input.splitlines():
name = line.lstrip('\t')
depth = len(line) - len(name)
if '.' in name:
maxlen = max(maxlen, pathlen[depth] + len(name))
else:
pathlen[depth+1] = pathlen[depth] + len(name) + 1
return maxlen
In [116]:
class Solution(object):
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
roman = {"I": 1, "V": 5, "X": 10, "L": 50, "C": 100, "D": 500, "M": 1000}
if len(s) == 0:
return 0
res = roman[s[-1]]
idx = len(s) - 2
while idx >= 0:
if roman[s[idx]] < roman[s[idx+1]]:
res -= roman[s[idx]]
else:
res += roman[s[idx]]
idx -= 1
return res
In [117]:
class Solution(object):
def parse(self, digit, index):
nums = {1: "I", 2: "II", 3: "III", 4: "IV", 5: "V", 6: "VI", 7: "VII", 8: "VIII", 9: "IX"}
roman = {
"I": ["I", "X", "C", "M"],
"V": ["V", "L", "D", "?"],
"X": ["X", "C", "M", "?"]
}
s = nums[digit]
return s.replace("X", roman["X"][index]).replace("V", roman["V"][index]).replace("I", roman["I"][index])
def intToRoman(self, num):
"""
:type num: int
:rtype: str
"""
ans = ""
index = 0
while num > 0:
digit = num % 10
if digit != 0:
ans = self.parse(digit, index) + ans
num = int(num / 10)
index += 1
return ans
# # solution 1
# nums = [
# ["I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],
# ["X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],
# ["C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],
# ["M", "MM", "MMM"]
# ]
# ans = ""
# row = 0
# while num > 0:
# digit = num % 10
# if digit != 0:
# ans = nums[row][digit-1] + ans
# num = num / 10
# row += 1
# return ans
https://leetcode.com/problems/find-the-celebrity/description/
In [118]:
# The knows API is already defined for you.
# @param a, person a
# @param b, person b
# @return a boolean, whether a knows b
# def knows(a, b):
class Solution(object):
def findCelebrity(self, n):
"""
:type n: int
:rtype: int
"""
candidate = 0
for i in range(1, n):
if knows(candidate, i):
candidate = i
for i in range(candidate):
if not knows(i, candidate) or knows(candidate, i):
return -1
for i in range(candidate+1, n):
if not knows(i, candidate) or knows(candidate, i):
return -1
return candidate
In [120]:
nums = [0, 1, 3, 50, 75]
In [123]:
for k, v in enumerate(nums):
print(k, v, nums[k])
In [155]:
class Solution(object):
def findMissingRanges(self, nums, lower, upper):
"""
:type nums: List[int]
:type lower: int
:type upper: int
:rtype: List[str]
"""
res = []
start = lower
for k, v in enumerate(nums): # 两端点和一头一尾形成的区间 + for循环扫描中间形成的区间
if v < start:
continue
elif v == start:
start += 1
continue
res.append(self.addRange(start, v-1))
start = v + 1
if start <= upper: # corner case
res.append(self.addRange(start, upper))
return res
def addRange(self, start, end): # – 利用函数让自己的代码更简洁 （见代码）
return str(start) if start == end else str(start) + "->" + str(end)
In [124]:
starts = [2, 1, 15, 8]
idx = sorted(range(len(starts)), key=lambda x: starts[x])
idx
Out[124]:
In [125]:
intervals = [[8,10], [2,6]]
intervals.sort()
In [126]:
intervals
Out[126]:
In [156]:
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[Interval]
"""
intervals = sorted(intervals, key=lambda x: x.start) # sort skill !!!
res = []
for interval in intervals:
if len(res) == 0 or res[-1].end < interval.start: # when to add interval
res.append(interval)
else:
res[-1].end = max(res[-1].end, interval.end)
return res
In [157]:
# Definition for an interval.
# class Interval(object):
# def __init__(self, s=0, e=0):
# self.start = s
# self.end = e
class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
intervals = intervals + [newInterval]
intervals = sorted(intervals, key=lambda x: x.start)
res = []
for interval in intervals:
if len(res) == 0 or res[-1].end < interval.start:
res.append(interval)
else:
res[-1].end = max(res[-1].end, interval.end)
return res
http://www.lintcode.com/zh-cn/problem/first-position-unique-character/
In [127]:
dic = {'1':[1,5,8], '0':[2,4,3]}
In [128]:
for key, value in dic.items():
print(key, value)
In [158]:
class Solution:
"""
@param: s: a string
@return: it's index
"""
def firstUniqChar(self, s):
# write your code here
dic = {}
for c in s:
dic[c] = dic.get(c, 0) + 1
for i in range(len(s)):
if dic[s[i]] == 1:
return i
return -1
In [135]:
ord('a'), chr(97)
Out[135]:
In [138]:
abs([1,2])
In [139]:
from collections import Counter
Counter('aba')
Out[139]:
In [140]:
dic = {'a': 2, 'b': 1}
In [141]:
del dic['a']
dic
Out[141]:
In [159]:
# class Solution(object):
# def findAnagrams(self, s, p):
# """
# :type s: str
# :type p: str
# :rtype: List[int]
# """
# m, n = len(s), len(p)
# res = []
# if m < n:
# return res
# pc = collections.Counter(p)
# sc = collections.Counter(s[:n-1])
# for i in range(m-n+1):
# sc[s[n-1+i]] += 1
# if sc == pc:
# res.append(i)
# sc[s[i]] -= 1
# if sc[s[i]] == 0:
# del sc[s[i]]
# return res
class Solution:
"""
@param: s: a string
@param: p: a string
@return: a list of index
"""
def findAnagrams(self, s, p):
# write your code here
m, n = len(s), len(p)
res = []
if m < n:
return res
det = [0 for i in range(26)]
for i in range(n):
jp = ord(p[i]) - ord('a')
det[jp] -= 1
js = ord(s[i]) - ord('a')
det[js] += 1
sum = 0
for d in det:
sum += abs(d)
if sum == 0:
res.append(0)
for i in range(0, m-n):
jl = ord(s[i]) - ord('a')
sum -= abs(det[jl])
det[jl] -= 1
sum += abs(det[jl])
jr = ord(s[i+n]) - ord('a')
sum -= abs(det[jr])
det[jr] += 1
sum += abs(det[jr])
if sum == 0:
res.append(i+1)
return res
In [144]:
set().union('he'), set().union(['he'])
Out[144]:
In [160]:
len(set().union('he'))
Out[160]:
In [161]:
def getAbbr(word):
if len(word) > 2:
return word[0] + str(len(word) - 2) + word[-1]
return word
In [167]:
d = collections.defaultdict(set)
for word in ['aa', 'bb', 'cc', 'cc','bb']:
d[getAbbr(word)].add(word)
d
Out[167]:
In [164]:
collections.defaultdict?
In [168]:
class ValidWordAbbr(object):
def __init__(self, dictionary):
"""
:type dictionary: List[str]
"""
self.dic = collections.defaultdict(set)
for word in dictionary:
self.dic[self.getAbbr(word)].add(word)
def getAbbr(self, word):
return word if len(word) < 3 else word[0] + str(len(word)-2) + word[-1]
def isUnique(self, word):
"""
:type word: str
:rtype: bool
"""
abbr = self.getAbbr(word)
if abbr not in self.dic:
return True
else:
return len(self.dic[abbr]) == 1 and word in self.dic[abbr]
# class ValidWordAbbr(object):
# def __init__(self, dictionary):
# """
# :type dictionary: List[str]
# """
# self.dic = {}
# for word in dictionary:
# abrr = self.abrr(word)
# self.dic[abrr] = self.dic.get(abrr, set()).union([word])
# def abrr(self, word):
# return word if len(word) < 3 else word[0] + str(len(word)-2) + word[-1]
# def isUnique(self, word):
# """
# :type word: str
# :rtype: bool
# """
# abrr = self.abrr(word)
# if abrr in self.dic:
# if len(self.dic[abrr]) > 1 or word not in self.dic[abrr]:
# return False
# return True
# # Your ValidWordAbbr object will be instantiated and called as such:
# # obj = ValidWordAbbr(dictionary)
# # param_1 = obj.isUnique(word)
https://leetcode.com/problems/longest-consecutive-sequence/description/
In [169]:
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dic = {}
for n in nums:
dic[n] = False
maxlen = 0
for n in nums:
if dic[n]:
continue
length = 1
left, right = n - 1, n + 1
while left in dic:
length += 1
dic[left] = True
left -= 1
while right in dic:
length += 1
dic[right] = True
right += 1
maxlen = max(maxlen, length)
return maxlen
In [145]:
a = set().union('he')
In [149]:
a = [0, 1, 2]
a.pop()
a
Out[149]:
In [154]:
import random
for i in range(15):
print(random.randint(0, 5 - 1))
In [170]:
class LoadBalancer:
def __init__(self):
# do intialization if necessary
self.ids = []
self.index = {}
"""
@param: server_id: add a new server to the cluster
@return: nothing
"""
def add(self, server_id):
# write your code here
self.ids.append(server_id)
self.index[server_id] = len(self.ids) - 1
"""
@param: server_id: server_id remove a bad server from the cluster
@return: nothing
"""
def remove(self, server_id):
# write your code here
idx = self.index[server_id]
del self.index[server_id]
last_id = self.ids[-1]
self.index[last_id] = idx
self.ids[idx] = last_id
self.ids.pop()
"""
@return: pick a server in the cluster randomly with equal probability
"""
def pick(self):
# write your code here
import random
idx = random.randint(0, len(self.ids)-1)
return self.ids[idx]
https://leetcode.com/problems/convert-bst-to-greater-tree/description/
In [1]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def convertBST(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
self.sum = 0
self.dfs(root)
return root
def dfs(self, root):
if root is None:
return
if root.right:
self.dfs(root.right)
self.sum += root.val
root.val = self.sum
if root.left:
self.dfs(root.left)
https://leetcode.com/problems/inorder-successor-in-bst/description/
(a) Inorder (Left, Root, Right) : 4 2 5 1 3
(b) Preorder (Root, Left, Right) : 1 2 4 5 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1
In [2]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def inorderSuccessor(self, root, p):
"""
:type root: TreeNode
:type p: TreeNode
:rtype: TreeNode
"""
succ = None
while root:
if root.val <= p.val:
root = root.right
else:
succ = root
root = root.left
return succ
https://leetcode.com/problems/binary-tree-upside-down/description/
In [3]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def upsideDownBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if root is None or root.left is None:
return root
new_root = self.upsideDownBinaryTree(root.left)
root.left.left = root.right
root.left.right = root
root.left = None
root.right = None
return new_root
https://leetcode.com/problems/find-leaves-of-binary-tree/description/
In [4]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findLeaves(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
result = []
self.dfs(root, result)
return result
def dfs(self, root, result):
if root is None:
return 0
level = max(self.dfs(root.left, result), self.dfs(root.right, result)) + 1
if level > len(result):
result.append([])
result[level-1].append(root.val)
return level
https://leetcode.com/problems/binary-tree-vertical-order-traversal/description/
In [5]:
a = []
a.append((1,2))
a
Out[5]:
In [6]:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
result = collections.defaultdict(list)
level = [(root, 0)]
while level:
next_level = []
for node, order in level:
if node:
result[order].append(node.val)
next_level.append((node.left, order-1))
next_level.append((node.right, order+1))
level = next_level
return [result[i] for i in sorted(result)]
1.BFS是用来搜索最短径路的解是比较合适的，比如求最少步数的解，最少交换次数的解，因为BFS搜索过程中遇到的解一定是离根最近的，所以遇到一个解，一定就是最优解，此时搜索算法可以终止。这个时候不适宜使用DFS，因为DFS搜索到的解不一定是离根最近的，只有全局搜索完毕，才能从所有解中找出离根的最近的解。（当然这个DFS的不足，可以使用迭代加深搜索ID-DFS去弥补）
2.空间优劣上，DFS是有优势的，DFS不需要保存搜索过程中的状态，而BFS在搜索过程中需要保存搜索过的状态，而且一般情况需要一个队列来记录。
3.DFS适合搜索全部的解，因为要搜索全部的解，那么BFS搜索过程中，遇到离根最近的解，并没有什么用，也必须遍历完整棵搜索树，DFS搜索也会搜索全部，但是相比DFS不用记录过多信息，所以搜素全部解的问题，DFS显然更加合适。
4.基本原则：能用BFS的时候就用BFS，不能用的时候再用DFS。
In [ ]:
## version 1: traversal
queue = [start]
while queue:
node = queue.pop(0)
new_node = node + 1 # or other conditions
queue.append(new_node)
## version 2: length of shortest path
length, level = 0, [start]
while level:
new_level = []
for node in level:
new_node = node + 1
new_level.append(new_node)
length += 1
level = new_level
https://leetcode.com/problems/surrounded-regions/description/
小技巧总结：
• 在网格图、矩阵图、棋盘上做多个方向扩展时，用dx dy数组会让程序写起 来更方便
In [11]:
any?
In [12]:
any([[]])
Out[12]:
In [83]:
row = 'XXSi'
['XO'[c == 'S'] for c in row]
Out[83]:
In [86]:
board = ["XXXX","XOOX","XXOX","XSXX"]
board[:] = [['XO'[c == 'S'] for c in row] for row in board]
board
Out[86]:
In [95]:
board = [list("XXXX"),list("XOOX"),list("XXOX"),list("XSXX")]
for row in board:
for i, c in enumerate(row):
row[i] = 'XO'[c == 'S']
board
Out[95]:
In [89]:
class Solution(object):
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
if not any(board):
return
m, n = len(board), len(board[0])
save = [ij for k in range(max(m,n)) for ij in ((0, k), (m-1, k), (k, 0), (k, n-1))]
while save:
i, j = save.pop()
if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
board[i][j] = 'S'
save += (i+1, j), (i-1, j), (i, j+1), (i, j-1)
for row in board:
for i, c in enumerate(row):
if c == 'S':
row[i] = 'O'
else:
row[i] = 'X'
# for row in board:
# for i, c in enumerate(row):
# row[i] = 'XO'[c == 'S']
# board[:] = [['XO'[c == 'S'] for c in row] for row in board]
In [93]:
c = Solution()
board = [list("XXXX"),list("XOOX"),list("XXOX"),list("XOXX")] # board is a list of list !!!
c.solve(board)
board
Out[93]:
https://leetcode.com/problems/walls-and-gates/description/
小技巧总结：
– 多源点单终点 --> 单源点多终点，最短路常用转化套路
– 多源多终点 --> 单源多终点 （增加超级源，最短路常用转化套路）
– BFS可以求边长=1的图的最短路（如此题的棋盘图）
In [82]:
class Solution(object):
def wallsAndGates(self, rooms):
"""
:type rooms: List[List[int]]
:rtype: void Do not return anything, modify rooms in-place instead.
"""
if not any(rooms): return
IFN = 2147483647
m, n = len(rooms), len(rooms[0])
queue = [(i, j) for i, row in enumerate(rooms) for j, c in enumerate(row) if c == 0]
while queue:
i, j = queue.pop(0)
for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):
if 0 <= x < m and 0 <= y < n and rooms[x][y] == IFN:
rooms[x][y] = rooms[i][j] + 1
queue.append((x, y))
In [ ]:
## version 1: traversal
stack = [start]
while stack:
node = stack.pop()
new_node = node + 1 # or other conditions
stack.append(new_node)
## version 2: Divide & Conquer
def dfs(root): # ex: binary tree
## null or leaf
if root is None:
## do something and return;
## Divide
left = dfs(root.left);
right = dfs(root.right);
## Conquer
result = Merge(left, right)
return result
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
In [3]:
digits ='23'
chr = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
res = []
In [4]:
for i in range(len(digits)):
num = int(digits[i])
temp = []
for c in chr[num]:
if len(res) == 0:
temp += [c]
else:
for r in res:
temp += [r + c]
res[:] = temp
res
Out[4]:
In [96]:
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
n, res = len(digits), []
if n == 0: return res
letters = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
for i in range(n):
num = int(digits[i])
temp = []
for c in letters[num]:
if len(res) == 0:
temp.append(c)
else:
for j in range(len(res)):
temp.append(res[j]+c)
res[:] = temp
return res
In [97]:
# 思路：
# • 基础枚举型DFS（按方法1 执行过程理解）
# – 输入数字串长度为n，做n个阶段的选择，DFS n层
# – 每一阶段枚举该位的数字对应的一个字母
# – 直到所有情况都枚举完
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
def dfs(num, string, res):
if num == n:
res.append(string)
return
for c in letters[int(digits[num])]:
dfs(num+1, string+c, res)
n, res = len(digits), []
if n == 0: return res
letters = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
dfs(0, '', res)
return res
http://www.lintcode.com/zh-cn/problem/factorization/
(1) the way to add path
(2) the way to copy temp in the last problem
In [33]:
a = []
a.append([1,2,3])
a.append([2,3])
a
Out[33]:
In [63]:
class Solution:
"""
@param: n: An integer
@return: a list of combination
"""
def getFactors(self, n):
# write your code here
def dfs(start, remain):
if remain == 1:
if len(path) > 1:
print(path, result)
result.append(path)
print(result)
return
for i in range(start, remain):
if i > int(remain / i):
break
if remain % i == 0:
path.append(i)
dfs(i, int(remain/i))
path.pop()
path.append(remain)
dfs(remain, 1)
path.pop()
# print(result)
result, path = [], []
dfs(2, n)
return result
In [64]:
c = Solution()
In [65]:
c.getFactors(8)
Out[65]:
In [47]:
a = [[2, 2, 2]]
a.append([2,4])
a += [[1]]
a
Out[47]:
In [98]:
# 思路：
# • DFS：
# – 扩展：枚举每一个位置的因子
# • 每次从前一个枚举的因子start开始枚举，以保证枚举因子的顺序是从小到大
# – 退出条件：n除以已枚举因子之后还剩的数remain = 1 时
# • 用什么方法记录状态
# – start、remain采用方法1 放到DFS函数的参数中
# – 记录已枚举因子的数组path采用方法3 成员变量手动模拟栈
class Solution:
"""
@param: n: An integer
@return: a list of combination
"""
def getFactors(self, n):
# write your code here
def dfs(start, remain):
if remain == 1:
if len(path) > 1:
result.append(path[:])
return
for i in range(start, int(remain**0.5) + 1):
if remain % i == 0:
path.append(i)
dfs(i, remain/i)
path.pop()
path.append(remain)
dfs(start, 1)
path.pop()
path, result = [], []
dfs(2, n)
return result
In [78]:
alist = ['a1', 'a2', 'a3']
blist = ['b1', 'b2', 'b3']
for i, (a, b) in enumerate(zip(alist, blist)):
print(i, a, b)
In [99]:
class Solution(object):
def wordSquares(self, words):
"""
:type words: List[str]
:rtype: List[List[str]]
"""
n, res = len(words[0]), []
starts = collections.defaultdict(list)
for i in range(1, n):
for word in words:
starts[word[:i]].append(word)
def dfs(square):
k = len(square)
if k == n:
res.append(square)
return
start = ''
for i in range(k):
start += square[i][k]
for word in starts[start]:
dfs(square + [word])
for word in words:
dfs([word])
return res
https://leetcode.com/problems/expression-add-operators/description/
In [100]:
class Solution(object):
def addOperators(self, num, target):
"""
:type num: str
:type target: int
:rtype: List[str]
"""
n, res = len(num), []
def dfs(left, temp, cur, last):
if len(left) == 0:
if cur == target:
res.append(temp[:])
return
for i in range(1, len(left)+1):
val = left[:i]
if i == 1 or (i > 1 and left[0] != '0'):
dfs(left[i:], temp + '+' + val, cur + int(val), int(val))
dfs(left[i:], temp + '-' + val, cur - int(val), -int(val))
dfs(left[i:], temp + '*' + val, cur -last + last*int(val), last*int(val))
for i in range(1, n+1):
if i == 1 or (i > 1 and num[0] != '0'):
dfs(num[i:], num[:i], int(num[:i]), int(num[:i]))
return res
https://leetcode.com/problems/search-a-2d-matrix/description/
In [ ]:
# binary search template
while start + 1 < end:
mid = start + (end - start) / 2
if ....
In [172]:
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
m, n = len(matrix), len(matrix[0])
start, end = 0, m*n - 1
while start + 1 < end:
mid = start + (end - start) / 2
i = mid / n
j = mid % n
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
end = mid - 1
else:
start = mid + 1
i = start / n
j = start % n
if matrix[i][j] == target:
return True
i = end / n
j = end % n
if matrix[i][j] == target:
return True
return False
https://leetcode.com/problems/search-a-2d-matrix-ii/description/
In [171]:
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if len(matrix) == 0 or len(matrix[0]) == 0:
return False
m, n = len(matrix), len(matrix[0])
r, c = 0, n-1
while r < m and c >= 0:
if matrix[r][c] == target:
return True
elif matrix[r][c] > target:
c -= 1
else:
r += 1
return False
In [174]:
for i in range(-1):
print(i)
In [175]:
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
for i in range(m):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
for i in range(m):
for j in range(n/2):
matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
https://leetcode.com/problems/sparse-matrix-multiplication/description/
In [176]:
class Solution(object):
def multiply(self, A, B):
"""
:type A: List[List[int]]
:type B: List[List[int]]
:rtype: List[List[int]]
"""
m, n, l = len(A), len(B), len(B[0])
dicA, dicB = {}, {}
for i in range(m):
for j in range(n):
if A[i][j] != 0:
dicA[i] = dicA.get(i, []) + [(j, A[i][j])]
for i in range(n):
for j in range(l):
if B[i][j] != 0:
dicB[i] = dicB.get(i, []) + [(j, B[i][j])]
C = [[0 for j in range(l)] for i in range(m)]
for i in dicA:
for a in dicA[i]:
j = a[0]
if j in dicB:
for b in dicB[j]:
k = b[0]
C[i][k] += a[1]*b[1]
return C
# # faster
# m, n, l = len(A), len(B), len(B[0])
# C = [[0 for j in range(l)] for i in range(m)]
# for i in range(m):
# for j in range(n):
# if A[i][j] != 0:
# for k in range(l):
# C[i][k] += A[i][j]*B[j][k]
# return C
http://www.lintcode.com/zh-cn/problem/big-integer-addition/
https://leetcode.com/problems/add-strings/description/
ord(num1[i]) - ord('0') is faster than int(num1[i])
do not forget i -= 1
In [1]:
class Solution(object):
def addStrings(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
i, j = len(num1) - 1, len(num2) - 1
carry, res = 0, ''
while i >= 0 or j >= 0:
if i >= 0:
carry += ord(num1[i]) - ord('0')
i -= 1
if j >= 0:
carry += ord(num2[j]) - ord('0')
j -= 1
res = str(carry % 10) + res
carry /= 10
return res if carry == 0 else str(carry) + res
In [2]:
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
i, j = len(a) - 1, len(b) - 1
res, carry = '', 0
while i >= 0 or j >= 0:
if i >= 0:
if a[i] == '1':
carry += 1
i -= 1
if j >= 0:
if b[j] == '1':
carry += 1
j -= 1
res = str(carry % 2) + res
carry /= 2
return res if carry == 0 else '1' + res
In [3]:
# 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
"""
dummy = ListNode(0)
p = dummy
carry = 0
while True:
if l1 is not None:
carry += l1.val
l1 = l1.next
if l2 is not None:
carry += l2.val
l2 = l2.next
p.val = carry % 10
carry /= 10
if l1 is not None or l2 is not None or carry != 0:
temp = ListNode(0)
p.next = temp
p = p.next
else:
break
return dummy
https://leetcode.com/problems/add-two-numbers-ii/description/
stack
reverse a linked list !!!
In [178]:
a = [1,2,3]
In [179]:
a.pop()
Out[179]:
In [180]:
a
Out[180]:
In [181]:
a.pop(0)
Out[181]:
In [183]:
a.pop()
Out[183]:
In [4]:
# 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
"""
nums1, nums2 = [], []
while l1 is not None:
nums1.append(l1.val)
l1 = l1.next
while l2 is not None:
nums2.append(l2.val)
l2 = l2.next
res = ListNode(0)
carry = 0
while len(nums1) > 0 or len(nums2) > 0:
if len(nums1) > 0:
carry += nums1.pop()
if len(nums2) > 0:
carry += nums2.pop()
res.val = carry % 10
carry /= 10
p = ListNode(carry)
p.next = res
res = p
return res if res.val != 0 else res.next
In [8]:
# 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 = self.reverseList(l1)
l2 = self.reverseList(l2)
dummy = ListNode(0)
p = dummy
carry = 0
while True:
if l1 is not None:
carry += l1.val
l1 = l1.next
if l2 is not None:
carry += l2.val
l2 = l2.next
p.val = carry % 10
carry /= 10
if l1 is not None or l2 is not None or carry != 0:
p.next = ListNode(0)
p = p.next
else:
break
return self.reverseList(dummy)
def reverseList(self, l):
prev = None
while l:
curr = l
l = l.next
curr.next = prev
prev = curr
return prev
In [188]:
'0'*0
Out[188]:
In [9]:
class Solution(object):
def multiply(self, num1, num2):
"""
:type num1: str
:type num2: str
:rtype: str
"""
len1, len2 = len(num1), len(num2)
num3 = [0] * (len1 + len2)
for i in range(len1-1, -1, -1):
carry = 0
for j in range(len2-1, -1, -1):
product = num3[i + j + 1] + carry + (ord(num1[i]) - ord('0')) * (ord(num2[j]) - ord('0'))
num3[i + j + 1] = product % 10
carry = product / 10
num3[i] = carry
res = ''
i = 0
while i < len1 + len2 - 1 and num3[i] == 0:
i += 1
while i < len1 + len2:
res += str(num3[i])
i += 1
return res
In [189]:
n = -3
-n
Out[189]:
In [10]:
class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if n == 0:
return 1
if n < 0:
x = 1.0 / x
n = -n
res = 1
temp = x
while n != 0:
if n % 2 == 1:
res *= temp
temp *= temp
n /= 2
return res
https://leetcode.com/problems/reverse-linked-list/description/
In [6]:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
prev = None
while head is not None:
curr = head
head = head.next # do not mass up the order !!!
curr.next = prev
prev = curr
return prev
https://leetcode.com/problems/reverse-linked-list-ii/description/
In [7]:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
mth_prev = self.find_kth(dummy, m-1)
mth = mth_prev.next
nth = self.find_kth(dummy, n)
nth_next = nth.next
nth.next = None
self.reverse(mth)
mth_prev.next = nth
mth.next = nth_next
return dummy.next
def reverse(self, head):
prev = None
while head is not None:
curr = head
head = head.next
curr.next = prev
prev = curr
return prev
def find_kth(self, head, k):
for i in range(k):
if head is None:
return None
head = head.next
return head
https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
In [ ]: