当前位置：首页 > article >正文

LeetCode599 两个列表的最小索引总和

article 2025/1/11 9:08:22

解决餐厅选择难题：寻找共同喜爱且索引和最小的餐厅

在生活中，我们常常会面临各种选择难题，就像 Andy 和 Doris 在决定晚餐去哪家餐厅时遇到的困扰。他们各自心中都有一份喜爱餐厅的清单，而现在的任务是找出他们共同喜爱的餐厅中，索引和最小的那些。这看似是一个简单的日常问题，实则蕴含着有趣的编程逻辑。今天，我们就来深入探讨如何通过代码解决这个问题。

一、问题的详细剖析

给定两个字符串数组 list1 和 list2，它们分别代表 Andy 和 Doris 最喜爱的餐厅列表，同时我们还知道这两个数组的长度 list1Size 和 list2Size。我们需要编写一个名为 findRestaurant 的函数，这个函数要返回一个字符串数组，其中包含所有 Andy 和 Doris 共同喜爱且在两个列表中索引和最小的餐厅名字。而且，如果存在多个这样的餐厅，函数需要将它们全部输出，并且不需要考虑输出的顺序。另外，题目假设必定存在这样的共同喜爱餐厅。

例如，假设 list1 为 ["Shogun", "Tapioca Express", "Burger King", "KFC"]，list2 为 ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"]。在这个例子中，“Shogun” 在 list1 中的索引为 0，在 list2 中的索引为 3，其索引和为 3。我们的任务就是找到所有这样索引和最小的共同餐厅。

二、解题思路与策略

初始化关键变量

首先，我们需要一个变量来记录最小的索引和。考虑到最坏情况，我们将其初始化为 list1Size + list2Size，这样在后续比较中可以确保找到真正的最小值。
定义一个二维字符数组指针 result 用于存储最终的结果，也就是那些共同喜爱且索引和最小的餐厅名字，初始时将其设为 NULL。
再定义一个变量 resultCount 来记录当前结果数组中元素的个数，初始值为 0。

嵌套循环遍历

使用嵌套循环，外层循环遍历 list1，内层循环遍历 list2。对于每一个 list1 中的元素和每一个 list2 中的元素，我们使用 strcmp 函数来判断它们是否相同。strcmp 函数会比较两个字符串，如果相同则返回 0。
当找到两个相同的餐厅名字时，计算它们在各自列表中的索引和。假设当前 list1 中的素索引为 i，list2 中的元素索引为 j，则索引和为 i + j。

结果更新与存储

如果计算得到的索引和小于当前记录的最小索引和 minIndexSum，这意味着我们找到了一组更优的结果。此时，我们需要清理之前可能存储在 result 中的数据（如果有的话），重新分配内存来存储当前这个餐厅名字，并更新 minIndexSum 和 resultCount。
如果计算得到的索引和等于当前的最小索引和 minIndexSum，说明我们又找到了一个符合条件的餐厅，这时我们通过 realloc 函数扩展 result 数组的大小，将新的餐厅名字添加进去，并增加 resultCount。

三、代码实现

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

char** findRestaurant(char** list1, int list1Size, char** list2, int list2Size, int* returnSize) {
    int minIndexSum = list1Size + list2Size;
    char** result = NULL;
    int resultCount = 0;

    for (int i = 0; i < list1Size; i++) {
        for (int j = 0; j < list2Size; j++) {
            if (strcmp(list1[i], list2[j]) == 0) {
                int indexSum = i + j;
                if (indexSum < minIndexSum) {
                    minIndexSum = indexSum;
                    if (result!= NULL) {
                        for (int k = 0; k < resultCount; k++) {
                            free(result[k]);
                        }
                        free(result);
                    }
                    result = (char**)malloc(sizeof(char*));
                    result[0] = (char*)malloc((strlen(list1[i]) + 1) * sizeof(char));
                    strcpy(result[0], list1[i]);
                    resultCount = 1;
                } else if (indexSum == minIndexSum) {
                    result = (char**)realloc(result, (resultCount + 1) * sizeof(char*));
                    result[resultCount] = (char*)malloc((strlen(list1[i]) + 1) * sizeof(char));
                    strcpy(result[resultCount], list1[i]);
                    resultCount++;
                }
            }
        }
    }

    *returnSize = resultCount;
    return result;
}

int main() {
    char* list1[] = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
    char* list2[] = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
    int returnSize;
    char** commonRestaurants = findRestaurant(list1, 4, list2, 4, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", commonRestaurants[i]);
    }
    for (int i = 0; i < returnSize; i++) {
        free(commonRestaurants[i]);
    }
    free(commonRestaurants);
    return 0;
}

四、代码解读

变量初始化：在 findRestaurant 函数的开头，我们对 minIndexSum、result 和 resultCount 进行了初始化。minIndexSum 被设为一个较大的值，result 初始化为 NULL，resultCount 设为 0。
嵌套循环：通过两层嵌套的 for 循环，我们遍历了 list1 和 list2 中的每一个元素组合。
字符串比较与索引和计算：使用 strcmp 函数判断两个餐厅名字是否相同，如果相同则计算它们的索引和。
结果处理：根据索引和与 minIndexSum 的比较结果，我们要么更新 result 数组，要么扩展 result 数组来存储新的符合条件的餐厅名字。
内存管理：在 main 函数中，我们不仅调用了 findRestaurant 函数获取结果，还对分配的内存进行了释放，以避免内存泄漏。

五、总结与拓展

通过以上的步骤和代码，我们成功地解决了帮助 Andy 和 Doris 选择共同喜爱且索引和最小的餐厅的问题。这个问题看似简单，但涉及到了数组遍历、字符串比较、动态内存分配和管理等多个重要的编程概念。在实际应用中，这种算法思路可以应用到很多场景，比如在两个有序列表中查找共同元素并根据某种规则筛选，或者在多个数据集之间进行高效的匹配和筛选等。希望通过这篇文章，你不仅掌握了这个问题的解决方案，还能对编程中的逻辑思维和问题解决能力有更深入的理解。

查看全文

http://www.kler.cn/a/487879.html