Algorithm
2022-08-12· 25min
#相关定义
#时间复杂度
- 定义：执行算法所需要的计算工作量，其复杂度反映了程序执行时间随输入规模增长而增长的量级
- 通常用大 O 符号表述，定义为 (n) = O(f(n))
- Ο(1) 常数型 ＜ Ο(log n) 对数型 ＜ Ο(n) 线性型＜ Ο(nlog n) 线性对数型 ＜ Ο(n^2) 平方型 ＜Ο(n^3) 立方型 < ... < O(n^k)k 次方型 < O(2^n) 指数型 < O(n!) 阶乘型
#空间复杂度
- 定义：执行算法所需内存的大小
- O(1): 所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量
function fff() {
return 1 + 1;
}
- O(n): 定义一个数组的空间，数组的长度随着 n 的规模不同，会不一样
function fff(n) {
let arr = [];
for (let i = 0; i < n; i++) {
arr.push(i);
}
return arr;
}
console.log(fff(2)); // [0, 1]
- O(n^2): 定义二维数组的空间
function fff(n) {
let arr = [];
for (let i = 0; i < n; i++) {
arr[i] = [];
for (let j = 0; j < n; j++) {
arr[i][j] = j;
}
}
return arr;
}
console.log(fff(2)); // [[0,1], [0,1]]
#数据结构
#栈（Stack）
- 后入先出（LIFO, Last In First Out）的数据结构
class Stack {
constructor() {
this.items = [];
}
// 入栈
push(i) {
this.items.push(i);
}
// 出栈
pop() {
return this.items.pop();
}
// 查看栈顶元素
peek() {
return this.items[this.items.length - 1];
}
// 获取栈的长度
size() {
return this.items.length;
}
//清空栈
clear() {
this.items = [];
}
// 判断栈是否空
isEmpty() {
return this.items.length === 0;
}
}
#队列（Queue）
- 先进先出（FIFO, First In First Out）的数据结构
class Queue {
constructor() {
this.items = [];
}
// 入队
push(i) {
this.items.push(i);
}
// 出队
pop() {
return this.items.shift();
}
// ...
}
#链表（Linked List）
- 一种线性表，但并不会按线性的顺序存储数据，链表中每一个节点中存储了到下一个节点的指针
// 节点
class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}
- 常见结构：单链表、循环链表、双链表、双循环链表
- 单链表（Singly linked list）：每一个节点中存储了到下一个节点的指针，若结点为链表的尾端，则尾节点指针指向null
- 循环链表（Circular linked list）：头节点和尾节点被连接在一起，它的第一个节点之前就是最后一个节点
- 双链表（Doubly linked list）：每个节点存储两个指针，一个指向前一个节点，另一个指向下一个节点
- 双循环链表：头节点的前趋指针指向尾节点，尾节点的后驱指针指向头节点
- 单链表（Singly linked list）：每一个节点中存储了到下一个节点的指针，若结点为链表的尾端，则尾节点指针指向null
#热热身
#509. 斐波那契数
/**
* 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和
*
* 用数列表示为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…，数列中的每一项都被称为斐波那契数
* 用符号Fn表示：F(0)=1，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N）。
*
* @param {number} n
* @return {number}
*
* 复杂度分析
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*
*/
var fib = function (n) {
if (n < 2) return n;
let p = 0;
let q = 0;
let r = 1;
for (let i = 2; i <= n; i++) {
p = q;
q = r;
r = p + q;
}
return r;
};
fib(3); // F(3) = F(2) + F(1) = 1 + 1 = 2
fib(5); // 2 + 3 = 5
// n = 0 1 2 3 4 5 6 7 8
// f(n) = 0 1 1 2 3 5 8 13 21
function fib2(n) {
if (n <= 1) return n;
let fib = [0, 1]; // 保存斐波那契数列的结果
for (let i = 2; i <= n; i++) {
fib[i] = fib[i - 1] + fib[i - 2]; // 计算第 i 个斐波那契数
}
return fib[n];
}
#796. 旋转字符串
function rotateString(s, gloal) {
return s.length && gloal.length && (s + s).includes(gloal);
}
console.log(rotateString("abcde", "cdeab")); // true
console.log(rotateString("abcde", "abced")); // false
#112. 路径总和
/**
* 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。如果存在，返回 true; 否则，返回 false 。
* 叶子节点 是指没有子节点的节点。
*
* * function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*
* 复杂度分析
* 时间复杂度：O(n)，其中 n 为二叉树的节点个数。
* 空间复杂度：O(n)，最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。
*
* @param {TreeNode} root
* @param {number} targetSum
* @return {boolean}
*/
var hasPathSum = function (root, targetSum) {
if (root === null) return false;
targetSum -= root.val;
if (root.left === root.right) return targetSum === 0;
return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
};
#415. 字符串相加
/**
* 给定两个字符串形式的非负整数 num1 和 num2 ，计算它们的和并同样以字符串形式返回。
*
* 时间复杂度：O(max(len1,len2))
* 空间复杂度：O(1)
/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
var addStrings = function (num1, num2) {
let i = num1.length - 1;
let j = num2.length - 1;
let add = 0;
const ans = [];
while (i >= 0 || j >= 0 || add != 0) {
const x = i >= 0 ? num1.charAt(i) - "0" : 0;
const y = j >= 0 ? num2.charAt(j) - "0" : 0;
const result = x + y + add;
ans.push(result % 10);
add = Math.floor(result / 10);
i -= 1;
j -= 1;
}
return ans.reverse().join("");
};
addStrings("110", "22"); // '132'
#5. 最长回文子串
- Ref: 题解
/**
* 给你一个字符串 s，找到 s 中最长的回文子串。
*
* @param {string} s
* @return {string}
*
* 时间复杂度：𝑂(𝑁^2)
*/
var longestPalindrome = function (s) {
if (s.length < 2) return s;
let res = "";
for (let i = 0; i < s.length; i++) {
// 回文子串长度是奇数
helper(i, i);
// 回文子串长度是偶数
helper(i, i + 1);
}
function helper(m, n) {
while (m >= 0 && n < s.length && s[m] == s[n]) {
m--;
n++;
}
// 注意此处 m,n 的值循环完后 是恰好不满足循环条件的时刻
// 此时m到n的距离为 n-m+1，但是 mn 两个边界不能取 所以应该取 m+1 到 n-1 的区间 长度是 n-m-1
if (n - m - 1 > res.length) {
// slice 也要取[ m+1,n-1] 这个区间
res = s.slice(m + 1, n);
}
}
return res;
};
longestPalindrome("dddccee"); // ddd
longestPalindrome("abba"); // abba
- 稀疏数组：数组的元素不是连续有值
function convertToSparseArray(originalArray) {
let sparseArray = [];
const rowCount = originalArray.length;
const colCount = originalArray[0].length;
let nonZeroCount = 0;
for (let i = 0; i < rowCount; i++) {
for (let j = 0; j < colCount; j++) {
if (originalArray[i][j] !== 0) {
nonZeroCount++;
sparseArray.push([i, j, originalArray[i][j]]);
}
}
}
sparseArray = [[rowCount, colCount, nonZeroCount], ...sparseArray];
return sparseArray;
}
var originalArray = [
[1, 0, 0, 0, 0],
[0, 1, 0, 0, 0],
];
var sparseArray = convertToSparseArray(originalArray);
console.log(sparseArray);
[
[2, 5, 2], // row: 2, col: 5, nonZeroCount: 2
[0, 0, 1],
[1, 1, 1],
];
- Array 转 TreeNode
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
function arrayToTreeNode(arr) {
if (!arr.length) return null;
const root = new TreeNode(arr[0]);
const queue = [root];
let i = 1;
while (i < arr.length) {
const current = queue.shift();
if (arr[i] !== null) {
current.left = new TreeNode(arr[i]);
queue.push(current.left);
}
i++;
if (i < arr.length && arr[i] !== null) {
current.right = new TreeNode(arr[i]);
queue.push(current.right);
}
i++;
}
return root;
}
const arr = [1, 2, 3];
const treeRoot = arrayToTreeNode(arr);
console.log(treeRoot);
// {
// "val": 1,
// "left": {
// "val": 2,
// "left": null,
// "right": null
// },
// "right": {
// "val": 3,
// "left": null,
// "right": null
// }
// }
#稀疏数组搜索
/**
* 稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。
*
* @param {string[]} words
* @param {string} s
* @return {number}
*/
var findString = function (words, s) {
// 时间复杂度是 O(n)
// 方式1:
// for (const i in words) if (words[i] === s) return i;
// return -1;
// 方式2:
// return words.indexOf(s)
// 时间复杂度是 O(logn)
// 方式: 二分查找
// 1. 初始左右指针
let left = 0;
let right = words.length - 1;
while (left <= right) {
// 2. 计算中间位置
let mid = Math.floor((left + right) / 2);
// 3. 处理空字符串
if (words[mid] === "") {
let leftMid = mid - 1;
let rightMid = mid + 1;
while (true) {
if (leftMid < left && rightMid > right) {
return -1;
} else if (rightMid <= right && words[rightMid] !== "") {
mid = rightMid; // 找到右侧最近的非空字符串
break;
} else if (leftMid >= left && words[leftMid] !== "") {
mid = leftMid; // 找到左侧最近的非空字符串
break;
}
rightMid++;
leftMid--;
}
}
// 4. 比较中间元素与目标字符串
// (字符串比较会先转成 ascii 码，"ball".charCodeAt())
if (words[mid] === s) {
return mid;
} else if (words[mid] < s) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
};
var words = ["at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""],
s = "ball";
findString(words, s); // 4