实验室暑假学习第二周算法总结

骑猪看日落 2023-02-28 11:15 67阅读 0赞

## LeetCode 628. 三个数的最大乘积 ##

**难度** 简单

给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。

**示例1**

输入: [1,2,3]
    输出: 6

**示例2**

输入: [1,2,3,4]
    输出: 24

**注意**  
1.给定的整型数组长度范围是\[3,104\]，数组中所有的元素范围是\[-1000, 1000\]。  
2.输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。

--------------------

**解法** 快速排序  
语言：C

int* cmp(const void* a, const void* b) {         /* qsort函数的cmp参数，表示升序排序 */
        return *(int*)a - *(int*)b;
    }
    
    int maximumProduct(int* nums, int numsSize) { 
        qsort(nums, numsSize, sizeof(int), cmp);    /* 对整型数组进行升序快速排序 */
        return nums[numsSize-1] * nums[numsSize-2] * nums[numsSize-3] > nums[0] * nums[1] * nums[numsSize-1]?
               (nums[numsSize-1] * nums[numsSize-2] * nums[numsSize-3]) : (nums[0] * nums[1] * nums[numsSize-1]);
    }

读完题后，我的第一想法就是对给出的数组进行排序，这样可以把数组中的整型元素按照从小到大的顺序清楚地排列出来，进而方便下一步找出最大乘积。为了尽可能提高排序的效率，这里我使用了`stdlib.h`头文件中的函数`qsort()`进行快速排序。在使用`qsort()`排序之前，我们还应当指定其中的一个参数`cmp`。具体实现过程请参考上面的代码。  
排好顺序后，我们需要列举出所有可能出现的情况：找出的三个数  
1.均为负数，乘积为负数；  
2.两负一非负，乘积为非负数；  
3.一负两非负，乘积为非正数；  
4.均为非负数，乘积为非负数。  
对于上述情况1和4，我们只需要找出最大的三个数令其相乘，得到的结果即为最大乘积；对于情况2，又会分为两种情况，即涉及最小的两个负数乘积与次大、次次大的两个非负数乘积的大小比较问题；对于情况3，如果真的出现这种情况的话，那么只有一种可能，即该数组的长度为3，最大乘积即为数组所有整型元素之积，也就是数组中最大的三个数的乘积。  
经过上述分析，可以总结出，对于一个排好序的整型数组，其中三个元素的最大乘积就是下标为`0`, `1`, `numsSize-1`对应元素的乘积与下标为`numsSize-3`, `numsSize-2`, `numsSize-1`对应元素的乘积的较大值。

## LeetCode 817. 链表组件 ##

**难度** 中等

给定链表头结点`head`，该链表上的每个结点都有一个**唯一的整型值**。  
同时给定列表`G`，该列表是上述链表中整型值的一个子集。  
返回列表`G`中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表`G`中）构成的集合。

**示例1**

输入: 
    head: 0->1->2->3
    G = [0, 1, 3]
    输出: 2
    解释：
    链表中，0和1是相连接的，且G中不包含2，所以[0, 1]是G的一个组件，同理[3]也是一个组件，故返回2。

**示例2**

输入: 
    head: 0->1->2->3->4
    G = [0, 3, 1, 4]
    输出: 2
    解释: 
    链表中，0和1是相连接的，3和4是相连接的，所以[0, 1]和[3, 4]是两个组件，故返回2。

**提示**  
1.如果`N`是给定链表`head`的长度，`1 <= N <= 10000`。  
2.链表中每个结点的值所在范围为`[0, N - 1]`。  
3.`1 <= G.length <= 10000`。  
4.`G`是链表中所有结点的值的一个子集。

--------------------

**解法** 数组标记法  
语言：C

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
    
    
    int numComponents(struct ListNode* head, int* G, int GSize) { 
        bool flag[10000] = { 0};
        struct ListNode* node = head;
        int ret = 0;
        for (int i = 0; i < GSize; i++)
            flag[G[i]] = 1;
        while (node) { 
            if (flag[node->val]) { 
                ret++;
                while (node && flag[node->val])
                    node = node->next;
            }
            if (node)
                node = node->next;
        }
        return ret;
    }

这道题的思路和上周做过的**LeetCode 697. 数组的度**的思路非常相似，都是使用了标记数组。首先定义一个布尔型数组`flag`并且使其所有元素为`0`，作为标记数组，初始化指向结构体的指针变量`node`指向单链表头结点`head`，初始化返回值`ret = 0`。遍历给定数组`G`，对于`G`中的每个元素`G[i]`，令`flag[G[i]] = 1`。这样一来，凡是在数组`G`中出现的值，在标记数组`flag`中以其为下标的元素值均为`1`，其余元素值均为`0`。  
遍历单链表，如果`flag[node->val]`的值为`1`，`ret`自加1，并且遍历至`flag[node->val] = 0`或单链表尾结点为止；如果`flag[node->val]`的值为`0`，令`node = node->next`，继续遍历。重复这个流程，直到单链表遍历结束，此时的`ret`即为所求结果。

> 采用布尔型数组而非整型数组作为标记数组，可以降低内存消耗。