力扣解题报告
2022-08-22 06:25
LeetCode 48. 旋转图像
题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
48. 旋转图像
提示：
一、解题关键词
二、解题报告
1.思路分析
方法一：
坐标转换问题
先看提示，一定会使用rowLen 和colLen 也就意味着每个元素必须遍历到
纵坐标换到横坐标｜｜ colLen - i- 1 换成y坐标
进行元素复制 方法二：
方法一的基础上联想到交换值
a = b;
b = tmp;
方法三：交换行列
2.时间复杂度
3.代码示例
方法一：
int rowlen = matrix.length;
int colLen = matrix[0].length;
int[][] newMatrix = new int[rowlen][colLen];
for(int i = 0;i < rowlen;i++){
for(int j = 0;j < colLen;j++){
//原地修改
newMatrix[j][colLen - i - 1] = matrix[i][j];
}
}
for(int i = 0;i < rowlen;i++){
for(int j = 0; j < colLen;j++){
matrix[i][j] = newMatrix[i][j];
}
}
}
方法二：
int rowLen = matrix.length;
int colLen = matrix[0].length;
for(int i = 0; i < rowLen / 2;++i){
for(int j = 0;j < (colLen + 1) / 2;++j){
int tmp = matrix[i][j];
matrix[i][j] = matrix[colLen - j - 1][i];
matrix[colLen - j - 1][i] = matrix[colLen - i - 1][colLen - j - 1];
matrix[colLen - i - 1][colLen - j - 1] = matrix[j][colLen - i - 1];
matrix[j][colLen - i - 1] = tmp;
}
}
}
方法三：
int rowLen = matrix.length;
int colLen = matrix.length;
//水平翻转
for(int i = 0; i < rowLen / 2;++i){
for(int j = 0; j < rowLen;++j){
int tmp = matrix[i][j];
matrix[i][j] = matrix[rowLen - i - 1][j];
matrix[rowLen - i - 1][j] = tmp;
}
}
//对角线翻转
for(int i = 0; i < rowLen;++i){
for(int j = 0;j < i;++j){
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}
}
2.知识点
目标值需要处理每一个元素，那一定会进行遍历到每一个元素进行处理
总结
相同题目
xxx
LeetCode 101. 对称二叉树
@TOC
题目描述
给你一个二叉树的根节点 root ， 检查它是否轴对称。
对称二叉树提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
一、解题关键词
二、解题报告
1.思路分析
遇到问题，分析问题的过程本身比解答问题更重要
递归着眼解决当前层的问题，深入递归的事情让程序做
当前层需要几个参数确定方式：由几个需要操作比较的对象确定
2.时间复杂度
3.代码示例
//一定可以用递归解答
//根节点唯一 左子树 == 右子树
//可以广度 也可以深度
public boolean isSymmetric(TreeNode root) {
return root == null? true :dfs(root.left,root.right);
}
boolean dfs(TreeNode left,TreeNode right){
if(left == null && right == null){
return true;
}
if(left == null || right == null || left.val != right.val){
return false;
}
return dfs(left.left,right.right) &&dfs(left.right,right.left);
}
方法二：
//迭代 迭代就是循环
public boolean isSymmetric(TreeNode root) {
return bfs(root,root);
}
boolean bfs(TreeNode left,TreeNode right){
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(left);
queue.offer(right);
while(!queue.isEmpty()){
left = queue.poll();
right = queue.poll();
if(left == null && right == null){
continue;
}
if((left == null || right == null) || (left.val != right.val)){
return false;
}
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
2.知识点
总结
相同题目
xxx
LeetCode 64. 102. 二叉树的层序遍历
@TOC
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。
二叉树的层序遍历提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
一、解题关键词
二、解题报告
1.思路分析
2.时间复杂度
3.代码示例
public List<List<Integer>> levelOrder(TreeNode root) {
if (null == root) {
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> levelList = new ArrayList<>();
for (int i = 0; i < size; ++i) {
TreeNode node = queue.poll();
levelList.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(levelList);
}
return result;
}
2.知识点
总结
相同题目
xxx
本文使用 文章同步助手 同步
