LeetCode100 刷题记录

本文主要是介绍LeetCode100 刷题记录，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

矩阵相关

1. 旋转矩阵

题目描述： 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
题解思路： 先将矩阵上下翻转，然后对矩阵进行对角线翻转。
题解代码：

class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n = matrix.size();// 使用两次反转，先上下翻转，后对角线翻转// 上下翻转for (int i = 0; i < (n / 2); i++) {for (int j = 0; j < n; j++) {swap(matrix[i][j], matrix[n-i-1][j]);}}// 对角线翻转for (int i = 0; i < n; i++) {for (int j = 0; j < i; j++) {swap(matrix[i][j], matrix[j][i]);}}}
};

关键结论：对于矩阵中的元素 $\text{matrix}[\text{row}][\text{col}]$，在旋转后，它的新位置为 ${\text{matrix}}_{\text{new}}[\text{col}][n-\text{row}-1]$ 。

---

2. 搜索二维矩阵

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

• 每行的元素从左到右升序排列。
• 每列的元素从上到下升序排列。
  
  题解思路： 由于每一行都是单调递增的，因此可以逐行使用二分查找，这样就可以将时间复杂度控制在$O(nlogm)$之内。
  题解代码：

class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(const auto&  row : matrix){auto it = lower_bound(row.begin(),row.end(),target);if( it != row.end() && *it == target){return true;}}return false;}
};

注意，需要先判断it != row.end()，再判断*it == target，否则，判断*it == target会不合法，导致未定义行为（Undefined Behavior, UB）

关于 lower_bound(StartIterator, EndIterator, Value)方法的使用：
StartIterator：范围开始的迭代器。
EndIterator：范围结束的迭代器。
Value：需要查找的值。

---

这篇关于LeetCode100 刷题记录的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---