外观
数组
参考：代码随想录 数组内容
1. 数组介绍
数组是存放在连续内存空间上的相同类型数据的集合。
- 数组下标都是从0开始
- 数组内存空间的地址都是连续的
因为数组的内存空间地址都是连续的，所以在 删除或增添元素 的时候，就难免要移动其他元素的地址。
例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：
即数组的元素不能删除，只能覆盖
2. 二分查找
使用二分查找的前提：
- 数组为有序数组
- 数组中无重复元素（有重复元素的话，寻找到的满足题目要求的元素可能不唯一）
二分查找的边界问题：
遵循循环不变量的原则：在二分查找的过程中，保持不变量，即 在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则
二分查找中的区间定义有两种方式：
- 左闭 右闭：[left, right] (说明右边的元素能够被选中，因此应该是 left <= right )
- 左闭 右开：[left, right) (说明右边的元素无法被选中, 因此应该是 left < right)
2.1 二分查找
link : LeetCode 704
方法一：暴力
方法二：左闭右闭
图示：在数组：1,2,3,4,7,9,10中查找元素2，
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
// 采用左闭右闭的写法
// 即 需要满足题目的条件在一个左闭右闭的区间中
while(left <= right){
int mid = (left + right) / 2;
if (nums[mid] < target) left = mid + 1;
else if (nums[mid] > target) right = mid - 1;
else return mid;
}
return -1;
}
}方法三：左闭右开
图示：
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length-1;
// 采用左闭右开的写法
// 即 需要满足题目的条件在一个左闭右开的区间中
// 因为左闭右开, right不能被选中
while(left < right){
int mid = (left + right) / 2;
if (nums[mid] < target) left = mid + 1;
// 因为 nums[mid] 肯定不满足条件, 但是right不能被选中, 所以 righ = mid
else if (nums[mid] > target) right = mid;
else return mid;
}
return -1;
}
}3. 移除元素(快慢双指针)
link : LeetCode 27
思考:
- 数组中的元素的内存地址是连续的,不能直接删除某一个元素, 只能覆盖
暴力:
两层for循环，一个for循环遍历数组元素 ，当遇到目标元素后；第二个for循环更新数组（该元素后面的元素统一向前移动一位）。
双指针：
快慢指针法：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。（需要仔细考虑）
- 快指针：寻找新数组的元素 ，即最终的新数组就是不含有目标元素的数组，所以就是寻找 不等于 val 的元素 （存储的也是下标）
- 慢指针：指向 新数组 的下标（用来存储快指针指向的非val元素）
图示：
class Solution {
public int removeElement(int[] nums, int val) {
int fastIndex = 0, slowIndex = 0;
// 快指针需要遍历 整个原数组, 从而找到所有不等于val的元素
while(fastIndex < nums.length){
if (nums[fastIndex] != val){
nums[slowIndex] = nums[fastIndex];
fastIndex++;
slowIndex++;
}else{
fastIndex++;
}
}
return slowIndex;
}
}4. 有序数组的平方 (相向双指针)
link: LeetCode 977
暴力：
双指针（相向双指针）：
数组一开始是有序的，但是负数平方之后变成了最大数，所以数组平方后的最大值要么在原数组的最左边，要么在原数组的最右边，从而采用相向指针
class Solution {
public int[] sortedSquares(int[] nums) {
int n = nums.length;
int res[] = new int[n];
int size = n-1;
// 使用双指针, 相向指针
// left 指针从左边开始, right指针从右边开始
int left = 0, right = n-1;
while(left <= right){
if (nums[left]*nums[left] > nums[right] * nums[right]) {
res[size] = nums[left] * nums[left];
left++;
size--;
}else{
res[size] = nums[right] * nums[right];
right--;
size--;
}
}
return res;
}
}关于循环中是 还是 :
- 可以先模拟一遍，发现最后当 left=right的时候，正好是中间的值，需要进行处理；
- 也可以直接运行，然后调试
5. 长度最小的子数组（滑动窗口）
link: LeetCode 59
暴力：
滑动窗口：
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果
在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。
滑动窗口如何用一个for循环来完成这个操作？
- 首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。
如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？ 此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。 那么滑动窗口的起始位置如何移动呢？
图示：s=7， 数组是 2，3，1，2，4，3， 
实现滑动窗口的要素：
- 窗口内是什么？
- 如何移动窗口的起始位置？
- 如何移动窗口的结束位置？
窗口就是满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。（只要窗口内 满足题目条件, 就需要一直移动起始位置, 即一直缩小窗口, 直到窗口内不满足条件为止, 从而得到最小的窗口）
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是for循环里的索引。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
// 因为有一个子区间满足题目条件
// 所以使用滑动窗口
int left=0, right=0;
// 定义窗口内的数值和
int sum = 0;
// 定义窗口的长度, 因为要求最小长度, 定义一个超大值
int len = 100010;
// 滑动窗口需要经过整个数组, 即窗口右边到数组最右端终止
for (;right<nums.length; right++){
// 首先窗口是第一个数组
sum += nums[right];
// 当窗口满足条件的时候, 持续缩小窗口, 直到不满足条件, 从而找到一个最小的子区间
while(sum >= target){
// 取最小值
len = len< right-left+1?len: right-left+1;
sum -= nums[left];
left++;
}
}
return len < 100010?len:0;
}
}6. 螺旋矩阵
link: LeetCode 59
思考：
在进行矩阵模拟的时候, 也需要坚持循环不变量的原则
模拟顺时针画矩阵的过程:
- 填充上行从左到右
- 填充右列从上到下
- 填充下行从右到左
- 填充左列从下到上
由外向内一圈一圈这么画下去。
这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样这一圈才能按照统一的规则画下来。（即在循环中 坚持循环不变量）
按照左闭右开的原则，图示：
同时，进行模拟矩阵，需要首先确定的要素：
每一圈的起始位置的 x 和 y
能够循环多少圈
定义 offset 控制每一条边的遍历长度，每循环一次右边界收缩一位
矩阵中心位置(非必须)
class Solution {
public int[][] generateMatrix(int n) {
// 起始位置
int startx = 0, starty = 0;
// 圈数
int loop= n /2;
// 长度控制
int offset = 1; // 左开右闭
// 中心位置
int mid = n/2;
int res[][] = new int[n][n];
int count = 1;
while(loop-- > 0){
int i=startx, j=starty;
// 从左向右
for (;j < n-offset; j++)
res[i][j] = count++;
// 从上到下
for (;i < n-offset; i++)
res[i][j] = count++;
// 从右向左
for (; j > starty; j--)
res[i][j] = count++;
for (; i > startx; i--)
res[i][j] = count++;
startx++;
starty++;
offset++;
}
// 如果有正中心
if ( n % 2 != 0) res[startx][starty] = count;
return res;
}
}