剑指offer【40~49】

题目链接:

剑指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 那么多次(从 1210012145 ),即 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 外,其他都设置为 0dp[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 终于过了一遍,大多数题目还是很简单的,但是题目具有代表性,涉及链表、数组、深搜回溯、字符串、数组、数学、位运算、动态规划等。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【剑指Offer】49. 丑数

    把只包含因子 2、3 和 5 的数称作丑数(Ugly Number)。例如 6、8 都是丑数,但 14 不是,因为它包含因子 7。习惯上我们把 1 当做是第一个...

    瑞新
  • 剑指offer(31-40)题解

    又因为他要求我们是从小到大排序然后输出,所以我们就需要对满足这种格式的数据进行排序,但是这里的难点就是我们如何才能实现排序的 思路是既然通用公式已经确定,...

    萌萌哒的瓤瓤
  • 剑指offer(31-40题)题解

    思路: 最笨的方法(可过)。使用字符串,将从1道n的字符串拼凑成新的字符串,然后遍历查找1就可以了。至于数学方法的话当初想了一会感觉考虑点挺多,后面还会再想想。

    bigsai
  • 【剑指Offer】40. 最小的 K 个数

    快速排序的 partition() 方法,会返回一个整数 j 使得 a[l…j-1] 小于等于 a[j],且 a[j+1…h] 大于等于 a[j],此时 a[j...

    瑞新
  • Day68:剑指Offer总结

      本人花了两个月时间刷完了牛客网带上的剑指Offer,一共67题。本人是从4月21日开始刷题,每天一题,截止到7月6日已经全部刷完。这67题均是考察的数据结构...

    一计之长
  • leetcode 剑指 Offer 40. 最小的k个数

    输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

    TrueDei
  • 套路-面试题49 把字符串转化成整数

    程序员小王
  • leetcode题解 | 48. 旋转图像

    你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

    ACM算法日常
  • python-剑指offer21-40

    输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

    西西嘛呦
  • C++版 - Leetcode 8: String to Integer (myAtoi,C库函数atoi模拟) (剑指offer 面试题49) 解题报告

    提交网址: https://leetcode.com/problems/string-to-integer-atoi/

    Enjoy233
  • 剑指Offer LeetCode 面试题40. 最小的k个数

    输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。

    TrueDei
  • 剑指Offer-2

    晚上没宵夜
  • 剑指Offer-1

    晚上没宵夜
  • 【刷题】2020最新剑指Offer汇总

    新手村 关卡1-1 洛谷的第一个任务 P1000 超级玛丽游戏:点击这里 P1001 A+B Problem:点击这里 P1421 小玉买文具:点击这里...

    瑞新
  • 剑指Offer系列刷题笔记汇总

    版权声明:本文为博主原创文章,未经博主允许不得转载。个人网站:http://cuijiahua.com。 ...

    Jack_Cui
  • 牛客网剑指offer java 全部题解

    https://mp.weixin.qq.com/s?__biz=MzI5MzYzMDAwNw==&mid=2247485570&idx=2&sn=bcde8b...

    乔戈里
  • 剑指 Offer(C++版本)系列:剑指 Offer 13 机器人的运动范围

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 剑指 Offer(C++版本)系列:剑指 Offer 12 矩阵中的路径

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮
  • 剑指 Offer(C++版本)系列:剑指 Offer 10- II 青蛙跳台阶问题

    同步GitHub在此 ? https://github.com/TeFuirnever/GXL-Skill-Tree

    我是管小亮

扫码关注云+社区

领取腾讯云代金券