0-线性表
💡 线性表从语言的实现角度上讲，有两种结构：① 一体式结构：存储表信息的单元与元素存储区以连续的方式安排在一块存储区里，两部分数据的整体形成一个完整的顺序表对象。这种结构整体性强，易于管理。（C和C++都是一体式的结构）② 分离式结构：表对象里只保存与整个表有关的信息（即容量和元素个数），实际数据元素存放在另一个独立的元素存储区里，通过链接与基本表对象关联。（Java和Python是分离式结构）
- 🛒 容量扩充的两种策略
- 每次扩充增加固定数目的存储位置，如每次扩充增加10个元素位置，这种策略可称为线性增长。特点：节省空间，但是扩充操作频繁，操作次数多。
- 每次扩充容量加倍，如每次扩充增加一倍存储空间。特点：减少了扩充操作的执行次数，但可能会浪费空间资源。以空间换时间，推荐的方式。
1-数组
- 🖇️🖇️🖇️ 数组
- 特征：可以通过
索引快速访问，数组大小和数组长度可以不同（大小代表容量，长度代表实际存的元素个数） - 一般情况下从下标
0开始访问，也可以用下标 0 的位置来存储数组的元素个数 - 增删改查：增和删时注意元素的移动，特别是边界值的处理
- 特征：可以通过
2-合并两个有序数组
题目：力扣 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
- 🧠 思路演进
1>简单思路，申请一个新的数组，从头比较后加入新数组中，之后移动到nums1中即可。缺点：空间复杂度 O(n)2>第二个思路，nums1已经有那么大的空间了，nums2加进去后，进行排序即可。缺点：面试官不喜欢3>第三个思路，nums1空间足够，我们可以从后比较，然后从后填入，优点：不消耗额外空间，也只需要遍历一遍
3-删除数组元素
题目：这里有两个题，一个题原地删除值等于 val 的元素，返回数组新的长度（ 力扣 ）；另一个题，删除数组中重复出现的元素（ 力扣 ）
- 🧠 思路演进
- 我们知道，数组中元素删除需要伴随着大量元素的移动，但如果按位置依次移动的话，又会浪费大量的时间，一个题一个题的看
1>第一题删除值为 val 的元素，此题中并没有要求保持原来的顺序，所以我们可以不管顺序如何，只要将不是 val 的元素放到数组前面即可快慢双指针，慢指针从头开始，快指针往后找不是 val 的元素，找到后写到慢指针位置即可（该思路最简单）对撞双指针，左指针从数组最左端开始，右指针从数组最右端开始，左指针找 val 元素，右指针找非 val 元素，找到后用右指针的值覆盖左指针的值，之后继续移动，两个指针对撞即结束
2>原地删除重复的值，同样，可以用快慢双指针，慢指针在左，快指针在右，找到和慢指针不相等的元素，找到后慢指针后移一位用快指针的值进行覆盖，之后接着找，知道快指针遍历完该数组（该题给的前提：数组升序）
💡💡💡 可以发现，上面两个题目我们都用到了
双指针的思想，双指针不一定是指针，可以是两个变量，使用双指针，不论是快慢、对撞都是常用的思想，需要熟悉。905. 按奇偶排序数组 也是一个用对撞双指针思想的题，和以上相比只是将比较的对象变为了奇偶数（代码比较简单且典型，如下：）
class Solution {
public int[] sortArrayByParity(int[] nums) {
int low = 0, right = nums.length - 1; // 双指针
while (low <= right) { // 对撞条件
if (nums[low] % 2 == 1 && nums[right] % 2 == 0) {
int temp = nums[low];
nums[low] = nums[right];
nums[right] = temp;
}
if (nums[low] % 2 == 0) low++;
if (nums[right] % 2 == 1) right--;
}
return nums;
}
}4-轮转数组
题目：189. 轮转数组 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。（链表的这个轮转题是做过的：旋转链表）
- 🧠 思路演进
- 🚩 和旋转链表类似，不一样的点在于链表我们只需要更改指针即可，而数组则需要将值进行实际的移动
- 💡 回顾之前的 重要思想，除了
双指针，还有反转。这题就可以通过多次反转来完成，当然，实现反转这一步也用到了双指针
5-数组区间专题
题目：228. 汇总区间 数组没有重复元素，找出数组中的连续区间。还有扩展，不过思路是一样的，扩展题为找数组中的缺失区间 需要力扣会员
- 🧠 思路演进
- 我的第一反应
双指针，使用快慢双指针，找到区间的边界，即可，需要注意，判断条件为nums[fast] + 1 == nums[fast + 1]，所以快指针只能遍历到倒数第二个元素，不然会越界，到最后一个元素后单独处理一下（还有空数组的情况） - 缺失区间也是相同思路，找到不连续的区间即可
- 我的第一反应
6-字符串空格替换问题
- 🧠 问题讨论 剑指 Offer 05. 替换空格
- 替换很常用，且高级语言里，字符串都提供了对应的 API ，所以通过这个题并不难。需要刨析这个题背后的考点，分两种情况：
1>原来的字符串长度不可变，而现在将一个字符替换为多个字符，原来的空间不够，则需要开辟新的空间，这个也简单，遍历一遍，遇到替换字符替换即可2>第二种情况是给定的字符串已经给足了替换的空间，这就要求在空间复杂度为 O(1) 的情况下解决。较好一点的方法，遍历一遍找到需要替换字符的个数，有了新字符串的长度后再从尾部移动即可
7-数组中元素出现次数的合集
题目：
① 剑指 Offer 39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
② 136. 只出现一次的数字 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
③ 剑指 Offer 03. 数组中重复的数字 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
- 🧠 思路演进
1>除了最简单的次数统计，超过一半，也意味着排序后中位数一定就是这个数；但这些做法都比较麻烦，使用hash进行统计，需要消耗 O(n) 的空间；进阶办法可以使用两个变量记录，一个变量记值，一个变量记次数，超过一半的次数意味着其他值按次数一对一的抵消后，该值也还有剩余（进阶思路利用了过半）2>用集合依然能解，遇到重复则剔除，剩下的那一个数就是，缺点还是要消耗额外空间；进阶我们关注 其余元素均出现两次 ，这意味着可以两两抵消，异或运算可以很好的解决这个问题，相同元素异或为0，0与任何元素异或则等于该元素，所以仅需用一个0与数组中所有元素进行异或运算即可（进阶思路用到了位运算的思想）3>找任意重复的元素，用集合依然简单，不重复加入集合，遇到重复直接返回即可
🚩🚩🚩
总结：数组元素次数问题，我们会用到Hash、集合、位运算等东西，Hash可以用于计数统计，集合用于去重，位运算可以去除偶数个元素，理解即可
8-颜色分类问题（排序）
题目：75. 颜色分类 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
- 🧠思路演进
1>问题转换后就是一个排序问题，简单一点做，用冒泡排序即可，问题在于需要遍历较多遍；进一步，用基于双指针的冒泡排序，第一次遍历将0移到最前面，第二次遍历仅对1和2进行交换即可，只需要遍历两次（用第二种已经不错了）2>面试官要求只能遍历一次，如果是两个元素，用对撞双指针进行交换，我们就仅需要两个指针。现在有三个元素，很自然的想到需要有三个指针，左指针保证左边所有元素为0，右指针保证右边所有元素为2，中间指针用于遍历。难点在于考虑各种情况，如下图：
