算法和数据结构
引言
在面试过程中，通常会有一个电话面试和全天的现场面试，检查编码技能和文化适应性。几乎没有例外的是，决定因素是编码能力。毕竟，工程师们每天都要交付可工作的软件。传统上，使用白板来测试这种能力。与其得到正确的答案，不如清晰地表达思考过程。在代码和生活中，正确的答案并不总是清晰的，但是好的推理通常已经足够了。有效推理的能力表明了学习、适应和发展的潜力。最好的工程师总是在成长，最好的公司总是在创新。
算法挑战是有效的，因为有多种解决方法。这为决策的制定和决策的计算打开了可能性。当解决算法问题时，我们应该挑战自己从多个角度来看问题定义，然后权衡不同方法的利弊。通过足够的实践，我们甚至可能看到一个普遍的真理：没有“完美”的解决方案。
真正掌握算法是要理解它们与数据结构的关系。数据结构和算法就像阴阳、玻璃和水一样密不可分。没有玻璃，水就不能被包容。没有数据结构，我们没有对象来应用逻辑。没有水，玻璃是空的，没有营养。没有算法，对象就不能被转换或“消耗”。
入门
应用到代码中，算法只是将某个输入数据结构转换为某个输出数据结构的function。内部的logic决定了转换。首先，输入和输出应该被明确地定义，最好作为unit tests。这需要充分理解手头的问题，这个问题的全面分析是不可低估的，因为对问题的彻底分析可以自然地提出解决方案，而不需要编写任何代码。
“问题明确地陈述是问题的一半得到解决。”- 美国发明家查尔斯·凯特林
一旦完全掌握了问题领域，就可以开始解决方案空间的头脑风暴。需要什么变量？多少循环和什么样的循环？有没有一些聪明的内置方法可以帮助？要考虑的边缘情况？复杂或重复的逻辑可能难以阅读和理解。是否可以提取或抽象辅助函数？算法通常需要可扩展性。随着输入大小的增加，函数的性能将如何？应该有某种缓存机制吗？通常，为了获得性能提升（时间），需要牺牲内存优化（空间）。
“为了使问题更具体，画出图表！”
当解决方案的高级结构开始出现时，就可以开始伪代码。为了真正打动面试官，可以提前寻找重构和重用代码的机会。有时，类似行为的函数可以组合成一个更通用的函数，该函数接受一个额外的参数。其他时候，通过currying去参数化更好。保持函数的纯净以便于测试和维护也显示了远见。换句话说，在计算你的决策时，考虑架构和设计模式。
“如果有任何不清楚的地方，请询问澄清！”
大O表示法
为了帮助计算运行时复杂度，我们将算法的可扩展性通过将其输入大小向无限大推导来近似，然后计算所需的操作数量。在最坏情况下的运行时间上限，我们可以删除系数和加法项，仅保留主导函数的因子。因此，几个类别就可以描述几乎任何算法的可扩展性。
最佳的算法在常数时间和空间中缩放。这意味着它完全不关心其输入的增长。其次是对数时间或空间，然后是线性、线性对数、二次和指数。最坏的是阶乘时间或空间。在大O表示法中：- 常数: O(1)
- 对数: O(log n)
- 线性: O(n)
- 线性对数: O(n log n)
- 平方: O(n²)
- 指数: O(2^n)
- 阶乘: O(n!)
在考虑算法的时间和空间复杂度之间的权衡时，Big-O 渐近分析 是一个不可或缺的工具。但是，在实际实践中，Big O忽略了常数因子，而实际上这些因子可能很重要。此外，优化时间和空间可能会增加实现时间或对代码可读性产生负面影响。在设计算法的结构和逻辑时，对于什么是真正可以忽略不计的直觉感觉同样重要。
数组
通常，最干净的算法利用了语言中固有的_标准_对象，可以说在计算机科学中最重要的对象是 Arrays。在 JavaScript 中，没有其他对象比数组更具有实用性方法。值得记忆的数组方法有：sort、reverse、slice 和 splice。数组元素从第0个索引开始插入。这意味着最后一个元素位于 array.length — 1。数组最适合于索引（pushing），但可能在插入、删除（不是弹出）和搜索方面表现糟糕。在 JavaScript 中，数组可以动态增长。
在 Big O 中：
- 索引: O(1)
- 插入: O(n)
- 删除: O(n)
- 暴力搜索: O(n)
- 优化搜索: O(log n)
这些 Array 方法的代码示例：
值得一读的是关于 Arrays 的完整文档：
类似于数组的是 Sets 和 Maps。在 set 中，项保证是唯一的。在 map 中，项由字典式关系中的键和值组成。当然，Objects（和它们的文字）也可以用于存储键值对，但键必须是 strings。
迭代
与 Arrays 密切相关的是使用循环迭代它们。在 JavaScript 中，我们可以使用五种不同的控制结构进行迭代。最可定制的是 for 循环，我们可以使用它以几乎任何顺序迭代数组索引。如果无法确定迭代次数，我们可以使用 while 和 do while 循环，直到满足某个条件为止。对于任何对象，我们都可以使用 for in 和 for of 循环分别迭代其键和值。要同时获取两个值，我们可以通过其 entries() 循环。我们也可以使用 break 语句随时中断循环，或使用 continue 语句跳到下一个迭代。对于最大控制，迭代通过 generator 函数是最好的。
迭代所有项目的本机数组方法是：indexOf、lastIndexOf、includes、fill 和 join。此外，我们可以为以下方法提供 callback 函数：findIndex、find、filter、forEach、map、some、every 和 reduce。
这些 Array 方法的代码示例：
//html
<div id="mocha"></div>
// js
class Obj {
constructor(obj) {
this.obj = new Object(obj);
}
indexOf(searchElement, fromIndex = 0) {
for (let i = fromIndex; i < this.obj.length; i++) {
if (this.obj[i] === searchElement) return i;
}
return -1;
}
lastIndexOf(searchElement, fromIndex = this.obj.length - 1) {
for (let i = fromIndex; i >= 0; i--) {
if (this.obj[i] === searchElement) return i;
}
return -1;
}
includes(searchElement, fromIndex = 0) {
let i = fromIndex;
while (i < this.obj.length) {
if (this.obj[i++] === searchElement) return true;
}
return false;
}
fill(value, start = 0, end = this.obj.length - 1) {
let i = start;
do this.obj[i++] = value;
while (i <= end);
return this.obj;
}
join(separator = ",") {
let str = "";
let i = 0;
for (const value of this.obj) {
++i;
str += value + (i < this.obj.length ? separator : "");
}
return str;
}
findIndex(callback) {
for (const key in this.obj) {
if (callback(this.obj[key], key)) return key;
}
return null;
}
find(callback) {
for (const key in this.obj) {
if (callback(this.obj[key], key)) return this.obj[key];
}
return undefined;
}
filter(callback) {
const obj = {};
for (const key in this.obj) {
if (callback(this.obj[key], key)) obj[key] = this.obj[key];
}
return obj;
}
forEach(callback) {
for (const key in this.obj) {
this.obj[key] = callback(this.obj[key], key);
}
return this.obj;
}
map(callback) {
const obj = {};
for (const key in this.obj) {
obj[key] = callback(this.obj[key], key);
}
return obj;
}
some(callback) {
for (const key in this.obj) {
if (callback(this.obj[key], key)) return true;
}
return false;
}
every(callback) {
for (const key in this.obj) {
if (callback(this.obj[key], key)) continue;
return false;
}
return true;
}
reduce(callback, initialValue) {
let accumulator = initialValue;
for (const key in this.obj) {
accumulator = callback(accumulator, this.obj[key], key);
}
return accumulator;
}
}
mocha.setup("bdd");
const { assert } = chai;
describe("Arrays", () => {
it("Should implement indexOf", () => {
const arr = new Obj(["a", "b", "c"]);
assert.equal(arr.indexOf("b"), 1);
assert.equal(arr.indexOf("e"), -1);
});
it("Should implement lastIndexOf", () => {
const arr = new Obj(["a", "b", "c"]);
assert.equal(arr.lastIndexOf("a"), 0);
assert.equal(arr.lastIndexOf("e"), -1);
});
it("Should implement includes", () => {
const arr = new Obj(["a", "b", "c"]);
assert.equal(arr.includes("c"), true);
assert.equal(arr.includes("e"), false);
});
it("Should implement fill", () => {
const arr = new Obj(["a", "b", "c"]);
assert.deepEqual(arr.fill("e"), ["e", "e", "e"]);
});
it("Should implement join", () => {
const arr = new Obj(["a", "b", "c"]);
assert.equal(arr.join(", "), "a, b, c");
});
});
describe("Objects", () => {
it("Should implement findIndex", () => {
const obj = new Obj({ a: 1, b: 2 });
assert.equal(obj.findIndex((value, key) => value === 2), "b");
assert.equal(obj.findIndex((value, key) => value === 3), null);
});
it("Should implement find", () => {
const obj = new Obj({ a: 1, b: 2 });
assert.equal(obj.find((value, key) => value === 2), 2);
assert.equal(obj.find((value, key) => value === 3), undefined);
});
it("Should implement filter", () => {
const obj = new Obj({ a: 1, b: 2 });
assert.deepEqual(obj.filter((value, key) => value > 0), { a: 1, b: 2 });
assert.deepEqual(obj.filter((value, key) => value > 2), {});
});
it("Should implement forEach", () => {
const obj = new Obj({ a: 1, b: 2 });
assert.deepEqual(obj.forEach((value, key) => value * 2), { a: 2, b: 4 });
});
it("Should implement map", () => {
const obj = new Obj({ a: 1, b: 2 });
assert.deepEqual(obj.map((value, key) => value * 3), { a: 3, b: 6 });
});
it("Should implement some", () => {
const obj = new Obj({ a: 1, b: 2 });
assert.equal(obj.some((value, key) => value > 1), true);
assert.equal(obj.some((value, key) => value > 2), false);
});
it("Should implement every", () => {
const obj = new Obj({ a: 1, b: 2 });
assert.equal(obj.every((value, key) => value > 0), true);
assert.equal(obj.every((value, key) => value > 1), false);
});
it("Should implement reduce", () => {
const obj1 = new Obj({ a: 1, b: 2 });
assert.equal(obj1.reduce((sum, value, key) => sum + value, 0), 3);
const obj2 = new Obj({ a1: { b1: 1, b2: 2 }, a2: { b3: 3, b4: 4 } });
assert.deepEqual(
obj2.reduce((accumulator, value, key) => ({ ...accumulator, ...value }), {}),
{ b1: 1, b2: 2, b3: 3, b4: 4 }
);
});
xit("Should flatten objects", () => {
const flatten = obj => {
if (obj instanceof Obj) {
return obj.reduce(
(accumulator, value, key) =>
Object.assign({}, accumulator, flatten(new Obj(value))),
{}
);
}
return obj;
};
assert.deepEqual(
flatten(
new Obj({
a1: { b1: 1, b2: { c1: 1, c2: 2 } },
a2: { b3: 3, b4: { c3: 3, c4: 4 } }
})
),
{ b1: 1, c1: 1, c2: 2, b3: 3, c3: 3, c4: 4 }
);
});
});
mocha.run();
递归
在一篇开创性的论文中，Church-Turing Thesis 证明了任何迭代函数都可以用递归函数重现，反之亦然。有时，递归方法更清晰、更明确、更优雅。例如，这个迭代的 factorial 函数:
const factorial = number => {
let product = 1;
for (let i = 2; i <= number; i++) {
product *= i;
}
return product;
};
表达为 recursive 函数，只需要_一行_代码!
const factorial = number => number < 2 ? 1 : number * factorial(number - 1);
所有递归函数都共享一个_共同模式_。它们是由创建一个调用自身的递归部分和一个不调用自身的基本情况组成的。每当一个 function 调用它自身时，它就会将一个新的 execution context 推到 execution stack 上。这将继续，直到达到基本情况，然后堆栈解开，上下文一个接一个地弹出。因此，对递归的草率依赖可能会导致可怕的 stack overflow 运行时错误。
在实时代码中的 factorial 函数：
//html
<div id="mocha"></div>
//js
const factorial = number => number < 2 ? 1 : number * factorial(number - 1);
const factorialize = number => {
let product = 1;
for (let i = 2; i <= number; i++) {
product *= i;
}
return product;
};
mocha.setup("bdd");
const { assert } = chai;
describe("Factorial", () => {
it("Should implement factorial", () => {
assert.equal(factorial(0), 1);
assert.equal(factorial(1), 1);
assert.equal(factorial(2), 2);
assert.equal(factorial(3), 6);
assert.equal(factorial(4), 24);
assert.equal(factorial(5), factorialize(5));
});
});
mocha.run();
热门算法问题
在这一部分中，我们将按照难度的顺序讨论 22 个常见的算法问题。我们还将讨论备选方法及其权衡和运行时间复杂度。通常，最优雅的解决方案利用了一个特殊的“技巧”或关键洞察力。有了这个想法，让我们开始吧！
1. 字符串反转
给定一个字符字符串作为_输入_，编写一个function，将其带有_反向字符_的返回。
describe("String Reversal", () => {
it("Should reverse string", () => {
assert.equal(reverse("Hello World!"), "!dlroW olleH");
});
});
分析：
如果我们知道“技巧”，解决方案就是微不足道的。这个技巧是要意识到我们可以简单地使用内置的reverse方法来处理一个_数组。_首先，我们使用 split 方法在_字符串_上生成一个字符数组，然后我们可以应用 reverse 方法，然后使用 join 方法将字符重新组合成一个_字符串。这个解决方案可以在一行代码中编写！虽然不太优雅，但该问题也可以使用最新的语法和助手方法解决。通过新的 for of 循环迭代任何字符串的每个字符，我们可以展示我们对最新语法的熟悉。或者，我们还可以使用数组的 reduce 方法，消除了保留临时变量的需要。给定一个字符字符串，需要访问每个字符一次。虽然这个过程会多次发生，但是时间复杂度规范为线性。由于没有保留单独的内部数据结构，因此空间复杂度为常量。
代码：
const reverse = string =>
string
.split("")
.reverse()
.join("");
const _reverse = string => {
let result = "";
for (let character of string) result = character + result;
return result;
};
const __reverse = string =>
string.split("").reduce((result, character) => character + result);
mocha.setup("bdd");
const { assert } = chai;
describe("String Reversal", () => {
it("Should reverse string", () => {
assert.equal(reverse("Hello World!"), "!dlroW olleH");
assert.equal(_reverse("Hello World!"), "!dlroW olleH");
assert.equal(__reverse("Hello World!"), "!dlroW olleH");
});
});
mocha.run();
2. Palindrome
回文是一个正反读都相同的单词或短语。编写一个函数来检查这一点。
describe("Palindrome", () => {
it("Should return true", () => {
assert.equal(isPalindrome("Cigar? Toss it in a can. It is so tragic"), true);
}); it("Should return false", () => {
assert.equal(isPalindrome("sit ad est love"), false);
});
});
分析：
关键的洞察力在于我们可以建立在从前一个问题中学到的基础上。但是，我们需要返回一个布尔值。这就像是针对原始字符串返回三重等式检查一样简单。我们也可以使用数组上的新的every方法，检查第一个和最后一个字符是否顺序匹配并向中心靠拢。但是，这将检查比必要多两次。与前一个问题类似，两者的运行时复杂度的时间和空间都是相同的。
如果我们想扩展我们的功能来测试整个短语怎么办？我们可以创建一个帮助函数，该函数使用正则表达式和字符串上的replace方法仅保留字母。如果不允许正则表达式，则可以创建一个可接受字符的数组用作过滤器。
代码：
const isPalindrome = string => {
const validCharacters = "abcdefghijklmnopqrstuvwxyz".split("");
const stringCharacters = string
.toLowerCase()
.split("")
.reduce(
(characters, character) =>
validCharacters.indexOf(character) > -1
? characters.concat(character)
: characters,
[]
);
return stringCharacters.join("") === stringCharacters.reverse().join("");
};
const _isPalindrome = string =>
string
.split("")
.every((character, index) => character === string[string.length - 1 - index]);
const __isPalindrome = string => {
const cleaned = string.replace(/\W/g, "").toLowerCase();
return (
cleaned ===
cleaned
.split("")
.reverse()
.join("")
);
};
mocha.setup("bdd");
const { assert } = chai;
describe("Palindrome", () => {
it("Should return true", () => {
assert.equal(isPalindrome("Cigar? Toss it in a can. It is so tragic"), true);
assert.equal(
__isPalindrome("Cigar? Toss it in a can. It is so tragic"),
true
);
});
it("Should return false", () => {
assert.equal(isPalindrome("sit ad est love"), false);
assert.equal(_isPalindrome("sit ad est love"), false);
});
});
mocha.run();
3. 整数翻转
给定一个整数，颠倒数字的顺序。
describe("Integer Reversal", () => {
it("Should reverse integer", () => {
assert.equal(reverse(1234), 4321);
assert.equal(reverse(-1200), -21);
});
});
分析：
聪明的技巧在于首先使用内置的toString方法将整数转换为字符串。然后，我们可以简单地重用String Reversal算法的逻辑。数字翻转后，我们可以使用全局的parseInt函数将字符串转换回整数，并使用Math.sign来保留极性。这种方法可以简化为一行代码！
由于我们重用String Reversal的逻辑，因此此算法的运行时复杂度也与空间复杂度相同。
代码：
const reverse = integer =>
parseInt(
integer
.toString()
.split("")
.reverse()
.join("")
) * Math.sign(integer);
mocha.setup("bdd");
const { assert } = chai;
describe("Integer Reversal", () => {
it("Should reverse integer", () => {
assert.equal(reverse(1234), 4321);
assert.equal(reverse(-1200), -21);
});
});
mocha.run();
4. Fizz Buzz
给定一个数字作为输入，从1打印到该数字的每个整数。但是，当整数可被2整除时，请打印“Fizz”；当它可被3整除时，请打印“Buzz”；当它既可被2又可被3整除时，请打印“Fizz Buzz”。
describe("Fizz Buzz", () => {
beforeEach(() => (output = fizzBuzz(30))); it("Should output number", () => {
assert.equal(output[0], 1);
}); it("Should output Fizz", () => {
assert.equal(output[1], "Fizz");
}); it("Should output Buzz", () => {
assert.equal(output[2], "Buzz");
}); it("Should output Fizz Buzz", () => {
assert.equal(output[5], "Fizz Buzz");
});
});
分析 ：
当我们意识到模运算符可以用于检查可被整除性时，这个经典的算法挑战变得微不足道。模数除以两个数字并返回余数。因此，我们可以简单地循环遍历每个整数，并检查0的余数。为了展示我们的数学能力，我们可以考虑到当一个数字被a和b整除时，它也被它们的最小公倍数整除。
通常情况下，运行时复杂度是相同的，因为每个整数都被访问和检查，而不需要保留内部状态。
代码：
onst fizzBuzz = number => {
let output = [];
for (let i = 1; i <= number; i++) {
if (i % 6 === 0) output.push("Fizz Buzz");
else if (i % 2 === 0) output.push("Fizz");
else if (i % 3 === 0) output.push("Buzz");
else output.push(i);
}
return output;
};
mocha.setup("bdd");
const { assert } = chai;
let output;
describe("Fizz Buzz", () => {
beforeEach(() => (output = fizzBuzz(30)));
it("Should output number", () => {
assert.equal(output[0], 1);
});
it("Should output Fizz", () => {
assert.equal(output[1], "Fizz");
});
it("Should output Buzz", () => {
assert.equal(output[2], "Buzz");
});
it("Should output Fizz Buzz", () => {
assert.equal(output[5], "Fizz Buzz");
});
});
mocha.run();
5. 最大字符
给定一个字符字符串，返回出现最多的字符。
describe("Max Character", () => {
it("Should return max character", () => {
assert.equal(max("Hello World!"), "l");
});
});
分析：
诀窍是创建一个表，该表统计循环遍历字符串时每个字符的出现次数。可以使用对象字面量创建此表，其中字符是键，计数器是值。然后，我们可以通过保留其键和值的临时变量来遍历表，以找到具有最大计数器的字符。
虽然我们使用了两个分别遍历两个不同输入（字符字符串和字符映射）的循环，但时间复杂度仍然是线性的。它可以从字符字符串推导出来，但是最终，字符映射的大小将达到极限，因为任何语言中只有有限数量的字符。出于同样的原因，尽管保留了内部状态，输入字符串增长，临时原语也可以忽略不计。
代码：
const max = string => {
const characters = {};
for (let character of string)
characters[character] = characters[character] + 1 || 1;
let maxCount = 0;
let maxCharacter = null;
for (let character in characters) {
if (characters[character] > maxCount) {
maxCount = characters[character];
maxCharacter = character;
}
}
return maxCharacter;
};
mocha.setup("bdd");
const { assert } = chai;
describe("Max Character", () => {
it("Should return max character", () => {
assert.equal(max("Hello World!"), "l");
});
});
mocha.run();
6. Anagrams
变位词是包含相同数量字符的单词或短语。创建一个检查此内容的函数。
describe("Anagrams", () => {
it("Should implement anagrams", () => {
assert.equal(anagrams("hello world", "world hello"), true);
assert.equal(anagrams("hellow world", "hello there"), false);
assert.equal(anagrams("hellow world", "hello there!"), false);
});
});
分析：
一个显而易见的方法是创建一个字符映射，该映射记录每个输入字符串的字符数量。然后，我们可以比较地图以查看它们是否相同。创建字符映射的逻辑可以提取为帮助函数，以便更轻松地重用。为了详细说明，我们应该首先从输入字符串中删除所有非字母字符，然后将其余部分全部小写化。
正如我们所看到的，字符映射具有线性时间复杂度和恒定空间复杂度。要更加准确，此方法的时间为O（n + m），因为检查了两个不同的字符串。
一种更优雅的方法是意识到我们可以简单地对输入字符串进行排序，然后检查它们是否相等！但是，缺点是排序通常需要线性对数时间。
代码：
const charCount = string => {
const table = {};
for (let char of string.replace(/\W/g, "").toLowerCase())
table[char] = table[char] + 1 || 1;
return table;
};
const anagrams = (stringA, stringB) => {
const charCountA = charCount(stringA);
const charCountB = charCount(stringB);
if (Object.keys(charCountA).length !== Object.keys(charCountB).length)
return false;
for (let char in charCountA)
if (charCountA[char] !== charCountB[char]) return false;
return true;
};
const _sort = string => string.replace(/\W/g, "").toLowerCase().split("").sort().join("");
const _anagrams = (stringA, stringB) => _sort(stringA) === _sort(stringB);
mocha.setup("bdd");
const { assert } = chai;
describe("Anagrams", () => {
it("Should implement anagrams", () => {
assert.equal(anagrams("hello world", "world hello"), true);
assert.equal(anagrams("hellow world", "hello there"), false);
assert.equal(anagrams("hellow world", "hello there!"), false);
assert.equal(_anagrams("hello world", "world hello"), true);
assert.equal(_anagrams("hellow world", "hello there"), false);
});
});
mocha.run();
7. 元音字母
给定一个单词或短语的字符串，请计算元音字母的数量。
describe("Vowels", () => {
it("Should count vowels", () => {
assert.equal(vowels("hello world"), 3);
});
});
分析：
最简单的解决方案是利用正则表达式提取所有元音字母，然后计算它们。如果不允许正则表达式，则可以简单地循环遍历每个字符并将其与元音字母集合进行比较。字符串应首先转换为小写。
这两种方法都具有线性时间复杂度和恒定空间复杂度，因为每个字符都需要被检查，临时原语可以忽略不计。
代码：
const vowels = string => {
let count = 0;
const choices = "aeiou"; // or ['a', 'e', 'i', 'o', 'u']
for (let character of string.toLowerCase())
if (choices.includes(character)) count++;
return count;
};
const _vowels = string => {
matches = string.match(/[aeiou]/gi);
return matches ? matches.length : 0;
}
mocha.setup("bdd");
const { assert } = chai;
describe("Vowels", () => {
it("Should count vowels", () => {
assert.equal(vowels("hello world"), 3);
assert.equal(_vowels("hello world"), 3);
});
});
mocha.run();
8. 数组分块
给定一个数组和一个大小，将数组项拆分为给定大小的数组列表。
describe("Array Chunking", () => {
it("Should implement array chunking", () => {
assert.deepEqual(chunk([1, 2, 3, 4], 2), [[1, 2], [3, 4]]);
assert.deepEqual(chunk([1, 2, 3, 4], 3), [[1, 2, 3], [4]]);
assert.deepEqual(chunk([1, 2, 3, 4], 5), [[1, 2, 3, 4]]);
});
});
分析：
一个显而易见的解决方案是保留对最后一个“块”的引用，并在循环遍历数组项时检查其大小。更优雅的解决方案是使用内置的slice方法。这样，不需要引用，生成了更清晰的代码。这可以通过以给定大小的步长增加的方式使用while循环或for循环来实现。
这些算法的时间复杂度都是线性的，因为需要访问每个数组项。它们还具有线性空间复杂度，因为保留了“块”的内部数组，其大小与输入数组成比例增长。
代码：
const chunk = (array, size) => {
const chunks = [];
for (let item of array) {
const lastChunk = chunks[chunks.length - 1];
if (!lastChunk || lastChunk.length === size) chunks.push([item]);
else lastChunk.push(item);
}
return chunks;
};
const _chunk = (array, size) => {
const chunks = [];
let index = 0;
while (index < array.length) {
chunks.push(array.slice(index, index + size));
index += size;
}
return chunks;
};
const __chunk = (array, size) => {
const chunks = [];
for (let i = 0; i < array.length; i += size) {
chunks.push(array.slice(i, i + size));
}
return chunks;
};
mocha.setup("bdd");
const { assert } = chai;
describe("Array Chunking", () => {
it("Should implement array chunking", () => {
assert.deepEqual(chunk([1, 2, 3, 4], 2), [[1, 2], [3, 4]]);
assert.deepEqual(chunk([1, 2, 3, 4], 3), [[1, 2, 3], [4]]);
assert.deepEqual(chunk([1, 2, 3, 4], 5), [[1, 2, 3, 4]]);
assert.deepEqual(_chunk([1, 2, 3, 4], 2), [[1, 2], [3, 4]]);
assert.deepEqual(_chunk([1, 2, 3, 4], 3), [[1, 2, 3], [4]]);
assert.deepEqual(_chunk([1, 2, 3, 4], 5), [[1, 2, 3, 4]]);
assert.deepEqual(__chunk([1, 2, 3, 4], 2), [[1, 2], [3, 4]]);
assert.deepEqual(__chunk([1, 2, 3, 4], 3), [[1, 2, 3], [4]]);
assert.deepEqual(__chunk([1, 2, 3, 4], 5), [[1, 2, 3, 4]]);
});
});
mocha.run();
9. 数组反转
给定一个包含元素的 array，将其顺序 反转。
describe("Reverse Arrays", () => {
it("Should reverse arrays", () => {
assert.deepEqual(reverseArray([1, 2, 3, 4]), [4, 3, 2, 1]);
assert.deepEqual(reverseArray([1, 2, 3, 4, 5]), [5, 4, 3, 2, 1]);
});
});
分析：
当然，一个显而易见的解决方案是使用内置的 reverse 方法。但这太简单了！如果不允许使用内置方法，我们可以简单地遍历数组的一半并使用 交换 将开头与结尾交换。这意味着我们需要临时存储 一个 元素在内存中。为了避免这种需要，我们可以使用带有数组匹配的 解构赋值。
虽然只有输入数组的一半被访问，但时间复杂度仍然是 线性 的，因为大 O 渐进地忽略系数。
代码：
const reverseArray = array => {
for (let i = 0; i < array.length / 2; i++) {
const temp = array[i];
array[i] = array[array.length - 1 - i];
array[array.length - 1 - i] = temp;
}
return array;
};
const _reverseArray = array => {
for (let i = 0; i < array.length / 2; i++) {
[array[i], array[array.length - 1 - i]] = [
array[array.length - 1 - i],
array[i]
];
}
return array;
};
mocha.setup("bdd");
const { assert } = chai;
describe("Reverse Arrays", () => {
it("Should reverse arrays", () => {
assert.deepEqual(reverseArray([1, 2, 3, 4]), [4, 3, 2, 1]);
assert.deepEqual(reverseArray([1, 2, 3, 4, 5]), [5, 4, 3, 2, 1]);
assert.deepEqual(_reverseArray([1, 2, 3, 4, 5]), [5, 4, 3, 2, 1]);
});
});
mocha.run();
10. 单词反转
给定一个 phrase，将每个单词的字符顺序 反转。
describe("Reverse Words", () => {
it("Should reverse words", () => {
assert.equal(reverseWords("I love JavaScript!"), "I evol !tpircSavaJ");
});
});
分析：
我们可以使用 split 方法创建一个单词的数组。然后对于每个单词，我们可以重复使用 反转字符串 中的逻辑来反转其字符。另一种方法是反向循环每个单词，并将结果存储在临时变量中。无论哪种方法，我们都需要临时保存所有反转的单词，然后在最后将它们连接起来。
由于每个字符都被访问并且所需的临时变量与输入字符串成比例增长，因此时间和空间复杂度均为 线性。 代码：
const reverseWords = string => {
const wordsReversed = [];
string.split(" ").forEach(word => {
let wordReversed = "";
for (let i = word.length - 1; i >= 0; i--) wordReversed += word[i];
wordsReversed.push(wordReversed);
});
return wordsReversed.join(" ");
};
const _reverseWords = string =>
string
.split(" ")
.map(word =>
word
.split("")
.reverse()
.join("")
)
.join(" ");
mocha.setup("bdd");
const { assert } = chai;
describe("Reverse Words", () => {
it("Should reverse words", () => {
assert.equal(reverseWords("I love JavaScript!"), "I evol !tpircSavaJ");
assert.equal(_reverseWords("I love JavaScript!"), "I evol !tpircSavaJ");
});
});
mocha.run();
11. 大写首字母
给定一个 phrase，将每个单词的首字母 大写。
describe("Capitalization", () => {
it("Should capitalize phrase", () => {
assert.equal(capitalize("hello world"), "Hello World");
});
});
分析：
一种方法是遍历每个字符，并在前一个字符是 空格 时，应用 toUpperCase 来大写当前字符。因为在 JavaScript 中 字符串文字 是 不可变 的，所以我们需要使用适当的大写重建输入字符串。这种方法要求我们始终大写第一个字符。也许更清晰的方法是将输入字符串 split 成一个 单词数组。然后，我们可以循环遍历这个数组并将第一个字符大写，然后再将单词连接在一起。由于不可变性的原因，我们需要在内存中保留一个包含适当大写的临时数组。
两种方法的时间复杂度都为 线性，因为每个字符至少被访问一次。它们的空间复杂度也是 线性，因为需要保留一个随着输入字符串成比例增长的临时变量。
代码：
const capitalize = phrase => {
const words = [];
for (let word of phrase.split(" "))
words.push(word[0].toUpperCase() + word.slice(1));
return words.join(" ");
};
const _capitalize = phrase => {
let title = phrase[0].toUpperCase();
for (let i = 1; i < phrase.length; i++)
title += phrase[i - 1] === " " ? phrase[i].toUpperCase() : phrase[i];
return title;
};
mocha.setup("bdd");
const { assert } = chai;
describe("Capitalization", () => {
it("Should capitalize phrase", () => {
assert.equal(capitalize("hello world"), "Hello World");
assert.equal(_capitalize("hello world"), "Hello World");
});
});
mocha.run();
12. 凯撒密码
给定一个 phrase，通过将每个字符上下移动给定的 整数 来 替换 它。如果必要，移位应该围绕字母表的开头或结尾进行。
describe("Caesar Cipher", () => {
it("Should shift to the right", () => {
assert.equal(caesarCipher("I love JavaScript!", 100), "E hkra FwrwOynelp!");
});it("Should shift to the left", () => {
assert.equal(caesarCipher("I love JavaScript!", -100), "M pszi NezeWgvmtx!");
});
});
分析：
首先，我们需要创建一个_字母表字符_ 的 array，以便计算移动字符的结果。这意味着在迭代其字符之前需要将输入字符串转换为小写。我们应该使用常规的 for 循环来轻松地跟踪当前索引。我们需要构建一个 new string，其中包含每次迭代的移位字符。当我们遇到非字母字符时，应立即将其附加到我们的解决方案字符串的末尾，并使用 continue 语句跳到下一次迭代。关键见解是意识到我们可以使用 模运算符 来模仿移动超过 26 时回到字母表数组开头或结尾的行为。最后，在将结果附加到我们的解决方案之前，我们需要检查原始字符串中的大写字母。
由于需要访问输入字符串中的每个字符并从中创建一个新字符串，因此该算法具有 线性 的时间和空间复杂度。 代码：
const caesarCipher = (string, number) => {
const alphabet = "abcdefghijklmnopqrstuvwxyz".split("");
const input = string.toLowerCase();
let output = "";
for (let i = 0; i < input.length; i++) {
const letter = input[i];
if (alphabet.indexOf(letter) === -1) {
output += letter;
continue;
}
let index = alphabet.indexOf(letter) + number % 26;
if (index > 25) index -= 26;
if (index < 0) index += 26;
output +=
string[i] === string[i].toUpperCase()
? alphabet[index].toUpperCase()
: alphabet[index];
}
return output;
};
function _caesarCipher(str, n) {
let result = Array(str.length);
for (let i = 0; i < str.length; i++) {
let code = str.charCodeAt(i);
let lower = "a".charCodeAt(0);
if (code >= lower && code < lower + 26)
code = (code - lower + n) % 26 + lower;
let upper = "A".charCodeAt(0);
if (code >= upper && code < upper + 26)
code = (code - upper + n) % 26 + upper;
result[i] = String.fromCharCode(code);
}
return result.join("");
}
mocha.setup("bdd");
const { assert } = chai;
describe("Caesar Cipher", () => {
it("Should shift to the right", () => {
assert.equal(caesarCipher("I love JavaScript!", 100), "E hkra FwrwOynelp!");
assert.equal(_caesarCipher("I love JavaScript!", 100), "E hkra FwrwOynelp!");
});
it("Should shift to the left", () => {
assert.equal(caesarCipher("I love JavaScript!", -100), "M pszi NezeWgvmtx!");
// assert.equal(_caesarCipher("I love JavaScript!", -100), "M pszi NezeWgvmtx!");
});
});
mocha.run();
13. 赎金信
给定一个 magazine of words 和一个 ransom note，确定是否可以从 magazine words 中 “剪切” 并创建 ransom note。
const magazine =
"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum";describe("Ransom Note", () => {
it("Should return true", () => {
assert.equal(ransomNote("sit ad est sint", magazine), true);
});it("Should return false", () => {
assert.equal(ransomNote("sit ad est love", magazine), false);
});it("Should return true", () => {
assert.equal(ransomNote("sit ad est sint in in", magazine), true);
});it("Should return false", () => {
assert.equal(ransomNote("sit ad est sint in in in in", magazine), false);
});
});
分析：
一个显而易见的解决方案是将杂志词和赎金词分割为单独的单词 数组，然后检查每个赎金词是否与每个杂志词相匹配。然而，这种嵌套导致 二次 时间复杂度，即 O(n * m)，这不适用于大型输入。如果我们首先创建一个杂志单词的表格，然后检查每个赎金单词是否与此表格匹配，我们可以实现 线性 时间。这是因为 map 对象 中的表格查找在 常量 时间内发生。但是，我们将需要牺牲空间复杂度以在内存中保留映射对象。
在代码中，这意味着我们创建每个杂志单词的计数，然后检查此“哈希表”是否包含正确数量的赎金单词。
代码 :
const ransomNote = (note, magazine) => {
const magazineWords = magazine.split(" ");
const magazineHash = {};
magazineWords.forEach(word => {
if (!magazineHash[word]) magazineHash[word] = 0;
magazineHash[word]++;
});
const noteWords = note.split(" ");
let possible = true;
noteWords.forEach(word => {
if (magazineHash[word]) {
magazineHash[word]--;
if (magazineHash[word] < 0) possible = false;
} else possible = false;
});
return possible;
};
mocha.setup("bdd");
const { assert } = chai;
const magazine =
"Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum";
describe("Ransom Note", () => {
it("Should return true", () => {
assert.equal(ransomNote("sit ad est sint", magazine), true);
});
it("Should return false", () => {
assert.equal(ransomNote("sit ad est love", magazine), false);
});
it("Should return true", () => {
assert.equal(ransomNote("sit ad est sint in in", magazine), true);
});
it("Should return false", () => {
assert.equal(ransomNote("sit ad est sint in in in in", magazine), false);
});
});
mocha.run();
14. 均值、中位数和众数
给定一个数字的 array，计算 均值、中位数 和 众数。
const stat1 = new Stats([1, 2, 3, 4, 4, 5, 5]);
const stat2 = new Stats([1, 1, 2, 2, 3, 3, 4, 4]);describe("Mean", () => {
it("Should implement mean", () => {
assert.equal(Stats.round(stat1.mean()), 3.43);
assert.equal(Stats.round(stat2.mean()), 2.5);
});
});describe("Median", () => {
it("Should implement median", () => {
assert.equal(stat1.median(), 4);
assert.equal(stat2.median(), 2.5);
});
});describe("Mode", () => {
it("Should implement mode", () => {
assert.deepEqual(stat1.mode(), [4, 5]);
assert.deepEqual(stat2.mode(), []);
});
});
分析：
就难度而言，找到一组数字的 均值 的算法最简单。在统计学上，mean 定义为集合的 总和 除以其 大小。因此，我们可以简单地使用数组的 reduce 方法来计算其总和，然后将其除以其 length。该算法的运行时复杂度为 线性 时间和 常数 空间，因为需要添加每个数字，而不需要内部存储器。
找到一组数字的 中位数 的算法的难度适中。首先，我们需要对数组进行排序，但如果其大小为偶数，则需要额外的逻辑来处理两个中间数字。在这些情况下，我们将需要返回这两个数字的 平均值。该算法具有 线性对数 时间复杂度，因为排序和 线性 空间复杂度需要内部存储器来保存排序后的数组。
找到一组数字的 众数 的算法是最具挑战性的。由于 mode 定义为出现最多的数字或数字，我们将需要维护一个_频率表格_。更进一步，如果每个值出现相同的次数，则没有模式。在代码中，这意味着我们需要创建一个 哈希映射，其中记录每个唯一数字的频率，然后循环遍历它以收集最大数字或数字，或者没有。由于需要计算每个数字以创建哈希表，而该哈希表存储在内存中，因此该算法具有 线性 时间和空间复杂度。
15. 两数之和
给定一个数字的 array，返回所有加起来得到给定 sum 的 所有对数。数字可以使用多次。
describe("Two Sum", () => {
it("Should implement two sum", () => {
assert.deepEqual(twoSum([1, 2, 2, 3, 4], 4), [[2, 2], [3, 1]]);
});
});
分析：
一个显而易见的解决方案是创建_嵌套循环_，检查同一数组中的每个数字是否与其他数字相加。加起来得到给定的总和可以作为对推入 solution array。然而，这种嵌套导致_二次_ 时间复杂度，不适用于大型输入。
一个聪明的技巧是在迭代输入数组时维护一个包含每个数字“对应项”的数组，同时检查每个数字的对应项的存在。通过维护这样的数组，我们牺牲了空间效率，以获得线性时间复杂度。
代码：
const twoSum = (array, sum) => {
const pairs = [];
const store = [];
for (let part1 of array) {
const part2 = sum - part1;
if (store.indexOf(part2) !== -1) pairs.push([part1, part2]);
store.push(part1);
}
return pairs;
};
mocha.setup("bdd");
const { assert } = chai;
describe("Two Sum", () => {
it("Should implement two sum", () => {
assert.deepEqual(twoSum([1, 2, 2, 3, 4], 4), [[2, 2], [3, 1]]);
});
});
mocha.run();
16. 最大利润
给定一个股票价格的数组，找到产生最大利润的最小购买价格和最大卖出价格。
describe("Max Profit", () => {
it("Should return minimum buy price and maximum sell price", () => {
assert.deepEqual(maxProfit([1, 2, 3, 4, 5]), [1, 5]);
assert.deepEqual(maxProfit([2, 1, 5, 3, 4]), [1, 5]);
assert.deepEqual(maxProfit([2, 10, 1, 3]), [2, 10]);
assert.deepEqual(maxProfit([2, 1, 2, 11]), [1, 11]);
});
分析：
同样，我们可以创建嵌套循环，检查每个购买价格和卖出价格的所有可能组合，以查看哪个组合产生了最大利润。由于在技术上我们不能在购买之前出售，因此不需要检查每个组合。具体来说，对于给定的购买价格，我们可以忽略卖出价格的所有前面的价格。因此，此算法的时间复杂度优于二次方。
通过更深入的思考，我们可以使用仅一次循环遍历价格数组来解决问题。关键的洞察力是要意识到卖出价格不应小于购买价格；如果是这样，我们应该以更低的价格购买该股票。在代码中，这意味着我们可以简单地持有一个临时布尔值，以指示我们应在下一次迭代中更改购买价格。只需要一个循环，这种优雅的方法具有线性时间和恒定空间复杂度。
代码：
17. 厄拉多塞筛法
对于给定的数字，找到从零到该数字的所有质数。
describe("Sieve of Eratosthenes", () => {
it("Should return all prime numbers", () => {
assert.deepEqual(primes(10), [2, 3, 5, 7]);
});
});
分析：
乍一看，我们可能会尝试循环遍历每个可能的数字，并使用模数运算符检查所有可能的可除性。但是，很容易推断出这种方法非常低效，其时间复杂度比二次方还要差。值得庆幸的是，地理学家_Eratosthenes of Cyrene_，也发明了一种识别质数的高效方法。
在代码中，第一步是创建一个与给定数字一样大的数组，其所有值都初始化为“true”。换句话说，数组索引表示所有可能的质数，一开始全部为“true”。然后，我们创建一个for循环，从2到给定数字的平方根，使用数组键插值将每个数字的乘积指定为false。根据定义，任何整数的乘积都不能是质数，而0和1被忽略，因为它们的可除性不会影响质数性。最后，我们可以简单地过滤掉所有虚假值，以得到所有质数。
通过牺牲空间效率以维护内部“哈希表”，这个埃拉托斯特尼筛法具有比二次方更好的时间复杂度，即O(n * log (log n))。
18. 斐波那契数列
实现一个函数，返回给定索引处的斐波那契数。
describe("Fibonacci", () => {
it("Should implement fibonacci", () => {
assert.equal(fibonacci(1), 1);
assert.equal(fibonacci(2), 1);
assert.equal(fibonacci(3), 2);
assert.equal(fibonacci(6), 8);
assert.equal(fibonacci(10), 55);
});
});
分析：
由于斐波那契数是前两个数的和，最简单的方法是使用递归。斐波那契数列的前两个数是0和1；因此，我们可以利用这个事实来创建我们的基本情况。对于大于2的索引，我们可以调用我们的斐波那契函数来添加前两个数。虽然非常优雅，但这种递归方法非常低效，具有指数时间和线性空间复杂度。因为每个函数调用在调用堆栈上需要指数内存，它会很快崩溃。
虽然不太优雅，但迭代方法更加高效。通过使用循环构建到给定索引的整个斐波那契数列，它实现了线性时间和空间。
19. 记忆化斐波那契数列
实现一个性能良好的递归函数，用于斐波那契数列。
describe("Memoized Fibonacci", () => {
it("Should implement memoized fibonacci", () => {
assert.equal(fibonacci(6), 8);
assert.equal(fibonacci(10), 55);
});
});
分析：
由于斐波那契数列使冗余指数调用本身，因此可以从称为“记忆化”的策略中获益。换句话说，如果我们在调用函数时保留所有输入和输出的缓存，调用次数将减少到线性时间。当然，这意味着我们牺牲了额外的内存。
在代码中，我们可以在函数本身内实现记忆化技术，或者我们可以将其抽象为一个高阶实用程序函数，该函数使用记忆化装饰任何函数。
代码：
20. 楼梯
对于给定数量的步骤，使用哈希和空格打印出“楼梯”。
describe("Steps", () => {
it("Should print steps", () => {
assert.equal(steps(3), "# \n## \n###\n");
assert.equal(_steps(3), "# \n## \n###\n");
});
});
分析：
关键的洞察力是要意识到，随着我们向下移动步骤，哈希数递增，而空格数递减。如果我们有n步，整体尺寸为n乘n。这意味着运行时复杂度对于时间和空间都是二次的。
递归方法也是可行的，只是我们需要传递额外的参数来代替必要的临时变量。
代码：
21. 金字塔
对于给定数量的级别，使用哈希和空格打印出一个“金字塔”。
describe("Pyramid", () => {
it("Should print pyramid", () => {
assert.equal(pyramid(3), " # \n ### \n#####\n");
assert.equal(_pyramid(3), " # \n ### \n#####\n");
});
});
分析：
关键的洞察力是要意识到，具有n个步骤（高度）的金字塔宽度为2 * n - 1。然后，只是从中心开始向外递增哈希数并递减空格数，从而向下移动级别。由于此算法迭代地构建了一个大小为n乘2 * n - 1的金字塔，因此它具有二次运行时复杂度和空间复杂度。
同样，递归方法也是可行的，只是我们需要传递额外的参数来代替必要的临时变量。
22. 矩阵螺旋
创建一个给定大小的“方阵”，其中元素按螺旋顺序排列。
describe("Matrix Spiral", () => {
it("Should implement matrix spiral", () => {
assert.deepEqual(spiral(3), [[1, 2, 3], [8, 9, 4], [7, 6, 5]]);
});
});
分析：
虽然这是一个非常具有挑战性的问题，但技巧在于创建指向当前行和当前列的“临时变量”，两者都在“开始”和“结束”处。这样，我们就可以迭代地递增“起始行”和“起始列”，并递减“结束行”和“结束列”，以一种朝向矩阵中心的螺旋方式。因为这个算法会迭代地构建一个给定大小的_方_矩阵，所以它的时间和空间复杂度都是_二次_的。
数据结构算法
由于数据结构是算法的“基石”，因此值得探索最流行的数据结构。
同样地，对于快速的高级分析，请查看：
队列
给定两个queues作为输入，通过“编织”它们来创建一个_新_队列。
describe("Weaving with Queues", () => {
it("Should weave two queues together", () => {
const one = new Queue();
one.enqueue(1);
one.enqueue(2);
one.enqueue(3); const two = new Queue();
two.enqueue("one");
two.enqueue("two");
two.enqueue("three"); const result = weave(one, two);
assert.equal(result.dequeue(), 1);
assert.equal(result.dequeue(), "one");
assert.equal(result.dequeue(), 2);
assert.equal(result.dequeue(), "two");
assert.equal(result.dequeue(), 3);
assert.equal(result.dequeue(), "three");
assert.equal(result.dequeue(), undefined);
});
分析：
至少，Queue类需要具有enqueue，dequeue和peek方法。然后，我们可以使用while循环来_查看_存在性，如果是真值，我们可以将其_出队_，然后将其_入队_到我们的新queue中。
该算法的时间和空间复杂度均为O(n+m)，因为我们需要遍历两个不同的集合并将它们存储起来。
栈
使用两个_栈_实现一个Queue类。
describe("Queue from Stacks", () => {
it("Should implement queue using two stacks", () => {
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
assert.equal(queue.peek(), 1);
assert.equal(queue.dequeue(), 1);
assert.equal(queue.dequeue(), 2);
assert.equal(queue.dequeue(), 3);
assert.equal(queue.dequeue(), undefined);
});
});
分析：
我们可以从初始化两个栈的_类构造函数_开始。因为在栈中，插入的最后一个记录是删除的第一个记录，我们需要循环到最后一个记录来“出队”或“查看”以模仿队列的行为，其中插入的第一个记录是删除的第一个记录。我们可以通过使用第二个栈_临时_保存来自第一个栈的所有项目，直到我们到达末尾。在“查看”或“出队”之后，我们只需将所有内容移回第一个栈即可。“入队”记录时，我们可以简单地将其推入第一个栈中。
尽管我们使用了两个栈并需要循环两次，但该算法在时间和空间上仍然是渐进_线性_的。
链表
单链表通常具有以下功能：
describe("Linked List", () => {
it("Should implement insertHead", () => {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.head.data, 1);
}); it("Should implement size", () => {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.size(), 1);
}); it("Should implement getHead", () => {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.getHead().data, 1);
}); it("Should implement getTail", () => {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.getTail().data, 1);
}); it("Should implement clear", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.clear();
assert.equal(chain.size(), 0);
}); it("Should implement removeHead", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.removeHead();
assert.equal(chain.size(), 0);
}); it("Should implement removeTail", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.removeTail();
assert.equal(chain.size(), 0);
}); it("Should implement insertTail", () => {
const chain = new LinkedList();
chain.insertTail(1);
assert.equal(chain.getTail().data, 1);
}); it("Should implement getAt", () => {
const chain = new LinkedList();
chain.insertHead(1);
assert.equal(chain.getAt(0).data, 1);
}); it("Should implement removeAt", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.removeAt(0);
assert.equal(chain.size(), 0);
}); it("Should implement insertAt", () => {
const chain = new LinkedList();
chain.insertAt(0, 1);
assert.equal(chain.getAt(0).data, 1);
}); it("Should implement forEach", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.forEach((node, index) => (node.data = node.data + index));
assert.equal(chain.getTail().data, 2);
}); it("Should implement iterator", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
for (let node of chain) node.data = node.data + 1;
assert.equal(chain.getTail().data, 2);
});
});
挑战#1：中点
在不保留计数器的情况下，返回链表的_中间值_。
describe("Midpoint of Linked List", () => {
it("Should return midpoint of linked list", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.insertHead(3);
chain.insertHead(4);
chain.insertHead(5);
assert.equal(midpoint(chain).data, 3);
});
});
分析：
诀窍是遍历列表_两次_，其中之一是_两倍_的速度。当更快的一方到达末尾时，更慢的一方在中间停止！
该算法具有_线性_时间和_常量_空间。
挑战#2：循环
在不保留节点引用的情况下，检查链表是否_循环_。
describe("Circular Linked List", () => {
it("Should check for circular linked list", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.insertHead(3);
chain.head.next.next.next = chain.head;
assert.equal(circular(chain), true);
});
});
分析：
许多链接列表功能的前提是具有_明确_的结束节点。因此，确保它不是循环的至关重要。同样，诀窍是遍历列表两次，其中之一是两倍的速度。如果列表是循环的，最终更快的一方将循环并与较慢的一方重合。我们可以在这里退出循环并返回true。否则，将到达末尾，我们可以返回false。
该算法也具有_线性_时间和_常量_空间。
挑战#3：从尾部
在不保留计数器的情况下，返回距离结尾给定的step处的链表中的_value_。
describe("From Tail of Linked List", () => {
it("Should step from tail of linked list", () => {
const chain = new LinkedList();
chain.insertHead(1);
chain.insertHead(2);
chain.insertHead(3);
chain.insertHead(4);
chain.insertHead(5);
assert.equal(fromTail(chain, 2).data, 3);
});
});
分析：
诀窍与之前类似，我们遍历列表两次。在这种情况下，然而，“更快”的那个从给定的step处开始_前进_。然后，我们以相同的步伐将它们两个都向下走，直到更快的一个到达末尾。此时，较慢的那个正好距离结尾正确的步骤。
该算法也具有_线性_时间和_常量_空间。
树
树通常具有以下功能：
describe("Trees", () => {
it("Should add and remove nodes", () => {
const root = new Node(1);
root.add(2);
assert.equal(root.data, 1);
assert.equal(root.children[0].data, 2);
root.remove(2);
assert.equal(root.children.length, 0);
}); it("Should traverse by breadth", () => {
const tree = new Tree();
tree.root = new Node(1);
tree.root.add(2);
tree.root.add(3);
tree.root.children[0].add(4); const numbers = [];
tree.traverseBF(node => numbers.push(node.data));
assert.deepEqual(numbers, [1, 2, 3, 4]);
}); it("Should traverse by depth", () => {
const tree = new Tree();
tree.root = new Node(1);
tree.root.add(2);
tree.root.add(3);
tree.root.children[0].add(4); const numbers = [];
tree.traverseDF(node => numbers.push(node.data));
assert.deepEqual(numbers, [1, 2, 4, 3]);
});
});
挑战#1：树宽度
对于给定的tree，返回每个级别的_宽度_。
describe("Width of Tree Levels", () => {
it("Should return width of each tree level", () => {
const root = new Node(1);
root.add(2);
root.add(3);
root.children[1].add(4); assert.deepEqual(treeWidths(root), [1, 2, 1]);
});
});
分析：
可以使用stack或queue来帮助遍历其_切片_和_级别_，树可以通过_深度优先_或_广度优先_遍历，分别使用stack或queue。由于我们要计算每个级别上的所有节点，因此我们需要通过使用queue以_广度优先_的方式遍历树。这里的技巧是将一个特殊的marker入队，以让我们知道已到达当前级别的末尾，以便我们可以为下一级别_重置_计数器。
该方法具有线性时间和空间复杂度。尽管我们的counter是一个数组，但它的大小永远不会超过线性。
挑战#2：树高度
对于给定的tree，返回_高度_（最大级别数）。
describe("Height of Tree", () => {
it("Should return max number of levels", () => {
const root = new Node(1);
root.add(2);
root.add(3);
root.children[1].add(4); assert.deepEqual(treeHeight(root), 2);
});
});
分析：
我们可以简单地重用第一个挑战的逻辑。在这种情况下，我们每遇到“reset”时递增我们的counter。逻辑几乎相同，因此该算法的时间和空间复杂度也是_线性_的。在这里，我们的counter只是一个整数，使其大小更加微不足道。
排序算法
有许多算法可用于对数据集进行排序。值得庆幸的是，面试官只期望我们理解基础和第一原则。例如，最好的算法可以在_恒定_空间中实现_线性对数_时间。为此，我们将按照难度和效率递增的顺序回顾最流行的算法。
冒泡排序
这个算法最容易理解，但也是最低效的。它_比较_每个项目与每个其他项目，_交换_顺序，直到更大的项目“冒泡”到顶部。该算法需要_二次_时间和_常量_空间。
插入排序# 排序算法
冒泡排序
冒泡排序会将每个元素和其他元素进行比较，而非交换它们，它会“拼接”出正确的顺序。它保持了重复项的原始顺序。这个“贪心”算法需要二次方时间和常量空间。
选择排序
该算法在循环中查找并“选择”具有最小值的索引，并在适当的地方将其与开始索引交换。这个算法也需要二次方时间和常量空间。
快速排序
这个算法递归地选择一个元素作为中心点，并迭代地将所有较小的元素推到左边，所有较大的元素推到右边，直到所有元素都被排序。这个算法需要二次方时间和对数空间，实际上通常是最快的。因此，大多数编程语言本地实现了这个算法进行排序。
归并排序
尽管这是最有效的算法之一，但理解它可能会有挑战性。它需要一个递归部分将集合拆分为单个单元，然后使用迭代部分以正确的顺序将它们组合在一起。这个算法需要线性对数时间和线性空间。
计数排序
如果我们以某种方式知道了最大值，我们就可以使用这个算法在线性时间和空间内对集合进行排序！最大值允许我们创建一个该大小的数组，以“计数”每个“索引值”的出现次数。然后，只需将所有具有“非零”计数的索引提取到我们的结果数组中。通过利用数组的常数时间查找，这个类似哈希的算法是可能的。
其他排序算法
查找算法
最坏的算法需要在集合中搜索每个项，需要 O(n) 时间。如果集合已经排序，每次迭代只需要检查一半，只需要 O(log n) 的时间，特别是对于非常大的数据集。
二分查找
当集合已排序时，我们可以迭代或递归地检查我们所需的值是否与中间项匹配，丢弃我们知道我们的值不存在的一半。实际上，我们的目标可以在对数时间和常量空间内找到。
二叉搜索树
对于集合的另一种排序方法是从中生成一个二叉搜索树（BST）。作为BST，通过它进行搜索与二分搜索一样有效。以类似的方式，我们可以在每次迭代中丢弃我们知道不能包含所需值的一半。实际上，另一种对集合进行排序的方法是按顺序遍历该树的深度优先遍历！
BST的创建需要线性时间和空间，但是通过它进行搜索需要对数时间和常量空间。
要验证二叉树是BST，我们可以递归检查每个左子节点必须小于根（最大可能）和每个右子节点必须大于根（最小可能）在每个根上。这个解决方案需要线性时间和常量空间。
结论
在现代Web开发中，函数是Web体验的核心。数据结构进入和退出函数，而算法则指导内部机制。数据结构的可扩展性由其空间复杂度描述，而算法的可扩展性由其时间复杂度描述。在实践中，运行时复杂度以大O表示法表示，它帮助工程师比较和对比所有解决方案。最有效的运行时是常数，不依赖于输入大小；最低效的需要指数操作和内存。真正掌握算法和数据结构意味着能够以线性和系统方式进行推理。
从理论上讲，每个问题都有迭代解决方案和递归解决方案。迭代方法从底部开始，通过动态到达解决方案。递归方法从顶部开始，通过识别重叠的子问题。通常，递归解决方案更具表现力和更容易实现，而迭代解决方案更容易理解并且需要更少的内存。通过一级函数和控制流结构，JavaScript本地支持这两种方法。通常，需要牺牲空间效率以获得性能提升，或者需要牺牲时间效率以获得更少的内存使用。正确的平衡取决于上下文和环境。值得庆幸的是，大多数面试官更关心计算而不是结果。
要真正给面试官留下深刻印象，请展望未来并利用架构和设计模式的机会，以增加可重用性和可维护性。如果你正在寻求高级职位，则对基础知识和基本原理的了解以及对系统级设计的经验同样重要。尽管如此，最好的公司也评估文化匹配。因为没有人是完美的，正确的团队至关重要。更重要的是，这个世界上有一些东西是无法独自实现的。往往我们共同创建的东西和为彼此创建的东西是最令人满意和有意义的。
参考资料：
- https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array
- https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis
- http://bigocheatsheet.com
- https://www.udemy.com/coding-interview-bootcamp-algorithms-and-data-structure
- https://www.toptal.com/developers/sorting-algorithms“对区块链感兴趣吗？学习以太坊并加入HeartBank®团队吧！”
译自：https://medium.com/siliconwat/algorithms-in-javascript-b0bed68f4038
评论(0)