http://blog.csdn.net/DERRANTCM/article/details/46887821
目錄

第01-10題

【劍指Offer學(xué)習(xí)】【面試題02：實現(xiàn)Singleton 模式——七種實現(xiàn)方式】

【劍指Offer學(xué)習(xí)】【面試題03：二維數(shù)組中的查找】

每行遞增，每列遞增（注意是每列，不是第一列）：先指針指向右上角元素，如果>target: 列 = 列-1 （j = j-1)
如果< target ，行(i = i-1)

【劍指Offer學(xué)習(xí)】【面試題04：替換空格】

先遍歷一遍看有多少個空格需要替換，后面增加相應(yīng)的空格，然后從后往前雙指針填補空白

【劍指Offer學(xué)習(xí)】【面試題05：從尾到頭打印鏈表】

用棧，再出棧

【劍指Offer學(xué)習(xí)】【面試題06：重建二叉樹】

參考leetcode，二叉樹里面

【劍指Offer學(xué)習(xí)】【面試題07：用兩個棧實現(xiàn)隊列】

【劍指Offer學(xué)習(xí)】【面試題08：旋轉(zhuǎn)數(shù)組的最小數(shù)字】

二分查找 O(logN)

【劍指Offer學(xué)習(xí)】【面試題09：斐波那契數(shù)列】
dp ，標(biāo)準(zhǔn)遞推，dp[0]=0,dp[1]=1, dp[i] = dp[i-1] + dp[i-2]

【劍指Offer學(xué)習(xí)】【面試題10：二進制中1 的個數(shù)】

第11-20題

【劍指Offer學(xué)習(xí)】【面試題11：數(shù)值的整數(shù)次方】

【劍指Offer學(xué)習(xí)】【面試題12：打印1 到最大的n 位數(shù)】

【劍指Offer學(xué)習(xí)】【面試題13：在O（1）時間刪除鏈表結(jié)點】

【劍指Offer學(xué)習(xí)】【面試題14：調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面】

簡化版的快排，兩層while，相當(dāng)于快排里的每次迭代，雙指針，碰到符合要求的pair進行交換

【劍指Offer學(xué)習(xí)】【面試題15：鏈表中倒數(shù)第k個結(jié)點】

快慢指針

【劍指Offer學(xué)習(xí)】【面試題16：反轉(zhuǎn)鏈表】

非遞歸 tail = None
while head:
  new  = head.next
  head.next = tail
  tail = head  
  head = new
return tail

【劍指Offer學(xué)習(xí)】【面試題17：合并兩個排序的鏈表】

和歸并差不多

【劍指Offer學(xué)習(xí)】【面試題18：樹的子結(jié)構(gòu)】

寫一個方法判斷兩個樹是否match(遞歸，判斷當(dāng)前節(jié)點與左右節(jié)點）
另一個方法遍歷樹A，對于樹A的每個節(jié)點，如果值和B的根節(jié)點值一樣，去調(diào)用match方法，當(dāng)match為True，則返回

【劍指Offer學(xué)習(xí)】【面試題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學(xué)習(xí)】【面試題20：順時針打印矩陣】

第21-30題

【劍指Offer學(xué)習(xí)】【面試題21：包含min函數(shù)的錢】

【劍指Offer學(xué)習(xí)】【面試題22：棧的壓入、彈出序列】

【劍指Offer學(xué)習(xí)】【面試題23：從上往下打印二叉樹】

層次遍歷
使用隊列

【劍指Offer學(xué)習(xí)】【面試題24：二叉搜索樹的后序遍歷序列】

【劍指Offer學(xué)習(xí)】【面試題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學(xué)習(xí)】【面試題26：復(fù)雜鏈表的復(fù)制】

【劍指Offer學(xué)習(xí)】【面試題27：二叉搜索樹與雙向鏈表】

【劍指Offer學(xué)習(xí)】【面試題28：字符串的排列】

全排列，個人感覺DFS最簡潔

【劍指Offer學(xué)習(xí)】【面試題29：數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字】

一個元素保存當(dāng)前str，一個保存當(dāng)前次數(shù)c
如果碰到一樣的元素 c+1，否則c -1，如果c<0則str替換成當(dāng)前的數(shù)字，最終的str肯定是超過一半的哪一個

【劍指Offer學(xué)習(xí)】【面試題30：最小的k個數(shù)】

堆排序，前k個數(shù)先整成最大堆，之后nums[k+1:]每個數(shù)和最大堆堆頂進行比較，
如果 <堆頂 則替換掉堆頂?shù)脑兀僬?復(fù)雜度k*log(k) + (N-k)*log(k) =  N*log(k)

第31-40題

【劍指Offer學(xué)習(xí)】【面試題31：連續(xù)子數(shù)組的最大和】

基礎(chǔ)DP 
            cur_max = max(nums[i],cur_max+nums[i])
            tmp_max = max(cur_max,tmp_max)

【劍指Offer學(xué)習(xí)】【面試題32：求從1到n的整數(shù)中1出現(xiàn)的次數(shù)】

【劍指Offer學(xué)習(xí)】【面試題33：把數(shù)組排成最小的數(shù)】

【劍指Offer學(xué)習(xí)】【面試題34：丑數(shù)】

【劍指Offer學(xué)習(xí)】【面試題35：第一個只出現(xiàn)一次的字符】
字典遍歷一遍，value存count,再遍歷一遍，碰到第一個value == 1的字符，時間o(N),空間o(N)

【劍指Offer學(xué)習(xí)】【面試題36：數(shù)組中的逆序?qū)Α?/p>

歸并排序，完全一樣的代碼，歸并過程中判斷l(xiāng)eft 和right有沒有逆序?qū)?，逆序?qū)ount + (len(left) - i)   if right[j] < left[i]

【劍指Offer學(xué)習(xí)】【面試題37：兩個鏈表的第一個公共結(jié)點】

一個函數(shù)計算長度，長度差為diff
標(biāo)記兩個鏈表為long和short，long先走diff步
long和short一起往前走，直到long == short

【劍指Offer學(xué)習(xí)】【面試題38：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)】

二分查找，找到后雙指針前后掃，平均O(logN)，最壞O(N)
或者二分查找，找到后繼續(xù)查找開頭和結(jié)尾位置,平均O(logN)

【劍指Offer學(xué)習(xí)】【面試題39：二叉樹的深度】

return max(depth(left) + depth(right)) + 1

【劍指Offer學(xué)習(xí)】【面試題40：數(shù)組中只出現(xiàn)一次的數(shù)字】

第41-50題

【劍指Offer學(xué)習(xí)】【面試題41：和為s 的兩個數(shù)字vs 和為s 的連續(xù)正數(shù)序列】

第一題: 2 SUMS
第二題: 相當(dāng)于雙指針，起始[1,2]，分別為開頭left和結(jié)尾right，如果和小于s則結(jié)尾right+1，如果和大于s則開頭left + 1
一種實現(xiàn)：直接while True，當(dāng)最后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學(xué)習(xí)】【面試題42：翻轉(zhuǎn)單詞順序vs左旋轉(zhuǎn)字符串】

【劍指Offer學(xué)習(xí)】【面試題43 : n 個鍛子的點數(shù)】

【劍指Offer學(xué)習(xí)】【面試題44：撲克牌的順子】

【劍指Offer學(xué)習(xí)】【面試題45：圓圈中最后剩下的數(shù)字(約瑟夫環(huán)問題)】

【劍指Offer學(xué)習(xí)】【面試題47：不用加減乘除做加法】

【劍指Offer學(xué)習(xí)】【面試題49：把字符串轉(zhuǎn)換成整數(shù)】

【劍指Offer學(xué)習(xí)】【面試題50：樹中兩個結(jié)點的最低公共祖先】

第51-60題

【劍指Offer學(xué)習(xí)】【面試題51：數(shù)組中重復(fù)的數(shù)字】

【劍指Offer學(xué)習(xí)】【面試題52：構(gòu)建乘積數(shù)組】

【劍指Offer學(xué)習(xí)】【面試題53：正則表達式匹配】

【劍指Offer學(xué)習(xí)】【面試題54：表示數(shù)值的字符串】

【劍指Offer學(xué)習(xí)】【面試題55：字符流中第一個不重復(fù)的字符】

【劍指Offer學(xué)習(xí)】【面試題56：鏈表中環(huán)的入口結(jié)點】

【劍指Offer學(xué)習(xí)】【面試題57：刪除鏈表中重復(fù)的結(jié)點】

【劍指Offer學(xué)習(xí)】【面試題58：二叉樹的下一個結(jié)點】

【劍指Offer學(xué)習(xí)】【面試題59：對稱的二叉樹】

【劍指Offer學(xué)習(xí)】【面試題60：把二叉樹打印出多行】

第61-67題

【劍指Offer學(xué)習(xí)】【面試題61：按之字形順序打印二叉樹】

【劍指Offer學(xué)習(xí)】【面試題62：序列化二叉樹】

【劍指Offer學(xué)習(xí)】【面試題63：二叉搜索樹的第k個結(jié)點】

【劍指Offer學(xué)習(xí)】【面試題64：數(shù)據(jù)流中的中位數(shù)】

【劍指Offer學(xué)習(xí)】【面試題65：滑動窗口的最大值】

【劍指Offer學(xué)習(xí)】【面試題66：矩陣中的路徑】

【劍指Offer學(xué)習(xí)】【面試題67：機器人的運動范圍】

特別聲明