基本的数据结构
最近一直在letcode上刷数据结构和算法题，因此博客更新比较慢。本文主要整理这段时间学习到的基本数据结构，和一些常见的问题解法。
本文主要为letcode探索栏目相关课程的练习笔记，相关课程包括
感谢letcode提供如此好的在线课程！相关课程练习代码均放在github上。
数组
数组是一种基本的数据结构，用于在连续内存中按顺序存储元素。因为数组中的每个元素都可以通过数组索引来识别，因此数组中的元素可以随机存取。
双指针遍历
大多数情况下，遍历数组只需要一个从头开始的指针即可，但在某些时候，同时使用两个指针来遍历更优。
使用双指针一个经典的场景是：从两端向中间遍历数组，如
我们可以使用从头部0和尾部len-1开始的两个指针进行遍历，在每次循环中交换对应索引值的元素，直至两个指针相遇跳出循环为止
var reverse = function(arr) {
var i = 0;
var j = arr.length - 1;
while (i < j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
return arr
}寻找数组的中心索引，找到数组中心索引，其左侧所有元素相加的和等于其右侧所有元素相加的和。
我们可以先获取数组元素的总和，然后一次移动索引值，直至满足左右和相等
var pivotIndex = function(nums) {
var sum = 0
var len = nums.length
for (var i = 0; i < len; ++i) {
sum += nums[i];
}
var l = 0, r = sum - nums[0]
for(var i = 0; i < len; ++i){
if(l === r){
return i
}else {
l += nums[i];
if(nums[i+1]){
r -= nums[i + 1];
}
}
}
return -1
};快慢指针
在某些时候，我们可以使用两个不同步的指针（一个快指针，一个慢指针）来遍历数组，并根据需求来确定快指针和慢指针的移动策略，如
我们同时维护一个快指针i用于遍历数组，一个慢指针用于更新数组即可
var removeElement = function(nums, val) {
var k = 0;
for(var i = 0; i < nums.length; ++i){
if(nums[i] !== val){
nums[k] = nums[i]
++k
}
}
return k
};可以通过滑动窗口解决这个问题。同时维护左指针l和右指针r，使用sum表示 左右区间内元素之和，当sum符合题意时，再计算长度最小值。
var minSubArrayLen = function(s, nums) {
var l = 0;
var r = 0;
var sum = 0;
var len = nums.length;
var min = Infinity;
while (l < len) {
if (r < len && sum < s) {
sum += nums[r];
r++;
} else {
sum -= nums[l];
l++;
}
if(sum >= s){
min = Math.min(min, r - l)
}
}
return min === Infinity ? 0 : min
};滑动窗口是一个比较经典的算法，这里有一篇详细介绍滑动窗口的文章，不妨移步阅读。
队列
数组可以通过索引值随机访问数组元素，在某些情况下，我们可能想要限制处理顺序。
队列是一种先进先出的数据结构，元素的处理顺序与它们添加到队列的顺序是完全相同的顺序， 队列包含两个重要的操作，入队 enqueue 和出队 dequeue。
单调队列
单调队列指的是队列中的元素是单调递增或单调递减的
参考：单调队列及其应用。
广度优先BFS
队列可以实现广度优先搜索（BFS）算法，其常见应用有
- 树的层级遍历，每次遍历时将当前层级所有子节点入队列，并将当前层级的所有节点出队列
- 找出从根结点到目标结点的最短路径，由于每次遍历时都将最近的相邻节点先加入队列，因此越接近根节点的节点越找遍历，所以BFS可以
这篇文章里面有关于BFS和DFS的直观动图，不妨移步查看一下。
在广度优先搜索中，我们需要保证同一个节点不会被遍历两次，因此面对特定的问题，我们可能需要一个哈希表来保存已访问过的节点。
接下来看看广度优先搜索的几个例子
解题思路如下：
- 从起点开始，将未访问过的且相邻的海岛加入队列，直至队列为空时，表示一个海岛遍历完成
- 遍历网格，重复步骤1，遇见未访问过的海岛，将计数器加1
- 输出计数器
var numIslands = function(grid) {
var ans = 0;
var rows = grid.length;
if(!rows){
return 0
}
var cols = grid[0].length;
var visited = {};
function createKey(i, j) {
return i + "," + j;
}
function bfs(i, j) {
var queue = [];
queue.push({ i, j });
while (queue.length) {
var first = queue.shift();
var currentI = first.i,
currentJ = first.j;
push(queue, currentI - 1, currentJ);
push(queue, currentI + 1, currentJ);
push(queue, currentI, currentJ - 1);
push(queue, currentI, currentJ + 1);
}
}
function push(queue, i, j) {
//网格的边界条件
if (i >= 0 && i < rows && j >= 0 && j < cols) {
var key = createKey(i, j);
if (grid[i][j] == "1" && !visited[key]) {
visited[key] = true;
queue.push({ i, j });
}
}
}
for (var i = 0; i < rows; ++i) {
for (var j = 0; j < cols; ++j) {
var key = createKey(i, j);
// console.log(visited)
if (grid[i][j] === "1" && !visited[key]) {
ans++;
bfs(i, j);
}
}
}
return ans;
};思路：
- 从起点
0000开始，将相邻的且不在deadends列表中的组合加入队列 - 遍历每一步的组合，判断是否存在目标，如存在则直接返回，如不存在则将相邻的组合加入队列
- 重复步骤2直至队列为空，则返回-1
var openLock = function(deadends, target) {
var step = 0;
var queue = [];
var visited = {};
var start = '0000'
if(deadends.includes(start)){
return -1
}
queue.push(start);
visited[start] = true;
while (queue.length) {
var len = queue.length;
for (var i = 0; i < len; ++i) {
var cur = queue.shift();
if (cur === target) {
return step;
}
var siblings = getSiblings(cur);
siblings.forEach(function(item) {
if (!visited[item] && !deadends.includes(item)) {
queue.push(item);
visited[item] = true;
}
});
}
step++;
}
return -1;
function getSiblings(cur) {
var ans = [];
for (var i = 0; i < cur.length; ++i) {
var c = parseInt(cur[i]);
var arr = cur.split("");
arr[i] = c + 1;
if (arr[i] > 9) {
arr[i] = 0;
}
ans.push(arr.join(""));
arr[i] = c - 1;
if (arr[i] < 0) {
arr[i] = 9;
}
ans.push(arr.join(""));
}
return ans;
}
};思路：
- 首先获取小于等于n的所有平方数，从大到小依次排列
- 将最大的数入队列
var numSquares = function(n) {
var queue = [n];
var step = 0;
while (queue.length) {
var len = queue.length;
step++;
for (var i = 0; i < len; ++i) {
var curr = queue.shift();
for (var j = Math.floor(Math.sqrt(curr)); j >= 1; --j) {
var next = curr - j * j;
if (next == 0) {
return step;
}
queue.push(next);
}
}
}
return step;
};栈
栈是一种后进先出的数据结构，主要包含入栈push和出栈pop两个操作。
栈在处理判断回文字体、括号匹配等问题上可以大展身手。
一个经典的问题就是逆波兰表达式求值，逆波兰表达式是一种后缀表达式，因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序，逆波兰式在计算机看来却是比较简单易懂的结构
(a+b)*c-(a+b)/e的后缀表达式为：
(a+b)*c-(a+b)/e
→((a+b)*c)((a+b)/e)-
→((a+b)c*)((a+b)e/)-
→(ab+c*)(ab+e/)-
→ab+c*ab+e/-具体解题思路如下
- 遍历tokens数组，
- 遇见数字则入栈，遇见操作符则将连续出栈两次，第一次出栈的是右操作数r，第二次出栈的是左操作数l，运算
l + 操作符 + r表达式的值，并将该值入栈， - 重复步骤2，直至tokens数组遍历完毕，正常情况栈中只有一个元素，即为输出结果
var evalRPN = function(tokens) {
// 将逆波兰表达式解析成中缀表达式
function isOperator(c) {
return ["*", "/", "+", "-"].includes(c);
}
var st = [];
for (var i = 0; i < tokens.length; ++i) {
var c = tokens[i];
if (isOperator(c)) {
var r = st.pop();
var l = st.pop();
var res;
if (c === "+") {
res = parseInt(l) + parseInt(r);
} else if (c === "-") {
res = parseInt(l) - parseInt(r);
} else if (c === "*") {
res = parseInt(l) * parseInt(r);
} else if (c === "/") {
res = parseInt(parseInt(l) / parseInt(r));
}
st.push(res);
} else {
st.push(c);
}
}
return st.join("");
};单调栈
单调栈指的是栈中的元素必须严格的递增或者递减的顺序，否则将执行出栈。单调栈主要解决下面几种问题
- 比当前元素更大的下一个元素
- 比当前元素更大的前一个元素
- 比当前元素更小的下一个元素
- 比当前元素更小的前一个元素
下面有一个使用单调栈的例子。
思路：
- 使用一个栈来保存每天温度的索引值
- 如果当天
i温度大于栈顶stack.peek()温度时，则表示可已升温，此时更新栈顶对应索引值等待stack.peek() - i天后温度，然后执行出栈操作。（由于大于当天温度的值都已出栈，因此这个栈是一个表示温度递减的栈） - 接着重复执行步骤2，检测前面是否有可以更新等待升温天数的值，直至栈为空或者当天温度小于等于栈顶温度，这样就可以一直保持递减栈
- 返回每一步更新的
stack.peek() - i组成的结果
var dailyTemperatures = function(T) {
var res = []
var stack = []
for(var i = 0; i < T.length; ++i){
res[i] = 0
}
for(var i = 0; i < T.length; ++i) {
while (stack.length && T[i] > T[stack[stack.length - 1]]) {
var t = stack[stack.length - 1];
stack.pop();
res[t] = i - t;
}
stack.push(i)
}
return res
};深度优先DFS
深度优先搜索（DFS）也可用于查找从根结点到目标结点的路径。实现dfs有两种方式：递归和显示栈。
通过递归，我们使用由系统提供的隐式函数调用栈来实现dfs
递归实现树的中序遍历
var inorderTraversal = function(root){
if(!root){
return null
}
var ans
function inorder(root){
if(!root){
return
}
inorder(root.left)
ans.push(root.val)
inorder(root,right)
}
inorder(root)
return ans
}房间和钥匙也是一道比较经典的dfs问题。
其大致思路是
- 从第一个房间开始，访问第一个房间内所有钥匙可以打开的房间
- 递归访问每一个房间可以打开的钥匙，记录访问过的房间
- 遍历房间列表，判断所有房间是否已经全部访问
var canVisitAllRooms = function(rooms) {
var visited = []
function dfs(roomNumber){
if(visited[roomNumber]){
return
}
visited[roomNumber] = true // 记录已经访问过的房间
var keys = rooms[roomNumber]
for(var i = 0; i < keys.length; ++i){
dfs(keys[i]);
}
}
dfs(0)
for(var i = 0; i < rooms.length; ++i){
if(!visited[i]){
return false
}
}
return true
};为了避免函数调用栈过多导致溢出堆栈移除，我们显式地使用栈来实现dfs，
通过显式栈来实现树的中序遍历的例子
var inorderTraversal = function(root) {
if (root === null) {
return [];
}
var st = [root];
var ans = [];
var visited = new Map();
while (st.length) {
var top = st[st.length - 1];
var left = top.left;
if (!left || visited.has(left)) {
ans.push(top.val);
st.pop(); // 弹出节点
var right = top.right;
if (right) {
st.push(right);
}
} else {
if (!visited.has(left)) {
visited.set(left, true);
st.push(left);
}
}
}
return ans;
};链表
链表也是一种线性的数据结构，每个节点都保存了下一个节点的引用。由于链表不需要保存在连续的的内存中，因此其增加和删除节点比较方便。
参考：链表常见问题汇总
- 判断链表是否有环
- 如果存在环，找到入环节点
- 如果存在环，确定环的长度
- 如果存在环，求链表长度
- 如何判断两个无环链表是否相交：将其中一个链表首尾相连，再求另外一个链表是否有环
- 求两个相交链表的交点
双指针遍历
与在数组中类似，我们也可以在链表的遍历中使用双指针
- 两个指针
从不同位置出发：一个从始端开始，另一个从末端开始； - 两个指针
以不同速度移动：一个指针快一些，另一个指针慢一些。
在单链表中，由于只能通过节点访问下一个节点，因此第二种使用场景更为普遍
一个经典的问题就是：如何判断链表是否有环？如何获取入环的节点?
- 如果没有环，快指针会停留在链表的末尾
- 如果有环，快指针最终与慢指针相遇，一个安全的选择是每次移动慢指针
一步，而移动快指针两步，如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针
如果还需要返回第一个入环的节点，则需要连续使用两次双指针，
- 第一次通过快慢指针判断是否有环并得到环的长度m，
- 第二次将两个指针同时移动动头节点，然后将快指针提前移动m步，然后每次循环将快慢指针都移动一步，下次相遇的节点即为入环的节点。
var detectCycle = function(head) {
var pf = head; // 快指针
var ps = head; // 慢指针
var m = 0; // 环的长度
var hasFirstMeet = false;
while (pf && pf.next && ps && ps.next) {
pf = pf.next.next;
ps = ps.next;
if (hasFirstMeet) {
m++;
}
if (ps === pf) {
if (!hasFirstMeet) {
hasFirstMeet = true;
} else {
break;
}
}
}
if (hasFirstMeet && m > 0) {
// 得到环的长度之后，将快慢指针同时指向head，并将快指针提前移动m步，后续每次循环时快慢指针都走一步，下次相遇时则为开始起环的节点
pf = head
ps = head
while(m > 0){
pf = pf.next
m--
}
while(pf !== ps){
pf = pf.next
ps = ps.next
}
return ps
} else {
return null;
}
};另外的一个问题是：判断链表是否相交
把两个单链表看作是两段线段，以两条线段相加的和不变这个条件，分别遍历两个链表。参考解法：实现相交链表。
现有线段ACD和线段BCD，两条线段相交于C点。
同时从A、B分别开始遍历ACD和BCD，遍历点记为PA和PB，经过的长度用len记录，遍历步长为1。
当PA遍历到D时，PB在I，此时len为5。由于ACD已经遍历完，PA就跳到B点开始遍历BCD；当BCD遍历完时，PB跳转到A。
当两个指针相遇时，他们走过的路程相同，相遇的地方就是两条链表的交点
分解一下PA和PB的遍历轨迹就是，
- PA：AECHIDBFGC。
- PB：BFGCHIDAEC。
// 双指针法
var getIntersectionNode = function(headA, headB) {
var pa = headA;
var pb = headB;
if (!pa || !pb) {
return null;
}
while(pa !== pb){
if(!pa){
pa = headB;
}else {
pa = pa.next
}
if(!pb){
pb = headA
}else {
pb = pb.next;
}
}
return pa
};空间复杂度O(1)
链表中的很多问题都可以通过O(1)的空间复杂度来解决，经典问题诸如
var reverseList = function(head) {
if (!head) {
return null;
}
// 只有一个节点
if (!head.next) {
return head;
}
var first = head.next; // 现在链表的起始节点
var last = head;
while (head.next) {
// 将下一个节点添加到链表的头部
head.next = first.next;
first.next = last;
// 迭代
last = first;
first = head.next;
}
return last;
};双链表
单链表的每个节点值保存了下一个节点的引用，因此删除某个节点时，需要先找到其前面的那个节点；双链表在单链表的基础上，其中的每个节点还增加了前一个节点的引用，因此双链表可以从两端向中间遍历。
树
树也是一种常见的数据结构，树里的每一个节点有一个根植和一个包含所有子节点的列表。
二叉树的遍历
二叉树是一种更为典型的树状结构，其每个节点最多有两个子节点，通常被称为左子树和右子树。
树的一个重要操作就是遍历，可以通过BFS和DFS来进行遍历
树的BFS层级遍历
var levelOrder = function(root) {
if (!root) {
return [];
}
var queue = [];
queue.push(root);
var ans = [];
while (queue.length) {
var row = []
var len = queue.length
for(var i = 0; i < len; ++i){
var node = queue.shift()
row.push(node.val) // 把当前这一行的数据保存在一起
// 将下一层相关的节点继续保存在队列中中
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
}
ans.push(row)
}
return ans
};树的DFS深度遍历
根据根节点的访问时机，树的DFS又可以分为
- 根->左子树->右子树，前序遍历
- 左子树->根->右子树，中序遍历
- 左子树->右子树->根，后续遍历
// 前序遍历
var preorderTraversal = function(root) {
var ans = [];
function preorder(node) {
if (!node) {
return;
}
ans.push(node.val);
preorder(node.left);
preorder(node.right);
}
preorder(root);
return ans;
};
// 前面深度优先时展示了树的中序遍历，因此这里不再赘述
// 后序遍历
var postorderTraversal = function(root) {
var res = [];
function post(root) {
if (!root) {
return;
}
post(root.left);
post(root.right);
res.push(root.val);
}
post(root);
return res;
};当你删除树中的节点时，删除过程将按照后序遍历的顺序进行。 也就是说，当你删除一个节点时，你将首先删除它的左节点和它的右边的节点，然后再删除节点本身
两种递归方式
树可以以递归的方式定义为一个节点（根节点），它包括一个值和一个指向其他节点指针的列表， 递归是树的特性之一。
- 如果能够通过节点自身解决出发，来确定子节点的参数和结果，则可以使用自顶向下的方式来实现递归。
- 假如能够知道子节点，就能够计算出其父节点的答案，则可以使用自底向上的方式来实现递归
求解二叉树的最大深度
我们设定根节点的深度为1，则其子节点的深度为2，子节点的子节点深入为3，依次类推，根节点的最大深度即为左右子树深度的最大值加1
var maxDepth = function(root) {
function dfs(node, deep) {
if (!node) {
return deep - 1;
}
var l = dfs(node.left, deep + 1);
var r = dfs(node.right, deep + 1);
return Math.max(l, r);
}
return dfs(root, 1);
};知道了根节点的值val，则可以简化成子树中是否存在sum - val的问题，通过递归可以较方便地解决这个问题。
var hasPathSum = function(root, sum) {
if (!root) {
return false;
}
var { left, right } = root;
// 叶子节点的值等于sum，满足条件
if (!left && !right) {
return root.val === sum;
}
return hasPathSum(left, sum - root.val) || hasPathSum(right, sum - root.val);
};N叉树与前缀树
N叉树与二叉树基本相似，只是将二叉树的左右节点换成了children子节点列表，相关的遍历操作与解题思路基本类似
前缀树是N叉树的一种特殊形式，通常用来存储字符串，其每个节点代表一个字符串或字符串前缀。
前缀树的一个重要特性是：节点所有的后代都与该节点相关的字符串有着共同的前缀。前缀树可用于自动补全，拼写检查等应用场景。
二叉搜索树
二叉搜索树BST是二叉树的一种特殊形式。 二叉搜索树具有以下性质：每个节点中的值必须大于（或等于）其左侧子树中的任何值，但小于（或等于）其右侧子树中的任何值。
由于其结构的特殊性，我们可以通过二分查找来快速找到目标节点。
判断树是否为二叉树
中序遍历二叉树得到的应该是一个升序数组，所以判断树是否为BST可以通过中序遍历来实现。
var isValidBST = function(root) {
var ans = [];
function inorder(root) {
if (!root) {
return ans;
}
inorder(root.left);
ans.push(root.val);
inorder(root.right);
}
inorder(root)
for (var i = 0; i < ans.length - 1; ++i) {
if(ans[i] >= ans[i+1]){
return false
}
}
return true
};BST中搜索目标节点
在BST中搜索可以通过自顶向下来实现
var searchBST = function(root, val) {
if(!root){
return null
}
if(root.val === val){
return root
}else if(root.val > val){
return searchBST(root.left, val)
}else if(root.val < val){
return searchBST(root.right, val)
}
};二叉平衡搜索树
在极端情况下，二叉树会退化成一条链表，此处查找的时间复杂度就变成了O(n)，为了解决这个问题，引入了二叉平衡树AVL
- 具有二叉查找树的全部特性
- 每个节点的左子树和右子树的高度差至多等于1。
当插入或删除节点时，可能会导致节点的左子树和右子树的高度差超过1，此时需要进行左旋或右旋操作，具体操作可以参考这篇文章。
红黑树
因为平衡树要求每个节点的左子树和右子树的高度差至多等于1，这个要求实在是太严了，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而我们都需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。
在插入、删除十分频繁的场景中，平衡树的性能会大打折扣，因此又引入了红黑树。红黑树的规则比平衡树的规则要宽松一些，因此相当于是BST和AVL的一种折中方案。
关于平衡树和红黑树，在后续的学习中再继续深入。参考： 腾讯面试题：有了二叉查找树、平衡树为啥还需要红黑树？
哈希表
哈希表是一种支持快速插入和搜索的数据结构。哈希表的关键思想是使用哈希函数将键映射到存储桶。理想情况下，完美的哈希函数将是键和桶之间的一对一映射，而在实际情况下，哈希函数需要在桶的数量和容量之间进行权衡。
大多数编程语言都内置了其实现，在JavaScript中，原始对象字面量{}就可以当做一个哈希表。
哈希集合
哈希集合用于存储非重复值。在JavaScript中还可以使用Set来作为哈希集合使用，一般用来判断目标值是否已经存在。在哈希集合中，我们一般只需要关注键名。
可以先遍历nums1，获取不同元素的集合，然后再遍历nums2，如果元素存在于集合中，则加入到结果集中
var intersection = function(nums1, nums2) {
var hash = new Set();
for (var val of nums1) {
hash.add(val);
}
var ans = new Set()
for (var val of nums2) {
if(hash.has(val)){
ans.add(val)
}
}
return Array.from(ans)
};哈希映射
哈希映射用于存储(key, value)键值对，我们需要关注键名和键值之间的联系。
需要找到和为目标值的两个元素的索引，则可以在映射中保存每个元素的值和索引，这样查找值为target - nums[i]的时间复杂度就变成了1，如果在映射中，则表示存在答案，返回true即可。
var twoSum = function(nums, target) {
var map = new Map();
for (var i = 0; i < nums.length; ++i) {
if (!map.has(nums[i])) {
map.set(nums[i], i);
}
}
for (var i = 0; i < nums.length; ++i) {
var diff = target - nums[i];
if (map.has(diff) && map.get(diff) !== i) {
return [i, map.get(diff)];
}
}
return false;
};小结
最近的前端学习一直不在状态，写了三年前端，总觉得少了些什么东西，很多技术都没有实际深入去研究。回想起来，还是要老老实实打好基础才行。因此打算回过头来学习数据结构和算法。
算法学习是一个比较漫长的过程。以前一直比较畏惧，学习念头也是三天打鱼两天晒网。因为算法学习不像学习新技术框架那样能立即获取成就感。总之，要踏踏实实静下心来学习才行。
现在刚学习完基础的数据结构，下一篇文章会总结一些常见的基础算反，之后就是继续刷题，目前一共刷了三百多道题，距离刷满一千题还有很长的路要学习~
你要请我喝一杯奶茶？
版权声明：自由转载-非商用-保持署名和原文链接。
本站文章均为本人原创，参考文章我都会在文中进行声明，也请您转载时附上署名。
