leetcode594-643

LeetCode 探索：发散你的思维

[594] 最长和谐子序列

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在，给定一个整数数组，你需要在所有可能的子序列中找到最长的和谐子序列的长度。

解题思路：使用Hash-Map，以元素值作为key，元素的个数作为value存到map中，然后使用迭代器遍历map，若当前key+1存在，则更新res

/*
 * @lc app=leetcode.cn id=594 lang=cpp
 *
 * [594] 最长和谐子序列
 */

// @lc code=start
class Solution
{
public:
    int findLHS(vector<int> &nums)
    {
        int res = 0;
        map<int, int> table;
        for (int n : nums)
            table[n]++;
        for (auto i : table)
        {
            if (table.count(i.first + 1))
            {
                res = max(res, table[i.first] + table[i.first + 1]);
            }
        }
        return res;
    }
};
// @lc code=end

[598] 范围求和 II

给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。

操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。

在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。

解题思路：只需返回所有操作的坐标的交集即可，即每个操作坐标的最小值

/*
 * @lc app=leetcode.cn id=598 lang=cpp
 *
 * [598] 范围求和 II
 */

// @lc code=start
class Solution
{
public:
    int maxCount(int m, int n, vector<vector<int>> &ops)
    {
        if (ops.size() == 0)
            return m * n;
        int x = INT_MAX, y = INT_MAX;
        for (vector<int> op : ops)
        {
            x = min(x, op[0]);
            y = min(y, op[1]);
        }
        return x * y;
    }
};
// @lc code=end

[599] 两个列表的最小索引总和

假设Andy和Doris想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。

你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。 如果答案不止一个，则输出所有答案并且不考虑顺序。 你可以假设总是存在一个答案。

解题思路：创建一个HashMap，餐厅名字作为key，餐厅出现的次数和其下标作为value。然后用迭代器遍历该HashMap，若餐厅出现的次数大于1时，则进行判断：如果该餐厅的下标小于当前最小下标minIndex时，则将结果清空，并将该餐厅推入结果中；或若该餐厅的下标等于当前最小下标minIndex时，则简单地将其推入结果中。

/*
 * @lc app=leetcode.cn id=599 lang=cpp
 *
 * [599] 两个列表的最小索引总和
 */

// @lc code=start
class Solution
{
public:
    vector<string> findRestaurant(vector<string> &list1, vector<string> &list2)
    {
        map<string, pair<int, int>> table;
        vector<string> res;
        int minIndex = INT_MAX;
        for (int i = 0; i < list1.size(); i++)
        {
            table[list1[i]].first++;
            table[list1[i]].second += i;
        }
        for (int i = 0; i < list2.size(); i++)
        {
            table[list2[i]].first++;
            table[list2[i]].second += i;
        }
        for (auto i : table)
        {
            if (i.second.first > 1)
            {
                if (i.second.second < minIndex)
                {
                    res.clear();
                    res.push_back(i.first);
                    minIndex = i.second.second;
                }
                else if (i.second.second == minIndex)
                    res.push_back(i.first);
            }
        }
        return res;
    }
};
// @lc code=end

[605] 种花问题

假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。

解题思路：首先定义一个函数，用于找到当前下标后第一个“1”的位置。

算法步骤：

• front记录的是当前1的位置。front从-2开始，是为了给第一段连续的0预留位置，即当第一段的情况是[0,0,1]时，第一个位置可以种花
• back是从front+1往后第一个1出现的位置
• 当back不为-1时，即当前位置后面还有1时，则执行循环
• 当back - front > 1时，则n -= ((back - front) / 2 - 1)
• 然后更新back和front
• 在最后判断尾部[1,0,0]的情况

/*
 * @lc app=leetcode.cn id=605 lang=cpp
 *
 * [605] 种花问题
 */

// @lc code=start
class Solution
{
public:
    int findOne(vector<int> &flowerbed, int pos)
    {
        for (int i = pos; i < flowerbed.size(); i++)
        {
            if (flowerbed[i] == 1)
                return i;
        }
        return -1;
    }

    bool canPlaceFlowers(vector<int> &flowerbed, int n)
    {
        int front = -2;
        int back = findOne(flowerbed, 0);
        while (back != -1)
        {
            if (back - front > 1)
                n -= ((back - front) / 2 - 1);
            front = back;
            back = findOne(flowerbed, front + 1);
        }
        if (front != flowerbed.size() - 1 && back == -1)
            n -= ((flowerbed.size() + 1 - front) / 2 - 1);
        return n <= 0;
    }
};
// @lc code=end

[606] 根据二叉树创建字符串

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

解题思路：由题意知道，当右子节点为空时，其空括号对可以省略。因此我们有以下处理：

• 若当前节点为空，则返回空串
• 若当前节点为叶子节点，则返回当前节点的值
• 若当前节点的右子节点为空，则返回当前节点的值和其左子节点递归
• 若左右子节点均不为空，则返回当前节点的值和其左右子节点递归

/*
 * @lc app=leetcode.cn id=606 lang=cpp
 *
 * [606] 根据二叉树创建字符串
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution
{
public:
    string tree2str(TreeNode *t)
    {
        if (t == NULL)
            return "";
        if (t->left == NULL && t->right == NULL)
            return to_string(t->val);
        if (t->right == NULL)
            return to_string(t->val) + "(" + tree2str(t->left) + ")";
        return to_string(t->val) + "(" + tree2str(t->left) + ")(" + tree2str(t->right) + ")";
    }
};
// @lc code=end

[617] 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL的节点将直接作为新二叉树的节点。

解题思路：由题意就可以很简单的知道：

• 当两个节点有一个为空或两者都为空时，则返回另外一个
• 当两个节点都不为空时，则将两个节点的值相加

同时递归遍历两棵树，用其中一棵树来储存结果，最后返回其根节点

/*
 * @lc app=leetcode.cn id=617 lang=cpp
 *
 * [617] 合并二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution
{
public:
    TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2)
    {
        if (t1 == NULL)
            return t2;
        if (t2 == NULL)
            return t1;
        t1->val += t2->val;
        t1->left = mergeTrees(t1->left, t2->left);
        t1->right = mergeTrees(t1->right, t2->right);
        return t1;
    }
};
// @lc code=end

[628] 三个数的最大乘积

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

解题思路：先排序，然后返回前两个和最后一个的乘积、最后三个的乘积的最大值。

/*
 * @lc app=leetcode.cn id=628 lang=cpp
 *
 * [628] 三个数的最大乘积
 */

// @lc code=start
class Solution
{
public:
    int maximumProduct(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int size = nums.size();
        return max(nums[0] * nums[1] * nums[size - 1], nums[size - 1] * nums[size - 2] * nums[size - 3]);
    }
};
// @lc code=end

[633] 平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 。

解题思路：若为可开平方数，则double(j) == int(j)

/*
 * @lc app=leetcode.cn id=633 lang=cpp
 *
 * [633] 平方数之和
 */

// @lc code=start
class Solution
{
public:
    bool judgeSquareSum(int c)
    {
        for (long i = 0; i * i <= c; i++)
        {
            double j = sqrt(c - i * i);
            if (j == int(j))
                return true;
        }
        return false;
    }
};
// @lc code=end

[637] 二叉树的层平均值

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.

解题思路：本题考查的是层次遍历，需要记录节点的高度。因此我们首先定义一个高度函数，并创建两个数组，一个res用于记录每一层的节点值的总和，一个count用于记录每一层的节点数。然后使用深度优先遍历节点，最后将res/count的值返回即可。

/*
 * @lc app=leetcode.cn id=637 lang=cpp
 *
 * [637] 二叉树的层平均值
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution
{
public:
    vector<double> averageOfLevels(TreeNode *root)
    {
        int h = height(root);
        vector<double> res(h);
        vector<int> count(h);
        DFS(root, 0, res, count);
        for (int i = 0; i < h; i++)
            res[i] /= count[i];
        return res;
    }

    int height(TreeNode *root)
    {
        if (root == NULL)
            return 0;
        return 1 + max(height(root->left), height(root->right));
    }

    void DFS(TreeNode *node, int height, vector<double> &res, vector<int> &count)
    {
        if (node == NULL)
            return;
        res[height] += node->val;
        count[height]++;
        DFS(node->left, height + 1, res, count);
        DFS(node->right, height + 1, res, count);
    }
};
// @lc code=end

[643] 子数组最大平均数 I

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

解题思路：首先计算前k项的和，记为sum。因为是连续子数组，因此从i=k开始遍历，每加上新一个元素，则需要减去子数组的第一个元素，res取当前值和最新值的最大者。

/*
 * @lc app=leetcode.cn id=643 lang=cpp
 *
 * [643] 子数组最大平均数 I
 */

// @lc code=start
class Solution
{
public:
    double findMaxAverage(vector<int> &nums, int k)
    {
        double sum = 0;
        for (int i = 0; i < k; i++)
            sum += nums[i];

        double res = sum;
        for (int i = k; i < nums.size(); i++)
        {
            sum += (nums[i] - nums[i - k]);
            res = max(res, sum);
        }
        return res / k;
    }
};
// @lc code=end