剑指offer【40~49】

echobingo

发布于 2019-12-20 11:58:48

4340

发布于 2019-12-20 11:58:48

文章被收录于专栏：Bingo的深度学习杂货店Bingo的深度学习杂货店

题目链接：

剑指offer 40-49

Python 实现：

40. 最小的 K 个数

快排或者堆排序，全排，时间复杂度为 O(n*logn)，pass；
方法一：实际上只需要维护一个大小为 k 的大根堆，时间复杂度最坏为 O(k*logk） + O((n-k)*logk) = O(n*logk)，这对于海量数据是非常可取的。代码如下：

# -*- 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 函数，能够做到时间复杂度为 O(n)，但是有缺点：（1）需要修改原数组；（2）找到的 k 个数不是排好序的；（3）海量数据是不可取的。代码如下：

# -*- 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:  # 此时数组中前 k 个数就是最小的了
                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 个数排序后再输出，不然报错

41.1 数据流中的中位数

使用堆，左边维护一个大根堆，其根存储小于中位数的最大的数，右边维护一个小根堆，其根存储大于等于中位数的最小的数。再使用一个变量记录插入的总数 size。
每次插入时，根据 size 分奇偶，对两个堆进行操作，始终保持上述性质。
每次查找中位数时，还是根据 size 分奇偶。如果 size 为偶数，则两个堆的根的平均值就是中位数；size 为奇数，右边的小根堆的根就是中位数（因为右边的堆比左边的堆的数目多 1）。

时间复杂度为：插入为 O(logn)，计算中位数为 O(1)；空间复杂度：O(n)。

# -*- coding:utf-8 -*-
import heapq
class Solution:
    def __init__(self):
        self.left = []  # 左边大根堆存较小的数
        self.right = []  # 右边小根堆存较大的数
        self.size = 0  # 数的个数，如果为奇数个，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，是因为函数头给错了，防止错误
        # 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 字符流中第一个不重复的字符

使用队列，同时使用一个一维数组记录每个字符出现的次数。如果在插入后某个字符出现次数超过 1 次，就从队列头部删除该数，这样可以保证队列头部始终是第一个出现 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  # 存储字符出现的次数，使用对应的 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. 连续子数组的最大和

动态规划水题，转移方程为：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 整数中 1 出现的次数

首先，暴力不用想肯定超时（n*logn），pass。那么就从数学上推导：

思想：将每一位上1出现的次数加起来，就是所求的总次数了。
我们以百位为例子，在 12x45 中，百位为 x ，那么百位前的数字为 12，百位后的数字为 45。此时分为 3 种情况：（1）x == 0，这时候后面的数字对百位上 1 的出现次数是没有影响的，只受前面数字的影响，即： 12 * 100，100 为百位的位数。（2）x == 1，此时既受前面数字的影响也受后面数字的影响，因为在 12 * 100 后，1 又出现了后面数字 +1 那么多次（从 12100 到 12145 ），即 12 * 100 + 45 + 1。（3）x > 1，此时因为必然包含 12100-12199 共100（百位的位数）个 1，所以百位上 1 出现的次数也与后面的数字没有关系，为 12 * 100 + 100 即 (12 + 1) * 100。
因此，当前位 cur_bit 中 1 出现的次数如下：

时间复杂度为 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. 数字序列中的某一位数字

观察规律，构造一个 bits = [9, 180, 2700, 36000, ...]，表示长度为 (i + 1) 的数字总共有 bits[i] 位；再求 presums 为 bits 的前缀和，表示长度为 (i + 1) 的数字前面总共有 bits[i] 位。
根据 presum 来确定第 n 位所代表的数字 x 位于哪个区间（即 x 是几位数），然后计算 x 在该区间中的偏移量即可。

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位所代表数字的区间
            if n >= presum[i]:
                n -= presum[i]
                break
            i -= 1
        pres = n // (i + 2)  # i+2 为该数字的长度
        n = n - (i + 2) * pres  # 该数字的偏移量
        num = (10 ** (i + 1)) + pres  # 该数字前面有num个数
        if n > 0:
            return str(num)[n-1]
        else:
            return str(num-1)[-1]

45. 把数组排成最小的数

按照 str1+str2 < str2+str1 的排序规则进行排序即可。如 32 排在 326 的前面，3 排在 32 的后面。注意 Python 的 cmp 写法和 C++ 不同。

# -*- coding:utf-8 -*-
from functools import cmp_to_key  # Python3 要实现 cmp 需要导入这个
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        def cmp(a, b):  # 参数 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))  # 排序规则的传递方法
        return "".join(snums)

如果不会这种 Python3 的 cmp 实现方法，可以自己写一个快排来是实现自定义排序规则：

# -*- coding:utf-8 -*-
class Solution:  
    # 自定义排序规则加快排
    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. 把数字翻译成字符串

举几个例子，找规律，发现是斐波那契数列。

设 dp[len(s) + 1]，初始值除了 dp[0] = 1 外，其他都设置为 0。（dp[0] = 1 是出口）。dp[i] 表示以 s[i-1] 结尾的编码数量，则 dp[lens] 就是答案；
注意：这道题编码是 1~26，因此要排除 == 0 和 > 26 的情况。当前位 s[i-1] != '0' 时，dp[i] = dp[i-1]，如果 s[i-1] 和前一个字符 s[i-2] 组成的数字在 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. 礼物的最大价值

动态规划：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：使用队列，记录不重复的连续子串。碰到一个字符在队列中出现过，更新最大长度，并从队列头部进行删除操作，直到碰到该字符（实际上可以理解为滑动窗口）。时间复杂度为 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. 丑数

方法1：使用集合只保存丑数，对于一个较小的丑数，把其 ×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：动态规划。用 dp[i] 表示第 i 个丑数的值，则 dp[index] 就是答案。

丑数序列是 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, …
因为丑数序列是通过乘以 2, 3, 5 构建，所以可以构建三个序列，每次取其中最小的，序列的构建是因子乘以丑数序列中的数。 (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 操作后的位置。在找下一个丑数的时候，一定会是这三个指针指向的丑数 ×2、×3、×5 中的最小数 val。同时，将指向 val 的指针（ind2、ind3、ind5 至少其中一个）向后移动一位，就能一直生成下一个丑数，直到得到答案 dp[index]。
注意：一次最少更新一个指针（如遇到第 n 个丑数是 6 时，ind2 和ind3 都要更新）。

时间复杂度和空间复杂度均为 O(n)。

# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        dp = [0] + [1] * index   # 第 0 个丑数的值为 0
        ind2 = ind3 = ind5 = 1
        for i in range(2, index + 1):
            # 下一个丑数取决于 3 个指针指向的丑数分别乘以 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 给丑数就是 val
        return dp[index]  # 或者 dp[-1] 是答案

剑指 offer 终于过了一遍，大多数题目还是很简单的，但是题目具有代表性，涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

python

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

python

编程算法

登录后参与评论

0 条评论

热度