网络安全黑客技术练习题大全(45)

题目41：最长不含重复字符的子字符串

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

解题思路：滑动窗口 + 哈希表。用左右指针维护一个无重复字符的窗口，哈希表记录字符最近出现的位置。右指针向右扩展，若当前字符已在窗口中，则移动左指针到重复字符的下一个位置。过程中更新最大长度。

Python代码示例：

def lengthOfLongestSubstring(s):    char_index = {}    left = 0    max_len = 0    for right, ch in enumerate(s):        if ch in char_index and char_index[ch] >= left:            left = char_index[ch] + 1        char_index[ch] = right        max_len = max(max_len, right - left + 1)    return max_len

题目42：圆圈中最后剩下的数字

问题描述：0, 1, …, n-1 这 n 个数字排成一个圆圈，从数字 0 开始，每次从这个圆圈里删除第 m 个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4 这 5 个数字组成一个圆圈，从数字 0 开始每次删除第 3 个数字，则删除的前 4 个数字依次是 2、0、4、1，最后剩下的数字是 3。

解题思路：约瑟夫环问题。设 f(n, m) 表示 n 个数字中最后剩下的数字。递推公式：f(1, m) = 0，f(n, m) = (f(n-1, m) + m) % n。可以自底向上迭代求解。

Python代码示例：

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

题目43：股票的最大利润

问题描述：假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？例如，一只股票在某些时间节点的价格为 [9,11,8,5,7,12,16,14]，如果我们能在价格为 5 的时候买入并在价格为 16 时卖出，则能收获最大的利润 11。

解题思路：一次遍历，维护当前最小价格和最大利润。每天计算如果今天卖出能获得的利润，并更新最大利润。

Python代码示例：

def maxProfit(prices):    min_price = float('inf')    max_profit = 0    for price in prices:        min_price = min(min_price, price)        max_profit = max(max_profit, price - min_price)    return max_profit

题目44：求 1+2+…+n

问题描述：求 1+2+...+n，要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句。

解题思路：利用逻辑与的短路特性实现递归终止。n and (n + sumNums(n - 1))：当 n > 0 时，n 为真，执行递归；当 n == 0 时，短路返回 0。也可利用 Python 的 and 运算和递归实现。

Python代码示例：

def sumNums(n):    return n and (n + sumNums(n - 1))

题目45：不用加减乘除做加法

问题描述：写一个函数，求两个整数之和，要求在函数体内不得使用 +、-、*、/ 四则运算符号。

解题思路：使用位运算。

• • 不考虑进位的加法：a ^ b（异或）。
• • 进位：(a & b) << 1。将两者相加，直到进位为 0。在 Python 中需要处理负数和无限位的问题，通常用掩码模拟 32 位整数。

Python代码示例：

def add(a, b):    mask = 0xFFFFFFFF    while b != 0:        a, b = (a ^ b) & mask, ((a & b) << 1) & mask    return a if a <= 0x7FFFFFFF else ~(a ^ mask)

题目46：构建乘积数组

问题描述：给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 之外的其他所有元素的乘积。不能使用除法。

解题思路：先从左到右遍历，计算每个位置左侧所有元素的乘积，存入结果数组。再从右到左遍历，用一个变量 right 维护右侧所有元素的乘积，乘到结果数组对应位置上。这样每个位置 B[i] 就是左侧乘积乘以右侧乘积。

Python代码示例：

def constructArr(a):    n = len(a)    if n == 0:        return []    b = [1] * n    for i in range(1, n):        b[i] = b[i - 1] * a[i - 1]    right = 1    for i in range(n - 1, -1, -1):        b[i] *= right        right *= a[i]    return b

题目47：和为 s 的两个数字

问题描述：输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于 s，则输出任意一对即可。

解题思路：双指针。左指针指向数组开头，右指针指向数组末尾。计算两数之和：若等于 s 则返回；若小于 s 则左指针右移；若大于 s 则右指针左移。

Python代码示例：

def twoSum(nums, target):    left, right = 0, len(nums) - 1    while left < right:        total = nums[left] + nums[right]        if total == target:            return [nums[left], nums[right]]        elif total < target:            left += 1        else:            right -= 1    return []

题目48：扑克牌中的顺子

问题描述：从扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这 5 张牌是不是连续的。2~10 为数字本身，A 为 1，J 为 11，Q 为 12，K 为 13，而大小王可以看成任意数字（这里用 0 表示）。数组长度为 5，数组元素范围是 [0, 13]。

解题思路：先排序，统计大小王（0）的数量。遍历非零元素，若出现重复元素则不是顺子；统计相邻非零元素之间的间隔总和，若间隔总和小于等于大小王数量，则为顺子。也可以直接用最大值减最小值小于 5 且无重复来判断。

Python代码示例：

def isStraight(nums):    nums.sort()    joker = nums.count(0)    for i in range(joker, 4):        if nums[i] == nums[i + 1]:            return False    return nums[4] - nums[joker] < 5

题目49：滑动窗口的平均值

问题描述：给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。实现 MovingAverage 类：

• • MovingAverage(size)：初始化对象，窗口大小为 size。
• • next(val)：成员函数 next 接收一个整数 val，返回滑动窗口里所有数字的平均值。

解题思路：使用队列维护窗口内的元素。每次加入新元素，若队列长度超过窗口大小则弹出队首元素。同时维护窗口内元素的总和，平均值即为总和除以当前窗口内元素个数。

Python代码示例：

from collections import dequeclass MovingAverage:    def __init__(self, size):        self.size = size        self.queue = deque()        self.total = 0    def next(self, val):        self.queue.append(val)        self.total += val        if len(self.queue) > self.size:            self.total -= self.queue.popleft()        return self.total / len(self.queue)

题目50：层数最深叶子节点的和

问题描述：给你一棵二叉树的根节点 root，请你返回层数最深的叶子节点的和。叶子节点是指没有子节点的节点。

解题思路：BFS 层序遍历。逐层处理节点，记录每层叶子节点的和。每层遍历完后，若该层有叶子节点则更新结果，最终结果即为最深层的叶子节点和。

Python代码示例（假设 TreeNode 类已定义）：

from collections import dequedef deepestLeavesSum(root):    if not root:        return 0    queue = deque([root])    result = 0    while queue:        level_sum = 0        for _ in range(len(queue)):            node = queue.popleft()            if not node.left and not node.right:                level_sum += node.val            if node.left:                queue.append(node.left)            if node.right:                queue.append(node.right)        if level_sum > 0:            result = level_sum    return result