leetcode557-590

LeetCode 探索：发散你的思维

[557] 反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

解题思路：找到非空格字符和空格字符的位置

/*
 * @lc app=leetcode.cn id=557 lang=cpp
 *
 * [557] 反转字符串中的单词 III
 */

// @lc code=start
class Solution
{
public:
    string reverseWords(string s)
    {
        int front = s.find_first_not_of(' ', 0);
        int behind = s.find_first_of(' ', front);
        while (front != string::npos && behind != string::npos)
        {
            reverse(s.begin() + front, s.begin() + behind);
            front = s.find_first_not_of(' ', behind);
            behind = s.find_first_of(' ', front);
        }
        if (behind == string::npos)
            reverse(s.begin() + front, s.end());
        return s;
    }
};
// @lc code=end

[559] N叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

解题思路：根据二叉树的树高公式 1+depth(left)+depth(right) 即可推广出来。

/*
 * @lc app=leetcode.cn id=559 lang=cpp
 *
 * [559] N叉树的最大深度
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution
{
public:
    int maxDepth(Node *root)
    {
        if (root == NULL)
            return 0;
        int depth = 0;
        for (Node *child : root->children)
        {
            int d = maxDepth(child);
            if (d > depth)
                depth = d;
        }
        return 1 + depth;
    }
};
// @lc code=end

[561] 数组拆分 I

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), … , (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。

解题思路：先排序，然后取每一组的第一个即可

/*
 * @lc app=leetcode.cn id=561 lang=cpp
 *
 * [561] 数组拆分 I
 */

// @lc code=start
class Solution
{
public:
    int arrayPairSum(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = 0; i < nums.size(); i += 2)
        {
            sum += nums[i];
        }
        return sum;
    }
};
// @lc code=end

[563] 二叉树的坡度

给定一个二叉树，计算整个树的坡度。

一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。

整个树的坡度就是其所有节点的坡度之和。

解题思路：递归计算每一个节点的坡度，然后将其累加起来

/*
 * @lc app=leetcode.cn id=563 lang=cpp
 *
 * [563] 二叉树的坡度
 */

// @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:
    int tilt = 0;

    int calculate(TreeNode *node)
    {
        if (node == NULL)
            return 0;
        int L = calculate(node->left);
        int R = calculate(node->right);
        tilt += abs(L - R);
        return node->val + L + R;
    }

    int findTilt(TreeNode *root)
    {
        if (root == NULL)
            return 0;
        calculate(root);
        return tilt;
    }
};
// @lc code=end

[566] 重塑矩阵

在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。

给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。

重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。

如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

解题思路：先用一个数组将元素给储存起来，然后再进行重塑

/*
 * @lc app=leetcode.cn id=566 lang=cpp
 *
 * [566] 重塑矩阵
 */

// @lc code=start
class Solution
{
public:
    vector<vector<int>> matrixReshape(vector<vector<int>> &nums, int r, int c)
    {
        int size = nums.size() * nums[0].size();
        if (r * c != size)
            return nums;
        vector<int> arr;
        for (vector<int> row : nums)
            arr.insert(arr.end(), row.begin(), row.end());
        nums.clear();
        for (int i = 0; i < r; i++)
        {
            nums.push_back(vector<int>(arr.begin() + (i * c), arr.begin() + ((i + 1) * c)));
        }
        return nums;
    }
};
// @lc code=end

[572] 另一个树的子树

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

解题思路：先编写一个 equals(s, t) 函数用于递归判断以当前节点为根节点的二叉树是否相等，然后再遍历 s 的每一个节点即可。

/*
 * @lc app=leetcode.cn id=572 lang=cpp
 *
 * [572] 另一个树的子树
 */

// @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:
    bool equals(TreeNode *s, TreeNode *t)
    {
        if (s == NULL && t == NULL)
            return true;
        if (s == NULL || t == NULL)
            return false;
        return s->val == t->val && equals(s->left, t->left) && equals(s->right, t->right);
    }

    bool isSubtree(TreeNode *s, TreeNode *t)
    {
        return s != NULL && (equals(s, t) || isSubtree(s->left, t) || isSubtree(s->right, t));
    }
};
// @lc code=end

[575] 分糖果

给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

解题思路：由题意可知，妹妹最多可以分到的糖果不超过 n / 2 ，当种类数小于 n / 2 时，则将所有种类各分一个给妹妹即可。

/*
 * @lc app=leetcode.cn id=575 lang=cpp
 *
 * [575] 分糖果
 */

// @lc code=start
class Solution
{
public:
    int distributeCandies(vector<int> &candies)
    {
        set<int> category;
        for (int n : candies)
            category.insert(n);
        return min(candies.size() / 2, category.size());
    }
};
// @lc code=end

[581] 最短无序连续子数组

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

解题思路：拷贝该数组并排序，然后顺序查找第一个不同的元素并记录其下标即可。

/*
 * @lc app=leetcode.cn id=581 lang=cpp
 *
 * [581] 最短无序连续子数组
 */

// @lc code=start
class Solution
{
public:
    int findUnsortedSubarray(vector<int> &nums)
    {
        vector<int> temp(nums.begin(), nums.end());
        sort(temp.begin(), temp.end());
        int front = 0, back = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            if (temp[i] != nums[i])
            {
                front = i;
                break;
            }
        }
        for (int i = nums.size() - 1; i >= 0; i--)
        {
            if (temp[i] != nums[i])
            {
                back = i;
                break;
            }
        }
        return back == front ? 0 : back - front + 1;
    }
};
// @lc code=end

[589] N叉树的前序遍历

给定一个 N 叉树，返回其节点值的前序遍历。

/*
 * @lc app=leetcode.cn id=589 lang=cpp
 *
 * [589] N叉树的前序遍历
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution
{
public:
    vector<int> res;

    //递归算法
    vector<int> preorder(Node *root)
    {
        if (root != NULL)
        {
            res.push_back(root->val);
            for (Node *child : root->children)
                preorder(child);
        }
        return res;
    }

    //迭代算法
    vector<int> preorder(Node *root)
    {
        if (root == NULL)
            return res;
        stack<Node *> nodes;
        nodes.push(root);
        while (!nodes.empty())
        {
            Node *node = nodes.top();
            nodes.pop();
            res.push_back(node->val);
            vector<Node *> temp = node->children;
            for (int i = temp.size() - 1; i >= 0; i--)
            {
                if (temp[i] != NULL)
                    nodes.push(temp[i]);
            }
        }
        return res;
    }
};
// @lc code=end

[590] N叉树的后序遍历

给定一个 N 叉树，返回其节点值的后序遍历。

/*
 * @lc app=leetcode.cn id=590 lang=cpp
 *
 * [590] N叉树的后序遍历
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution
{
public:
    vector<int> res;

    //递归方法
    vector<int> postorder(Node *root)
    {
        if (root == NULL)
            return res;
        for (Node *child : root->children)
            postorder(child);
        res.push_back(root->val);
        return res;
    }

    //迭代方法
    vector<int> postorder(Node *root)
    {
        if (root == NULL)
            return res;
        stack<Node *> nodes;
        nodes.push(root);
        while (!nodes.empty())
        {
            Node *node = nodes.top();
            nodes.pop();
            res.insert(res.begin(), node->val);
            for (Node *child : node->children)
            {
                if (child != NULL)
                    nodes.push(child);
            }
        }
        return res;
    }
};
// @lc code=end