介绍与约束

简介

对算法的理论理解固然重要，但仅靠理论是不够的。要解决任何算法设计问题，我们将采用以下五个步骤的策略：

• 约束条件
• 思路生成
• 复杂度分析
• 编码实现
• 测试验证

下面我们详细讨论约束条件。

约束条件

仅仅掌握算法知识并构建出合理的计算框架，并不足以解决技术问题。在技术面试中，面试官更关注的是你如何解决问题的过程。很多人常犯的错误是，没有主动提出后续问题，而是做出大量假设后直接开始求解。实际上，在着手解决问题之前，你应该从面试官那里获取尽可能多的信息。

在这一步中，我们需要明确并写下问题的所有约束条件。面试题不同于考试题，不会把所有细节都交代清楚。面试官希望你在过程中主动提问，以澄清问题的边界和细节。

我们来看一个例子，以便更好地理解“约束条件”的含义。

示例

假设面试官要求我们编写一个排序算法。此时，我们需要先澄清以下几个问题：

• 首先要明确输入的数据类型。例如，数据是否均为整数？
• 其次是数据规模。不同的输入规模会影响算法的设计——处理100个整数和处理10亿个整数所采用的方法可能完全不同。

数字数组的约束条件基本指导原则

• 数组最多包含多少个元素？
• 每个元素的取值范围是什么？
• 最小值和最大值分别是多少？
• 每个元素的数据类型是什么？是浮点数还是整数？
• 数组中的数据是否唯一？

字符串数组的约束条件基本指导原则

• 数组总共包含多少个元素？
• 每个字符串的长度是多少？最短和最长分别为多少？
• 数组中是否存在重复数据？

图结构的约束条件基本指导原则

• 图中有多少个节点？
• 图中有多少条边？
• 图是否有权重？权重的范围是多少？
• 图的边是有向的还是无向的？
• 图中是否存在环？
• 图中是否存在负权环？
• 图中是否有自环？