2026网安习题大全(12)

题目11：x 的平方根

问题描述：给定一个非负整数 x，计算并返回 x 的算术平方根，结果只保留整数部分，小数部分将被舍去。

解题思路：使用二分查找。在 [0, x] 范围内查找最大的整数 mid 使得 mid * mid <= x。注意使用 mid <= x // mid 避免整数溢出。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def mySqrt(x):    if x < 2:        return x    left, right = 1, x // 2    while left <= right:        mid = (left + right) // 2        if mid <= x // mid:            left = mid + 1        else:            right = mid - 1    return right

题目12：爬楼梯

问题描述：假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶，问有多少种不同的方法可以爬到楼顶。

解题思路：使用动态规划。设 dp[i] 表示爬到第 i 阶的方法数，则 dp[i] = dp[i-1] + dp[i-2]，初始条件为 dp[1] = 1、dp[2] = 2。可以用两个变量滚动更新，将空间复杂度优化为 O(1)。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
def climbStairs(n):    if n <= 2:        return n    prev, curr = 1, 2    for _ in range(3, n + 1):        prev, curr = curr, prev + curr    return curr

题目13：删除排序数组中的重复项

问题描述：给定一个升序排列的数组 nums，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。要求不使用额外空间，且元素的相对顺序保持一致。

解题思路：使用双指针。slow 指向当前已处理的不重复部分的末尾，fast 遍历数组。当 nums[fast] != nums[slow] 时，将 nums[fast] 赋值给 nums[slow + 1] 并移动 slow。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def removeDuplicates(nums):    if not nums:        return 0    slow = 0    for fast in range(1, len(nums)):        if nums[fast] != nums[slow]:            slow += 1            nums[slow] = nums[fast]    return slow + 1

题目14：移除元素

问题描述：给定一个数组 nums 和一个值 val，原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。要求不使用额外空间，且元素的相对顺序可以改变。

解题思路：使用双指针。slow 指向当前应放置有效元素的位置，fast 遍历数组。当 nums[fast] != val 时，将 nums[fast] 赋值给 nums[slow] 并移动 slow。最终 slow 即为新长度。

Python 代码示例：

1
2
3
4
5
6
7
8
9
def removeElement(nums, val):    slow = 0    for fast in range(len(nums)):        if nums[fast] != val:            nums[slow] = nums[fast]            slow += 1    return slow

题目15：找出字符串中第一个匹配项的下标

问题描述：给定两个字符串 haystack 和 needle，在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1。

解题思路：遍历 haystack，对每个位置检查从该位置开始的子串是否与 needle 相等。也可以使用 KMP 算法将时间复杂度优化到 O(m + n)。这里给出简单实现。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
def strStr(haystack, needle):    if not needle:        return 0    n, m = len(haystack), len(needle)    for i in range(n - m + 1):        if haystack[i:i + m] == needle:            return i    return -1

题目16：搜索插入位置

问题描述：给定一个排序数组 nums 和一个目标值 target，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。要求时间复杂度为 O(log n)。

解题思路：使用二分查找。若 nums[mid] < target，则目标位置在右侧；否则在左侧（包括中间）。循环结束时 left 即为插入位置。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
def searchInsert(nums, target):    left, right = 0, len(nums) - 1    while left <= right:        mid = (left + right) // 2        if nums[mid] == target:            return mid        elif nums[mid] < target:            left = mid + 1        else:            right = mid - 1    return left

题目17：最大连续 1 的个数

问题描述：给定一个二进制数组 nums，计算其中最大连续 1 的个数。

解题思路：遍历数组，用 count 记录当前连续 1 的个数，用 max_count 记录最大值。遇到 1 时 count 加一，遇到 0 时将 count 重置为 0，并更新最大值。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def findMaxConsecutiveOnes(nums):    max_count = 0    count = 0    for num in nums:        if num == 1:            count += 1            max_count = max(max_count, count)        else:            count = 0    return max_count

题目18：提莫攻击

问题描述：给定提莫攻击的时间序列 timeSeries 和中毒持续时间 duration，计算提莫处于中毒状态的总时间。若两次攻击间隔小于 duration，则中毒时间不会累加。

解题思路：遍历攻击时间序列，每次计算相邻两次攻击的时间差，若差值小于 duration 则累加差值，否则累加 duration。最后再加上最后一次攻击的持续时间。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
def findPoisonedDuration(timeSeries, duration):    if not timeSeries:        return 0    total = 0    for i in range(1, len(timeSeries)):        total += min(timeSeries[i] - timeSeries[i - 1], duration)    return total + duration

题目19：下一个更大元素 I

问题描述：给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。找出 nums1 中每个元素在 nums2 中的下一个比其大的值。如果不存在，则对应位置输出 -1。

解题思路：先用单调栈预处理 nums2，得到每个元素的下一个更大元素，存入哈希表。然后遍历 nums1，从哈希表中查找对应结果。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
def nextGreaterElement(nums1, nums2):    stack = []    next_greater = {}    for num in nums2:        while stack and stack[-1] < num:            next_greater[stack.pop()] = num        stack.append(num)    return [next_greater.get(num, -1) for num in nums1]

题目20：键盘行

问题描述：给定一个字符串数组 words，返回其中可以由键盘同一行字母打印出来的单词。键盘的三行字母分别为：

• • 第一行：qwertyuiop
• • 第二行：asdfghjkl
• • 第三行：zxcvbnm

解题思路：将每个字母映射到其所在的行号。遍历每个单词，检查所有字母是否属于同一行，若是则加入结果列表。

Python 代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def findWords(words):    row_map = {}    for i, row in enumerate(['qwertyuiop', 'asdfghjkl', 'zxcvbnm']):        for ch in row:            row_map[ch] = i    result = []    for word in words:        if len({row_map[ch.lower()] for ch in word}) == 1:            result.append(word)    return result