C语言数组编码面试题

本教程列出了面试中经常被问到的编码问题。所有问题都用 C 编程语言中被认为是最好的代码编写而成。所有问题均从互联网上的不同资源收集而来。

首先，数组是一种同质的、静态的数据结构，它在连续的内存位置存储元素。我们使用索引来访问数组的元素。正索引从（0到size-1）开始，负索引从数组的末尾（-1到-size）开始。C 编译器将数组名视为指针，指向数据结构的第一个元素。因此，我们可以使用指针算术来访问数组元素。

现在，让我们深入研究一些编码问题

1) 编写一个函数来识别数组中第一个不小于其邻居的元素。

解决方案

数组中至少会存在一个这样的元素，称为**“峰值元素”**。我们可以采用多种方法来查找该元素，例如遍历整个数组、找到数组中的最大元素等。这里，我们将使用最佳方法。请记住，我们只是被要求编写一个函数。因此，我们可以将数组及其大小作为两个参数，并编写函数

思考方式

我们需要高效的代码。如果遍历整个数组，则需要 O(n) 的时间。但我们不需要所有峰值元素；我们只需要一个。我们必须不断搜索该元素，从而排除数组的某些部分。

我们使用了二分搜索算法来排除我们不必遍历的数组部分。即使数组未排序，我们也必须找到一个局部较大的元素。

代码

2) 编写一个函数，使用递归反转数组的元素。

解决方案

我们可以声明两个变量，**l = 0, h = (n - 1)**。我们可以不断地在 l 和 h 的数组位置交换值，同时增加 l 并减少 h，直到 l 和 h 都到达中间元素或直到它们都相互超越。

函数

3) 编写一个函数，只遍历一次数组，即可分隔出数组中的 0 和 1。

解决方案

我们被要求只遍历数组一次。我们需要使用两个指针/变量来遍历数组。这里我们有两个选择

1. 使用两个从数组开头开始的变量
2. 使用一个从开头开始的变量，另一个从末尾开始的变量。

来自数组两端的变量

思考方式

我们使用两个变量 l 和 h，分别存储数组第一个和最后一个元素的索引。我们希望将 0 排在 1 的前面。l 从开头遍历的元素应该是 0，h 从末尾访问的元素应该是 1。如果 l 找到 1 或 h 找到 0，我们需要交换元素。

从数组开头开始的两个变量

思考方式

我们希望将 0 排在 1 的前面。我们将使用两个变量，它们都从数组开头开始遍历。一个变量用于访问元素并检查值，另一个变量专门用于停留在某个索引处。这里的逻辑是，每当访问变量找到 0 时，我们都应该交换两个变量处的元素。

请注意，在这两种方法中，我们都只遍历了整个数组一次。

4) 编写一个 C 函数，将给定整数数组中的所有负数移到一侧。

解决方案

我们可以像上面那样解决这个问题。我们得到了一个包含随机排列的正数和负数的整数数组。我们应该将数组排列成正数在前，负数在后，或负数在前，正数在后。

在上面的问题中，我们编写了代码来排列 0 在前的数组。这里，我们需要使用相同的算法来排列负数在前，正数在后的数组。

来自数组两端的变量

从数组开头开始的两个变量

5) 编写一个 C 函数，找出给定数组中 k 个连续元素的 sums 的最大值。

解决方案

我们得到了一个整数数组和一个整数 k。我们需要找出数组中 k 个连续索引的元素相加可以得到的最大 sums。使用嵌套循环，我们可以使用暴力方法来检查数组中所有大小为 k 的可能子数组。这可能效率不高。另一个我们可以使用的值得注意的技术是“**滑动窗口技术**”。

滑动窗口技术

我们从用户那里获取 k 的值，这里的概念是我们创建一个大小为 k 的窗口，然后将其按单位索引滑动。

例如

假设我们需要 2 个连续索引的最大 sums，创建一个大小为 2 的窗口，然后将其在整个数组中滑动（遍历）。我们将计算每个窗口元素的 sums，并返回最大 sums。

代码

6) 编写一个 C 函数，从非负数数组中找到具有给定 sums 的子数组。

解决方案

我们得到一个全为正数的数组和一个所需的 sums。我们需要找到一个子数组，其元素的 sums 等于给定的 sums。可能存在不止一个这样的子数组。我们可以使用嵌套循环并检查所有可能子数组的 sums，但这可能效率不高。因此，我们可以使用上面提到的“**滑动窗口技术**”。

思考方式

假设数组中的所有元素都是正数。因此，如果存在一个子数组的 sums 大于给定的 sums，那么就是它了。我们需要保持数组元素不变。因此，如果数组中也包含负数，我们就不能在所有情况下都使用滑动窗口技术，因为 sums 会不断变化。

1. 不断向窗口/子数组添加元素，直到元素的 sums 小于给定的 sums。
2. 如果 sums 超过给定的 sums，则从窗口的开头移除元素。

遍历

例如

代码

7) 编写一个 C 函数，在给定的已排序数组中查找给定整数的出现次数。

解决方案

我们得到了一个已排序的数组和一个整数。我们的任务是找出该整数在数组中出现的次数。这是一个简单的问题。我们可以使用我们想要的任何搜索算法来解决它。

思考方式

我们可以使用线性搜索或二分搜索来解决这个问题。这是对传统二分排序的优化，以提高效率。但是，我们需要使用改进的二分搜索算法来以 O(Log n) 的时间解决这个问题。

算法

1. 使用二分排序找到整数第一次出现的索引
2. 使用二分排序找到整数最后一次出现的索引
3. 返回计数 = 最后一个索引 - 第一个索引 + 1

代码

三个函数

1. **Firstoc**：查找整数在数组中第一次出现的索引
2. **Lastoc**：在剩余数组中查找整数最后一次出现的索引。
3. **Count**：计算从 firstoc 到 lastoc 整数出现的次数。

8) 编写一个高效的 C 函数，使用两个数的 GCD 来查找 LCM。

解决方案

整个逻辑在于两个数的 LCM 和 GCD 之间的关系。假设 a 和 b 是这两个数

a * b = LCM (a, b) * GCD (a, b)

LCM (a, b) = a * b / GCD (a, b)

9) 编写一个 C 函数，找出数字的各位之和，并以 C 语言反转打印该数字。

解决方案

要找出数字的所有数字之和并反转它们，我们需要将它们从数字中分离出来。我们可以通过除法和模运算（乘以 10 的倍数）来访问数字的各位。

代码

10) 编写一个 C 函数来确定给定的年份是否为闰年。

解决方案

检查给定的年份是否为闰年的逻辑

1. 是 400 的倍数，或
2. 是 4 的倍数而不是 100 的倍数

代码