LeetCode.733.695.617.116(广度优先搜索&深度优先搜索)

今天的题目真滴难，一天都花在这上面，UE4都没碰

733.图像渲染

class Solution {
  public:
    int n, m, w;
    vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc, int newColor) {
        n = image.size();
        m = image[0].size();
        w = image[sr][sc];
        if (w != newColor) // 起点像素与新颜色值不同则以此为起点开始深搜
            DFS(image, sr, sc, newColor);
        return image;
        // 277/277 cases passed (8 ms)
        // Your runtime beats 74.59 % of cpp submissions
        // Your memory usage beats 90.95 % of cpp submissions (13.5 MB)
        //*运用两个函数，使用全局变量，就可以避免每次都要记录一下原颜色值，从而占用空间的情况

        /*if (newColor == image[sr][sc])
            return image;
        int oldColor = image[sr][sc];
        image[sr][sc] = newColor;
        if (sr > 0 && image[sr - 1][sc] == oldColor)
            floodFill(image, sr - 1, sc, newColor);
        if (sr < image.size() - 1 && image[sr + 1][sc] == oldColor)
            floodFill(image, sr + 1, sc, newColor);
        if (sc > 0 && image[sr][sc - 1] == oldColor)
            floodFill(image, sr, sc - 1, newColor);
        if (sc < image[sr].size() - 1 && image[sr][sc + 1] == oldColor)
            floodFill(image, sr, sc + 1, newColor);
        return image;*/
        // 277/277 cases passed (8 ms)
        // Your runtime beats 74.59 % of cpp submissions
        // Your memory usage beats 5.07 % of cpp submissions (14.3 MB)
    }
    void DFS(vector<vector<int>> &image, int x, int y, int c) {
        if (x < 0 || x >= n || y < 0 || y >= m || image[x][y] != w ||
            image[x][y] == c) // 退出条件：位置越界 或 当前像素与起始点不同 或 当前像素与新颜色相同
            return;
        image[x][y] = c;         // 渲染当前位置像素为新颜色值
        DFS(image, x + 1, y, c); // 深搜4个方向
        DFS(image, x - 1, y, c);
        DFS(image, x, y + 1, c);
        DFS(image, x, y - 1, c);
    }
};

695.岛屿的最大面积

class Solution {
  public:
    /*int maxsize = 0, size = 0, w, h;
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        w = grid.size() - 1;
        h = grid[0].size() - 1;
        for (int i = 0; i <= w; i++) {
            for (int j = 0; j <= h; j++) {
                if (grid[i][j]) {
                    dfs(grid, i, j);
                    maxsize = size > maxsize ? size : maxsize;
                    size = 0;
                }
            }
        }
        return maxsize;
    }
    void dfs(vector<vector<int>> &grid, int i, int j) {
        grid[i][j] = 0;
        size++;
        if (i < w && i > 0 && j < h && j > 0 && !grid[i - 1][j] && !grid[i + 1][j] && !grid[i][j - 1] &&
            !grid[i][j + 1])
            return;
        else {
            if (i < w && grid[i + 1][j])
                dfs(grid, i + 1, j);
            if (i > 0 && grid[i - 1][j])
                dfs(grid, i - 1, j);
            if (j < h && grid[i][j + 1])
                dfs(grid, i, j + 1);
            if (j > 0 && grid[i][j - 1])
                dfs(grid, i, j - 1);
        }
    }*/
    // 728/728 cases passed (12 ms)
    // Your runtime beats 92.55 % of cpp submissions
    // Your memory usage beats 51.2 % of cpp submissions (22.7 MB)
    //照猫画虎的本事还是可以的/thumb
    int maxAreaOfIsland(vector<vector<int>> &grid) {
        int m = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    m = max(dfs(grid, i, j), m);
                }
            }
        }
        return m;
    }
    int dfs(vector<vector<int>> &grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[0].size() || grid[i][j] == 0) {
            return 0;
        } //应该先判断越界再执行递归的==
        grid[i][j] = 0;
        int count = 1;
        count += dfs(grid, i + 1, j);
        count += dfs(grid, i - 1, j);
        count += dfs(grid, i, j + 1);
        count += dfs(grid, i, j - 1);
        return count;
    }
    // 728/728 cases passed (16 ms)
    // Your runtime beats 74.69 % of cpp submissions
    // Your memory usage beats 87.45 % of cpp submissions (22.5 MB)
};

617.合并二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
  public:
    TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2) {
        /*if (!root1 && !root2)
            return nullptr;
        TreeNode *root3 = new TreeNode((root1 ? root1->val : 0) + (root2 ? root2->val : 0),
                                       mergeTrees(root1 ? root1->left : nullptr, root2 ? root2->left : nullptr),
                                       mergeTrees(root1 ? root1->right : nullptr, root2 ? root2->right : nullptr));
        return root3;*/
        // 182/182 cases passed (44 ms)
        // Your runtime beats 16.36 % of cpp submissions
        // Your memory usage beats 6.98 % of cpp submissions (33.3 MB)
        /*return (!root1 && !root2)
                   ? nullptr
                   : new TreeNode((root1 ? root1->val : 0) + (root2 ? root2->val : 0),
                                  mergeTrees(root1 ? root1->left : nullptr, root2 ? root2->left : nullptr),
                                  mergeTrees(root1 ? root1->right : nullptr, root2 ? root2->right : nullptr));*/
        // 182/182 cases passed (28 ms)
        // Your runtime beats 91.49 % of cpp submissions
        // Your memory usage beats 6.3 % of cpp submissions (33.4 MB)
        //究极一行哈哈哈o(*≧▽≦)ツ┏━┓
        if (!root1 && !root2)
            return nullptr;
        if (root1)
            root1->val = (root1 ? root1->val : 0) + (root2 ? root2->val : 0);
        else
            root1 = new TreeNode((root1 ? root1->val : 0) + (root2 ? root2->val : 0));
        root1->left = mergeTrees(root1 ? root1->left : nullptr, root2 ? root2->left : nullptr);
        root1->right = mergeTrees(root1 ? root1->right : nullptr, root2 ? root2->right : nullptr);
        return root1;
        // 182/182 cases passed (32 ms)
        // Your runtime beats 77.91 % of cpp submissions
        // Your memory usage beats 83.79 % of cpp submissions (31.4 MB)
        //不需要使用第三个树，把第二个并到第一个上面就好了
    }
};

116.填充每个节点的下一个右侧节点指针

/*
// Definition for a Node.
class Node {
  public:
    int val;
    Node *left;
    Node *right;
    Node *next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node *_left, Node *_right, Node *_next) : val(_val), left(_left), right(_right), next(_next) {}
};
*/
//树是满的
class Solution {
  public:
    /*Node *connect(Node *root) {
        queue<Node *> Next;
        Next.push(root);
        int i = 0, n = 1;
        while (!Next.empty()) {
            if (++i == n * 2 - 1) {
                Next.push(nullptr);
                i--;
            }
            Node *temp = Next.front();
            Next.pop();
            if (temp) {
                if (temp->left)
                    Next.push(temp->left);
                if (temp->right)
                    Next.push(temp->right);
                temp->next = Next.front();
            } else {
                n *= 2;
            }
        }
        return root;
    }*/
    // 59/59 cases passed (16 ms)
    // Your runtime beats 86.7 % of cpp submissions
    // Your memory usage beats 23.51 % of cpp submissions (16.7 MB)
    //广搜可以借用队列和循环解决
    Node *connect(Node *root) {
        if (root == nullptr || root->left == nullptr)
            return root;
        if (root->left->next == nullptr)
            root->left->next = root->right;
        if (root->right->next == nullptr)
            root->right->next = root->next == nullptr ? nullptr : root->next->left;
        connect(root->left);
        connect(root->right);
        return root;
        // 59/59 cases passed (16 ms)
        // Your runtime beats 86.7 % of cpp submissions
        // Your memory usage beats 96.91 % of cpp submissions (16.2 MB)
        //有点穿针引线的意思感觉
    }
};