LeetCode剑指offer题目记录8

leetcode刷题开始啦, 每天记录几道题.

目录

• 剑指 Offer 42. 连续子数组的最大和
• • 题目描述
  • 思路
  • 改进策略
  • • python
• 剑指 Offer 43. 1～n 整数中 1 出现的次数
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 44. 数字序列中某一位的数字
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 45. 把数组排成最小的数
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 46. 把数字翻译成字符串
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 47. 礼物的最大价值
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 48. 最长不含重复字符的子字符串
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 49. 丑数
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 50. 第一个只出现一次的字符
• • 题目描述
  • 思路
  • • python
• 剑指 Offer 52. 两个链表的第一个公共节点
• • 题目描述
  • 示例
  • 思路
  • • python
• 剑指 Offer 53 - I. 在排序数组中查找数字 I
• • 题目描述
  • 思路
  • • python
    • • 思路1
      • 思路2
• 剑指 Offer 53 - II. 0～n-1中缺失的数字
• • 题目描述
  • 思路
  • • python

剑指 Offer 42. 连续子数组的最大和 题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为O(n)。

思路

这题我记得我做过, 是用动态规划. 我想想.

用f[i] 表示以第 i 个元素结尾的连续子数组的最大和, 然后返回最大的 f[i]. 状态转移方程怎么写呢. 考察第 i 个元素 num[i], 如果它添加到 f[i-1] 对应的子数组里比它自己大, 那 f[i] 对应的子数组就是 f[i-1] 对应的子数组添加上 nums[i]. 否则 f[i] = nums[i].

改进策略

• 通过打擂台的方式维护最大值, 可以减少一次遍历;
• 通过用 f0 和 f1 滚动记录 f[i-1] 和 f[i], 可以省下一个数组的空间.

python

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        f0 = 0
        Max = -float('inf')

        for num in nums:
            if f0 + num > num:
                f1 = f0 + num
            else:
                f1 = num
            if f1 > Max:
                Max = f1
            f0 = f1

        return Max

剑指 Offer 43. 1～n 整数中 1 出现的次数 题目描述

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

思路

找找规律.

• 0~最大的一位数 0~9, 1, 1次;
• 0~最大的二位数 0~99,
  • 十位: 10~19, 10次;
  • 个位: 01, 11, 21, …, 91, 10次;
• 0~最大的三位数 0~999,
  • 百位: 100~199, 100次;
  • 十位: 010~019, 110~119, …, 910~919, 100次;
  • 个位: 001, 011, 021, …991, 100次.

先判断 n 是几位数, 比如 n = 4321, 那么在个十百位上, 完整的0~999出现了4次, 千位上1出现了完整的1000次, 再求 321 中有多少个1, (递归调用), 再加上就可以了.

python

class Solution:
    def countDigitOne(self, n: int) -> int:
        if n == 0:
            return 0
        if n < 10:
            return 1
         
        digit_num = 0
        topDigit = 0
        mirror = n
        while mirror != 0:
            topDigit = mirror
            digit_num += 1
            mirror = mirror // 10
                  
        full_exist = digit_num - 1
        full_unit = 10 ** (full_exist - 1)
        top_unit = full_unit * 10
        residual = n - topDigit * top_unit
        
        res = full_exist * full_unit * topDigit
        if topDigit == 1:
            res += residual + 1
        else:
            res += top_unit 
        res += self.countDigitOne(residual)

        return res

剑指 Offer 44. 数字序列中某一位的数字 题目描述

数字以0123456789101112131415…的格式序列化到一个字符序列中。

在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

思路

先排除最简单的情形: n == 0. 此时直接返回 0.

一位数从1~9, 有 9 - 1 + 1 = 9 个数, 在序列里占 9 位; 二位数从 10~99, 有 99 - 10 + 1 = 90 个数, 在序列里占 180 位. 所以, 记 m 位数的起点为 x, m 位数应有 9x 个, 占 9x * m 位. 所以我们可以迭代来确定 n 所对应的数字是几位数, 再判断它是第几个数, 再判断它在这个数的第几位.

python

class Solution:
    def findNthDigit(self, n: int) -> int:
        if n == 0:
            return 0
        digit, left, total = 1, 1, 9
        while n > total:
            n -= total
            digit += 1
            left = left * 10
            total = 9 * digit * left
        loc, ith = n // digit, n % digit
        if ith == 0:
            num = left + loc - 1
            return num % 10
        else:
            num = left + loc
            return (num // (10 ** (digit - ith))) % 10

剑指 Offer 45. 把数组排成最小的数 题目描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

思路

这个题我一下又没想出来. 看别人的题解说要排序, 但我也没想明白为什么排序可以传递.

python

class Solution:
    def minNumber(self, nums: List[int]) -> str:       
        def greaterThan(a, b):
            stra = str(a)
            strb = str(b)
            return int(stra + strb) >= int(strb + stra)       

        def qSort(nums):
            if len(nums) == 1:
                return str(nums[0])
            if not nums:
                return ""

            a = nums[0]
            less, greater = [], []
            for num in nums[1:]:
                if greaterThan(num, a):
                    greater.append(num)
                else:
                    less.append(num)
            
            return qSort(less) + str(a) + qSort(greater)
        
        return qSort(nums)

剑指 Offer 46. 把数字翻译成字符串 题目描述

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。

一个数字可能有多个翻译。

请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

思路

这个题目一眼就想到用动态规划. f[i] 表示前 i 个数字能有多少种翻译. 下面推导转移公式. 如果第 i 个能和第 i-1 个组成一种翻译, 那 f[i] = f[i-1] + f[i-2]. 否则 f[i] = f[i-1]. 推一下边界条件为 f[0] = f[1] = 1.

python

class Solution:
    def translateNum(self, num: int) -> int:
        nums = str(num)
        n = len(nums)
        if n == 1:
            return 1
        f0, f1 = 1, 1
        for i in range(1,n):
            case1 = nums[i-1] == "1"
            case2 = nums[i-1] == "2" and "0" <= nums[i] <= "5"
            if case1 or case2:
                f2 = f0 + f1
            else:
                f2 = f1
            f0, f1 = f1, f2
        
        return f2

剑指 Offer 47. 礼物的最大价值 题目描述

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。

你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

思路

很典型的动态规划, 设 f[i][j] 是走到第 i, j 个单元格时的礼物最大价值. 转移公式是自然的:
f[i][j] = max(f[i-1][j] + f[i][j-1]) + grid[i][j].

先处理左边和上边两个边. 它们只能由初始点沿一个方向到达. 再按上面的转移公式得到 f[i][j]. 注意, 在转移的过程中可以直接修改grid, 不必开辟额外的空间.

python

class Solution:
    def maxValue(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        if m == 1:
            return sum(grid[0])
        if n == 1:
            return sum(grid[:][0])

        for j in range(1, n):
            grid[0][j] += grid[0][j-1]
        for i in range(1, m):
            grid[i][0] += grid[i-1][0]
        
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] += max(grid[i-1][j], grid[i][j-1]) 

        return grid[m-1][n-1]

剑指 Offer 48. 最长不含重复字符的子字符串 题目描述

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

思路

再考虑动态规划. 用 f[i] 表示以 s[i] 结尾的最长不重复子串的长度, 最后返回最大的 f[i]. 转移公式怎么推?

• 如果在 f[i-1] 所表示的长度内, 都没有和 s[i] 相同的字符, 那 f[i] = f[i-1] + 1;
• 如果在 f[i-1] 所表示的长度内有和 s[i] 相同的字符, 那 f[i] 就是其中最后一个和 s[i] 相同的字符到 i 的距离.

所以我们要能在更新时获得最后一个和 s[i] 相同的元素的索引. 这个用哈希表比较容易, 遇到没出现过的, 添加它的索引; 遇到出现过的, 更新它的索引.

仍然用打擂台的方式更新最大值, 减少之后的遍历. 注意, 循环时从第二个字符开始, 要注意索引.

python

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        if len(s) == 1:
            return 1

        dic = {s[0]:0}

        Max = f1 = 1 
        for i, char in enumerate(s[1:]):
            i = i + 1
            if char not in dic or (i - dic[char] > f1):
                f2 = f1 + 1
            else:
                f2 = i - dic[char]
            dic[char] = i
            if f2 > Max:
                Max = f2
            f1 = f2
        
        return Max

剑指 Offer 49. 丑数 题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。

求按从小到大的顺序的第 n 个丑数。

思路

把所有的丑数列出来, 可以发现后面的丑数是前面的某个丑数乘上 2 或 3 或 5, 即 f[i] = f[p2] * 2 or f[p3] * 3 or f[p5] * 5. 用动态规划, 假定 f[i] 是第 i 个丑数, f[1] = 1. 假定我已经知道 f[i-1], 并且有 p2, p3, p5 指向三个丑数, 能让 f[p2] * 2, f[p3] * 3, f[p5] * 5 都比 f[i-1] 大, 那 f[i] 就应该从这三个里选最小的. 比如选到了 f[p2] * 2 = f[i], 那我的下一步要让 f[p2] * 2, f[p3] * 3, f[p5] * 5 都比 f[i] 大, 这样才能选出 f[i+1], 怎么办呢? 那自然是把这三个里能和 f[i] 相等的 pi 都加一. 初始时 p2 p3 p5 都指向 1 就可以满足条件.

python

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        f = [0 for i in range(n+1)]
        f[1] = 1

        p2 = p3 = p5 = 1

        for i in range(2, n+1):
            f2, f3, f5 = f[p2] * 2, f[p3] * 3, f[p5] * 5

            f[i] = min(f2, f3, f5)
            if f[i] == f2:
                p2 += 1
            if f[i] == f3:
                p3 += 1
            if f[i] == f5:
                p5 += 1

        return f[n]

剑指 Offer 50. 第一个只出现一次的字符 题目描述

在字符串 s 中找出第一个只出现一次的字符。

如果没有，返回一个单空格。

s 只包含小写字母。

思路

遍历一遍数组, 用一个字典存下所有字符和对应的个数, 再遍历一遍字典, 返回第一个值为1的键.

python

class Solution:
    def firstUniqChar(self, s: str) -> str:
        dic = {}

        for char in s:
            if char in dic:
                dic[char] += 1
            else:
                dic[char] = 1
        
        for char in dic:
            if dic[char] == 1:
                return char
            
        return ' '

剑指 Offer 52. 两个链表的第一个公共节点 题目描述

输入两个链表，找出它们的第一个公共节点。

示例

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。

在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

思路

如果有一个链表是空的, 那它们不可能有公共节点, 所以此时返回 None.

如果两个链表都不是空的, 简单描述, 用 a 代表 A 中独有的节点, ab 代表共有的节点, b 代表 B 中独有的节点.

• A: a->a->a->ab->ab
• B: b->b->ab->ab

那么, 我们把 B 接到 A 后面, 和把 A 接到 B 后面, 可以得到两个链表:

• AB: a->a->a->ab->ab->b->b->ab->ab
• BA: b->b->ab->ab->a->a->a->ab->ab

我们可以发现, 两个链表的公共节点必定会以相同的索引出现在 AB 和 BA 的尾部. 那么, 我们用两个指针指向 AB 和 BA, 一直循环, 直到两个指针指向的节点相同, 即为第一个公共节点. 如果两个链表的私有元素个数相同, 甚至不用遍历到尾部即可找到目标节点.

这样就能满足 O(1) 的空间复杂度要求.

python

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if not headA or not headB:
            return None
        
        pointerAB = headA
        pointerBA = headB

        while pointerAB != pointerBA:
            if pointerAB == None:
                pointerAB = headB
            else:
                pointerAB = pointerAB.next

            if pointerBA == None:
                pointerBA = headA
            else:
                pointerBA = pointerBA.next

        return pointerAB

剑指 Offer 53 - I. 在排序数组中查找数字 I 题目描述

统计一个数字在排序数组中出现的次数。

思路

一个想法是用两次二分查找, 一次查找左端, 一次查找右端.

• 左端满足: 是小于 target 的闭区间的右端+1
• 右端满足: 是大于 target 的闭区间的左端-1

另一个思路是先二分找到这个数字, 再从这个位置出发向左右探查.

python 思路1

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)
        if n == 0:
            return 0
        low, high = 0, n - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] < target:
                low = mid + 1
            if nums[mid] >= target:
                high = mid - 1
        
        left_idx = low

        low, high = left_idx, n - 1
        while low <= high:
            mid = low + ((high - low) >> 1)
            if nums[mid] > target:
                high = mid - 1
            if nums[mid] <= target:
                low = mid + 1
        
        return low - left_idx

思路2

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        n = len(nums)

        def biSearch(low, high):
            while low <= high:
                mid = low + ((high - low) >> 1)
                if nums[mid] == target:
                    return mid
                if nums[mid] < target:
                    low = mid + 1
                if nums[mid] > target:
                    high = mid - 1
            return -1
        
        turn_left = biSearch(0, n-1)
        turn_right = turn_left + 1
        if turn_left == -1:
            return 0
        
        count = 0
        while turn_left >= 0 and nums[turn_left] == target:
            count += 1
            turn_left -= 1
        while turn_right < n and nums[turn_right] == target:
            count += 1
            turn_right += 1
        
        return count

剑指 Offer 53 - II. 0～n-1中缺失的数字 题目描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。

在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

思路

排序数组, 还是用二分查找. 左边的闭区间满足 nums[i] == i, 右边的满足 nums[i] != i. 要找到右边的左端点. 用 low <= high 作循环条件, 终止时 low 就走到右区间的左端点了.

python

class Solution:
    def missingNumber(self, nums: List[int]) -> int: 
        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high - low >> 1)
            if nums[mid] == mid:
                low = mid + 1
            if nums[mid] != mid:
                high = mid - 1
            
        return low