数组

只出现一次的数字 原题链接：https://leetcode.cn/problems/single-number/description/ 给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。 1.位运算1234567891011//异或运算 ^=class Solution {public: int singleNumber(vector<int>& nums) { int ans = 0; for (int i = 0; i < nums.size(); ++i) { ans ^= nums[i]; } return ans; }}; 0 ^ x = x x ^ x = 0 异或满足交换律 2.暴力枚举1234567891011121314//暴力双层for循环 ---- 超出时间限制class Solution {public: int singleNumber(vector<int>& nums) { for (int i = 0; i < nums.size(); ++i) { int flag = 1; for (int j = 0; j < nums.size(); ++j) { if (nums[j] == nums[i] && i != j) flag = 0; } if (flag) return nums[i]; } return -1; }}; 3.常见位运算的操作 得到右数第 k 位值：(x >> k) & 1 把右数第 k 位值置1：x | (1 << k) 把右数第 k 位值取反：x ...

二进制求和 原题链接：https://leetcode.cn/problems/add-binary/ 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。 1.参考解答==思路==：大整数加法 1

加一 原题链接：https://leetcode.cn/problems/plus-one/ 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数0之外，这个整数不会以零开头。 1.参考解答==思路==：大整数加法 将最后一位加1 如果最后一位在加法操作后等于10，则需要进行进位 如果在下标为0的数字位等于10，则需要将数字的整体位数加1 1

最大子数组和 原题链接：https://leetcode.cn/problems/maximum-subarray/ 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 子数组是数组中的一个连续部分。 12345678class Solution {public: int maxSubArray(vector<int>& nums) { int final = nums[0], ans = nums[0]; ans = max(nums[i], ans + nums[i]); fin = max(fin, ans); }}; 这是一道典型的使用「动态规划」解决的问题，需要我们掌握动态规划问题设计状态的技巧（无后效性）， 并且需要知道如何推导状态转移方程，最后再去优化空间。 1.动态规划step1问题理解「力扣」第 53 题（最大子序和）是「力扣」第 124 题（二叉树的最大路径和）的线性版本，它们的状态设计思想和状态转移是类似的，希望大家能够通过本题题解进一步体会状态是如何想到的（即子问题的定义需要从哪些方面考虑）。 本题接的重点在「关键 1：理解题意」和「关键 2：如何定义子问题（如何定义状态）」和「最后再谈谈「无后效性」。 关键 1：理解题意 题目要我们找出和最大的连续子数组的值是多少，「连续」是关键字，连续很重要，不是子序列。 题目只要求返回结果，不要求得到最大的连续子数组是哪一个。这样的问题通常可以使用「动态规划」解决。 关键 2：如何定义子问题（如何定义状态） 设计状态思路：把不确定的因素确定下来，进而把子问题定义清楚，把子问题定义得简单。动态规划的思想通过解决了一个一个简单的问题，进而把简单的问题的解组成了复杂的问题的解。 友情提示：上面这句话大家姑且这么一看，脑子里有个印象，没有那么绝对。可能不同的人看会有不同的理解。如果我以后讲解的动态规划的设计思想与这里讲解的「设计状态思路」不一样的，我会再和大家说明。如果讲解有误导的地方，还请大家指出。 我们 不知道和最大的连续子数组一定会选哪一个数，那么我们可以求出 所有 经过输入数组的某一个数的连续子数组的最大和。 例如，示例 1 输 ...

搜索插入位置 原题链接：https://leetcode.cn/problems/search-insert-position/ 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 1.暴力法123456789class Solution {public: int searchInsert(vector<int>& nums, int target) { for (int i = 0; i < nums.size(); ++i) { if (nums[i] >= target) return i; } return nums.size(); }}; 2.二分查找12345678910111213141516class Solution {public: int searchInsert(vector<int>& nums, int target) { if (nums[nums.size() - 1] < target) return nums.size(); int l = 0, r = nums.size() - 1; while (l != r) { int mid = (l + r) / 2; if (nums[mid] >= target) { r = mid; } else { l = mid + 1; } } return l; }};

移除指定元素 原题链接：https://leetcode.cn/problems/remove-element/ 1.巧妙的移动元素1234567891011121314class Solution {public: int removeElement(vector<int>& nums, int val) { int count = 0; for (int i = 0; i < nums.size(); ++i) { if (nums[i] == val) { count++; } else { nums[i - count] = nums[i]; } } return nums.size() - count; }}; 2.重复项删除类似12345678910111213class Solution {public: int removeElement(vector<int>& nums, int val) { int black = 0; for (int red = 0; red < nums.size(); ++red) { if (nums[red] != val) { nums[black] = nums[red]; black++; } } return black; }};