實(shí)現(xiàn)三叉樹的 insert() 和 delete()函數(shù) (2017 OA)
def delete(self, root, value):
if root:
if value < root.val:
root.left = self.delete(root.left, value)
elif value > root.val:
root.right = self.delete(root.right, value)
else:
if root.mid:
root.mid = self.delete(root.mid, value)
elif root.right:
min = self.find_min(root.right)
root.val = min
root.right = self.delete(root.right, min)
else:
root = root.left
return root
def find_min(self, node):
while node.left:
return self.find_min(node.left)
return node.val
String to long (2017 OA)
def string_to_long(self, str):
if len(str) == 0: return 0
res = i = 0
sign = 1
while str[i] == ' ':
i += 1
if str[i] == '+' or str[i] == '-':
sign = 1 if str[i] == '+' else -1
i += 1
while i < len(str) and str[i].isdigit():
res = res * 10 + ord(str[i]) - ord('0')
i += 1
return min(max(res * sign, -2**63), 2**63 - 1)
Lowest Common Ancestor （2016 一面）
def LCA(self, root, p, q):
if p.val < root.val and q.val < root.val:
self.LCA(root.left, p, q)
elif p.val > root.val and q.val > root.val:
self.LCA(root.right, p, q)
return root
給一個(gè)數(shù), 判定他的二進(jìn)制表示是否是一個(gè)palindrome
比如3的二進(jìn)制是11, 就是palindrome
def solution(self, number):
#首先把數(shù)轉(zhuǎn)換成二進(jìn)制
number = int("{0:b}".format(number))
#然后判斷palindrome
if number == 0 or (number != 0 and number % 10 == 0): return False
res = 0
while res < number:
res = res * 10 + number % 10
number /= 10
return res == number or res / 10 == number
給了一個(gè)int數(shù)組, 里面幾乎包括了32bit能表示的所有數(shù), 但是missing了幾個(gè)數(shù)字, 你要把這些數(shù)字找出來, 用最少的內(nèi)存.
異或運(yùn)算纠屋。這個(gè)講的比較詳細(xì)瘸味。http://blog.csdn.net/smile_watermelon/article/details/45194901
Blackjack問題, 給一堆牌, 返回盡可能接近21點(diǎn)的組合. 因?yàn)锳可以表示1或者11
應(yīng)該是用dp吧，不過沒有找到原題翅阵。
給一個(gè)字符串, 返回第一個(gè)出現(xiàn)了一次的字母. （2016）
O(N)解法
import string
class Solution(object):
def firstUniqChar(self, s):
a = len(s)
m = 0
result = []
while m < a:
for i in string.ascii_lowercase:
if s.count(i) == 1:
result.append(s.find(i))
if i in s:
m += 1
if not result:
return -1
return min(result)
Word Break （LC 139）
給一個(gè)字符串, 還有一個(gè)字典, 返回這個(gè)字符串否被字典里的單詞分割
Validate Binary Search Tree (LC 98)
還沒做過
Plus One (LC 66)
class Solution(object):
def plusOne(self, digits):
i = len(digits) - 1
while i >= 0:
if digits[i] == 9:
digits[i] = 0
i -= 1
else:
digits[i] += 1
return digits
digits[0] = 1
return digits + [0]
Given an array of integers, find a partition index so that sum of all integers on the left equals sum of all integers on the right. e.g. [1, 2, 1] returns 1, [1, 2, -4, 8, 5, 9, -2] returns 4
保持一個(gè)left_sum 和 right_sum鸠项， 然后遍歷數(shù)組熬粗，若果當(dāng)前位置兩者相等就return司抱，否組左邊加當(dāng)前，右邊減當(dāng)前
Fibonacci 數(shù)列之和
solution有四種肿孵，遞歸，dp包括滾動(dòng)數(shù)組疏魏，線代停做，數(shù)學(xué)歸納法的方程
two sum (2016 一面)
leetcode 1
給一個(gè)grid走迷宮，有障礙物大莫，四個(gè)方向隨便走蛉腌，要左上角到右下角的最短路徑
bfs／dfs
Hashtable和BST的區(qū)別
http://bookshadow.com/weblog/2015/04/02/advantages-of-bst-over-hash-table/
哈希表支持在Θ(1)時(shí)間內(nèi)完成下列操作：哈希表支持在Θ(1)時(shí)間內(nèi)完成下列操作：1) 查找 2) 插入 3) 刪除
對(duì)于自平衡的二叉搜索樹，比如紅黑樹（Red-Black Tree），平衡二叉樹（AVL Tree）眉抬，伸展樹（Splay Tree）等贯吓，上述操作的時(shí)間復(fù)雜度是O(Logn)。
因此對(duì)于常用操作哈希表似乎完勝BST蜀变。那么我們?cè)谑裁磿r(shí)候應(yīng)該選擇BST而不是哈希表悄谐，BST的優(yōu)勢(shì)何在。下面是BST的幾項(xiàng)比較重要的優(yōu)勢(shì)库北。
我們只需通過中序遍歷BST即可獲得排好序的key列表爬舰。而這并非哈希表的自然操作，需要額外的工作才可以實(shí)現(xiàn)寒瓦。
使用BST可以很容易地執(zhí)行順序統(tǒng)計(jì)情屹，找出最接近的最小和最大元素，執(zhí)行范圍查詢杂腰。像排序一樣垃你，這些操作也不是哈希表的自然操作。
BST相較于哈希表更容易實(shí)現(xiàn)喂很，我們可以很容易地實(shí)現(xiàn)自定義的BST惜颇。而要實(shí)現(xiàn)哈希表，我們一般需要依賴編程語言提供的庫函數(shù)少辣。
使用BST凌摄，所有的操作都可以確保在O(Logn)時(shí)間內(nèi)完成，而對(duì)于哈希表漓帅， Θ(1) 是平均時(shí)間锨亏，對(duì)于某些特定的操作代價(jià)可能會(huì)比較高，尤其是當(dāng)表的大小需要調(diào)整時(shí)忙干。
Difference between Thread and Process
Both processes and threads are independent sequences of execution. The typical difference is that threads (of the same process) run in a shared memory space, while processes run in separate memory spaces.
