对刷过的算法进行总结，所用解法都是最符合我个人逻辑的，以后再刷的话就看这篇帖子了
# 代码随想录——数组理论基础
首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题
数组是存放在连续内存空间上的相同类型数据的集合
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
举一个字符数组的例子，如图所示：
需要两点注意的是
- 数组下标都是从0开始的。
- 数组内存空间的地址是连续的
正是因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。
大家如果使用C++的话，要注意 vector 和 array 的区别，vector 的底层实现是 array，严格来讲vector 是容器，不是数组。数组的元素是不能删的，只能覆盖。
1、买卖股票的最佳时机
题目描述：
解法：
只用遍历一次数组，思路分为2部分：
- 使用数组中的首元素作为股票最低价格(minPrice)，使用for循环遍历数组，找到真正的minPrice；
- 当卡住数组中临时的一个 minPrice 时，进入 else 来获取当前的利润(profit)，这样不断往复，最终会获取到题目要求的最大利润。这样的解法十分优美！
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
int minPrice = prices[0];
for(int i = 1; i < prices.size(); ++i){
// 找到数组中的最小元素
if(prices[i] < minPrice){
minPrice = prices[i];
}
// 找到最大利润
else{
if(prices[i] - minPrice > profit){
profit = prices[i] - minPrice;
}
}
}
return profit;
}
};2、移除元素
题目描述：
解法：
题目要求原地修改原数组，但数组的特性是：数组中的元素只能覆盖，不能删除。所以设一个新的索引 index 来重新排列修改后的数组。
使用 for 循环遍历数组时，如果 nums[i] == val， 则continue，程序不往下继续进行，而是进入下一次循环。当下一个 nums[i] != val 时，则将当前元素的索引赋值给新的索引 nums[index]， 并且 index++ , 准备好接收下一个 != val 的数组元素。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int index = 0;
for(int i = 0; i < nums.size(); ++i){
if(nums[i] == val){
// 跳过下面的赋值，进入下一次循环
continue;
}
nums[index] = nums[i];
index++;
}
return index;
}
};3、合并两个有序数组
题目描述：
解法：
利用了2个数组非递减的特性，使用尾指针从后向前往 nums1 中加入元素。率先使用 resize 将 nums1 的长度扩大到 m + n，以便向 nums1 中加入新元素。
设置这样的 while 循环判断条件是考虑到2个数组总会有一方的索引先 < 0， 在消耗完其中一方时，再接一个 while 循环将另一方数组中的剩余元素添加至新的数组中
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
// 要将nums2合并到nums1中，nums1数组长度发生改变，定义新的长度以便定义新的尾指针
nums1.resize(m + n);
// 定义数组的尾指针
int i = m - 1;
int j = n - 1;
int index = m + n - 1;
while(i >= 0 && j >= 0){
if(nums1[i] < nums2[j]){
nums1[index] = nums2[j];
index--;
j--;
}
else{
nums1[index] = nums1[i];
index--;
i--;
}
}
while(i >= 0){
nums1[index] = nums1[i];
index--;
i--;
}
while(j >= 0){
nums1[index] = nums2[j];
index--;
j--;
}
}
};4、删除有序数组中的重复项
题目描述：
解法：
为数组首元素设置慢指针 slow，第二个元素设置快指针 fast，指针 fast 向后遍历，直至越界。指针 slow 只在指针 fast 遇到不重复项时向后移动一位，以此接收不重复项。最终返回 slow + 1即新数组的长度
题目中提到，返回的是最终的数组长度 ，是一个整数。但为什么输出的答案是数组呢？ 输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的，根据我们函数返回的长度，它会打印出该长度范围内所有的元素
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 0;
int fast = 1;
while(fast < nums.size()){
if(nums[fast] != nums[slow]){
// 出现不重复的元素，用++slow去接收
++slow;
nums[slow] = nums[fast];
}
else{
// 出现重复元素，slow不动，fast往后走
fast++;
}
}
return slow + 1;
}
};5、删除有序数组中的重复项Ⅱ
题目描述：
解法：
首先给出第一次 AC 了8%测试用例的版本，方便记录我忽略了这道题[最关键的信息]。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int slow = 1;
int fast = 3;
while(fast < nums.size()){
if(nums[fast] == nums[slow] && nums[fast - 1] == nums[slow]){
slow++;
nums[slow] = nums[fast - 1];
fast++;
}
else{
slow++;
nums[slow] = nums[fast];
fast++;
}
}
return slow + 1;
}
};由于这段代码的逻辑完全建立在第一个测试用例上
nums = [1,1,1,2,2,3]
可以处理前 3 个元素相同时的情况，但如果是下面这种情况：
nums = [0,0,1,1,1,2,2,3,3,4]
会将第二个元素 0 覆盖掉，很愁啊，修改了判断条件后连第一个测试用例都 AC 不过了！
那么关键是什么呢？答：“数组的前两个元素必然满足条件，无需处理”这一点官方解答中也提到了。
所以慢指针 slow 设在索引为 2 的位置上，使用一个循环，从索引为 2的位置开始遍历数组。对于当前遍历的元素，如果它与慢指针 slow 前两个位置的元素不相同，则将其加入到新数组中，同时慢指针 slow 增加。
正解：
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int n = nums.size();
// 打印 n 范围内所有的元素
if(n <= 2) return n;
int slow = 2;
for(int fast = 2; fast < n; ++fast){
// 当前元素要和它左边第 2 个元素进行比较
if(nums[fast] != nums[slow - 2]){
nums[slow] = nums[fast];
++slow;
}
}
return slow;
}
};还有一点值得注意：自增符 ++ 可以放在 nums[slow++] 中去写
- nums[slow++] —— 先用 nums[slow] 接收新值， slow 再加 1；
- nums[++slow] —— slow 先加 1，再用 nums[slow + 1] 接收新值；
6、多数元素
题目描述：
解法：
使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数
对于数组的遍历，使用 C++11 中新增的 增强型 for 循环 ：
for(int num: nums)
num 会遍历容器 nums 中的所有元素，这样可以很方便地记录每个元素的值和它们出现的次数
class Solution {
public:
int majorityElement(vector<int>& nums) {
// 利用映射类型的哈希结构，键存元素，值存出现次数
unordered_map<int, int> counts;
// 用来记录当前出现次数最多的元素以及它的出现次数
int Cur = 0;
int CurCnt = 0;
for(int num: nums){
++counts[num];
// 擂台赛
if(counts[num] > CurCnt){
Cur = num; // 更新主要元素为当前元素
CurCnt = counts[num]; // 更新出现次数最多的元素的出现次数
}
}
return Cur;
}
};使用 if 语句进行元素间的擂台赛，决出最终出现次数最多的元素，这个操作可以省去遍历哈希表找出值最大者这一过程
7、轮转数组
题目描述：
解法：
首先给出第一次 AC 了99%测试用例的版本，方便记录我忽略了这道题[最关键的信息]。
这道题的思路是容易想到的，说是“轮转”数组，其实用[滚动]数组描述更为贴切，每次从末尾元素开始，末尾元素滚至 下标0 的位置，剩余所有元素都要向右移动。
此时应注意的时，如果从头向尾移动，那么下标较大的元素会被下标较小的元素覆盖掉，所以应该从后向前移动每个元素，当除了原本的末尾元素还未就位，其余元素都已完成了位置的轮转，而且下标0 的位置被空出来了，把末尾元素插进去就好了，那么末尾元素为什么不会被覆盖掉呢？
我们可以提前使用一个临时变量来存储末尾元素
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
while(k--){
int tmp = nums[n - 1]; // 将尾元素放在临时变量中
for(int i = n - 1; i > 0; i--){
nums[i] = nums[i - 1];
}
nums[0] = tmp;
}
}
};但是这种方法的时间复杂度是 O(k*n)，k是旋转步数，n是数组的长度，在最后一个测试用例上超时了。
正解：
使用额外的等长数组来存储轮转后的元素，并将这个数组中的元素依次赋值回原数组，这个解法的时间复杂度只有O(n)，因为只需要遍历1次数组
class Solution {
public:
void rotate(vector<int>& nums, int k) {
// 使用额外的等长数组
int n = nums.size();
vector<int> newNums(n);
for(int i = 0; i < n; ++i){
newNums[(i + k) % n] = nums[i];
}
for(int i = 0; i < n; ++i){
nums[i] = newNums[i];
}
}
};只是在判断元素的新下标时的公式不好想
(i + k) % n
总觉得有点像哈希冲突时的解法，希望下次写这题时我还记得这个公式
8、罗马数字转整数
题目描述：
解法：
这题的唬人程度根本不是简单题的难度！官方给的描述太冗杂了，实际上就是
“如果当前字符的值小于其后面一个字符的值（即罗马数字规则中小数在大数左边表示减法），则将该值从结果中减去；否则将该值加到结果中。”
class Solution {
public:
int romanToInt(string s) {
// 标准的键值对形式，使用映射类型的哈希表结构存储
unordered_map<char, int> Roma = {
{'I', 1},
{'V', 5},
{'X', 10},
{'L', 50},
{'C', 100},
{'D', 500},
{'M', 1000},
};
int n = s.length();
int ans = 0;
for(int i = 0; i < n; ++i){
if(i < n - 1 && Roma[s[i]] < Roma[s[i + 1]]){
ans -= Roma[s[i]]; // 小数在大数左边表示减法
}else{
ans += Roma[s[i]];
}
}
return ans;
}
};对于官方提供的罗马数字和阿拉伯数字之间的对应关系，应该很自然地想到使用哈希表来存储它
if 语句的判断条件为：确保 i 不是最后一个元素，因为最后一个元素没有更后的元素和它比较了
当前元素如果小于后一个元素，则进行减法，否则进行加法
