題目鏈接：

劍指offer 40-49

目錄：

40. 最小的 K 個數(shù)
41.1 數(shù)據(jù)流中的中位數(shù)
41.2 字符流中第一個不重復的字符
42. 連續(xù)子數(shù)組的最大和
43. 從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)
44. 數(shù)字序列中的某一位數(shù)字
45. 把數(shù)組排成最小的數(shù)
46. 把數(shù)字翻譯成字符串
47. 禮物的最大價值
48. 最長不含重復字符的子字符串
49. 丑數(shù)

Python 實現(xiàn)：

40. 最小的 K 個數(shù)

• 快排或者堆排序，全排，時間復雜度為 O(n*logn)，pass；
• 方法一：實際上只需要維護一個大小為 k 的大根堆，時間復雜度最壞為 O(k*logk） + O((n-k)*logk) = O(n*logk)，這對于海量數(shù)據(jù)是非?？扇〉?。代碼如下：

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k == 0 or k > len(tinput):
            return []
        heap = []
        for i in range(len(tinput)):
            if len(heap) < k:  # 建堆（k*logk）
                heapq.heappush(heap, -tinput[i])  # 取負號是為了建立大根堆
            elif len(heap) == k:   # 調整堆（(n-k)*logk）
                if heap[0] < -tinput[i]:
                    heapq.heapreplace(heap, -tinput[i])
        return [-h for h in heapq.nlargest(k, heap)]

更簡單一些：

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        return heapq.nsmallest(k, tinput) if k <= len(tinput) else []

• 方法二：利用快排的 partition 函數(shù)，能夠做到時間復雜度為 O(n)，但是有缺點：（1）需要修改原數(shù)組；（2）找到的 k 個數(shù)不是排好序的；（3）海量數(shù)據(jù)是不可取的。代碼如下：

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        # 劃分
        def partition(lo, hi):
            r, i, j = tinput[lo], lo + 1, hi
            while i <= j:
                while i <= j and tinput[i] < r:
                    i += 1
                while i <= j and tinput[j] > r:
                    j -= 1
                if i <= j:
                    tinput[i], tinput[j] = tinput[j], tinput[i]
                    i += 1
                    j -= 1
            tinput[lo], tinput[j] = tinput[j], tinput[lo]
            return j
        
        # 查找，這里使用遞歸，也可以使用迭代的方法
        def find(k, lo, hi):
            ind = partition(lo, hi)
            if k == ind + 1:  # 此時數(shù)組中前 k 個數(shù)就是最小的了
                return
            elif k < ind + 1:
                find(k, lo, ind - 1)
            elif k > ind + 1:
                find(k, ind + 1, hi)
        
        if k == 0 or k > len(tinput):
            return []
        find(k, 0, len(tinput) - 1)
        return sorted(tinput[:k])  # 前 k 個數(shù)排序后再輸出，不然報錯

41.1 數(shù)據(jù)流中的中位數(shù)

• 使用堆，左邊維護一個大根堆，其根存儲小于中位數(shù)的最大的數(shù)，右邊維護一個小根堆，其根存儲大于等于中位數(shù)的最小的數(shù)。再使用一個變量記錄插入的總數(shù) size。
• 每次插入時，根據(jù) size 分奇偶，對兩個堆進行操作，始終保持上述性質。
• 每次查找中位數(shù)時，還是根據(jù) size 分奇偶。如果 size 為偶數(shù)，則兩個堆的根的平均值就是中位數(shù)；size 為奇數(shù)，右邊的小根堆的根就是中位數(shù)（因為右邊的堆比左邊的堆的數(shù)目多 1）。

時間復雜度為：插入為 O(logn)，計算中位數(shù)為 O(1)；空間復雜度：O(n)。

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def __init__(self):
        self.left = []  # 左邊大根堆存較小的數(shù)
        self.right = []  # 右邊小根堆存較大的數(shù)
        self.size = 0  # 數(shù)的個數(shù)，如果為奇數(shù)個，right 比 left 多一個
    
    def Insert(self, num):
        # write code here
        if self.size % 2 == 0:
            heapq.heappush(self.left, -num)
            heapq.heappush(self.right, -heapq.heappop(self.left))
        else:
            heapq.heappush(self.right, num)
            heapq.heappush(self.left, -heapq.heappop(self.right))
        self.size += 1
        
    def GetMedian(self, a):  # 這里隨便寫個 a，是因為函數(shù)頭給錯了，防止錯誤
        # write code here
        if self.size == 0:
            return 0
        if self.size % 2 == 0:
            return (-self.left[0] + self.right[0]) / 2.0
        else:
            return self.right[0]

41.2 字符流中第一個不重復的字符

使用隊列，同時使用一個一維數(shù)組記錄每個字符出現(xiàn)的次數(shù)。如果在插入后某個字符出現(xiàn)次數(shù)超過 1 次，就從隊列頭部刪除該數(shù)，這樣可以保證隊列頭部始終是第一個出現(xiàn) 1 次的字符。

時間復雜度：插入為 O(n)，查找為 O(1)；空間復雜度為：O(n)。

# -*- coding:utf-8 -*-
import collections
class Solution:
    # 返回對應char
    def __init__(self):
        self.q = collections.deque()
        self.cnt = [0] * 256  # 存儲字符出現(xiàn)的次數(shù)，使用對應的 ASCLL 下標
    
    def FirstAppearingOnce(self):
        # write code here
        return self.q[0] if self.q else "#"
        
    def Insert(self, char):
        # write code here
        self.cnt[ord(char)] += 1
        self.q.append(char)
        while self.q and self.cnt[ord(self.q[0])] > 1:  # 將超過一次的字符刪除
            self.q.popleft()

42. 連續(xù)子數(shù)組的最大和

• 動態(tài)規(guī)劃水題，轉移方程為：dp[i] = max(array[i], dp[i-1] + array[i])，其中 dp[i] 表示以 i 為結尾的最大子段和。最后 max(dp) 即為答案。
• 可以使用兩個變量完成，一個 tmp 記錄局部累加最大值，一個 ans 記錄全局最大值。當 tmp > 0 累加 arrayp[i]，否則 tmp = array[i]。每次更新 ans = max(ans, tmp)，最后 ans 就是答案。

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        ans = tmp = array[0]  # ans 為全局最大值，tmp 為局部最大值
        for i in range(1, len(array)):
            if tmp > 0:
                tmp += array[i]
            else:
                tmp = array[i]
            ans = max(ans, tmp)
        return ans

43. 從 1 到 n 整數(shù)中 1 出現(xiàn)的次數(shù)

首先，暴力不用想肯定超時（n*logn），pass。那么就從數(shù)學上推導：

• 思想：將每一位上1出現(xiàn)的次數(shù)加起來，就是所求的總次數(shù)了。
• 我們以百位為例子，在 12x45 中，百位為 x ，那么百位前的數(shù)字為 12，百位后的數(shù)字為 45。此時分為 3 種情況：
  （1）x == 0，這時候后面的數(shù)字對百位上 1 的出現(xiàn)次數(shù)是沒有影響的，只受前面數(shù)字的影響，即： 12 * 100，100 為百位的位數(shù)。
  （2）x == 1，此時既受前面數(shù)字的影響也受后面數(shù)字的影響，因為在 12 * 100 后，1 又出現(xiàn)了后面數(shù)字 +1 那么多次（從 12100 到 12145 ），即 12 * 100 + 45 + 1。
  （3）x > 1，此時因為必然包含 12100-12199 共100（百位的位數(shù)）個 1，所以百位上 1 出現(xiàn)的次數(shù)也與后面的數(shù)字沒有關系，為 12 * 100 + 100 即 (12 + 1) * 100。
• 因此，當前位 cur_bit 中 1 出現(xiàn)的次數(shù)如下：
  

時間復雜度為 O(logn)，空間復雜度為 O(1)。

# -*- coding:utf-8 -*-
class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        ans, i = 0, 1
        while i <= n:
            high, low = divmod(n, i)
            cur_bit = high % 10
            if cur_bit == 0:
                ans += high // 10 * i
            elif cur_bit == 1:
                ans += (high // 10)* i + (low + 1)
            elif cur_bit > 1:
                ans += (high // 10 + 1) * i
            i *= 10
        return ans

44. 數(shù)字序列中的某一位數(shù)字

• 觀察規(guī)律，構造一個 bits = [9, 180, 2700, 36000, ...]，表示長度為 (i + 1) 的數(shù)字總共有 bits[i] 位；再求 presums 為 bits 的前綴和，表示長度為 (i + 1) 的數(shù)字前面總共有 bits[i] 位。
• 根據(jù) presum 來確定第 n 位所代表的數(shù)字 x 位于哪個區(qū)間（即 x 是幾位數(shù)），然后計算 x 在該區(qū)間中的偏移量即可。

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n < 10:
            return n
        bits = [9 * (10 ** i) * (i + 1) for i in range(8)]
        presum = [0] * len(bits)  # 前面有多少位
        presum[0] = bits[0]
        for i in range(1, len(bits)):
            presum[i] = presum[i-1] + bits[i] 
        i = len(presum) - 1
        while i >= 0:  # 找到第n位所代表數(shù)字的區(qū)間
            if n >= presum[i]:
                n -= presum[i]
                break
            i -= 1
        pres = n // (i + 2)  # i+2 為該數(shù)字的長度
        n = n - (i + 2) * pres  # 該數(shù)字的偏移量
        num = (10 ** (i + 1)) + pres  # 該數(shù)字前面有num個數(shù)
        if n > 0:
            return str(num)[n-1]
        else:
            return str(num-1)[-1]

45. 把數(shù)組排成最小的數(shù)

按照 str1+str2 < str2+str1 的排序規(guī)則進行排序即可。如 32 排在 326 的前面，3 排在 32 的后面。注意 Python 的 cmp 寫法和 C++ 不同。

# -*- coding:utf-8 -*-
from functools import cmp_to_key  # Python3 要實現(xiàn) cmp 需要導入這個
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        def cmp(a, b):  # 參數(shù) a, b 的順序和 C++ 的相反，所以下面是 >
            return 1 if a + b > b + a else -1  # 返回的是 1 和 -1，而不是 1 和 0
        snums = [str(num) for num in numbers]
        snums.sort(key=cmp_to_key(cmp))  # 排序規(guī)則的傳遞方法
        return "".join(snums)

如果不會這種 Python3 的 cmp 實現(xiàn)方法，可以自己寫一個快排來是實現(xiàn)自定義排序規(guī)則：

# -*- coding:utf-8 -*-
class Solution:  
    # 自定義排序規(guī)則加快排
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ""
        numbers = map(str, numbers)
        pivot = numbers[0]
        less = [num for num in numbers[1:] if (pivot+num)>(num+pivot)]
        great = [num for num in numbers[1:] if (pivot+num)<=(num+pivot)]
        ans = "".join(self.PrintMinNumber(less))+ pivot + "".join(self.PrintMinNumber(great))
        return ans

46. 把數(shù)字翻譯成字符串

舉幾個例子，找規(guī)律，發(fā)現(xiàn)是斐波那契數(shù)列。

• 設 dp[len(s) + 1]，初始值除了 dp[0] = 1 外，其他都設置為 0。（dp[0] = 1 是出口）。dp[i] 表示以 s[i-1] 結尾的編碼數(shù)量，則 dp[lens] 就是答案；
• 注意：這道題編碼是 1~26，因此要排除 == 0 和 > 26 的情況。當前位 s[i-1] != '0' 時，dp[i] = dp[i-1]，如果 s[i-1] 和前一個字符 s[i-2] 組成的數(shù)字在 10 ~ 26 之間，則 dp[i] 還需要累加 dp[i-2]，即 dp[i] += dp[i-2]。

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s: 
            return 0
        lens = len(s)
        dp = [1] + [0] * lens
        for i in range(1, lens + 1):
            if s[i-1] != '0':   # 當前位不為 0
                dp[i] = dp[i-1]
            if i >= 2 and 10 <= int(s[i-2: i]) <= 26:   # 能組成兩位（10~26）
                dp[i] += dp[i-2]
        return dp[lens]

47. 禮物的最大價值

動態(tài)規(guī)劃：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i-1][j-1]，最后 dp[-1][-1] 就是答案。

# -*- coding:utf-8 -*-
class Bonus:
    def getMost(self, board):
        # write code here
        dp = [[0] * (len(board[0]) + 1) for _ in range(len(board) + 1)]
        for i in range(1, len(board) + 1):
            for j in range(1, len(board[0]) + 1):
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + board[i-1][j-1]
        return dp[-1][-1]

48. 最長不含重復字符的子字符串

方法1：使用隊列，記錄不重復的連續(xù)子串。碰到一個字符在隊列中出現(xiàn)過，更新最大長度，并從隊列頭部進行刪除操作，直到碰到該字符（實際上可以理解為滑動窗口）。時間復雜度為 O(n^2)，空間復雜度為 O(n)。在 Leetcode 第 3 題中擊敗了 88.56% 的 Python3 提交。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxl = 0
        q = collections.deque()
        for i in range(len(s)):
            if s[i] in q:
                maxl = max(maxl, len(q))  # 更新最大長度
                while q and q[0] != s[i]:  # 從隊列頭部刪除，直到s[i]
                    q.popleft()
                q.popleft()  # 刪除
            q.append(s[i])
        return max(len(q), maxl)  # 最后一段可能是最大長度

方法2：哈希表 Hash Table + 滑動窗口。使用一個變量 left 記錄窗口左界，每次碰到窗口內的字符，更新最大長度，同時更新 left 為當前字符位置 +1，即滑動窗口左界到下一個位置。時間復雜度為 O(n)，空間復雜度為 O(n)。在 Leetcode 第 3 題中擊敗了 94.13% 的 Python3 提交。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxl = 0
        dic = dict()
        left = 0  # 記錄滑動窗口的左界
        for i in range(len(s)):
            if s[i] in dic and dic[s[i]] >= left:  # s[i] 必須在滑動窗口內
                maxl = max(maxl, i - left)  # 更新最大長度
                left = dic[s[i]] + 1  # 更新滑動窗口的左界
            dic[s[i]] = i
        return max(maxl, len(s) - left)  # 最后一段可能是最大長度

49. 丑數(shù)

方法1：使用集合只保存丑數(shù)，對于一個較小的丑數(shù)，把其 ×2、×3 和 ×5 的值也保存在集合中，每次從集合中選一個最小值并移除。時間復雜度較高，但能 AC。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index == 0:
            return 0
        ans = 1
        sets = {1}
        for i in range(index):
            ans = min(sets)
            sets.add(ans * 2)
            sets.add(ans * 3)
            sets.add(ans * 5)
            sets.remove(ans)
        return ans

方法2：動態(tài)規(guī)劃。用 dp[i] 表示第 i 個丑數(shù)的值，則 dp[index] 就是答案。

• 丑數(shù)序列是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
• 因為丑數(shù)序列是通過乘以 2, 3, 5 構建，所以可以構建三個序列，每次取其中最小的，序列的構建是因子乘以丑數(shù)序列中的數(shù)。
  (1) 1×2, 2×2, 3×2, 4×2, 5×2, …
  (2) 1×3, 2×3, 3×3, 4×3, 5×3, …
  (3) 1×5, 2×5, 3×5, 4×5, 5×5, …
• 因此，可以使用 3 個指針 ind2、ind3、ind5 分別指向最后一次進行 ×2，×3，×5 操作后的位置。在找下一個丑數(shù)的時候，一定會是這三個指針指向的丑數(shù) ×2、×3、×5 中的最小數(shù) val。同時，將指向 val 的指針（ind2、ind3、ind5 至少其中一個）向后移動一位，就能一直生成下一個丑數(shù)，直到得到答案 dp[index]。
• 注意：一次最少更新一個指針（如遇到第 n 個丑數(shù)是 6 時，ind2 和ind3 都要更新）。

時間復雜度和空間復雜度均為 O(n)。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        dp = [0] + [1] * index   # 第 0 個丑數(shù)的值為 0
        ind2 = ind3 = ind5 = 1
        for i in range(2, index + 1):
            # 下一個丑數(shù)取決于 3 個指針指向的丑數(shù)分別乘以 2，3，5 中的最小值
            val = min(dp[ind2] * 2, dp[ind3] * 3, dp[ind5] * 5)  
            if val == dp[ind2] * 2:  # 更新指針移動到下一位
                ind2 += 1
            if val == dp[ind3] * 3:  # 這里不能使用 elif，因為可能也會移動
                ind3 += 1
            if val == dp[ind5] * 5:  # 這里不能使用 elif，因為可能也會移動
                ind5 += 1
            dp[i] = val  # 第 i 給丑數(shù)就是 val
        return dp[index]  # 或者 dp[-1] 是答案

劍指 offer 終于過了一遍，大多數(shù)題目還是很簡單的，但是題目具有代表性，涉及鏈表、數(shù)組、深搜回溯、字符串、數(shù)組、數(shù)學、位運算、動態(tài)規(guī)劃等。這里做一個總結：

劍指offer【03~09】
劍指offer【10~19】
劍指offer【20~29】
劍指offer【30~39】
劍指offer【40~49】
劍指offer【50~59】
劍指offer【60~68】