【LeetCode】HOT 100（18）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】HOT 100（18）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

题单介绍：

题目：148. 排序链表 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：152. 乘积最大子数组 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

题目：148. 排序链表 - 力扣（Leetcode）

【LeetCode】HOT 100（18）,LeetCode HOT 100,leetcode,算法,c++

题目的接口：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {

    }
};

解题思路：

这道题，如果直接做的话并不难，

就直接把链表的值塞进数组里面，然后sort一下就行，

最后在把值送回链表里面，

如果考虑进阶的空间复杂度的话，就需要用很复杂的归并来做，

今天时间不太够，我把这道题收藏了，之后再用归并做进阶，

代码如下：

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        vector<int> v;
        ListNode* cur = head;
        while(cur) {
            v.push_back(cur->val);
            cur = cur->next;
        }
        sort(v.begin(), v.end());
        cur = head;
        for(int i = 0; i < v.size(); i++) {
            cur->val = v[i];
            cur = cur->next;
        }
        return head;
    }
};

过过过过啦！！！！

【LeetCode】HOT 100（18）,LeetCode HOT 100,leetcode,算法,c++

题目：152. 乘积最大子数组 - 力扣（Leetcode）

题目的接口：

class Solution {
public:
    int maxProduct(vector<int>& nums) {

    }
};

解题思路：

这道题怎么说呢，

一眼动态规划，

但是，规划不出来。。。

学习动态规划真的是刻不容缓，

但是我最近有没有时间，只好先收藏为敬，

等我暑假拿下动态规划，系统学习一遍之后，再来找她报仇。

那现在我就先用其他方法做了，

虽然这些是动态规划的题目，但是，总会有大神能想出牛逼的方法，

思路如下：

实际上这个乘积的最大值只有两种情况，

第一种：如果数组中存在0，那就是求各个子数组乘积的最大值，

直接遍历求解即可，（更新最大值，遇到0就重新开始计算）

第二种；如果数组中不存在0，那就又分成两种情况：

1. 负数存在偶数个，那最大值就是整个数组的乘积

2. 负数存在奇数个，那最大值就是：

max(从左边开始乘到最后一个负数的值，从右边开始乘到最后一个负数的值)

代码如下：

代码：

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int sum = 1;
        int maxVal = nums[0];
        for(auto e : nums) {
            sum *= e;
            maxVal = max(maxVal, sum); //更新最大值
            if(e == 0) sum = 1; //如果有0，重新计算
        }
        sum = 1;
        for(int i = nums.size() - 1; i >= 0; i--) {
            sum *= nums[i];
            maxVal = max(maxVal, sum);
            if(nums[i] == 0) sum = 1;
        }
        return maxVal;
    }
};