数组、链表部分算法题
- 一、数组
- 1. 二分查找
- 2. 移除数组元素
- 3. 有序数组的平方
- 4. 长度最小的子数组
- 5. 螺旋矩阵
- 二、链表
- 1. 删除链表元素
- 2. 设计链表
- 3.反转链表
- 4.两两交换链表中的节点
- 5.删除链表倒数第n个节点
- 6.环形链表
提前声明：本博客内容均为笔者为了方便个人理解而发布，题目思路参考自代码随想录，如果大家有觉得写的不清晰的地方，欢迎在评论区提问。
一、数组
1. 二分查找
点击跳转到力扣题目
注意题目的前提条件：有序数组、无重复元素
解法：双指针
这道题目的难点在于边界的确定，[left,right]和[left,right)的边界处理是不一样的，前者right应该为nums.length-1，后者right应为nums.length。
第一种：左闭右闭，即从[left,right]区间搜索，以[1,2,3,4]，找1为例子带进去看看第一轮while循环
var search = function(nums, target) {
let left = 0; //左指针闭区间，指向第一个位置0
let right = nums.length - 1; //右指针闭区间，指向最后一个位置3
//由于是左闭右闭，那么left=right就是有意义的，代表一直找到了最后一个元素
while(left <= right) {
let middle = Math.floor((right - left)/2) + left //寻找中间位置1
//开始二分查找，不断缩小边界
if(target < nums[middle]) {
//缩小边界，由于right是闭区间，判断条件已经确定target<middle位置的值
//由于是闭区间，下一次搜索一定会搜索<=middle-1处的值，right要变为middle-1=0
right = middle - 1;
} else if (target > nums[middle]) {
left = middle + 1;//缩小边界，此时已确定target>middle位置的值，left要变为middle+1
} else {
return middle //如果中间位置这个数刚好对上，就返回，否则就会一直到循环的最后一轮
}
}
//如果没有return，就return-1
return -1
};
第一轮循环结束后，搜索区间变成了[0,0]，也就是左右指针都指向了位置0的元素1，此时左右指针相撞，left=right就是有意义的，所以while循环的条件就是<=，等于号的情况代表一直找到了最后一个元素
第二种：左闭右开，即从[left,right)区间搜索，以[1,2,3,4]，找1为例子带进去看看第一轮while循环
var search = function(nums, target) {
let left = 0; //左指针闭区间，指向第一个位置0
let right = nums.length; //右指针开区间，指向最后一个位置3的后面4
//由于是左闭右开，那么left=right就是没有意义的
while(left < right) {
let middle = Math.floor((right - left)/2) + left //寻找中间位置1
//开始二分查找，不断缩小边界
if(target < nums[middle]) {
//缩小边界，由于right是开区间，判断条件已经确定target<middle位置的值
//由于是开区间，下一次搜索一定会搜索<middle的值，right要变为middle=1
right = middle;
} else if (target > nums[middle]) {
//缩小边界，由于left是闭区间，判断条件已经确定target>middle位置的值
//由于是闭区间，下一次搜索一定会搜索>=middle+1的值，left要变为middle+1
left = middle + 1;
} else {
return middle //如果中间位置这个数刚好对上，就返回，否则就会一直到循环的最后一轮
}
}
//如果没有return，就return-1
return -1
};
第一轮循环结束后，搜索区间变成了[0,1)，也就是左指针指向了位置0的元素1，右指针指向了位置1的元素2，此时必然会锁定0位置的元素，所以while循环的条件就是<。
这个题有点不太好描述，感觉容易乱，先这样吧……我觉得最好按第一种方法来记
2. 移除数组元素
点击跳转到力扣题目
做这道题必须要知道数组的特点，那就是删除元素时只能覆盖，不是原地删除
解法：快慢指针法
想要用快慢指针法解这个问题，最关键的点就是理解slow和fast都代表什么
我们可以把慢指针理解为新数组的每个位置，快指针的作用是遍历整个数组，这样的话快指针只需要找到不用删除的元素，然后依次覆盖就可以了。
可以仔细看下注释，以removeElement([1,2,3,4],3)理解一下指针的移动过程
var removeElement = function(nums, val) {
let slow = 0; //慢指针，指向新数组的每个位置
for(let fast = 0; fast < nums.length; fast++) { //快指针fast遍历数组
if(nums[fast] !== val) {
//如果快指针指向的不是要删除的元素，那么就让快指针位置的值覆盖慢指针位置的值
nums[slow] = nums[fast]
slow++ //然后慢指针先移动，快指针再移动
}
//如果是要删除的元素，那么只有快指针移动（fast++），慢指针不动
//这样可以做到后面的值覆盖到当前慢指针指向的位置
}
//移除后数组长度，就是当前slow指向的这个索引
return slow //因为如果覆盖了当前元素，slow会先往后移，此时指向的是没有元素的位置
//比如[1,2,3,4]，删除3时，slow指向3，fast指向4，4覆盖3后slow指向4，此时索引为3，正好是数组长度
};
3. 有序数组的平方
点击跳转到力扣题目
解法：双指针法
这个题目相较于前面两个，更好理解一些，其实也可以先平方再快排，但是更好的是用空间换时间，使用双指针法，依次找最大的元素unshift，当两个指针相撞时，就是最小的那个元素。
//双指针法，空间换时间，时间复杂度O(N)
var sortedSquares = function(nums) {
let i = 0; //一个指针指向头部
let j = nums.length - 1; //一个指针指向尾部
let result = []; //开辟一个新的空间
//注意循环停止的条件，当i = j时，指针相撞，指向的应该是最小的元素，循环应继续
while(i<=j) {
let left = Math.pow(nums[i],2)
let right = Math.pow(nums[j],2)
if( left > right) {
result.unshift(left)
i++
} else {
result.unshift(right)
j--
}
}
return result
};
4. 长度最小的子数组
点击跳转到力扣题目
解法：暴力or滑动窗口
这道题目其实也可以用暴力求解，那就是双重for循环把所有可能的长度组合枚举出来，然后去找哪个是满足条件的长度最小子数组，并返回它的长度。
var minSubArrayLen = function(target, nums) {
let result = Number.MAX_VALUE; //获取已知的最大值
//外层循环，以每一个元素作为起点去找目标值
for(let i = 0; i < nums.length; i++) {
let sum = 0;
//内层循环，寻找目标值
for(let j = i; j < nums.length; j++) {
sum += nums[j];
if (sum >= target) {
result = Math.min(result, j - i + 1); //和上一个长度比较，取较小的值
break;
}
}
}
// 如果最后result没变化，那么说明没有比target大的组合
return result === Number.MAX_VALUE ? 0 : result;
};
这里有很妙的一个方法，可以把时间复杂度降低到O(n)：
为了方便理解，直接以target = 101, nums = [1,1,1,100,1]为例，走一遍下面的逻辑
滑动窗口：先确定终止的位置（因为如果先确定开始位置，那么终止位置的确定和暴力解法就一样了），确定的方式就是去遍历数组，找到第一个符合sum >= target的位置，作为第一个滑动窗口的终止位置，开始位置直接从0开始，然后第一个符合条件的长度就是 j - i + 1 此时窗口开始缩短（i向前移动），移动前要先把之前位置的数值从sum中删掉。之后一直循环直到条件不成立，则j开始移动，就这样不断滑动，可以过一遍所有可能的情况。
为什么时间复杂度是O(n)呢？因为每个元素只被过了2次，那就是O(2n)，也就是O(n)
var minSubArrayLen = function(target, nums) {
let result = Number.MAX_VALUE; //找到最大值，方便下面对result进行取小
let sum = 0; //初始化sum
let i = 0; //开始位置是第一个
for(let j = 0; j < nums.length; j++) {
sum = sum + nums[j]; //通过前几次循环，先找到符合条件的j值，作为滑动窗口终止位置
while (sum >= target) { //i开始移动
result = Math.min(result, j - i + 1) //如果目标长度比上一个小，就替换一下子
sum = sum - nums[i]; //替换之后，i继续蠢蠢欲动，移动前，先把旧i位置的值从sum删掉
i++; //窗口左侧开始滑动，看一下下一个值是否是符合条件的值，如果是，则继续循环移动开始位置
}
}
return result === Number.MAX_VALUE ? 0 : result;
};
5. 螺旋矩阵
点击跳转到力扣题目
这道题的难点在于各种边界的确定，我们需要哪些状态来协助我们进行数组的更新。
- 第一个能想到的状态是
count，因为要记录每次要填的数，每填一个就++ - 第二个就是每一圈x轴和y轴的坐标，第一圈从00开始，第二圈从11开始
- 第三个就是要转几圈，通过循环填充数字，那么转几圈是很重要的，偶数就是n/2圈，奇数则是向下取整圈，比如3那就转1圈，中间的数字单独考虑，5则转两圈，中间的数组单独考虑
- 第四个就是填充的时候这个偏移量offset，每一圈开始和结束的位置是不一样的，比如第一圈的第一行是从startX=0开始，到n-1结束，第二圈的第一行是从startX=1开始，到n-2结束的，所以offset每轮都要递增一下
- 仔细看下注释，你会明白的
var generateMatrix = function(n) {
//1.初始化各种需要的变量，其中二维数组所有元素补0（因为js中无法直接通过索引添加元素）
let result = new Array(n).fill(0).map(() => new Array(n).fill(0));
let count = 1; //从1开始计数，一直到n，依次填充到n方
let startX = 0; //初始化每一圈的x轴坐标
let startY = 0; //初始化每一圈的y轴坐标
let loop = Math.floor(n/2); //转几圈
let offset = 1;
//每一个while就是转一圈，转几圈取决于是奇数还是偶数，偶数就是n/2圈，奇数则最后一圈不转，单独填充下就行了
while(loop > 0) {
let row = startX; //初始化每一圈的行坐标
let col = startY; //初始化每一圈的列坐标
//填充上行从左到右，左闭右开，临界值是n-offset
for(; col < n - offset; col++) {
result[row][col] = count;
count++;
}
//此时col停在了右列，row开始移动
//填充右列从上到下
for(; row < n - offset; row++) {
result[row][col] = count;
count++;
}
//此时row停在了下列，col开始移动
//填充下行从右到左
for(; col > startX; col--) {
result[row][col] = count;
count++;
}
//此时col停在了左列，row开始移动
//填充左列从下到上
for(; row > startY; row--) {
result[row][col] = count;
count++;
}
loop--; //每转完一圈，loop减1
startX++; //每转完一圈，开始位置要移动，为下一圈做准备
startY++; //每转完一圈，开始位置要移动，为下一圈做准备
offset++; //每转完一圈，填充的临界值（n-offset）都要缩小
}
//如果是奇数n，那么需要单独给矩阵中间的位置赋值，索引就是迭代到最后一圈时x和y轴的坐标位置
if (n % 2 === 1) {
result[startX][startY] = count
}
return result;
};
二、链表
1. 删除链表元素
点击跳转到力扣题目
解法：添加虚拟头节点，双指针
这个其实比较简单，方法是添加一个虚拟头节点，然后删除时，让上一个节点的next指向当前节点的next就可以了：
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
let dummyHead = new ListNode(0, head) //创建一个虚拟头节点
let pre = dummyHead //指针1，指向虚拟头节点
let current = head //指针2，指向头节点
//循环移动指针，一直到current指向null，所有链表元素遍历完毕
while(current) {
if(current.val === val) {
//如果找到要删除的元素
pre.next = current.next //pre指向current后面，这样被跳过的元素会被自动回收
current = current.next //指针current移动
} else {
//否则，移动两个指针继续寻找
pre = current
current = current.next
}
}
return dummyHead.next
};
2. 设计链表
点击跳转到力扣题目
这里其实不需要虚拟头节点，我没有用虚拟头节点，双指针pre默认为null，current默认为第一个节点，然后依次迭代
几个注意点：1.不用虚拟头节点 2.插入删除到0位置时单独判断 3.小心空指针情况（比如尾部插入时）
class LinkNode {
constructor(val) {
this.val = val;
this.next = null;
}
}
var MyLinkedList = function() {
this.head = null;
this.size = 0;
};
/**
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.get = function(index) {
if(index < 0 || index > this.size - 1) return -1;
let current = this.head;
for(let i = 0; i < index; i++) {
current = current.next
}
return current.val;
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtHead = function(val) {
const Node = new LinkNode(val);
Node.next = this.head;
this.head = Node;
this.size++;
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
const Node = new LinkNode(val);
let current = this.head;
if(this.head) {
while(current.next) {
current = current.next;
}
current.next = Node;
} else {
this.head = Node;
}
this.size++;
};
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index < 0 || index > this.size) return false
const Node = new LinkNode(val);
let pre = null;
let current = this.head;
for(let i = 0; i < index; i++) {
pre = current;
current = current.next;
}
if(index === 0) {
Node.next = this.head;
this.head = Node;
} else {
pre.next = Node;
Node.next = current;
}
this.size++;
};
/**
* @param {number} index
* @return {void}
*/
MyLinkedList.prototype.deleteAtIndex = function(index) {
if(index < 0 || index > this.size - 1) return false
let pre = null;
let current = this.head;
for(let i = 0; i < index; i++) {
pre = current;
current = current.next;
}
if(index === 0) {
this.head = current.next
} else {
pre.next = current.next
}
this.size--;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* var obj = new MyLinkedList()
* var param_1 = obj.get(index)
* obj.addAtHead(val)
* obj.addAtTail(val)
* obj.addAtIndex(index,val)
* obj.deleteAtIndex(index)
*/
3.反转链表
点击跳转到力扣题目
解法1：双指针迭代
双指针迭代就是定义两个指针pre和current，依次改变指针的指向，具体看下面的代码和注释：
function reverseList(head) {
let pre = null; //定义一个空指针在head的前面
let current = head; //定义另一个指针指向头节点
while(current) { //current指针为空的时候说明指到尾节点了，就停止循环
let temp = current.next; //定义一个temp来保存当前节点的下一个节点
current.next = pre; //关键一步，改变指针指向，把向后指的指针改为向前指
pre = current; //pre指针向后移，指向current
current = temp; //current指针向后移，指向当前节点的下一个节点（提前保存了）
}
return pre; //最后返回新的头指针（current指向了null）
}
解法2：递归
递归的实现思路和双指针迭代是类似的，也是要有两个指针向后指
function reverseList(head) {
return reverse(null,head); //初始 pre = null, current = head
}
//定义递归函数，作用其实就是让指针向后移
function reverse(pre,current) { //定义两个指针，一个pre指向前面，一个current指向当前
if(current == null) return pre; //递归停止的条件（最后一层递归开始出栈,返回头指针）
let temp = current.next; //保存后面的节点，方便后面让指针向后移
current.next = pre; //改变指向
return reverse(current,temp); //返回一个递归的调用
}
4.两两交换链表中的节点
点击跳转到力扣题目
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var swapPairs = function(head) {
//1.创建虚拟头节点
const dummyhead = new ListNode(0);
dummyhead.next = head;
//2.创建双指针
let pre = dummyhead;
let current = head;
//3.奇数和偶数项的结束条件，先判断current有没有，再判断curren.next有没有（逻辑中断）
while(current && current.next) {
//4.依次改变指针指向，注意不要出现空指针的情况
let temp = current.next; //测试中发现current.next会丢失，先保存一下
//4.1调转两个节点
pre.next = temp;
current.next = temp.next;
temp.next = current;
//4.2指针向后移动
pre = current;
current = current.next;
}
//综上如果无法在脑中模拟，画个图其实就明白了
return dummyhead.next;
};
5.删除链表倒数第n个节点
点击跳转到力扣题目
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
//使用头节点就是为了：不需要单独考虑删除头节点的情况
const dummyhead = new ListNode(0);
dummyhead.next = head;
//快慢指针法
let fast = dummyhead;
let slow = dummyhead;
n = n + 1;
//快指针先走n+1下，慢指针不动
while(n-- > 0) {
fast = fast.next;
}
//快慢指针一起移动，当快指针指向null时，慢指针指向的就是要删除的节点的前一个节点，仔细想想是不是
while(fast) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
//这里返回的不能是head，因为如果删除的是head，那么dummyhead指针指向了第二个节点
//但此时head还是有值的，通过head仍然能获取链表所有值，相当于head并没有被删掉（仔细想想删除头节点时指针的改变）
return dummyhead.next;
};
6.环形链表
点击跳转到力扣题目
解法：快慢指针
这里可以看代码随想录的证明，其实快慢指针相遇的点到环入口的距离和头节点到环入口的距离是相同的（快指针走两步慢指针走一步的情况下，慢指针第一圈内一定会和快指针相遇）
搞清楚这一点，我们只需要找到几个位置就可以了，首先是相遇的节点a，相遇后让两个指针分别指向head和a，同时按每次一个节点的速度移动，当两个指针相遇时，指针指向的节点就是环的入口。
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
//1.定义快慢指针指向头节点
let slow = head;
let fast = head;
//2.循环移动快慢指针，慢指针每次走一步，快指针每次走两步
while(fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
//3.快慢指针相遇时一定在环上，此时指针距离环入口的距离和head距离环入口的距离相同
if(slow === fast) {
let index1 = head;
let index2 = fast;
//4.同时移动两个指针直至相撞，那么撞的位置就是环的入口
while(index1 !== index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
//如果return null，只有两种情况，一种是链表只有1个节点或没有节点，这种情况不可能有环
//另一种情况就是链表没有环（不然在上面代码中已经return出去了）
return null;
};
