箭指offer笔记5

Posted on | In | 次阅读
Words count in article: 2.2k 字 | Reading time ≈ 9 min

面试中的各项能力

Q. 两个链表第一个公共节点
A. 思路：通过倒序遍历两个链表，即使用两个stack来装载两个链表的节点，分别比较两个stack.top()，直到不相等时说明出现了分叉

Q. 排序二叉树中两个节点的最低公共祖先
A. 思路：从根节点出发，如果root.value比两个节点的值都大，则遍历root.left; 如果root.value比两个节点的值都小，则遍历root.right; 否则root就是最低公共祖先

Q. 任意树(有指针指向父节点)中两个节点的最低公共祖先
A. 思路：从给定的两个节点出发，遍历到根节点，生成两个链表，从而转化为求两个链表的第一个公共节点问题

Q. 在排序数组中查找数字: 数字在排序数组中出现的个数 {1,1,2,2,3,3,3,3} -> {3: 4}
A. 思路：

  • 可以微调k调用两次二分查找，分别找到起止位置；
  • 可以加入判断，当number[mid] == k and number[mid-1] != k时，此时startIndex = mid; 否则继续查找左区间 right = mid-1；
  • 当number[mid] == k and number[mid+1] != k时，此时endIndex = mid; 否则继续查找右区间 left = mid+1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    def binarySearch(numbers: list, k):
        left, right = 0, len(numbers) - 1
        while left < right:
            mid = (left + right) // 2
            if numbers[mid] == k:
                return mid
            elif numbers[mid] > k:
                right = mid
            else:
                left = mid + 1

        return left

    def getNumberOfK(numbers: list, k):
        if numbers == None or len(numbers) == 0:
            return

        k1 = k - 0.1
        k2 = k + 0.1

        return binarySearch(numbers, k2) - binarySearch(numbers, k1)

Q. 二叉搜索树的第k大节点：给定一棵二叉搜索树，找出其中第k大的节点

1
2
3
4
k=3 -> 4
    5
  3   7
 2 4 6 8

A. 思路：中序遍历二叉搜索树，会得到递增序列，转化为求第k大的数

Q. 二叉树的深度：根节点到页节点的最长路径
A. 思路：递归遍历左右子树，返回1+max(left, right)即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class treeNode:
    def __init__(self):
        self.value = None
        self.left = None
        self.right = None

def getMaxDepth(root: treeNode):
    if root == None:
        return 0

    leftDepth = getMaxDepth(root.left)
    rightDepth = getMaxDepth(root.right)

    return 1 + max(leftDepth, rightDepth)

Q. 平衡二叉树：判断是否为平衡二叉树，即各节点左右子树深度不超过1
A. 思路：

  • 调用getMaxDepth函数，在每次计算两边深度时都进行一次判断，但会造成多次重复访问
  • 改造getMaxDepth函数，在访问某个节点时要记录其之前的深度，模拟后序遍历，先遍历左右子树，再判断当前节点深度差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isBalanced(root: treeNode, depth: int):
    if root == None:
        depth = 0
        return True, depth

    leftFlag, leftDepth = isBalanced(root.left, depth)
    rightFlag, rightDepth = isBalanced(root.right, depth)
    if leftFlag and rightFlag:
        diff = abs(leftDepth - rightDepth)
        if diff <= 1:
            depth = 1 + max(leftDepth, rightDepth)
            return True

    return False, depth

Q. 数组中数字出现的个数：一个数组中只有两个数字出现了一次，其余数字均出现了两次，请找出这两个数字，要求时间、空间复杂度O(n)、O(1)

1
{2,4,3,6,3,2,5,5} -> {4,6}

A. 思路：异或

  • 首先对数组中的元素逐个异或，由于相同的元素异或会抵消，所以最终结果的二进制位一定有一位是1（因为有两个元素不同）
  • 假设第n位为1，接下来通过第n位是否为1将原数组划分为两个数组，这样保证了相同的数字一定在同一个数组中，而且两个不同的数字一定位于不同的数组
  • 对两个数组逐个异或即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def findNumsApperOnce(numbers:list):
    if numbers == None or len(numbers) < 2:
        return

    xorResult = 0
    for num in numbers:
        xorResult = xorResult ^ num

    bit1Index = findFirstBitOf1(xorResult)
    numbers1, numbers2 = 0, 0
    for num in numbers:
        if isBit1InIndex(num, bit1Index):
            numbers1 = numbers1 ^ num
        else:
            numbers2 = numbers2 ^ num

    return numbers1, numbers2

def findFirstBitOf1(xor: int):
    index = 0
    while xor & 1 != 1:
        xor = xor >> 1
        index += 1
    return index

def isBit1InIndex(num: int, bitIndex: int):
    num = num >> bitIndex

    if num & 1 == 1:
        return True
    return False

Q. 数组中唯一只出现一次的数字：一个数组中除一个数字只出现一次外，其他数字都出现了三次，求只出现一次的数字
A. 思路：从位运算角度考虑，如果一个数字出现了三次，那么其对应的二进制位的1也出现了三次，对每个二进制位进行加和，只出现一次的数字对应的二进制位之和一定不能被3整除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def findNumsAppearOnceIn3(numbers: list):
    if numbers == None or len(numbers) <= 0:
        return

    bitSum = [0] * 32 # 32位二进制数
    for num in numbers:
        bitMask = 1 # 左移遍历到每一位
        for i in range(32):
            if num & bitMask != 0: # 左移遍历时判断 与 的结果是否为0
                bitSum[i] += 1
            bitMask = bitMask << 1

    result = 0
    for i in range(32):
        if bitSum[i] % 3 != 0:
            result += 2 ** i

    return result

Q. 和为s的两个数字：输入一个递增排序数组和一个数字s，在数组中查找两个数使得输入之和为s。
A. 思路：双指针法，分别指向头尾，如果当前加和结果小于s，则前指针后移，否则后指针前移。

Q. 和为s的连续正数序列：输入一个正数s，打印出所有和为s的连续的正数数列。15->{1,2,3,4,5},{4,5,6},{7,8}
A. 思路：双指针法，small,big分别从1,2开始，如果两个指针之间序列和小于s，则加大big，否则加大small

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def FindContinuousSequence(sum: int):
    if sum <= 0:
        return

    small, big = 1, 2
    while small <= sum / 2:
        sequenceSum = (small + big) * (big - small + 1) / 2
        if sequenceSum == sum:
            print([num for num in range(small, big+1)])
            small += 1
        elif sequenceSum < sum:
            big += 1
        else:
            small += 1

Q. 队列的最大值：给定一个数组和滑动窗口的大小，找出所有滑动窗口里的最大值。{2,3,4,2,6,2,5,1}, 3 -> {4,4,6,6,6,5}
A. 思路：

Q. n个骰子的点数：把n个骰子扔在地上，所有骰子朝上一面点数之和为s，打印出s的所有可能出现的值的概率
A. 思路：f(n) = f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)+f(n-6)

  • n个骰子点数和的最小值为n，最大值为6n，共有6^n种排列情况。
  • 递归法：定义一个6n-n+1长度的数组，将和为s的次数保存在第s-n的位置处。把骰子分成两拨，第一堆只有一个，第二堆有n-1个，时间效率不够好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def PrintProbablity(num: int):

    # n个骰子的和位于 n~6n
    sumList = [0] * (5*num + 1)
    for i in range(1, 7):
        PrintProbablityCore(num, num, i, sumList)

    print(sumList)

def PrintProbablityCore(original, current, sum, sumList):
    '''
    :param original: 起始位置，用于在sumList定位下标，固定为num
    :param current: 递归遍历n-1,n-2...n-6
    :param sum: 当前加和到了哪个值
    :param sumList: 记录频率出现情况
    '''
    # 递归到最后一个骰子时
    if current == 1:
        sumList[sum-original] += 1
    else:
        # 将骰子分成两拨，一堆递归剩余n-1个(current)，另一个枚举1～6的情况(i+sum)
        for i in range(1, 7):
            PrintProbablityCore(original, current-1, i+sum, sumList)

Q. 扑克牌中的顺子：从扑克牌中随机抽五张牌，判断是否是顺子，joker代替任意牌。
A. 思路：

  • 把joker看作0，JQK看作11、12、13；
  • 对数组排序，如果有对子则不可能是顺子；
  • 统计连续数组中有多少间隔，判断能否用joker补上。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def isContinuous(numbers: list):
    if numbers == None or len(numbers) <= 0:
        return

    numbers = sorted(numbers)
    jokerCnt = 0
    gapCnt = 0
    for i in range(len(numbers)):
        # joker
        if numbers[i] == 0:
            jokerCnt += 1
        # 对子
        elif i > 0 and numbers[i] == numbers[i-1]:
            return False
        # 不连续
        elif i > 0 and numbers[i-1] != 0 and numbers[i] - numbers[i - 1] != 1:
            gapCnt += numbers[i] - numbers[i - 1] - 1

    if gapCnt == 0 or gapCnt <= jokerCnt:
        return True
    return False

Q. 圆圈中最后剩下的数字：0,1…n-1排成一个圆圈，从0开始，每次从这个圆圈中删除第m个数字，求这个圆圈中剩下的最后一个数字。
A. 思路：

  • 用环形链表模拟圆圈，时间复杂度O(mn)
  • 递推：f(n, m) = (f(n-1, m) + m)%n | n>1; f(n, m) = 0 | n=1
1
2
3
4
5
6
7
8
9
def LastRemaining(n: int, m: int):
    if n < 1 or m < 1:
        return

    last = 0
    for i in range(2, n+1):
        last = (last + m) % n
    
    return last

Q. 股票的最大利润：把股票价格按时间顺序输入，如何买入一次卖出一次才能获得最大利润。{9,11,8,5,7,12,16,14}->{5入16出}
A. 思路：设diff[i]代表到i时能获得的最大利润，则diff[i] = price[i] - min[0:i-1]

1
2
3
4
5
6
7
8
9
10
11
12
def MaxDiff(price: list):
    if price == None or len(price) == 0:
        return

    minPrice = price[0]
    diff = [0] * len(price)
    for i in range(2, len(price)):
        if price[i] < minPrice:
            minPrice = price[i]
        diff[i] = price[i] - minPrice

    print(max(diff))
小手一抖⬇️