❗❗如果本文对您有帮助，请不要吝啬您的评论、点赞、收藏与小花，这对我非常重要！谢谢！❗❗

本文所涉及的题目均为基于个人学习和理解重新表述的内容，仅供学习交流之用，不代表任何实际考试题目。如有雷同，纯属巧合。

岗位：BSP驱动开发工程师-OS

题型：4 道编程题

1、编程题

1.1

小红的三消游戏：

小红在玩一个三消游戏，游戏中 n 个球排成一排，每个球都有一个颜色。若有 3 个颜色相同的球连在一起，则消除这 3 个球，然后剩下的球会重新连在一起。在没有 3 个颜色相同的球连在一起时，小红可以在任意一个球的左边（或右边）添加一个任意颜色的球。

小红觉得这个游戏很难，因此她准备按任意顺序重新排序这 n 个球。小红想知道在她重新排序这 n 个球后，最少需要添加多少个球才可以消除所有的球。

输入描述：

第一行输入 1 个整数 n(1 ≤ n ≤ 10^5)，表示球的数量。
第二行输入 n 个整数 ai(1 ≤ a ≤ 10^9)，表示每个球的颜色。

输出描述：

输出一个整数表示答案。

示例：

输入：
6
3 1 2 3 1 3

输出：3

说明：
重新排序成 [1,2,1,3,3,3]，3 个颜色为 3 的球可以直接消除，变成 [1,2,1]然后在第 1 个球右边增加 2 个颜色为 2 的球，变成 [1,2,2,2,1]，消除 3 个颜色为 2 的球；最后在第 1 个球左边增加 1 个颜色为 1 的球，变成 [1,1,1]，消除 3 个颜色为 1 的球。

解答：

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) 
{
    return (*(int*)a - * (int*)b);
}

int minAdditions(int* arr, int n) 
{
    int count = 0;

    qsort(arr, n, sizeof(int), compare);

    for (int i = 0; i < n; ) 
    {
        int j = i;
        while (j < n && arr[j] == arr[i]) {
            j++;
        }

        int length = j - i;

        if (length < 3) {
            count += 3 - length;
        }

        i = j;
    }

    return count;
}

int main() {
    int n;

    scanf("%d", &n);

    int arr[n];

    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    int result = minAdditions(arr, n);
    printf("%d\n", result);

    return 0;
}

1.2

小红的特殊数组：

小红定义一个数组为特殊数组：这个数组大小至少为 3 ，只由两种数字组成，且其中一种数字恰好出现一次。例如：[1,1,4]，[1,4,1] 是特殊数组（长度为 3，只有 1 和 4 组成且 4 恰好出现一次)，[1,4]，[5,1,4]，[1,1,1] 都不是特殊数组。

小红有一个长度为 n 的数组 a，她想知道这个数组有多少个子数组是特殊数组。