原地标记/交换 一、原地标记 题干：题目限制空间复杂度 思路： step1：想出空间o(n)map方法 step2：以原数组下标做o(n)map方法的key，想办法在数据上做手脚 step3：再遍历时，检查数据是否被做了手脚 448. 找到所有数组中消失的数字 class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res; int size=nums.size(); for(auto num:nums){ int temp = (num - 1) % size; nums[temp] += size; } for(int i=0;i<size;i++){ if(nums[i]<=size){ res.push_back(i+1); } } return res; } }; 442. 数组中重复的数据 class Solution {....

189. 轮转数组 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2: 输入： nums = [-1,-100,3,99], k = 2 输出： [3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100] 以矩阵的观点 \begin{matrix} C=[A,B] \\ C^T=[B^T,A^T]\\ 目标：[B,A]=[(B^T)^T,(A^T)^T] \end{matrix} 此题用R表示翻转 \begin{matrix} C=[A,B] \ \ \ C^R=[B^R,A^R]\\ 目标：[B,A]=[(B^R)^R,(A^R)^R] \end{matrix} 操作 结果 ....

前缀和 特征 求「连续段」区域和 分类 一维前缀和 303 二维前缀和 304 通用公式 ans = sum[j] - sum[i - 1]。 例子 303. 区域和检索 - 数组不可变 给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类： NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] ) 示例 1： 输入： ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 输出：....

数组的遍历 485、495、414、628 414. 第三大的数 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。 示例 1： 输入：[3, 2, 1] 输出： 1 解释： 第三大的数是 1 。 示例 2： 输入：[1, 2] 输出： 2 解释： 第三大的数不存在, 所以返回最大的数 2 。 示例 3： 输入：[2, 2, 3, 1] 输出： 1 解释： 注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。 提示： 1 <= nums.length <= 104 -231 <= nums[i] <= 231 - 1 进阶： 你能设计一个时间复杂度 O(n) 的解决方案吗？ 思路 方法一：堆排序 略 方法二：set容器排序+去重 class Solution { public: int thirdMax(vector<int>& nums) { set<int> s;//排序队列 for(in....

数组的遍历 485、495、414、628 495. 提莫攻击 在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。 当提莫攻击艾希，艾希的中毒状态正好持续 duration 秒。 正式地讲，提莫在 t 发起攻击意味着艾希在时间区间 [t, t + duration - 1]（含 t 和 t + duration - 1）处于中毒状态。如果提莫在中毒影响结束 前 再次攻击，中毒状态计时器将会 重置 ，在新的攻击之后，中毒影响将会在 duration 秒后结束。 给你一个 非递减 的整数数组 timeSeries ，其中 timeSeries[i] 表示提莫在 timeSeries[i] 秒时对艾希发起攻击，以及一个表示中毒持续时间的整数 duration 。 返回艾希处于中毒状态的 总 秒数。 示例 1： 输入： timeSeries = [1,4], duration = 2 输出： 4 解释： 提莫攻击对艾希的影响如下： 第 1 秒，提莫攻击艾希并使其立即中毒。中毒状态会维持 2 秒，即第 1 秒和第 2 秒。 第 4 ....

1002 A+B for Polynomials This time, you are supposed to find A+B where A and B are two polynomials. 这次，你需要找到两个多项式A和B的和。 Input Specification: Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N_1 a_{N1} N_2 a_{N2} ... N_{K} a_{NK} where K is the number of nonzero terms in the polynomial, N_{i} and a_{Ki} (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10 ， 0≤N_{K}<⋯<N_{2}<N_{1}....