java算法题解牛客BM99顺时针旋转矩阵示例

目录
  • 题目描述
  • 解题思路
  • 实践代码
    • 解法1
    • 解法2

题目描述

BM99 顺时针旋转矩阵

描述 有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。 给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵。 数据范围：0<n<300，矩阵中的值满足0≤val≤1000

要求：空间复杂度 O(N^2)，时间复杂度 O(N^2) 进阶：空间复杂度 O(1)，时间复杂度 O(N^2)

示例1
输入：
[[1,2,3],[4,5,6],[7,8,9]],3
返回值：
[[7,4,1],[8,5,2],[9,6,3]]

解题思路

1.解法1：利用辅助数组，通过推导，我们知道每一位移动数字位置为：res[j][n-i-1] = mat[i][j];

2.解法2：我们观察，其实顺时针旋转90度，相等于，先按照做左对角线翻转数组，然后再按照列的中轴线翻转数组 实例分析：[[1,2,3],[4,5,6],[7,8,9]],3

实践代码

解法1

空间复杂度 O(N^2)，时间复杂度 O(N^2)

import java.util.*;
public class Solution {
	public int[][] rotateMatrix(int[][] mat, int n) {
		int[][] res = new int[n][n]; //辅助数组
		for (int i = 0; i < res.length; i++) {
			for (int j = 0; j < res.length; j++) {
				res[j][n-i-1] = mat[i][j];
			}
		}
		return res;
	}
}

解法2

空间复杂度 O(1)，时间复杂度 O(N^2)

import java.util.*;
public class Solution {
	public int[][] rotateMatrix(int[][] mat, int n) {
		//按照做左对角线翻转数组
		for (int i = 0; i < mat.length; i++) {
			for (int j = i; j < mat.length; j++) {
				int temp = mat[i][j];
				mat[i][j] = mat[j][i];
				mat[j][i] = temp;
			}
		}
		//再按照列的中轴线翻转数组
		for (int i = 0; i < mat.length / 2; i++) {
			for (int j = 0; j < mat.length; j++) {
				int temp = mat[j][i];
				mat[j][i] = mat[j][n - i - 1];
				mat[j][n - i - 1] = temp;
			}
		}
		return mat;
	}
}

以上就是java算法题解牛客BM99顺时针旋转矩阵示例的详细内容，更多关于java算法顺时针旋转矩阵的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • java算法题解LeetCode30包含min函数的栈实例

    目录 题目 解题思路 题目 剑指 Offer 30. 包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min.push 及 pop 的时间复杂度都是 O(1). 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop();

  • java算法题解LeetCode35复杂链表的复制实例

    目录 题目 示例 1: 示例 2: 示例 3: 示例 4: 解题思路 题目 AC 剑指 Offer 35. 复杂链表的复制请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 示例 1: 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • Go Java算法之从英文中重建数字示例详解

    目录 从英文中重建数字 Java实现 Go实现 从英文中重建数字 给你一个字符串 s ,其中包含字母顺序打乱的用英文单词表示的若干数字(0-9).按 升序 返回原始的数字. 示例 1: 输入:s = "owoztneoer" 输出:"012" 示例 2: 输入:s = "fviefuro" 输出:"45" 提示: 1 <= s.length <= 105 s[i] 为 ["e","g&

  • Java C++ 算法题解leetcode669修剪二叉搜索树示例

    Java C++ 算法题解leetcode669修剪二叉搜索树示例

    目录 题目要求 思路一:模拟迭代 Java C++ 思路二:递归 Java C++ Rust 题目要求 思路一:模拟迭代 依次判断每个节点是否合法: 首先找出结果的根,若原根小了就拉右边的过来,大了拉左边的过来做新根: 然后分别判断左右子树的大小,由于二叉搜索树的性质,子树只需要判断一边就好: 左子树判断是否>low,合法就向左下走,不合法往右下: 右子树判断是否<high,合法就向右下走,不合法往左下. Java class Solution { public TreeNode trimBS

  • Java C++题解leetcode字符串轮转KMP算法详解

    Java C++题解leetcode字符串轮转KMP算法详解

    目录 题目要求 思路一:双指针(模拟) Java C++ 思路二:子串 手写KMP Java dp C++ dp 调API Java C++ 总结 题目要求 思路一:双指针(模拟) Java class Solution { public boolean isFlipedString(String s1, String s2) { if (s1.length() != s2.length()) return false; int n = s1.length(); if (n == 0) retu

  • Java C++算法题解leetcode1592重新排列单词间的空格

    Java C++算法题解leetcode1592重新排列单词间的空格

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 模拟就完了 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int

  • Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可. Java class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i =

  • Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    Java C++ 算法题解leetcode145商品折扣后最终价格单调栈

    目录 题目要求 思路一:暴力模拟 Java C++ Rust 思路二:单调栈 Java C++ Rust 题目要求 思路一:暴力模拟 由于数据范围不算离谱,所以直接遍历解决可行. Java class Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] res = new int[n]; for (int i = 0; i < n; i++) { int discount = 0; fo

  • Java C++ 算法题解leetcode1608特殊数组特征值

    目录 题目要求 思路一:枚举 + 二分 Java C++ 思路二:二分枚举 Java C++ 思路三:倒序枚举 Java C++ 题目要求 思路一:枚举 + 二分 逐一枚举值域内的所有值,然后二分判断是否合法. Java class Solution { public int specialArray(int[] nums) { Arrays.sort(nums); int n = nums.length; for (int x = 0; x <= nums[n - 1]; x++) { //

  • Java C++算法题解leetcode801使序列递增的最小交换次数

    Java C++算法题解leetcode801使序列递增的最小交换次数

    目录 题目要求 思路:状态机DP 实现一:状态机 Java C++ Rust 实现二:滚动数组 Java C++ Rust 总结 题目要求 思路:状态机DP 实现一:状态机 Java class Solution { public int minSwap(int[] nums1, int[] nums2) { int n = nums1.length; int[][] f = new int[n][2]; for (int i = 1; i < n; i++) f[i][0] = f[i][1]

随机推荐