oppo底软面经（已签两方）

编程题

第一道纯水题，判断输入的五个数满足特定关系即可

编程题描述相对宽泛，因为没有直接说明特定的关系是什么。不过，我可以给出一个常见的示例，比如判断输入的五个数是否满足递增关系（即每个数都大于前一个数），并基于这个示例来回答，同时模拟面试官的深入追问。

编程题回答

问题：编写一个程序，判断输入的五个数是否满足递增关系（即每个数都大于前一个数）。

回答：

#include <stdio.h>
#include <stdbool.h>

bool isIncreasing(int nums[], int size) {
    for (int i = 1; i < size; i++) {
        if (nums[i] <= nums[i - 1]) {
            return false; // 发现不满足递增关系，返回false
        }
    }
    return true; // 所有数都满足递增关系，返回true
}

int main() {
    int nums[5];
    printf("请输入五个整数（用空格分隔）: ");
    for (int i = 0; i < 5; i++) {
        scanf("%d", &nums[i]);
    }

    if (isIncreasing(nums, 5)) {
        printf("输入的五个数满足递增关系。\n");
    } else {
        printf("输入的五个数不满足递增关系。\n");
    }

    return 0;
}

面试官追问

1. 如果要求改为判断是否存在递减关系（即任意相邻两数后一个小于前一个），你会如何修改代码？

   • 这个问题考察的是对原问题的理解深度和灵活应变能力。
   • 回答：我会在isIncreasing函数中修改条件判断，将<=改为>，同时修改函数名以更准确地反映其功能，比如isDecreasing，然后在main函数中调用新函数并根据返回值输出结果。

2. 如果输入的数可以相等，但需要满足至少有三个数是递增的，如何修改程序？

   • 这个问题增加了逻辑复杂性，要求识别特定的递增序列长度。
   • 回答：可以设置一个计数器来跟踪递增序列的长度，一旦计数器达到3且后续数保持递增或相等，就返回true。但需注意，如果计数器达到3后，后续出现递减则应重置计数器。

3. 考虑性能优化，如果输入的数组非常大，如何高效地判断是否存在递增子序列的长度至少为3？

   • 这个问题涉及到算法效率优化。
   • 回答：对于大数组，可以采用双指针技术或动态规划来优化查找递增子序列的效率。对于判断至少长度为3的递增子序列，我们可以使用两个指针分别指向当前考虑的子序列的起始和结束位置，并动态调整它们的位置来寻找满足条件的子序列。这种方法的时间复杂度远低于遍历所有可能的子序列。

4. 如果输入数据是浮点数而非整数，程序需要做哪些调整？

   • 这个问题考察了数据类型对程序逻辑的影响。
   • 回答：需要将数组nums的类型从int改为float或double，同时在输入输出时使用相应的格式化字符串（如%f或%lf）。逻辑判断部分不需要改变，因为递增关系的定义对数据类型不敏感。

第二道题

男生和女生各n人，男生和女生对应喜欢的颜色分别为ai和bi，请问要挑出一对男生和女生满足其喜欢的颜色不同，有多少种挑选方案。

回答

为了解决这个问题，我们可以采用一种高效的方法来计算满足条件的男生和女生对的数量。基本思路是遍历所有可能的男生和女生的组合，并检查他们喜欢的颜色是否不同。然而，直接遍历所有组合（即O(n^2)的时间复杂度）在n较大时可能不够高效。我们可以通过一些优化来减少不必要的检查。

优化方法：

1. 使用哈希表：我们可以使用两个哈希表（或字典），一个用于存储男生及其喜欢的颜色，另一个用于存储女生及其喜欢的颜色。然后，对于每个男生，我们可以遍历女生的哈希表，查找颜色不同的女生数量。

2. 颜色计数：另一种方法是分别统计男生和女生各自喜欢每种颜色的数量。然后，对于每种男生喜欢的颜色，我们可以计算有多少女生不喜欢这种颜色，并将这些数量相加。

具体实现（采用第二种方法）：

1. 初始化两个数组（或哈希表），maleColors 和 femaleColors，用于统计男生和女生各自喜欢每种颜色的数量。
2. 遍历男生和女生的颜色列表，分别更新maleColors和femaleColors。
3. 初始化计数器count为0，用于记录满足条件的对的数量。
4. 遍历maleColors中的每种颜色，对于每种颜色，计算有多少女生不喜欢这种颜色（即总女生数减去喜欢这种颜色的女生数），并将这个数量加到count上。
5. 返回count作为结果。

代码示例（Python）：

def count_pairs(n, male_colors, female_colors):
    # 假设颜色种类是有限的，这里用字典来统计
    male_color_count = {}
    female_color_count = {}
    
    # 统计男生和女生各自喜欢的颜色数量
    for color in male_colors:
        male_color_count[color] = male_color_count.get(color, 0) + 1
    for color in female_colors:
        female_color_count[color] = female_color_count.get(color, 0) + 1
    
    # 计算满足条件的对的数量
    total_females = len(female_colors)
    count = 0
    for color, count_males in male_color_count.items():
        count_females_not_liking_this_color = total_females - female_color_count.get(color, 0)
        count += count_males * count_females_not_liking_this_color
    
    return count

# 示例
n = 3
male_colors = [1, 2, 3]
female_colors = [2, 3, 1]
print(count_pairs(n, male_colors, female_colors))  # 输出应为 6

面试官追问

1. 如果颜色种类非常多，甚至可能超过男生和女生的总数，你的方法是否仍然有效？

   • 回答：是的，即使颜色种类非常多，只要内存足够，使用哈希表或字典来统计颜色数量仍然是有效的。这种方法的时间复杂度主要取决于男生和女生的数量，而不是颜色的总数。

2. 如果要求输出每一对满足条件的男生和女生的索引，而不是总数，你应该如何修改你的算法？

   • 回答：为了输出每一对满足条件的男生和女生的索引，我需要在遍历男生和女生时，不仅统计颜色数量，还需要记录每个颜色的男生和女生的索引列表。然后，对于每个男生，遍历其不喜欢颜色的女生索引列表，输出所有可能的对。这将显著增加空间复杂度和时间复杂度。

3. 如果男生和女生的数量非常大，但颜色种类相对较少，有没有更优化的方法？

   • 回答：在这种情况下，可以考虑使用位运算或更紧凑的数据结构（如位向量）来存储颜色信息，以减少内存使用。同时，可以利用颜色种类少的特点，通过一些巧妙的位操作来加速查找和匹配过程。例如，可以使用位向量来表示每个男生和女生喜欢的颜色集合，然后通过位运算来快速判断两个集合是否有交集（即颜色是否相同）。

第三道题

#哈希表 前缀表

求所谓的等腰直角三元组[i,j,k]有多少个，等腰直角三元组满足：0<i<j<k<n，且a[i]=a[k]=a[j]+1

解法：两个哈希表，一个记录遍历过的数字及其出现过的次数（前缀表）；一个记录未遍历数字及其出现的次数（后缀表）。

先遍历一遍数组a，记录数字和频次到哈希表2，哈希表1为空

然后第二次遍历数组a，遍历元素作为a[j]，此时前缀表负责装遍历过的元素，后缀表则将已遍历过的元素删除。当前缀表和后缀表中a[j]+1都存在时，res+=前缀表[a[j]+1]*后缀表[a[j]+1]

回答

首先，让我们详细解释并优化这个问题的解决方案。题目要求找出满足条件的等腰直角三元组[i,j,k]，其中数组索引满足0<i<j<k<n，且数组元素满足a[i] = a[k] = a[j] + 1。原方案提出了使用两个哈希表的方法，但实际上，我们只需要一个哈希表（或者称为前缀表，因为它记录的是遍历过的元素及其频次）和一个简单的计数器（或者另一个哈希表，但用途不同）来实现这一需求。

步骤解析：

1. 初始化：

   • 创建一个哈希表prefix_count，用于记录遍历过程中元素值及其出现的次数。
   • 初始化结果变量res为0。

2. 第一遍遍历（填充哈希表）：

   • 遍历数组a，对于每个元素a[j]，检查a[j]+1是否已在prefix_count中。如果是，则对于每一个这样的a[j]+1，其对应的数量乘以prefix_count[a[j]+1]（因为此时a[j]还未被加入哈希表，所以这部分计数实际上是未来可能作为k位置的候选数量）。但这种方法实现起来较为复杂且效率不高，因为需要额外处理。
   • 实际上，我们可以简化这一步，仅记录每个元素的出现次数，而不进行实际的计数累加，因为这一步的累加依赖于后续遍历中a[j]的出现。

3. 第二遍遍历（实际计数）：

   • 再次遍历数组a，对于每个元素a[j]，检查a[j]+1是否存在于prefix_count中。如果存在，说明之前已经遍历过值为a[j]+1的元素，这些元素可能与当前的a[j]以及未来某个值为a[j]+1的元素形成等腰直角三元组。
   • 累加prefix_count[a[j]+1]到res，因为prefix_count[a[j]+1]表示在j之前，有多少个元素其值为a[j]+1，它们可以与当前的a[j]以及之后某个值为a[j]+1的元素形成满足条件的三元组。
   • 将a[j]加入prefix_count，更新其计数。

代码示例（简化逻辑，未直接实现后缀表）：

def count_isosceles_right_triplets(a):
    n = len(a)
    prefix_count = {}
    res = 0
    
    for j in range(n):
        if a[j] + 1 in prefix_count:
            res += prefix_count[a[j] + 1]
        prefix_count[a[j]] = prefix_count.get(a[j], 0) + 1
    
    return res

面试官追问

1. 为什么选择哈希表而不是其他数据结构？

   • 回答：哈希表能在O(1)平均时间复杂度内完成元素的查找、插入和删除操作，非常适合于这种需要频繁统计元素频次的问题。

2. 如果数组a中的元素范围非常大，这种方法会有什么问题？

   • 回答：如果元素范围非常大但出现频次很低，哈希表会占用大量空间来存储几乎为0的频次。可以考虑使用稀疏哈希表（如Python的collections.defaultdict）或者其他压缩存储策略。

3. 能否进一步优化空间复杂度？

   • 回答：虽然哈希表已经提供了较好的空间效率，但如果数组a中的元素种类数远小于n，可以考虑只存储出现过的元素及其频次，而不是使用完整的哈希表来映射所有可能的元素值。

4. 如果要求同时找出满足条件的三元组，而不仅仅是计数，你会怎么做？

   • 回答：需要额外的数据结构来记录每个元素的位置信息，可能是一个哈希表映射元素值到其所有索引的列表。在遍历时，对于每个a[j]，检查a[j]+1的索引列表，并与后续遍历中同样值为a[j]+1的元素进行配对检查。

八股

1. i++和++i的区别

回答

在C/C++等编程语言中，i++ 和 ++i 都用于将变量 i 的值增加1，但它们之间在表达式中的行为有所不同，主要体现在它们的返回值和操作顺序上。

• i++（后缀递增运算符）：首先返回变量 i 的当前值，然后将 i 的值增加1。这种操作通常被称为“先赋值后递增”。

• ++i（前缀递增运算符）：首先将变量 i 的值增加1，然后返回新的值。这种操作被称为“先递增后赋值”。

示例：

int i = 5;
int a = i++; // a = 5, 然后 i 变为 6
int b = ++i; // i 先变为 7, 然后 b = 7

深度解析

除了上述基本区别外，i++ 和 ++i 在不同的上下文（如循环、表达式计算等）中可能会有不同的性能影响，尽管在现代编译器优化后，这种差异通常被最小化。但在某些特定的嵌入式系统或低资源环境中，了解这些差异可能仍然很重要。

• 在循环中的使用：虽然从逻辑上讲，for(int i = 0; i < 10; i++) 和 for(int i = 0; i < 10; ++i) 在功能上是等价的，但后者在某些编译器和处理器上可能产生更高效的代码，因为它避免了先读取 i 的值再进行递增的步骤。

• 在表达：在更复杂的表达式中，如 和 ，两者的行为会有显著不同。前者首先根据 的当前值访问数组，然后递增 ；后者先递增 ，然后基于新值访问数组。