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

2020-07-21

LeetCode 628. 三个数的最大乘积

难度 简单

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

示例1 

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

示例2 

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

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

解法 快速排序
语言：C 

1
2
3
4
5
6
7
8
9
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 

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

示例2 

1
2
3
4
5
6
输入: 
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 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * 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即为所求结果。

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