1、解题思路区分 IPv4 和 IPv6：如果字符串包含 .，则可能是 IPv4。如果字符串包含 :，则可能是 IPv6。验证 IPv4：分割字符串为 4 部分，检查每组是否为有效数字（0-255，无前导零）。验证 IPv6：分割字符串为 8 部分，检查每组是否为有效的 16 进制数（1-4 位，允许大小写字母）。返回结果：根据验证结果返回 "IPv4"、"IPv6" 或 "Neither"。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规...

1、解题思路特殊情况处理： 如果数组为空，直接返回空字符串。如果数组只有一个字符串，直接返回该字符串本身。初始化公共前缀： 假设第一个字符串为初始公共前缀。遍历比较： 逐个字符与公共前缀比较，逐步缩短公共前缀的长度，直到找到所有字符串共有的前缀。返回结果： 最终得到的公共前缀即为答案。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param strs string字符串vector * @return string字符串 */ string longestCommonPr...

1、解题思路大小写转换：遍历字符串，逐个字符进行大小写转换。单词分割与反转：使用栈来存储单词，利用栈的先进后出特性实现单词顺序反转。处理结尾空格：检查原字符串末尾是否有空格，若有则保留在结果的首位。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @param n int整型 * @return string字符串 */ string trans(string s, int n) { // write code here if (n =...

1、解题思路动态规划：定义四个状态变量： buy1：第一次买入股票后的最大利润。sell1：第一次卖出股票后的最大利润。buy2：第二次买入股票后的最大利润。sell2：第二次卖出股票后的最大利润。初始化： buy1 = -prices[0]，表示第一次买入后的利润为负的买入价格。sell1 = 0，表示第一次卖出后的利润为 0（还未卖出）。buy2 = -prices[0]，表示第二次买入后的利润为负的买入价格。sell2 = 0，表示第二次卖出后的利润为 0（还未卖出）。状态转移： buy1 = max(buy1, -prices[i])：第一次买入后的利润为当前买入的负价格或之前的买入利...

1、解题思路贪心算法：每次在价格上升时买入和卖出，累计所有上升区间的利润总和。这样可以将多次买卖的总利润最大化。一次遍历即可完成，时间复杂度 O(n)，空间复杂度 O(1)。动态规划：定义 dp[i][0] 表示第 i 天不持有股票时的最大利润。定义 dp[i][1] 表示第 i 天持有股票时的最大利润。状态转移方程： dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])最终答案为 dp[n-1][0]。空间优化：由于 dp[i] 仅依赖于 dp[...

1、解题思路一次遍历法：遍历数组，记录当前遇到的最小价格（买入价格）。计算当前价格与最小价格的差值（当前利润），并更新最大利润。如果当前价格比最小价格还小，更新最小价格（因为后续卖出必须在买入之后）。最终的最大利润即为答案。关键点：买入必须在卖出之前。只需要一次遍历，时间复杂度 O(n)。使用常数空间，空间复杂度 O(1)。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param prices int整型vector * @return int整型 */ int maxP...

1、解题思路问题分解：由于第一个和最后一个房间相邻，可以将问题分解为两种情况： 不偷最后一个房间（即只考虑前 n-1 个房间）。不偷第一个房间（即只考虑后 n-1 个房间）。两种情况的最大值即为最终答案。动态规划：对于非环形问题，使用动态规划： dp[i] = max(dp[i-1], dp[i-2] + nums[i])。对于环形问题，分别计算两种情况的最大值。空间优化：使用两个变量 prev1 和 prev2 来存储前两个状态，优化空间复杂度。2、代码实现C++ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的...

1、解题思路动态规划： 定义 dp[i] 表示偷到第 i 个房间时的最大金额。状态转移方程： dp[i] = max(dp[i-1], dp[i-2] + nums[i])即当前房间的最大金额为：不偷当前房间（继承前一个房间的最大金额）或偷当前房间（前两个房间的最大金额加上当前房间金额）中的较大值。初始条件： dp[0] = nums[0]dp[1] = max(nums[0], nums[1])最终答案为 dp[n-1]。空间优化： 由于 dp[i] 仅依赖于 dp[i-1] 和 dp[i-2]，可以只用两个变量来存储前两个状态，将空间复杂度优化为 O(1)。2、代码实现C++ class ...

1、解题思路栈方法：使用栈来跟踪括号的匹配情况。栈中存储的是下标，初始时压入 -1 作为边界。遍历字符串： 遇到 '(' 时，将其下标压入栈。遇到 ')' 时，弹出栈顶元素： 如果栈为空，将当前下标压入栈作为新的边界。否则，计算当前有效子串长度（当前下标 - 栈顶元素）并更新最大值。时间复杂度：O(n)，空间复杂度：O(n)。动态规划：定义 dp[i] 表示以第 i 个字符结尾的最长有效括号子串的长度。状态转移： 如果 s[i] == ')' ： 若 s[i-1] == '('，则 dp[i] = dp[i-2] + 2。若 s[i-1] == ')' 且 s[i - dp[i-1] - 1]...

1、解题思路动态规划：定义 dp[i][j] 表示 str 的前 i 个字符和 pattern 的前 j 个字符是否匹配。状态转移： 如果 pattern[j-1] == '*' ： 匹配0次：dp[i][j] = dp[i][j-2]匹配1次或多次：(str[i-1] == pattern[j-2] || pattern[j-2] == '.') && dp[i-1][j]否则： (str[i-1] == pattern[j-1] || pattern[j-1] == '.') && dp[i-1][j-1]边界条件： dp[0][0] = true（空字符串...

1、解题思路动态规划：定义 dp[i][j] 表示将 str1 的前 i 个字符转换为 str2 的前 j 个字符所需的最少操作次数。状态转移方程：如果 str1[i-1] == str2[j-1]，则 dp[i][j] = dp[i-1][j-1]（无需操作）。否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1（分别对应删除、插入、替换操作）。边界条件：dp[0][j] = j（将空字符串转换为 str2 的前 j 个字符需要 j 次插入操作）。dp[i][0] = i（将 str1 的前 i 个字符转换为空字符串需要 i ...

1、解题思路回溯法： 递归地尝试在每个位置插入分隔符（.），确保每个段满足IP地址的条件。终止条件：已经插入三个分隔符，且剩余字符串也满足条件。剪枝条件： 字符串太长或太短（总长度应在4到12之间）。当前段的数字不在[0,255]范围内。当前段有前导零且长度大于1。条件检查： 段长度不超过3。段数字不超过255。段不能有前导零（除非是"0"本身）。2、代码实现C++ #include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param ...

1、解题思路中心扩展法：遍历字符串中的每一个字符，将其作为回文中心。向左右两边扩展，检查是否构成回文。考虑奇数长度（中心为一个字符）和偶数长度（中心为两个字符）的回文子串。动态规划：定义 dp[i][j] 表示字符串从 i 到 j 的子串是否是回文。状态转移方程： 如果 A[i] == A[j] 且 dp[i+1][j-1] 为 true，则 dp[i][j] = true。边界条件：单个字符 dp[i][i] = true，两个相同字符 dp[i][i+1] = (A[i] == A[i+1])。Manacher算法（进阶要求）：线性时间复杂度 O(n)，空间复杂度 O(n)。利用对称性和已...

1、解题思路动态规划：定义 dp[i] 为以 array[i] 结尾的子数组的最大和。状态转移方程： 对于每个 i，如果 dp[i-1] 为正，则 dp[i] = dp[i-1] + array[i]。否则，dp[i] = array[i]（即重新开始一个新的子数组）。初始条件： dp[0] = array[0]。结果： max_sum 是所有 dp[i] 中的最大值。优化（Kadane算法）：使用一个变量 current_sum 代替 dp 数组，记录当前子数组的和。另一个变量 max_sum 记录全局最大子数组和。遍历数组时，更新 current_sum 和 max_sum。2、代码实现C...