第一题
题目链接
题目简介
给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回 false 。
题目解析
- 模拟题目，对
mat数组进行四次90度旋转，来是否能和target一样
题目代码
class Solution { public boolean findRotation(int[][] mat, int[][] target) { for(int i = 0; i < 4; i++){ if(isSame(mat, target)){ return true; } xuan(mat); } return false; } public void xuan(int[][] mat){ int n = mat.length; for (int i = 0; i < n / 2; ++i) { for (int j = 0; j < (n + 1) / 2; ++j) { int temp = mat[i][j]; mat[i][j] = mat[n-1-j][i]; mat[n-1-j][i] = mat[n-1-i][n-1-j]; mat[n-1-i][n-1-j] = mat[j][n-1-i]; mat[j][n-1-i] = temp; } } } public boolean isSame(int[][] mat, int[][] target){ for(int i = 0; i < mat.length; i++){ for(int j = 0; j < mat[0].length; j++){ if(mat[i][j] != target[i][j]){ return false; } } } return true; } }
第二题
题目链接
题目简介
给你一个整数数组 nums ，你的目标是令 nums 中的所有元素相等。完成一次减少操作需要遵照下面的几个步骤：
- 找出 nums 中的 最大 值。记这个值为 largest 并取其下标 i （下标从 0 开始计数）。如果有多个元素都是最大值，则取最小的 i 。
- 找出 nums 中的
下一个最大值，这个值严格小于largest ，记为 nextLargest 。
- 将 nums[i] 减少到 nextLargest 。
返回使 nums 中的所有元素相等的操作次数。
题目解析
- 刚开始以为是个模拟题，模拟了一下，发现出现超时错误
- 后来发现规律：如数组nums[1,2,3,4,3,2]
- 将所有的4变成3，需要1次操作
- 将所有的3变成2，需要3次操作
- 再将所有的2变成1，需要5次操作
- 总共需要：1 + 3 + 5 = 8 次操作
- 所以，我们能找到一个规律：从最大值开始，依次进行减少，所以我们只需要枚举
最大~最小出现的次数，加起来就可以了
题目代码
class Solution { public int reductionOperations(int[] nums) { int[] num = new int[100000]; int min = 100000; int max = 0; for(int i = 0; i < nums.length; i++){ num[nums[i]]++; min = Math.min(min, nums[i]); max = Math.max(max, nums[i]); } int sum = 0; int cnt = 0; for(int i = max; i > min; i--){ if(num[i] != 0){ cnt += num[i]; sum += cnt; } } return sum; } }
第三题
题目链接
题目简介
给你一个二进制字符串 s 。你可以按任意顺序执行以下两种操作任意次：
- 类型 1 ：删除 字符串 s 的第一个字符并将它 添加 到字符串结尾。
- 类型 2 ：选择 字符串 s 中任意一个字符并将该字符 反转 ，也就是如果值为 ‘0’ ，则反转得到 ‘1’ ，反之亦然。
- 请你返回使 s 变成 交替 字符串的前提下， 类型 2 的 最少 操作次数 。
我们称一个字符串是 交替 的，需要满足任意相邻字符都不同。
- 比方说，字符串 “010” 和 “1010” 都是交替的，但是字符串 “0100” 不是。
题目解析
- 这个题目，一开始我使用的N^2的方法做的，发现超时，后来也没想到优化的办法
- 对于我们字符串来说，我们最后肯定要变成下方的样子
- 如果是偶数：
- 第一种情况：01010101
- 第二种情况：10101010
- 如果是奇数：
- 第一种情况：1010101
- 第二种情况：0101010
- 第三种情况：0100101
- 第四种情况：1011010
- 这四种情况我们使用滑动窗口来解决：
- 最原始的N^2的做法：每次进行删除后，重新计算当前字符串与目标串的不同位
- 置，最后返回一个
min
- 优化思路：我们想想，对于
当前字符串与目标串的不同位置可不可以通过O(1)的时间得到？我们可以想到，原字符串不断的进行删除放置末尾，也就相当于使用滑动窗口对于s+s进行遍历，如下图所示：
- 每次滑动窗口的大小都为：
s.length() - 每次滑动的距离为：1
- 在滑动的过程中，需要判断当前的值和目标值是否相等，若不等，则增加
- 当
i >= len，证明进入删除放置末尾的操作了，滑动的时候需要判断丢弃的元素是不是不等的 - 最后返回即可
题目代码
class Solution { public int minFlips(String str) { // 字符串的模式 // 01010101 // 10101010 int len = str.length(); String s = str + str; StringBuffer sb1 = new StringBuffer(); StringBuffer sb2 = new StringBuffer(); for(int i = 0; i < len; i++){ sb1.append("01"); sb2.append("10"); } int num1 = 0; int num2 = 0; int ans = 10000000; for(int i = 0; i < len * 2; i++){ if(s.charAt(i) != sb1.charAt(i)){ num1++; } if(s.charAt(i) != sb2.charAt(i)){ num2++; } if(i >= len){ if(s.charAt(i - len) != sb1.charAt(i-len)){ num1--; } if(s.charAt(i - len) != sb2.charAt(i-len)){ num2--; } ans = Math.min(ans, Math.min(num1, num2)); } } return ans; } }
