了解这些算法技术可以帮助你有效地解决实际问题。

每种流行的编程语言通常都带有通用语言功能、内置函数和标准库 API，可帮助开发人员使用特定语言进行通用编程。 仅了解这些概念就可以编写按顺序执行某些操作的代码，但实际的编程任务需要更好地理解计算算法。 计算算法是进行计算活动的逐步方式。 在计算机科学中，我们可以找到很多理论算法，可以用来解决构建软件系统时的实际问题。

算法子领域是计算机科学的一个关键领域，在编程过程中经常被实际使用。 一些程序员可以利用他们已知的核心算法概念轻松解决工程问题，但有些程序员却常常遇到困难，因此科技公司通常使用算法问题来雇用最好的程序员。 换句话说，算法领域（和数据结构）就像软件工程领域中的 IQ 指标。

了解算法技能可以帮助您实现梦想的编程工作，并激励您通过最佳解决方案有效地解决实际的软件工程问题。 我将在这个故事中解释几个测试你的计算算法技能的面试问题！ 我将使用 JavaScript 代码片段而不是伪代码来更实际地解释答案。

1. 理解神奇的 JSON

程序员经常使用树形数据结构来实现互连的数据节点系统，例如文件系统、数字历史、编程语言模型等。即使在大多数企业级、面向业务的软件系统中，树形结构也与数据库模型一起使用。 因此，了解树算法可以提高所有程序员的技能。

第一个问题测试您的基本树算法技能。 如果你向某人问这个问题，请不要提及树，因为问题的一部分是发现它需要树算法。 这是问题：

打印以下 JSON 结构中所有 v 字段中存储的所有值：

{  "v": 21,  "a": {    "v": 15,    "a": {      "v": 200,      "a": {        "v": 12      },      "b": {        "v": 20      }    },    "b": {      "v": 10    }  },  "b": {    "v": 1,    "b": {      "v": 55    }  }}

如果您仔细查看此 JSON 结构或使用 JSON 可视化工具在屏幕上将其可视化，您将意识到我们可以使用简单的二叉树来表示它。 我们可以使用 a 和 b 属性构造二叉树子节点，并可以使用 v 属性附加节点值。

您可以使用任何树遍历算法打印所有 v 值。 著名的 DFS（深度优先搜索）是一个方便的工具：

const tree = JSON.parse(`...`); // Add JSON here.function dfs(node) {  if(!node)     return;  console.log(node.v);  dfs(node.a);  dfs(node.b);}dfs(tree);

为了简单起见，这里我们使用递归，但您也可以使用带有 while 循环和堆栈的迭代方法。

2. 优化斐波那契数列

递归是程序员遵循的一个数学概念，使用调用自身的函数来解决问题。 递归帮助我们为计算问题实现简单且不言自明的算法，但它有一个众所周知的缺点，即成本——递归成本高昂——它经常会重复以前已经访问过的递归路径。 记忆化是一种流行的动态编程概念，用于消除自然递归问题中的重复递归路径。

这是第二个问题。 通过增加空间复杂度来提高以下斐波那契算法的性能，但使用相同的初级递归算法：

function fib(n) {  if(n === 0 || n === 1)    return n;  return fib(n - 1) + fib(n - 2);}console.log(fib(10));    // 55

您可以使用以下方法和标准性能 API 来测量上述算法的执行时间：

const start = performance.now();console.log(fib(10));    // 55console.log(`T = ${performance.now() - start} ms`);

该算法效率不高——您可以通过调用稍微高一点的值（例如 50）的 fib 函数来实际体验它。较大的值甚至可能会由于过多的递归函数调用而导致浏览器崩溃。 问题是，许多斐波那契值经常被重新计算，因为该算法在每次调用时都会创建两个单独的递归树。 例如，在计算 fib(10) 时，该函数将调用 fib(9) 和 fib(8)。 然后，即使可以使用 fib(9) 的预先计算结果来计算 fib(8)，该算法也会分别计算 fib(9) 和 fib(8)。

我们可以通过缓存最大化空间复杂度因子来提高时间复杂度因子：

let cache = {};function fib(n) {  if(n === 0 || n === 1)    return n;  if(n in cache)    return cache[n];  cache[n] = fib(n - 1) + fib(n - 2);  return cache[n];}

现在，即使您计算第 1000 个斐波那契数，浏览器也不会崩溃。 为了计算更高的斐波那契数，请使用具有对数时间复杂度的快速算法（即快速加倍）。

3. 剪彩问题

我们知道每种流行的编程语言都通过标准库提供对数函数。 此外，我们大多数人在具有基本数学概念和物理的大学里使用对数。 我们还知道对数规则和基于图形的对数表示。 对数函数到底是什么？如何实际解释它？

让我们通过第三个问题来理解对数的基本概念。 假设您有一个 L 单位长度的色带。 您还可以使用剪刀将其切成两个相同的部分。 您还可以将所得的两半切成四半，依此类推。 你需要用剪刀多少次才能将L尺寸的丝带剪成大小相等、长度单位的碎片？ 为此编写一个函数。

这里的问题是每次将一个元素分成两部分——所以大多数程序员可能会想起二分搜索算法。 二分查找算法的时间复杂度为O(log n)。 如果您非常了解对数时间复杂度，那么这是解决问题的一种方法。 让我们检查一下另一种方法。

如果 L 为 8（因为我们每次制作两个相同大小的片段），则第一次剪刀切割将制作 4 单位长度的两个片段。 接下来，它将制作 2 个单位长度的四块。 第三次切割将单位长度切成八块。 那么，8、2、3之间是什么关系呢？ 当你检查更多情况后，你会发现你需要找到以 2 为底的 L 的指数。这是 L 以 2 为底的对数：

function calcCuts(L) {  return Math.log2(L);}console.log(calcCuts(8));   // 3console.log(calcCuts(32));  // 5console.log(calcCuts(2));   // 1

递归思考并不容易，但递归是所有程序员的必备技能，因此大多数科技公司都会测试与递归解决方案思维相关的技能。 编译器设计、解析和图形渲染等计算机工程领域经常使用递归概念。 它也是动态规划和分而治之策略背后的主要技术。

第四题考验你的递归思维能力。 假设您必须使用 max(a, b) 函数来查找 N 个参数的最大值。 编写一个函数，根据输入 N 生成最大函数调用模式。例如，如果 N 为 3，则输出应如下所示：

max(a, max(a, b))

上面的代码语句接受三个参数。 如果 N 为 4，则输出应如下所示：

max(a, max(a, max(a, b)))

上面的代码语句接受四个参数。 如果你从递归的角度来看这个问题，你会发现 max 的第二个参数是递归的。

看下面的函数实现：

function gen(N) {  if(N === 2)    return 'max(a, b)';  return `max(a, ${gen(N - 1)})`;}console.log(gen(3));    // max(a, max(a, b))console.log(gen(4));    // max(a, max(a, max(a, b)))

我们经常使用条件语句在源代码中创建逻辑分支。 从简单的验证到高级计算机工程问题，众所周知的 if 条件都表现出色。 代码分支有时很容易，但在某些情况下，它会变得耗时、复杂，并且由于无法识别的逻辑流，可能会在代码库中产生新的错误。

最后一个问题测试基本的条件语句实现技巧。 它不是检查一个简单的布尔标志或检查一个数字是否高于另一个数字，而是需要根据多个条件比较三个变量。

编写一个函数来检查当所有三个边的长度都给定时是否可以形成三角形。

用笔和纸画几个不同边长的三角形。 然后你会发现，只有最大边小于另外两条边之和，才能构成三角形。 我们可以通过使用 O(1) 条件算法将边命名为 a、b 和 c 来解决这个问题。

看下面的代码片段：

function isTriangle(a, b, c) {  if((a >= b + c) || (b >= a + c) || (c >= a + b))     return false;  return true;}console.log(isTriangle(4, 2, 5));   //  trueconsole.log(isTriangle(1, 2, 3));   //  falseconsole.log(isTriangle(1, 1, 1));   //  true

您甚至可以通过反转条件覆盖来简化此条件语句，如下所示：

function isTriangle(a, b, c) {  return (a < b + c) && (b < a + c) && (c < a + b); }

在这里，我们避免使用三个条件（每个条件都假设唯一的边作为最大的边）进行排序和查找最新边。