这次的周赛比上一次好了一点，A了两道题，但是也暴露了自己存在的其他问题——思考问题不够全面，比如第一题，错了3次才A，这个题并不难，就是太繁琐，每次都会出现一些小错误。。。罚时三次才通过。后面两个题没想起来，找时间补一下。
第一题
思路
思路其实很简单，就是分四种情况遍历矩阵target，分别存在以下四种情况：
- 顺序遍历；
- 由下向上，由左至右；
- 由右向左，由下向上；
- 由上向下，由右向左；
上述四种情况分别对应下图的四个方向（左、上、右、下），
因此可以分别得到如下的代码：
代码
class Solution {
public boolean findRotation(int[][] mat, int[][] target) {
int n = mat.length;
int sign = 0;
//不旋转 对应右
for (int i=0,c=n-1;i<n;i++,c--){//行
for (int j=0,r=n-1;j<n;j++,r--)//列
{
if (mat[i][j] != target[i][j])
{
sign=1;
break;
}
}
if (sign==1)
break;
}
if (sign == 0)
return true;
//右旋转90° 对应上
sign=0;
for (int i=0,c=n-1;i<n;i++,c--){//行
for (int j=0,r=n-1;j<n;j++,r--)//列
{
// System.out.println(target[r][i]);
if (mat[i][j] != target[r][i])
{
sign=1;
break;
}
}
if (sign==1)
break;
}
if (sign == 0)
return true;
//右旋转270° 对应下
sign=0;
for (int i=0,c=n-1;i<n;i++,c--){//行
for (int j=0,r=n-1;j<n;j++,r--)//列
{
// System.out.println(target[j][c]);
if (mat[i][j] != target[j][c])
{
sign=1;
break;
}
}
if (sign==1)
break;
}
if (sign == 0)
return true;
//右旋转180° 对应左
sign=0;
for (int i=0,c=n-1;i<n;i++,c--){//行
for (int j=0,r=n-1;j<n;j++,r--)//列
{
if (mat[i][j] != target[c][r])
{
sign=1;
break;
}
}
if (sign==1)
break;
}
if (sign == 0)
return true;
return false;
}
}
第二题
思路
第二题还是蛮简单的，一次就AC了。根据题意，可以简单理解为——把数组内所有的元素均变成最小值。
实现步骤可以简化为：
- 统计各类元素的数量；
- 根据题意可以知道，每次数组内的最大值都要变成第二大的数值，直至数组内元素全部相等，由此可以知道，假设数组内含n类元素，最大的元素先变成第二大的，然后变成第三大的。。。，因此最大的元素的对应值改变了n-1次，第二大的元素改变了n-2次。。依此类推，因此得到如下算法步骤和代码。
算法步骤：
- 统计数组内各种元素的个数，这里使用HashMap帮助存储和计数；
- 把HashMap的key放在一个数组key内，方便进行排序和使用；
- 把数组进行排序（从大到小或从小到大都可以，只不过使用时操作起来不同）；
- 根据之前所述
最大值改变了n-1次、第二大的值改变了n-2次。。。，所以得到最终的结果。
需要注意的一点，在进行数组内元素个数统计时，使用了如下代码
for (int i: nums){
int c = map.get(i)==null? 1:map.get(i)+1;
map.put(i,c);
}
而不是常见的
for (int i: nums)
map.put(i,map.getOrDefault(map.get(i),0)+1);
原因是：对输入示例[1,1,2,2,3]进行测试时发现，2的个数居然是3，进行调试中发现，2的个数是从1，经过map.put(i,map.getOrDefault(map.get(i),0)+1)后直接变为3，怎么调试都不对，至今也不知道为什么。。。所以只能使用上面的代码先获取具体的值，然后赋值。
代码
class Solution {
public int reductionOperations(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
int ans = 0;
for (int i: nums){
int c = map.get(i)==null? 1:map.get(i)+1;
map.put(i,c);
}
int[] key = new int[map.size()];
int j = 0;
for (int i : map.keySet()){
key[j] = i;
j++;
}
Arrays.sort(key);
for (int i=1;i<map.size();i++)
{
ans += map.get(key[i]) * i;
}
return ans;
}
}
第三题
思路
因为前面两个题卡的时间比较久，所以没来的及做这个题。
首先简单分析以下，因为数据的范围是10的5次方，所以只能使用时间复杂度为O(n)的算法，也就是说代码中不能出现嵌套循环。
因为涉及到多情况，所以一般使用动态规划来做，而使用dp，关键是状态转移方程。
根据暴力方法的思路，可以得到动态规划方法的思路：
- 根据题意分析，最终得到的一定是形如
101010...或010101....的结果；类型一：删除的操作可以通过两个字符串相加，然后借助滑动窗口的思想来模拟实现； - 状态转移方程为：
当得到结果形如101010...时， d p 1 [ i ] = s s . c h a r A t ( i ) = = ′ 1 ′ ? d p 1 [ i − 1 ] : d p 1 [ i − 1 ] + 1 ; dp1[i] = ss.charAt(i) == '1'?dp1[i-1]:dp1[i-1]+1; dp1[i]=ss.charAt(i)==′1′?dp1[i−1]:dp1[i−1]+1;
当得到结果形如010101...时， d p 2 [ i ] = s s . c h a r A t ( i ) = = ′ 0 ′ ? d p 2 [ i − 1 ] : d p 2 [ i − 1 ] + 1 ; dp2[i] = ss.charAt(i) == '0'?dp2[i-1]:dp2[i-1]+1; dp2[i]=ss.charAt(i)==′0′?dp2[i−1]:dp2[i−1]+1; - 因为状态转移方程是用来维护前i个元素为
101010...或010101...的，所以当索引i为奇数和偶数时，状态转移方程有所不同：
如果i是偶数：
当得到结果形如101010...时， d p 1 [ i ] = s s . c h a r A t ( i ) = = ′ 1 ′ ? d p 1 [ i − 1 ] : d p 1 [ i − 1 ] + 1 ; dp1[i] = ss.charAt(i) == '1'?dp1[i-1]:dp1[i-1]+1; dp1[i]=ss.charAt(i)==′1′?dp1[i−1]:dp1[i−1]+1;
当得到结果形如010101...时， d p 2 [ i ] = s s . c h a r A t ( i ) = = ′ 0 ′ ? d p 2 [ i − 1 ] : d p 2 [ i − 1 ] + 1 ; dp2[i] = ss.charAt(i) == '0'?dp2[i-1]:dp2[i-1]+1; dp2[i]=ss.charAt(i)==′0′?dp2[i−1]:dp2[i−1]+1;
如果i是奇数
当得到结果形如101010...时， d p 1 [ i ] = s s . c h a r A t ( i ) = = ′ 0 ′ ? d p 1 [ i − 1 ] : d p 1 [ i − 1 ] + 1 ; dp1[i] = ss.charAt(i) == '0'?dp1[i-1]:dp1[i-1]+1; dp1[i]=ss.charAt(i)==′0′?dp1[i−1]:dp1[i−1]+1;
当得到结果形如010101...时， d p 2 [ i ] = s s . c h a r A t ( i ) = = ′ 1 ′ ? d p 2 [ i − 1 ] : d p 2 [ i − 1 ] + 1 ; dp2[i] = ss.charAt(i) == '1'?dp2[i-1]:dp2[i-1]+1; dp2[i]=ss.charAt(i)==′1′?dp2[i−1]:dp2[i−1]+1;
- 以
101010...的情况为例，奇数索引位置的值为1时、偶数索引位置的值为0时，不需要进行取反，不满足上述情况的话则次数加1，所以分情况对索引位置的值进行判断。
代码
暴力划动窗口，因为时间复杂度为O(n*n)一定会超时，这里放一下方便想后面的思路
public int minFlips(String s) {
int ans = Integer.MAX_VALUE;
int len = s.length();
String ss = s+s;//使用两个字符串相加，来模拟类型1的变换，并获取所有可能的情况
int sign = 1;
for (int i = 0;i<len;i++)
{
int cur = 0;
sign = 1;
for (int j=i;j<i+len;j++)
{
if ((sign==1 && ss.charAt(j) == '0') || (sign==-1 && ss.charAt(j) == '1'))
cur++;
sign *= (-1);
}
ans = Math.min(ans, cur);
sign = -1;
for (int j=i;j<i+len;j++)
{
if ((sign==1 && ss.charAt(j) == '0') || (sign==-1 && ss.charAt(j) == '1'))
cur++;
sign *= (-1);
}
ans = Math.min(ans, cur);
}
return ans;
}
动态规划
public int minFlips(String s) {
int len = s.length();
String ss = s+s;
int[] dp1 = new int[len*2];
int[] dp2 = new int[len*2];
//判断1010的情况
dp1[0] = ss.charAt(0) == '1'?0:1;
//判断0101的情况
dp2[0] = ss.charAt(0) == '0'?0:1;
for (int i=1;i<len*2;i++)
{
if (i%2==0){
dp1[i] = ss.charAt(i) == '1'?dp1[i-1]:dp1[i-1]+1;
dp2[i] = ss.charAt(i) == '0'?dp2[i-1]:dp2[i-1]+1;
}
else
{
dp1[i] = ss.charAt(i) == '0'?dp1[i-1]:dp1[i-1]+1;
dp2[i] = ss.charAt(i) == '1'?dp2[i-1]:dp2[i-1]+1;
}
}
int a=Integer.MAX_VALUE,b=Integer.MAX_VALUE;
for (int j=0;j<len;j++){
a = Math.min(dp1[j+len]-dp1[j], a);
b = Math.min(dp2[j+len]-dp2[j], b);
}
return Math.min(a,b);
}
第四题
思路
有时间的话再补。。