leetcode刷题记录10（2023-06-30）【最大正方形(二维动态规划) | 翻转二叉树(二叉树递归) |二叉树的最近公共祖先(二叉树后序遍历) | 除自身以外数组的乘积(前缀/后缀乘积)】

我会带着你远行 2024-03-17 13:15 8阅读 0赞

## 221. 最大正方形 ##

在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

示例 1：

![在这里插入图片描述][60f73f2c942b497990ee08100e0f4a7e.png]

输入：matrix = \[\[“1”,“0”,“1”,“0”,“0”\],\[“1”,“0”,“1”,“1”,“1”\],\[“1”,“1”,“1”,“1”,“1”\],\[“1”,“0”,“0”,“1”,“0”\]\]  
输出：4  
示例 2：

![在这里插入图片描述][0d7c68d28bef4dbeba7f36382bd9293b.png]

输入：matrix = \[\[“0”,“1”\],\[“1”,“0”\]\]  
输出：1  
示例 3：

输入：matrix = \[\[“0”\]\]  
输出：0

提示：

m = = m a t r i x . l e n g t h m == matrix.length m==matrix.length  
 n = = m a t r i x \[ i \] . l e n g t h n == matrix\[i\].length n==matrix\[i\].length  
 1 < = m , n < = 300 1 <= m, n <= 300 1<=m,n<=300  
matrix\[i\]\[j\] 为 ‘0’ 或 ‘1’

这道题目的状态转移方程如下：

// 伪代码
    if (grid[i - 1][j - 1] == '1') {
        dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
    }

![在这里插入图片描述][3e850f71cb064b06a0b936e2d00d9a2a.png]

![在这里插入图片描述][cc5f3afdd6664f1fa1a456fd32129d0f.png]

参考自leetcode题解1。

#include<vector>
    #include<iostream>
    using namespace std;
    
    class Solution {
        
    public:
        int maximalSquare(vector<vector<char>>& matrix) {
        
            int m = matrix.size();
            int n = matrix[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1));
            int maximal = 0;
            for (int i = 1; i <= m; i++) {
        
                for (int j = 1; j <= n; j++) {
        
                    if (matrix[i - 1][j - 1] == '1') {
        
                        dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), 
                            dp[i - 1][j - 1]) + 1;
                        if (dp[i][j] > maximal) {
        
                            maximal = dp[i][j];
                        }
                    }                
                }
            }
            return maximal * maximal;
        }
    };
    
    int main() {
        
        vector<vector<char>> vec = {
         
            {
        '1', '0', '1', '0', '0'},
            {
        '1', '0', '1', '1', '1'}, 
            {
        '1', '1', '1', '1', '1'},
            {
        '1', '0', '0', '1', '0'} 
        };
        
        Solution sol;
        int res = sol.maximalSquare(vec);
        cout << res << endl;
    }

## 226. 翻转二叉树 ##

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = \[4,2,7,1,3,6,9\]  
输出：\[4,7,2,9,6,3,1\]  
示例 2：

![在这里插入图片描述][213404ec97a94abf809e4d9795424063.png]

输入：root = \[2,1,3\]  
输出：\[2,3,1\]

示例 3：

![在这里插入图片描述][a2e94f7043ee4f8ab297e47b99ec647d.png]

输入：root = \[\]  
输出：\[\]

提示：

树中节点数目范围在 \[0, 100\] 内  
\-100 <= Node.val <= 100

思路就是采用递归算法，翻转左子树，然后翻转右子树。

#include<iostream>
    using namespace std;
    
    // 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* invertTree(TreeNode* root) {
        
            if (root == nullptr) {
        
                return nullptr;
            }
            swap(root->left, root->right);
            invertTree(root->left);
            invertTree(root->right);
            return root;
        }
    };

## 236. 二叉树的最近公共祖先 ##

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

![在这里插入图片描述][d798e36d3c2e40c0b4efe70b8da69dc3.png]

输入：root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 1  
输出：3  
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

![在这里插入图片描述][d272da6755c14cb2beb62f52c2b57475.png]

输入：root = \[3,5,1,6,2,0,8,null,null,7,4\], p = 5, q = 4  
输出：5  
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = \[1,2\], p = 1, q = 2  
输出：1

提示：

树中节点数目在范围 \[2, 105\] 内。  
 − 1 0 9 < = N o d e . v a l < = 1 0 9 -10^9 <= Node.val <= 10^9 −109<=Node.val<=109  
所有 Node.val 互不相同 。  
p != q  
p 和 q 均存在于给定的二叉树中。

这道题很难想到，是一道后续遍历的题目，但是需要返回遍历的状态结果给父节点，然后父节点进行判断是否是 `lowestCommonAncestor`，如果是就记录下来。

官方给的题解写得就已经很清晰了：[https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/][https_leetcode.cn_problems_lowest-common-ancestor-of-a-binary-tree_solution_er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2]

// Definition for a binary tree node.
    struct TreeNode {
        
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {
        }
    };
    
    class Solution {
        
        TreeNode* ans;
    public:
        bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            if (root == nullptr) {
        
                return false;
            }
            bool lson = dfs(root->left, p, q);
            bool rson = dfs(root->right, p, q);
            if ((lson && rson) || (root->val == p->val || root->val == q->val) && (lson || rson)) {
        
                ans = root;
            }
    
            return lson || rson || (root->val == p->val || root->val == q->val);
        }
    
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            dfs(root, p, q);
            return ans;
        }
    };

## 238. 除自身以外数组的乘积 ##

给你一个整数数组 nums，返回 数组 answer ，其中 answer\[i\] 等于 nums 中除 nums\[i\] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:  
输入: nums = \[1,2,3,4\]  
输出: \[24,12,8,6\]

示例 2:  
输入: nums = \[-1,1,0,-3,3\]  
输出: \[0,0,9,0,0\]

提示：  
 2 < = n u m s . l e n g t h < = 1 0 5 2 <= nums.length <= 10^5 2<=nums.length<=105  
 − 30 < = n u m s \[ i \] < = 30 -30 <= nums\[i\] <= 30 −30<=nums\[i\]<=30  
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

又是一道一次就通过了的题目，主要采用前缀乘积，搞两个数组，一个作为前缀乘积，另一个作为后缀的乘积，最终的结果就是两个元素对应相乘。

复杂度为O(1)的做法其实也很简单，就是不要搞两个数组，取而代之的是搞两个变量，用这两个变量来代表当前位数左右两边的前缀和后缀乘积，但是这样后缀就要先做一遍乘法再做一遍除法，相当于用时间换空间。

![在这里插入图片描述][b1aecf5e19314976908a64e8df61dd88.png]

#include<vector>
    using namespace std;
    
    class Solution {
        
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
        
            vector<int> forward = vector<int>(nums.size(), 1);
            vector<int> backward = vector<int>(nums.size(), 1);
    
            for (int i = 1; i < nums.size(); i++) {
        
                forward[i] = forward[i - 1] * nums[i - 1];
            }
    
            for (int i = nums.size() - 2; i >= 0; i--) {
        
                backward[i] = backward[i + 1] * nums[i + 1];
            }
    
            vector<int> ans(nums.size());
            for (int i = 0; i < nums.size(); i++) {
        
                ans[i] = forward[i] * backward[i];
            }
    
            return ans;
        }
    };

--------------------

1.  [https://leetcode.cn/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/][https_leetcode.cn_problems_maximal-square_solution_li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle] ↩︎

[60f73f2c942b497990ee08100e0f4a7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/6662be91561147e6a3ba045450100e1a.png
[0d7c68d28bef4dbeba7f36382bd9293b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d37c5bde027f46c0a1c4f042617800a9.png
[3e850f71cb064b06a0b936e2d00d9a2a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9d2f6ed805a24725af2e10be70173fb7.png
[cc5f3afdd6664f1fa1a456fd32129d0f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d99e9dd1149446d3aaf963fbb6363b93.png
[213404ec97a94abf809e4d9795424063.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/9a8deb14e8904b73816aed1a8c5df5b3.png
[a2e94f7043ee4f8ab297e47b99ec647d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/67dfe340af8748b388d662047128332b.png
[d798e36d3c2e40c0b4efe70b8da69dc3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/7a3c4f1a3d0242d6900cdd2df6ed93ac.png
[d272da6755c14cb2beb62f52c2b57475.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3b5e2fcd077d4948abfdb10fe3c8754c.png
[https_leetcode.cn_problems_lowest-common-ancestor-of-a-binary-tree_solution_er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2]: https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/
[b1aecf5e19314976908a64e8df61dd88.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/44334a5deb7f4d3aa8bad60ed26f0f3a.png
[https_leetcode.cn_problems_maximal-square_solution_li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle]: https://leetcode.cn/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/