1. 最大正方形【中等】

题目链接：https://leetcode.cn/problems/maximal-square/
参考题解：https://leetcode.cn/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/

1.1 题目描述

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

示例 1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4

示例 2：

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1

示例 3：

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

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 ‘0’ 或 ‘1’

1.2 解题思路

1.3 代码实现

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int num_rows = matrix.size();int num_cols = matrix[0].size();vector<vector<int>> dp(num_rows, vector<int>(num_cols));int maxLen = 0;for(int i = 0; i < num_rows; i++) {for(int j = 0; j < num_cols; j++) {if(matrix[i][j] == '1') {if(!i || !j)dp[i][j] = 1;elsedp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;maxLen = max(maxLen, dp[i][j]);}}}return maxLen * maxLen;}
};

2. 在排序数组中查找元素的第一个和最后一个位置【中等】

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
参考题解：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/

2.1 题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

2.2 解题思路

2.3 代码实现

class Solution {
public:int binarySearch(vector<int>& nums, int target, bool lower) {int len = nums.size();int left = 0, right = len - 1;int ans = len;while(left <= right) {int mid = (left + right) / 2;if(nums[mid] > target || (lower && nums[mid] >= target)) {ans = mid;right = mid - 1;}else left = mid + 1;}return ans;}vector<int> searchRange(vector<int>& nums, int target) {int left = binarySearch(nums, target, true);int right = binarySearch(nums, target, false) - 1;if(left <= right && nums[left] == target && nums[right] == target)return {left, right};return {-1, -1};}
};

3. 搜索二维矩阵 II【中等】

题目链接：https://leetcode.cn/problems/search-a-2d-matrix-ii/
参考题解：https://leetcode.cn/problems/search-a-2d-matrix-ii/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-5-4/

3.1 题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10^9 <= target <= 10^9

3.2 解题思路

3.3 代码实现

class Solution {
public:bool binarySearch(vector<int> nums, int target) {int left = 0, right = nums.size() - 1;while(left <= right) {int mid = (left + right) / 2;if(nums[mid] == target)return true;else if(nums[mid] < target)left = mid + 1;elseright = mid - 1;}return false;}bool searchMatrix(vector<vector<int>>& matrix, int target) {int num_rows = matrix.size();int num_cols = matrix[0].size();for(int i = 0; i < num_rows; i++) {if(matrix[i][0] > target)break;if(matrix[i][num_cols - 1] < target)continue;bool find = binarySearch(matrix[i], target);if(find)return true;}return false;}
};

4. 翻转二叉树【简单】

题目链接：https://leetcode.cn/problems/invert-binary-tree/
参考题解：https://leetcode.cn/problems/invert-binary-tree/solution/fan-zhuan-er-cha-shu-by-leetcode-solution/

4.1 题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

4.2 解题思路

4.3 代码实现

/*** 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)return root;TreeNode* leftSub = invertTree(root->left);TreeNode* rightSub = invertTree(root->right);root->right = leftSub;root->left = rightSub;return root;}
};

5. 最长连续序列【中等】

题目链接：https://leetcode.cn/problems/longest-consecutive-sequence/
参考题解：https://leetcode.cn/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/

5.1 题目描述

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

5.2 解题思路

5.3 代码实现

class Solution {
public:int longestConsecutive(vector<int>& nums) {int len = nums.size();unordered_set<int> hash;int maxLen = 0;for(int num : nums) {hash.insert(num);}for(int i = 0; i < len; i++) {int curLen = 0;if(!hash.count(nums[i] - 1)) {while(hash.count(nums[i]++)) {curLen++;}}maxLen = max(maxLen, curLen);}return maxLen;}
};