力扣解題報(bào)告
2022-08-22 06:25
LeetCode 48. 旋轉(zhuǎn)圖像
題目描述
?給定一個(gè) n × n 的二維矩陣 matrix 表示一個(gè)圖像。請(qǐng)你將圖像順時(shí)針旋轉(zhuǎn) 90 度。你必須在 原地 旋轉(zhuǎn)圖像，這意味著你需要直接修改輸入的二維矩陣。請(qǐng)不要 使用另一個(gè)矩陣來(lái)旋轉(zhuǎn)圖像。
48. 旋轉(zhuǎn)圖像
提示：
一、解題關(guān)鍵詞
二、解題報(bào)告
1.思路分析
方法一：
坐標(biāo)轉(zhuǎn)換問(wèn)題
先看提示，一定會(huì)使用rowLen 和colLen 也就意味著每個(gè)元素必須遍歷到
縱坐標(biāo)換到橫坐標(biāo)｜｜ colLen - i- 1 換成y坐標(biāo)
進(jìn)行元素復(fù)制 方法二：
方法一的基礎(chǔ)上聯(lián)想到交換值
?a = b;
?b = tmp;
方法三：交換行列
2.時(shí)間復(fù)雜度
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;
? ? ? ?//水平翻轉(zhuǎn)
? ? ? ?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;
? ? ? ? ? ?}
? ? ? ?}
? ? ? ?//對(duì)角線(xiàn)翻轉(zhuǎn)
? ? ? ?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.知識(shí)點(diǎn)
目標(biāo)值需要處理每一個(gè)元素，那一定會(huì)進(jìn)行遍歷到每一個(gè)元素進(jìn)行處理
總結(jié)
相同題目
xxx
LeetCode 101. 對(duì)稱(chēng)二叉樹(shù)
@TOC
題目描述
?給你一個(gè)二叉樹(shù)的根節(jié)點(diǎn) root ， 檢查它是否軸對(duì)稱(chēng)。
對(duì)稱(chēng)二叉樹(shù)提示：
? ?樹(shù)中節(jié)點(diǎn)數(shù)目在范圍 [1, 1000] 內(nèi)
? ?-100 <= Node.val <= 100
一、解題關(guān)鍵詞
二、解題報(bào)告
1.思路分析
遇到問(wèn)題，分析問(wèn)題的過(guò)程本身比解答問(wèn)題更重要
遞歸著眼解決當(dāng)前層的問(wèn)題，深入遞歸的事情讓程序做
當(dāng)前層需要幾個(gè)參數(shù)確定方式：由幾個(gè)需要操作比較的對(duì)象確定
2.時(shí)間復(fù)雜度
3.代碼示例
//一定可以用遞歸解答
? ?//根節(jié)點(diǎn)唯一 左子樹(shù) == 右子樹(shù)
? ?//可以廣度 也可以深度
? ?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);
? ?}
方法二：
? ?//迭代 迭代就是循環(huán)
? ?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.知識(shí)點(diǎn)
總結(jié)
相同題目
xxx
LeetCode 64. 102. 二叉樹(shù)的層序遍歷
@TOC
題目描述
?給你二叉樹(shù)的根節(jié)點(diǎn) root ，返回其節(jié)點(diǎn)值的 層序遍歷 。（即逐層地，從左到右訪(fǎng)問(wèn)所有節(jié)點(diǎn)）。
二叉樹(shù)的層序遍歷提示：
? ?樹(shù)中節(jié)點(diǎn)數(shù)目在范圍 [0, 2000] 內(nèi)
? ?-1000 <= Node.val <= 1000
一、解題關(guān)鍵詞
二、解題報(bào)告
1.思路分析
2.時(shí)間復(fù)雜度
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.知識(shí)點(diǎn)
總結(jié)
相同題目
xxx
本文使用?文章同步助手?同步
標(biāo)簽：
