𝒞𝒶𝓃𝒶𝓇𝓎

题目描述给定一个二进制数组 nums，计算其中最大连续 1 的个数。 示例 1： 123输入：nums = [1,1,0,1,1,1]输出：3解释：开头的两位和末尾的三位都是连续 1，所以最大连续 1 的个数是 3。 示例 2： 12输入：nums = [1,0,1,1,0,1]输出：2 解题思路本题要求找出二进制数组中最长的一段连续 1 的长度。核心思想是遍历数组并维护两个变量：当前连续 1 的长度（pre_sum）和全局最大连续 1 的长度（max_sum）。 算法分析步骤： 初始化 pre_sum = 0（当前连续 1 的长度）和 max_sum = 0（全局最大值）。 遍历数组中的每个元素 nums[i]： 尝试将当前元素累加到 pre_sum 上，计算结果 res = pre_sum + nums[i]。 关键判断： 如果 res == pre_sum，说明 nums[i] == 0（累加后值不变，即遇到 0）。此时： 用当前的 pre_sum（即上一个连续 1 段的长度）更新 max_sum。 将 pre_sum 重置为 0，开始下一段计数。 否则（res ...

题目描述给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。以数组形式返回答案。 例如：nums = [8,1,2,2,3]，输出 [4,0,1,1,3]。 解释：对于 nums[0]=8，存在四个比它小的数字（1,2,2,3）；对于 nums[1]=1，没有比它小的数字；对于 nums[2]=2，存在一个比它小的数字（1）；以此类推。 解题思路暴力法最直接的想法是对于每个元素，遍历整个数组统计比它小的元素个数，时间复杂度 O(n²)。当数据量较大时效率很低。 排序 + 哈希表（O(n log n)）本题的关键观察是：当我们把数组排序后，每个元素在排序数组中的下标，恰好就等于比它小的元素个数（因为排序后前面全是小于等于它的元素）。 具体步骤： 克隆并排序：将原数组 nums 克隆到 nums2，然后对 nums2 进行排序。 建立映射：遍历排序后的数组，建立”元素值 → 最小下标”的映射。注意处理重复元素——对于重复元素，应取第一次出现的位置（即最小的下标），因为比它小的元素个数应该是排序后第一个该值出现的下标。 使用 map.put...

题目描述给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3...,n} 中读取一个数字。使用栈操作 Push 和 Pop，构建目标数组 target。返回构建 target 所用的操作序列。 例如：target = [1,3]，n = 3，输出 ["Push","Push","Pop","Push"]。 解释：读取 1，Push（得到 [1]）；读取 2，Push（得到 [1,2]），但 2 不在 target 中，所以 Pop（得到 [1]）；读取 3，Push（得到 [1,3]），3 在 target 中。 解题思路核心思想题目本质是一个模拟问题。我们按顺序从 1 到 n 遍历数字，对于每个数字 i： 无论 i 是否在 target 中，我们都需要先执行 Push。 如果 i 不在 target 中，则紧接着执行 Pop（相当于 Push 之后马上 Pop 掉）。 如果 i 在 target 中，则保留，继续处理下一个数字。 当 target 中的所有数...

题目描述给你一个数组 nums，数组中有 2n 个元素，按 [x1,x2,...,xn,y1,y2,...,yn] 的格式排列。请你将数组按 [x1,y1,x2,y2,...,xn,yn] 格式重新排列，返回重排后的数组。 例如：nums = [2,5,1,3,4,7]，n = 3，输出 [2,3,5,4,1,7]。 解释：x1=2, x2=5, x3=1，y1=3, y2=4, y3=7，交错排列得 [2,3,5,4,1,7]。 解题思路核心思想这是一个数组重排问题，本质是双指针或交错填充。给定 n，我们知道： x 部分的元素在 nums[0] 到 nums[n-1]。 y 部分的元素在 nums[n] 到 nums[2n-1]。 目标是将两个部分交错：x1, y1, x2, y2, ..., xn, yn。 步骤 创建结果数组 ans，长度为 2n。 使用指针 i 在结果数组中填充，使用指针 j 遍历 x 部分和 y 部分： 每次迭代，先放入 nums[j]（来自 x 部分），然后放入 nums[j + n]（来自 y 部分）。 j 从 0 到 n-1。 示例以 n...

题目描述给你一个数组 prices，其中 prices[i] 是商店里第 i 件商品的价格。商店里正在进行促销活动，如果你要买第 i 件商品，那么你可以得到与 prices[j] 相等的折扣，其中 j 是满足 j > i 且 prices[j] <= prices[i] 的最小下标，如果没有满足条件的 j，你将没有任何折扣。请你返回一个数组，数组中第 i 个元素是折扣后你购买商品 i 最终需要支付的价格。 例如：prices = [8,4,6,2,3]，输出 [4,2,4,2,3]。 解释：商品 0 价格 8，右侧第一个 <= 8 的是价格 4，最终支付 8-4=4；商品 1 价格 4，右侧第一个 <= 4 的是价格 2，最终支付 4-2=2；商品 2 价格 6，右侧第一个 <= 6 的是价格 2，最终支付 6-2=4；商品 3 价格 2，右侧无 <= 2 的元素，最终支付 2；商品 4 价格 3，右侧无元素，最终支付 3。 解题思路暴力法对每个元素，向右侧扫描寻找第一个不大...

题目描述根据逆波兰表示法（Reverse Polish Notation，RPN），求表达式的值。有效的算符包括 +、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。注意两个整数之间的除法只保留整数部分。可以保证给定的逆波兰表达式总是有效的。 解题思路逆波兰表达式是一种后缀表达式，其特点是将运算符放在操作数之后。计算逆波兰表达式非常适合使用栈数据结构。 核心思路：遍历 tokens 数组中的每一个字符串： 如果当前字符串是数字（操作数），直接将其转换为整数并入栈。 如果当前字符串是运算符（+、-、*、/），则从栈中弹出两个操作数（注意弹出顺序：先弹出的是第二个操作数 num2，后弹出的是第一个操作数 num1），根据运算符执行相应的计算，并将计算结果压回栈中。 当遍历完所有 token 后，栈中剩下的唯一一个元素就是整个表达式的计算结果。 关键细节： 由于减法和除法不满足交换律，操作数的顺序很重要。在逆波兰表达式中，遇到运算符时，栈顶元素是右操作数，次栈顶元素是左操作数。例如对于 ["4", "3", "-&...

题目描述给你一个长度为 n 的整数数组 nums。请你构建一个长度为 2n 的答案数组 ans，ans 由两个 nums 数组串联形成。ans[i] == nums[i] 且 ans[i + n] == nums[i]。 例如：nums = [1,2,1]，输出 [1,2,1,1,2,1]。 解释：数组 ans 由两个 [1,2,1] 串联组成。 解题思路核心思想这是一个非常直接的数组操作问题，本质上是将原数组复制两遍拼接到一起。具体做法是： 创建一个长度为 2n 的新数组 ans。 遍历原数组，将每个元素 nums[i] 分别放到 ans[i] 和 ans[i + n] 两个位置。 一次遍历即可完成。 步骤 ans = new int[nums.length * 2] 对于 i 从 0 到 nums.length - 1： ans[i] = nums[i] ans[i + nums.length] = nums[i] 返回 ans。 示例说明以 nums = [1,2,1] 为例： n = 3，ans 长度为 6 i=0：ans[0]=...

问题描述给你一个含 n 个整数的数组 nums，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。 解题思路本题的核心难点在于要求 O(n) 时间复杂度和 O(1) 额外空间（返回列表不计入额外空间）。常规的哈希表做法需要 O(n) 空间，不符合要求。 原地哈希（标记法）元素的值范围是 [1, n]，恰好对应数组索引 [0, n-1]。利用这个特性，我们可以在原数组上进行”标记”： 第一次遍历 —— 标记出现过数字对应的索引： 对于每个元素 nums[i]，取其绝对值得到原值 val 计算索引 index = val - 1 将 nums[index] 变为负数（取反），表示”数字 val 已经出现过” 注意使用 Math.abs() 取绝对值，因为元素可能已经被之前的标记操作变成了负数 第二次遍历 —— 收集缺失的数字： 遍历数组，如果 nums[i] > 0（仍为正数），说明数字 i + 1 没有出现过 将所有正数位置的索引 + 1 收集到结果列表中 举例说明以输...

问题描述给定一个二进制数组 nums，计算其中最大连续 1 的个数。 解题思路本题是经典的遍历 + 计数器问题，思路直接但需要注意边界处理。 单指针遍历法使用两个变量： pre_sum：当前连续 1 的计数 max_sum：全局最大连续 1 的个数 遍历数组： 遇到 1：pre_sum 加 1（或加 num 本身，因为 1 的值为 1） 遇到 0： 用 max_sum = Math.max(max_sum, pre_sum) 更新全局最大值 将 pre_sum 重置为 0（连续被打断） 遍历结束后，再次比较 max_sum 和 pre_sum，因为数组可能以 1 结尾而没有遇到 0 来触发更新 举例说明以输入 nums = [1, 1, 0, 1, 1, 1] 为例： i num pre_sum max_sum 说明 0 1 1 0 遇到 1，计数增加 1 1 2 0 遇到 1，计数增加 2 0 0 2 遇到 0，更新 max_sum=2，重置 pre_sum 3 1 1 2 遇到 1，计数增加 4 1 2 2 遇到 1，计数增加...

题目描述有一个单线程 CPU 正在运行一个含有 n 道函数的程序。每道函数都有一个位于 [0, n-1] 的唯一标识符。 函数调用存储在一个调用栈上：当一个函数调用开始时，它的标识符将会推入栈中。而当一个函数调用结束时，它的标识符将会从栈中弹出。标识符位于栈顶的函数是当前正在执行的函数。 每当一个函数开始或者结束时，将会记录一条日志，包括函数标识符、是开始还是结束、以及相应的时间戳。给你一个由日志组成的列表 logs，请你返回每个函数的独占时间。 每条日志的格式为 "function_id:start|end:timestamp"，其中 timestamp 是一个非负整数，表示函数开始或结束的时间点。注意，同一个函数可能会被递归调用多次。 “独占时间” 是指该函数在 CPU 上执行的所有时间片段之和，不包括它调用其他函数所花费的时间。 解题思路本题的核心是模拟调用栈来跟踪当前正在执行的函数，并记录每个时间片段归谁所有。 关键点：时间片的含义时间戳表示某个时刻，函数从 timestamp 开始执行，或恰好在 timestamp 结束。举例来说： 0:start...