http://blog.csdn.net/DERRANTCM/article/details/46887821
目錄
第01-10題
【劍指Offer學習】【面試題02：實現(xiàn)Singleton 模式——七種實現(xiàn)方式】
【劍指Offer學習】【面試題03：二維數(shù)組中的查找】
每行遞增，每列遞增（注意是每列，不是第一列）：先指針指向右上角元素片排，如果>target: 列 = 列-1 （j = j-1)
如果< target ，行(i = i-1)
【劍指Offer學習】【面試題04：替換空格】
先遍歷一遍看有多少個空格需要替換凛辣，后面增加相應的空格，然后從后往前雙指針填補空白
【劍指Offer學習】【面試題05：從尾到頭打印鏈表】
用棧职烧，再出棧
【劍指Offer學習】【面試題06：重建二叉樹】
參考leetcode扁誓，二叉樹里面
【劍指Offer學習】【面試題07：用兩個棧實現(xiàn)隊列】
【劍指Offer學習】【面試題08：旋轉(zhuǎn)數(shù)組的最小數(shù)字】
二分查找 O(logN)
【劍指Offer學習】【面試題09：斐波那契數(shù)列】
dp ，標準遞推蚀之，dp[0]=0,dp[1]=1, dp[i] = dp[i-1] + dp[i-2]
【劍指Offer學習】【面試題10：二進制中1 的個數(shù)】
第11-20題
【劍指Offer學習】【面試題11：數(shù)值的整數(shù)次方】
【劍指Offer學習】【面試題12：打印1 到最大的n 位數(shù)】
【劍指Offer學習】【面試題13：在O（1）時間刪除鏈表結(jié)點】
【劍指Offer學習】【面試題14：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面】
簡化版的快排蝗敢，兩層while，相當于快排里的每次迭代恬总，雙指針前普，碰到符合要求的pair進行交換
【劍指Offer學習】【面試題15：鏈表中倒數(shù)第k個結(jié)點】
快慢指針
【劍指Offer學習】【面試題16：反轉(zhuǎn)鏈表】
非遞歸 tail = None
while head:
new = head.next
head.next = tail
tail = head
head = new
return tail
【劍指Offer學習】【面試題17：合并兩個排序的鏈表】
和歸并差不多
【劍指Offer學習】【面試題18：樹的子結(jié)構(gòu)】
寫一個方法判斷兩個樹是否match(遞歸，判斷當前節(jié)點與左右節(jié)點）
另一個方法遍歷樹A壹堰，對于樹A的每個節(jié)點，如果值和B的根節(jié)點值一樣骡湖，去調(diào)用match方法贱纠，當match為True，則返回
【劍指Offer學習】【面試題19：二叉樹的鏡像】
和leetcode226. Invert Binary Tree 一樣响蕴，node不為空谆焊，則交換左右，然后對左右調(diào)用同樣的方法
class Solution(object):
def invertTree(self, root):
"""
:type root: TreeNode
:rtype: TreeNode
"""
if not root:
return
root.left,root.right = root.right,root.left
if root.left:
self.invertTree(root.left)
if root.right:
self.invertTree(root.right)
return root
【劍指Offer學習】【面試題20：順時針打印矩陣】
第21-30題
【劍指Offer學習】【面試題21：包含min函數(shù)的錢】
【劍指Offer學習】【面試題22：棧的壓入浦夷、彈出序列】
【劍指Offer學習】【面試題23：從上往下打印二叉樹】
層次遍歷
使用隊列
【劍指Offer學習】【面試題24：二叉搜索樹的后序遍歷序列】
【劍指Offer學習】【面試題25：二叉樹中和為某一值的路徑】
DFS辖试，保存所有和為target的path
返回條件為到葉子節(jié)點（左右都NULL）
class Solution(object):
def pathSum(self, root, sum):
if root is None or sum is None:
return []
path = [root.val]
res = []
self.dfs(root,path,sum - root.val,res)
return res
def dfs(self,root,path,target,res):
if not root.left and not root.right:
if target == 0:
res.append(path)
if root.left is not None:
self.dfs(root.left,path+[root.left.val],target - root.left.val,res)
if root.right is not None:
self.dfs(root.right,path + [root.right.val],target - root.right.val,res)
【劍指Offer學習】【面試題26：復雜鏈表的復制】
【劍指Offer學習】【面試題27：二叉搜索樹與雙向鏈表】
【劍指Offer學習】【面試題28：字符串的排列】
全排列，個人感覺DFS最簡潔
【劍指Offer學習】【面試題29：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字】
一個元素保存當前str劈狐，一個保存當前次數(shù)c
如果碰到一樣的元素 c+1罐孝，否則c -1，如果c<0則str替換成當前的數(shù)字肥缔，最終的str肯定是超過一半的哪一個
【劍指Offer學習】【面試題30：最小的k個數(shù)】
堆排序莲兢，前k個數(shù)先整成最大堆，之后nums[k+1:]每個數(shù)和最大堆堆頂進行比較，
如果 <堆頂 則替換掉堆頂?shù)脑馗耐В僬?復雜度k*log(k) + (N-k)*log(k) = N*log(k)
第31-40題
【劍指Offer學習】【面試題31：連續(xù)子數(shù)組的最大和】
基礎DP
cur_max = max(nums[i],cur_max+nums[i])
tmp_max = max(cur_max,tmp_max)
【劍指Offer學習】【面試題32：求從1到n的整數(shù)中1出現(xiàn)的次數(shù)】
【劍指Offer學習】【面試題33：把數(shù)組排成最小的數(shù)】
【劍指Offer學習】【面試題34：丑數(shù)】
【劍指Offer學習】【面試題35：第一個只出現(xiàn)一次的字符】
字典遍歷一遍收班，value存count,再遍歷一遍，碰到第一個value == 1的字符谒兄，時間o(N),空間o(N)
【劍指Offer學習】【面試題36：數(shù)組中的逆序?qū)Α?/p>
歸并排序摔桦，完全一樣的代碼，歸并過程中判斷l(xiāng)eft 和right有沒有逆序?qū)Τ衅＃嫘驅(qū)ount + (len(left) - i) if right[j] < left[i]
【劍指Offer學習】【面試題37：兩個鏈表的第一個公共結(jié)點】
一個函數(shù)計算長度酣溃，長度差為diff
標記兩個鏈表為long和short，long先走diff步
long和short一起往前走纪隙，直到long == short
【劍指Offer學習】【面試題38：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)】
二分查找赊豌，找到后雙指針前后掃，平均O(logN)绵咱，最壞O(N)
或者二分查找碘饼，找到后繼續(xù)查找開頭和結(jié)尾位置,平均O(logN)
【劍指Offer學習】【面試題39：二叉樹的深度】
return max(depth(left) + depth(right)) + 1
【劍指Offer學習】【面試題40：數(shù)組中只出現(xiàn)一次的數(shù)字】
第41-50題
【劍指Offer學習】【面試題41：和為s 的兩個數(shù)字vs 和為s 的連續(xù)正數(shù)序列】
第一題: 2 SUMS
第二題: 相當于雙指針，起始[1,2]悲伶，分別為開頭left和結(jié)尾right艾恼，如果和小于s則結(jié)尾right+1，如果和大于s則開頭left + 1
一種實現(xiàn)：直接while True麸锉，當最后path出現(xiàn)兩個均大于 target一半 target //2的元素時break
def foo(target):
path = [1,2]
while True:
if len(path) == 2 and path[0] > target // 2 and path[1] > target//2:
break
s = sum(path)
# print(path)
if s == target:
res.append(path[:]) # 注意這里添加path[:] 避免淺拷貝
path.append(path[-1]+1)
elif s < target:
path.append(path[-1]+1)
else:
path.pop(0)
print(res)
foo(15)
【劍指Offer學習】【面試題42：翻轉(zhuǎn)單詞順序vs左旋轉(zhuǎn)字符串】
【劍指Offer學習】【面試題43 : n 個鍛子的點數(shù)】
【劍指Offer學習】【面試題44：撲克牌的順子】
【劍指Offer學習】【面試題45：圓圈中最后剩下的數(shù)字(約瑟夫環(huán)問題)】
【劍指Offer學習】【面試題47：不用加減乘除做加法】
【劍指Offer學習】【面試題49：把字符串轉(zhuǎn)換成整數(shù)】
【劍指Offer學習】【面試題50：樹中兩個結(jié)點的最低公共祖先】
第51-60題
【劍指Offer學習】【面試題51：數(shù)組中重復的數(shù)字】
【劍指Offer學習】【面試題52：構(gòu)建乘積數(shù)組】
【劍指Offer學習】【面試題53：正則表達式匹配】
【劍指Offer學習】【面試題54：表示數(shù)值的字符串】
【劍指Offer學習】【面試題55：字符流中第一個不重復的字符】
【劍指Offer學習】【面試題56：鏈表中環(huán)的入口結(jié)點】
【劍指Offer學習】【面試題57：刪除鏈表中重復的結(jié)點】
【劍指Offer學習】【面試題58：二叉樹的下一個結(jié)點】
【劍指Offer學習】【面試題59：對稱的二叉樹】
【劍指Offer學習】【面試題60：把二叉樹打印出多行】
第61-67題
【劍指Offer學習】【面試題61：按之字形順序打印二叉樹】
【劍指Offer學習】【面試題62：序列化二叉樹】
【劍指Offer學習】【面試題63：二叉搜索樹的第k個結(jié)點】
【劍指Offer學習】【面試題64：數(shù)據(jù)流中的中位數(shù)】
【劍指Offer學習】【面試題65：滑動窗口的最大值】
【劍指Offer學習】【面試題66：矩陣中的路徑】
【劍指Offer學習】【面試題67：機器人的運動范圍】
特別聲明
