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

题目21：买卖股票的最佳时机 II

问题描述：给你一个整数数组 prices，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。

解题思路：贪心。由于可以无限次交易，只要后一天价格高于前一天，就在前一天买入、后一天卖出，累积所有正收益。遍历数组，若 prices[i] > prices[i-1]，则将差值加入利润。

Python代码示例：

1
2
3
4
5
6
def maxProfit(prices):    profit = 0    for i in range(1, len(prices)):        if prices[i] > prices[i - 1]:            profit += prices[i] - prices[i - 1]    return profit

题目22：目标和

问题描述：给你一个整数数组 nums 和一个整数 target。向数组中的每个整数前添加 '+' 或 '-'，然后串联起所有整数，可以构造一个表达式。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

解题思路：转化为 0-1 背包问题。设所有元素之和为 sum，添加正号的元素之和为 P，添加负号的元素之和为 N，则 P + N = sum，P - N = target。解得 P = (sum + target) / 2。若 sum + target 为奇数或 target 绝对值大于 sum，则无解。问题转化为从 nums 中选出若干元素使其和为 P 的方案数。设 dp[j] 为凑成和 j 的方案数，状态转移：dp[j] += dp[j - num]，从后往前遍历。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def findTargetSumWays(nums, target):    total = sum(nums)    if abs(target) > total or (total + target) % 2 != 0:        return 0    P = (total + target) // 2    dp = [0] * (P + 1)    dp[0] = 1    for num in nums:        for j in range(P, num - 1, -1):            dp[j] += dp[j - num]    return dp[P]

题目23：最长公共子序列

问题描述：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。子序列是指从原字符串中删除若干字符（也可以不删除）而不改变剩余字符相对顺序形成的新字符串。

解题思路：动态规划。设 dp[i][j] 为 text1 前 i 个字符与 text2 前 j 个字符的最长公共子序列长度。状态转移：

• • 若 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1；
• • 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。最终返回 dp[m][n]。可用滚动数组优化空间。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
def longestCommonSubsequence(text1, text2):    m, n = len(text1), len(text2)    dp = [[0] * (n + 1) for _ in range(m + 1)]    for i in range(1, m + 1):        for j in range(1, n + 1):            if text1[i - 1] == text2[j - 1]:                dp[i][j] = dp[i - 1][j - 1] + 1            else:                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])    return dp[m][n]

题目24：被围绕的区域

问题描述：给你一个 m x n 的矩阵 board，由若干字符 'X' 和 'O' 组成。找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。被围绕的区域不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。

解题思路：从边界上的 'O' 开始 DFS/BFS，将所有与边界相连的 'O' 标记为特殊字符（如 '#'）。然后遍历整个棋盘，将剩余的 'O' 变为 'X'，将 '#' 恢复为 'O'。

Python代码示例：

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
def solve(board):    if not board:        return    m, n = len(board), len(board[0])    def dfs(i, j):        if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != 'O':            return        board[i][j] = '#'        dfs(i + 1, j)        dfs(i - 1, j)        dfs(i, j + 1)        dfs(i, j - 1)    for i in range(m):        dfs(i, 0)        dfs(i, n - 1)    for j in range(n):        dfs(0, j)        dfs(m - 1, j)    for i in range(m):        for j in range(n):            if board[i][j] == 'O':                board[i][j] = 'X'            elif board[i][j] == '#':                board[i][j] = 'O'

题目25：除法求值

问题描述：给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i]。每个 Ai 或 Bi 是一个表示单个变量的字符串。另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。输入总是有效的，你可以假设变量不会出现矛盾的结果。

解题思路：构建加权有向图。将每个变量视为节点，等式 Ai / Bi = values[i] 表示从 Ai 到 Bi 有一条权重为 values[i] 的边，同时从 Bi 到 Ai 有一条权重为 1/values[i] 的边。对于每个查询，使用 DFS 或 BFS 从 Cj 出发寻找 Dj，路径上边权的乘积即为答案。若无法到达则返回 -1.0。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from collections import defaultdictdef calcEquation(equations, values, queries):    graph = defaultdict(dict)    for (a, b), val in zip(equations, values):        graph[a][b] = val        graph[b][a] = 1 / val    def dfs(start, end, visited):        if start not in graph or end not in graph:            return -1.0        if start == end:            return 1.0        visited.add(start)        for neighbor, weight in graph[start].items():            if neighbor in visited:                continue            result = dfs(neighbor, end, visited)            if result != -1.0:                return weight * result        return -1.0    return [dfs(c, d, set()) for c, d in queries]

题目26：最长连续递增序列

问题描述：给定一个未经排序的整数数组 nums，找到最长且连续递增的子序列，并返回该序列的长度。连续递增的子序列可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1]，那么子序列 nums[l...r] 就是连续递增子序列。

解题思路：一次遍历。维护当前连续递增的长度 cur 和最大长度 max_len。若 nums[i] > nums[i-1]，则 cur += 1；否则 cur = 1。每次更新 max_len。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
def findLengthOfLCIS(nums):    if not nums:        return 0    max_len = cur = 1    for i in range(1, len(nums)):        if nums[i] > nums[i - 1]:            cur += 1            max_len = max(max_len, cur)        else:            cur = 1    return max_len

题目27：验证回文串

问题描述：给定一个字符串 s，验证它是否是回文串。只考虑字母和数字字符，可以忽略字母的大小写。空字符串定义为有效的回文串。

解题思路：双指针。左指针从左往右，右指针从右往左，跳过非字母数字字符，并统一转为小写后比较。若所有对应字符都相同，则为回文串。

Python代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
def isPalindrome(s):    left, right = 0, len(s) - 1    while left < right:        while left < right and not s[left].isalnum():            left += 1        while left < right and not s[right].isalnum():            right -= 1        if s[left].lower() != s[right].lower():            return False        left += 1        right -= 1    return True

题目28：反转字符串

问题描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。要求原地修改输入数组，使用 O(1) 的额外空间。

解题思路：双指针。左指针指向数组开头，右指针指向数组末尾，交换两指针指向的字符，然后左指针右移、右指针左移，直到两指针相遇。

Python代码示例：

1
2
3
4
5
6
def reverseString(s):    left, right = 0, len(s) - 1    while left < right:        s[left], s[right] = s[right], s[left]        left += 1        right -= 1

题目29：两个数组的交集

问题描述：给定两个数组 nums1 和 nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

解题思路：将 nums1 转为集合 set1，然后遍历 nums2，若元素在 set1 中则加入结果集合 result。最后将结果集合转为列表返回。

Python代码示例：

1
2
3
4
5
6
7
def intersection(nums1, nums2):    set1 = set(nums1)    result = set()    for num in nums2:        if num in set1:            result.add(num)    return list(result)

题目30：找不同

问题描述：给定两个字符串 s 和 t，它们只包含小写字母。字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。请找出在 t 中被添加的字母。

解题思路：利用异或运算的性质：a ^ a = 0，a ^ 0 = a。将 s 和 t 中所有字符的 ASCII 码依次异或，最终结果即为多出的那个字符。也可用字符计数法。

Python代码示例：

1
2
3
4
5
6
7
def findTheDifference(s, t):    result = 0    for ch in s:        result ^= ord(ch)    for ch in t:        result ^= ord(ch)    return chr(result)