实现三叉树的 insert() 和 delete()函数 (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
给一个数, 判定他的二进制表示是否是一个palindrome
比如3的二进制是11, 就是palindrome
def solution(self, number):
#首先把数转换成二进制
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
给了一个int数组, 里面几乎包括了32bit能表示的所有数, 但是missing了几个数字, 你要把这些数字找出来, 用最少的内存.
异或运算。这个讲的比较详细。http://blog.csdn.net/smile_watermelon/article/details/45194901
Blackjack问题, 给一堆牌, 返回尽可能接近21点的组合. 因为A可以表示1或者11
应该是用dp吧，不过没有找到原题。
给一个字符串, 返回第一个出现了一次的字母. （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）
给一个字符串, 还有一个字典, 返回这个字符串否被字典里的单词分割
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
保持一个left_sum 和 right_sum， 然后遍历数组，若果当前位置两者相等就return，否组左边加当前，右边减当前
Fibonacci 数列之和
solution有四种，递归，dp包括滚动数组，线代，数学归纳法的方程
two sum (2016 一面)
leetcode 1
给一个grid走迷宫，有障碍物，四个方向随便走，要左上角到右下角的最短路径
bfs／dfs
Hashtable和BST的区别
http://bookshadow.com/weblog/2015/04/02/advantages-of-bst-over-hash-table/
哈希表支持在Θ(1)时间内完成下列操作：哈希表支持在Θ(1)时间内完成下列操作：1) 查找 2) 插入 3) 删除
对于自平衡的二叉搜索树，比如红黑树（Red-Black Tree），平衡二叉树（AVL Tree），伸展树（Splay Tree）等，上述操作的时间复杂度是O(Logn)。
因此对于常用操作哈希表似乎完胜BST。那么我们在什么时候应该选择BST而不是哈希表，BST的优势何在。下面是BST的几项比较重要的优势。
我们只需通过中序遍历BST即可获得排好序的key列表。而这并非哈希表的自然操作，需要额外的工作才可以实现。
使用BST可以很容易地执行顺序统计，找出最接近的最小和最大元素，执行范围查询。像排序一样，这些操作也不是哈希表的自然操作。
BST相较于哈希表更容易实现，我们可以很容易地实现自定义的BST。而要实现哈希表，我们一般需要依赖编程语言提供的库函数。
使用BST，所有的操作都可以确保在O(Logn)时间内完成，而对于哈希表， Θ(1) 是平均时间，对于某些特定的操作代价可能会比较高，尤其是当表的大小需要调整时。
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.
