剑指offer【50~59】

题目链接:

剑指offer 50-59


Python 实现:

50. 第一个只出现一次的字符位置

使用大小为 256 的数组记录每个字符出现的次数。遍历两遍即可。

# -*- coding:utf-8 -*-
class Solution:
    def FirstNotRepeatingChar(self, s):
        # write code here
        dic = [0] * 256
        for i in range(len(s)):
            dic[ord(s[i])] += 1
        for i in range(len(s)):
            if dic[ord(s[i])] == 1:
                return i
        return -1

51. 数组中的逆序对
  • 常规方法 O(n^2),先 pass。可以使用归并排序的思想,在归并的过程中统计逆序对的数量。
  • 比如在归并过程中,left = [1,3,5,7,9],right = [2,4,6,8,10],发现 3 > 2,则 left[1:] 的所有数都比 right[0] 大,就累加逆序对数量,后面的也同理。
  • 详情可以参考博客 剑指Offer(三十五):数组中的逆序对
  • 这样时间复杂度为 O(nlogn),空间复杂度为 O(n)。但是 Python 卡了一下时间,AC 了 75%。
# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        self.ans = 0  # 逆序对数量
        self.mergeSort(data)   # 归并排序
        return self.ans % 1000000007
    
    def mergeSort(self, nums):
        # 递归过程
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.mergeSort(nums[:mid])
        right = self.mergeSort(nums[mid:])
        return self.merge(left, right)

    # 归并过程 + 统计逆序对数量
    def merge(self, left, right):
        result = []  # 保存归并后的结果
        i = j = 0
        left_len = len(left)
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:  # left[i] > right[j]
                self.ans += (left_len - i)  # 核心:说明 nums[i:] 都大于 nums[j]
                result.append(right[j])
                j += 1
        result = result + left[i:] + right[j:] # 剩余的元素直接添加到末尾
        return result

52. 两个链表的第一个公共结点
  • 设 A 的长度为 a + c,B 的长度为 b + c,其中 c 为尾部公共部分长度,可知 a + c + b = b + c + a。
  • 当访问链表 A 的指针 L1 访问到链表尾部时,令它从链表 B 的头部重新开始访问链表 B;同样地,当访问链表 B 的指针 L2 访问到链表尾部时,令它从链表 A 的头部重新开始访问链表 A。这样就能控制 L1 和 L2 能同时访问到公共结点。即 L1 总共走了 (a + c) + b,L2 总共走了 (b + c) + a。
  • 这样,链表 A 和链表 B 都走了 a + b + c 步,时间复杂度为 O(n),空间复杂度为 O(1)。
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def FindFirstCommonNode(self, pHead1, pHead2):
        # write code here
        l1, l2 = pHead1, pHead2
        while l1 != l2:
            l1 = l1.next if l1 != None else pHead2
            l2 = l2.next if l2 != None else pHead1
        return l1 # 或者 l2

53. 数字在排序数组中出现的次数

排序数组,很明显二分查找,找到第一个 >= k 的元素索引以及第一个 > k 的元素索引,两者相减即为答案,即 lowerBound - upperBound。时间复杂度为 O(logn),空间复杂度为 O(1)。

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if not data:
            return 0
        lo, hi = 0, len(data) - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if data[mid] >= k:
                hi = mid
            elif data[mid] < k:
                lo = mid + 1
        ind1 = lo if data[lo] >= k else len(data)  # >=k 的第一个元素
        lo, hi = 0, len(data) - 1
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if data[mid] > k:
                hi = mid
            elif data[mid] <= k:
                lo = mid + 1
        ind2 = lo if data[lo] > k else len(data)  # # >k 的第一个元素
        return ind2 - ind1  # 相减即为答案

更简洁的,可以使用 Python 的 bisect 模块中的函数实现。可以参考博客:二分查找及其变形与Python的bisect模块的关系

# -*- coding:utf-8 -*-
import bisect
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return bisect.bisect_right(data, k) - bisect.bisect_left(data, k)

54. 二叉查找树的第 K 个结点

中序遍历,找到第 k 个数即可。

#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回对应节点TreeNode
    def __init__(self):
        self.cnt = 0
        
    def KthNode(self, pRoot, k):
        # write code here
        if not pRoot or self.cnt >= k:  # self.cnt >= k 剪枝
            return None
        left = self.KthNode(pRoot.left, k)
        if left:
            return left
        self.cnt += 1
        if self.cnt == k:
            return pRoot
        right = self.KthNode(pRoot.right, k)
        if right:
            return right
        return None

55.1 二叉树的深度

递归左右子树找最大高度。注意:根的高度为 1。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1
55.2 平衡二叉树

平衡二叉树(AVL)的左右子树的高度差不超过 1,因此引入求高度的函数。并且,判断该树的每个结点的左右子树是否也满足 AVL 的定义。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        if abs(self.TreeDepth(pRoot.left) - self.TreeDepth(pRoot.right)) > 1:  # 不满足 AVL 的定义
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
        
    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1

改进:自顶向下在调用求树的高度的函数时,有很多重复的操作。因此,可以使用自底向上的方法,一边计算树的高度,一边判断是否是 AVL 树。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def IsBalanced_Solution(self, pRoot):
        # write code here
        self.isBalance = True
        self.TreeDepth(pRoot)  # 在求树的高度过程中判断 AVL
        return self.isBalance
        
    def TreeDepth(self, pRoot):
        if not pRoot:
            return 0
        left = self.TreeDepth(pRoot.left)
        right = self.TreeDepth(pRoot.right)
        if abs(left - right) > 1:   # 不满足 AVL 定义,修改 self.isBalance 的值
            self.isBalance = False
        return max(left, right) + 1

56. 数组中只出现一次的数字

如果只出现一次的数字只有一个,很好做,就是全部异或即可。但是,只出现一次的数字有两个怎么做呢?

  • 假设只出现一次的数字为 x 和 y,首先,还是先全部异或得到一个结果 xor,则 x ^ y = xor(相同的数字异或后抵消为 0)
  • 因为 x 和 y 肯定不同,那么它们的二进制表示中肯定有一位一个是 0, 一个是 1。比如 x = 6 (110),y = 4 (100),xor = 2 (10),则我们对 xor 从后往前找到倒数第一个 1 的位置 bits(倒数第 2 位),则以这个 1 为界限,x 和 y 的倒数第 2 位肯定是不同。
  • 因此,对原来的数组重新异或,将 bits 位置为 1 的全部异或,bits 为 0 的全部异或,就是最终的两个返回的结果。
# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        xor = 0
        ans = [0, 0]
        for num in array:
            xor ^= num
        bits = 0  # 找到倒数第 i 位为 1
        while xor & 1 << bits == 0:
            bits += 1
        for num in array:
            if num >> bits & 1 == 1:  # num 的倒数第 i 位为 1
                ans[0] ^= num
            else:  # num 的倒数第 i 位为 0
                ans[1] ^= num
        return ans

57.1 和为 S 的两个数字

双指针指向首尾,往中间走,碰到第一对和为 S 的就是答案。

# -*- coding:utf-8 -*-
class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        lo, hi = 0, len(array) - 1
        while lo < hi:   # 不能指向相同的数字
            if array[lo] + array[hi] == tsum:
                return [array[lo], array[hi]]
            elif array[lo] + array[hi] < tsum:
                lo += 1
            else:
                hi -= 1
        return []
57.2 和为 S 的连续正数序列

经典的滑动窗口例题,只不过该题的窗口大小不确定。用一个遍历 left 记录窗口左侧的值,window_sum 将窗口中数进行累加。当发现 window_sum >= S 时,相等时输出结果,更新 left 和 window_sum。

# -*- coding:utf-8 -*-
class Solution:
    def FindContinuousSequence(self, tsum):
        # write code here
        if tsum <= 1:  # 特殊情况
            return []
        ans = []
        left, window_sum = 1, 0  # left 记录窗口左界
        for i in range(1, (tsum + 1) // 2 + 1):  # 窗口中至少两个数
            window_sum += i  # 窗口中的累加和
            while window_sum >= tsum:
                if window_sum == tsum:  # 输出一组结果
                    ans.append([j for j in range(left, i + 1)])
                window_sum -= left  # 修改窗口中的累加和
                left += 1  # 修改窗口的左界
        return ans

58.1 翻转单词顺序列

如果要求空间复杂度为 O(1),即只能使用字符串本身,该怎么操作呢?

  • 如 s = "I am a student.",先将各个单词翻转,得 s = ".tneduts a ma I";
  • 再将整个字符串翻转,得 s = "student. a am I"

这样就可以在字符串本身上做修改,使得空间复杂度为 O(1) 了。

注意:但是使用 Python 实现得话,由于不能修改字符串本身,所以还是先要将字符串转化为列表。但是如果使用 C++ 的字符数组,就不用开辟空间了。

# -*- coding:utf-8 -*-
class Solution:
    def ReverseSentence(self, s):
        # write code here
        def reverseWord(s, i, j):
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1
        
        s = list(s)  # python 中 s 不能修改,先转化为 list 
        start = 0  # start 指向当前单词的起始位置
        lens = len(s)
        for i in range(lens + 1):
            if i == lens or s[i] == ' ':
                reverseWord(s, start, i - 1) # 先翻转每个单词
                start = i + 1  # 下一个单词的起始位置
        reverseWord(s, 0, lens - 1)  # 再将整个句子翻转
        return "".join(s)
58.2 左旋转字符串

如果也不能使用空间,怎么做呢?参考上面的 58.1,如 s = "abcXYZdef",n = 3,先将 "abc" 和 "XYZdef" 分别翻转,得到 "cbafedZYX",然后再把整个字符串翻转得到 "XYZdefabc"。这样就可以空间复杂度为 O(1) 了。

# -*- coding:utf-8 -*-
class Solution:
    def LeftRotateString(self, s, n):
        # write code here
        def reverseWord(s, i, j):
            while i < j:
                s[i], s[j] = s[j], s[i]
                i += 1
                j -= 1
        
        if not s:
            return ""
        s = list(s)
        lens = len(s)
        n %= lens  # 循环左移
        reverseWord(s, 0, n - 1)  # 先将前 n 个字符翻转
        reverseWord(s, n, lens - 1)  # 再将后面的字符翻转
        reverseWord(s, 0, lens - 1)  # 最后将整个字符串翻转
        return "".join(s)  # 再转化回字符串

59. 滑动窗口的最大值

使用双向递减队列,队列中始终维护的是窗口中的递减值。

  • 如果队列的大小达到了 size,则应该把队列最前面的数字删除掉。
  • 如果从最右边加入了一个较大的数字,需要从右开始退队列(while 循环),使得队列是单调递减的。
  • 由于双向队列中,从左边出队列和从右边出队列的操作时间复杂度均为 O(1),因此该算法的时间复杂度为 O(n),空间复杂度为 O(n)。

例如,num = [2,3,4,2,6,2,5,1],size = 3,双向队列的变化情况为 dq: [2] -> [3] -> [4] -> [4,2] -> [6] (6 比 2 和 4 都大) -> [6,2] -> [6,5] (5 比 2 大) -> [5,1] (6 超出窗口,从队列首部出队)。

# -*- coding:utf-8 -*-
import collections
class Solution:
    def maxInWindows(self, num, size):
        # write code here
        if size > len(num) or size < 1:
            return []
        dq = collections.deque()  # [num[i], i]
        ans = []
        for i in range(len(num)):
            if dq and i - dq[0][1] >= size:
                dq.popleft()  # O(1)
            while dq and num[i] > dq[-1][0]: # 从后往前删除比 num[i] 大的数
                dq.pop()  # O(1)
            dq.append([num[i], i])
            if i >= size - 1:
                ans.append(dq[0][0])  # 队列首部始终最大
        return ans

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

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.jianshu.com/u/524cf64f28b5复制
如有侵权,请联系 yunjia_community@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 剑指offer(41-50)题解

    既然有了通项公式,那么其实我们也能推出这样一个结论,sum如果在n区间长的连续区间内满足,那么这个n区间长的区间是唯一的,不会存在第二个n长的连续区间满足,...

    萌萌哒的瓤瓤
  • LeetCode 开卷考试,不开心么

    马上快 3 月份,不知道小伙伴们有没有做好跳槽的打算,而不管想不想跳槽,很多时候都会有猎头来联系,有些猎头甚至会透露一些岗位的面试内容。

    五分钟学算法
  • 《剑指Offer》50道算法面试题

    《剑指Offer》50道算法面试题 - C++版,本来一开始想用Java来写,不过看看了,JDK里封装了很多算法,用Java写就没意思了,于是用选择了C++,顺...

    haifeiWu
  • 剑指offer | 面试题22:顺时针打印矩阵

    参考链接:https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution...

    千羽
  • 【剑指Offer】59. 1滑动窗口的最大值

    例如,如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3,那么一共存在 6 个滑动窗口,他们的最大值分别为 {4, 4, 6,...

    瑞新
  • 剑指offer | 面试题50:求1+2+…+n

    思考: 除了 if和 switch 等判断语句外,本题需要实现 “当 n = 1 时终止递归” 的需求,可通过短路效应实现。

    千羽
  • 一个正经的前端学习 开源 仓库(阶段二十五)

    一个 ☝️ 正经的前端学习 开源 仓库,启发来自 淘宝大佬 @冴羽 ,初心做一个真正能帮助到大家的仓库。(非常口语化的,手写总结)

    达达前端
  • 一个正经的前端学习 开源 仓库(阶段二十六)

    一个 ☝️ 正经的前端学习 开源 仓库,启发来自 淘宝大佬 @冴羽 ,初心做一个真正能帮助到大家的仓库。(非常口语化的,手写总结)

    达达前端
  • 剑指offer | 面试题51:不用加减乘除做加法

    参考链接:https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof...

    千羽
  • Day68:剑指Offer总结

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

    一计之长
  • 一个正经的前端学习 开源 仓库(每日更新)-572道知识点

    一个 ☝️ 正经的前端学习 开源 仓库,启发来自 淘宝大佬 @冴羽 ,初心做一个真正能帮助到大家的仓库。(非常口语化的,手写总结)

    达达前端
  • 一个正经的前端学习 开源 仓库(每日更新)-598道知识点

    一个 ☝ 正经的前端学习 开源 仓库,启发来自 淘宝大佬 @冴羽 ,初心做一个真正能帮助到大家的仓库。一个人可以走的更快,但一群人才能走的更远。(非常口语化的,...

    达达前端
  • emmo!!!

    一个 ☝ 正经的前端学习 开源 仓库,启发来自 淘宝大佬 @冴羽 ,初心做一个真正能帮助到大家的仓库。一个人可以走的更快,但一群人才能走的更远。(非常口语化的,...

    达达前端
  • 剑指offer | 面试题37:第一个只出现一次的字符

    题目描述 :在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。s 只包含小写字母。

    千羽
  • 剑指Offer LeetCode 面试题59 - I. 滑动窗口的最大

    输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释:

    TrueDei
  • [剑指offer题解]队列的最大值/滑动窗口的最大值

    有多高,以我目前不多的面试来看,在所有遇到的面试算法题中,出现原题的概率大概能有6成,如果把基于原题的变种题目算上,那么这个出现概率能到达9成,10题中9题见过...

    Rude3Knife的公众号
  • 剑指Offer-2

    晚上没宵夜
  • 剑指Offer-1

    晚上没宵夜
  • 两分钟弄懂对称二叉树

    大家好呀,我是吴师兄,今天照例来更新一道 LeetCode 算法题,根据以往数据来看,这类文章的打开率普遍不高,一般在三四千左右,远远低于水文或者热点文一两万的...

    五分钟学算法

扫码关注云+社区

领取腾讯云代金券