目录
一.拼正方形
1.题目
2.思路
首先把1x1的方块转换为2x2的方块，然后算出所有的2x2的方块，只需要对这个值求根即可，因为数据过大，剩余的几个方块可以忽略不计，最后乘以2即可(因为方块边长为2)
3.代码
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println(2717561*2);
scan.close();
}
}二.劲舞团
1.题目
2.思路
暴力枚举搜索即可，稍微有点麻烦的是数据处理，用一个二维的字符串数组来存储每条记录，在字符相等的前提下，找出时间相差1ms的连续数据的即可，需要注意的是k次正确敲击是k次连击，所以最后的结果需要加1
3.代码
public class text17 {
public static void main(String[] args) {
String[][] s = new String[10000][3];
Scanner scan = new Scanner(System.in);
int i = 0;
while(scan.hasNextLine()){
String p = scan.nextLine();
if(p.isEmpty()) break;
s[i++] = p.split(" ");
}
int max = 0;
int sum = 0;
for(int j = 1;j<2000;j++)
{
long tmp = Long.valueOf(s[j-1][2]);
if(s[j][0].equals(s[j][1]))
{
long temp = Long.valueOf(s[j][2]);
if(temp-tmp<=1000L)
{
sum++;
max = Math.max(sum,max);//这里的max实际上是k-1次连击
continue;
}
}
sum = 0;
}
System.out.println(max+1);
scan.close();
}
}
三.数组诗意
1.题目
2.思路
就是一道思维数学题，只有能找出规律就能写出来，找不到规律暴力求解只能通过30%，向这种大数据范围的数学题一般都有规律，我们先把满足题目要求的解小范围输出看看有没有什么规律，像这道题输出1000以内满足条件的数据就可以看出来只有是2的整数次幂的数字都不满足连续整数相加相等这个条件，所以只需要判断给的数据有多少个是2的整数次幂就可以
注:这里运用到了位运算，因为2的整数次幂的2进制表示只有一个1，x&(x-1)==0就是符合2的整数次幂的条件
eg:8 ->1000
7->0111
3.代码
public class Main {
public static int res;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
long[] a = new long[n];
for(int i = 0;i<n;i++)
{
a[i] = scan.nextLong();
if ((a[i] & (a[i] - 1)) == 0) {
res++;
}
}
System.out.println(res);
scan.close();
}
}四.封闭图形个数
1.题目
2.思路
本题就是考察排序，输入数据范围很大，用冒泡O(n*n)是肯定不能通过所有测试用例的，时间复杂度太高了，用Arrays提供的sort就可以(sort内部是快速排序O(nlogn))
先按照封闭个数排序，如果封闭个数相等就按数值排序
3.代码
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] res = {1,0,0,0,1,0,1,0,2,1};//分别对应数字1-9的封闭空间个数
//如果封闭空间个数相同,按数值大小比较
int[][] a = new int[n][2];
for(int i = 0;i<n;i++)
a[i][0] = scan.nextInt();
//思路:先按照封闭空间个数来排序，排序完再排数值大小
for(int i = 0;i<n;i++)
{
int tmp = a[i][0];
int sum = 0;
while(tmp>0)
{
int cnt = tmp % 10;
sum = sum + res[cnt];
tmp = tmp / 10;
}
if(a[i][0]==0) a[i][1] = 1;
else
a[i][1] = sum;//记录封闭个数
}
//已将全部数字的封闭个数处理完毕
Arrays.sort(a,(o1,o2)->o1[1]==o2[1] ? Integer.compare(o1[0],o2[0]) : Integer.compare(o1[1],o2[1]));
for(int i = 0;i<n;i++)
System.out.print(a[i][0]+" ");
scan.close();
}
}五.吊坠
1.题目
最小生成树问题，不会写哈，没学过这个
六.商品库存管理
1.题目
2.思路
看到区间修改，就应该想到前缀和与差分，将时间复杂度优化到O(1)
前缀和：设置一个数组，数组每个元素保存的是该下标前所有元素的和，通过sum[i]-sum[i-1]
可以得到第i个元素的值
差分：设置一个数组，数组每一个元素是该当前下标与前一个下标元素的差值，当对数组区间进行操作用差分时间复杂度低，差分数组的前缀和就是数组的值
eg:给[l,r]区间所有的数加1
只需要对差分数组d[l]++，d[r+1]--，即可
因为本题数据很大，暴力解法只能通过部分用例
3.代码
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[] a = new int[n+1];
int[] d = new int[n+2];
int[][] k= new int[m+1][2];
for(int i = 1;i<=m;i++)
{
k[i][0] = scan.nextInt();
k[i][1] = scan.nextInt();
d[k[i][0]]++;
d[k[i][1]+1]--;//更新差分数组
//如果不设置差分数组:每次操作都需要遍历一次时间复杂度为(遍历次数+操作次数)
}
int[] sum = new int[n+1];
sum[1] = d[1];
for(int i = 2;i<=n;i++)
sum[i] = sum[i-1] + d[i];//原数组
int res1 = 0;
for(int i = 1;i<=n;i++)
if(sum[i]==0) res1++;
for(int i = 1;i<=m;i++)
{
int left = k[i][0];
int right = k[i][1];
int res2 = 0;
for(int j = left;j<=right;j++)
{
if(sum[j]==1)
res2++;
}
System.out.println(res1+res2);
}
scan.close();
}
}七.挖矿
1.题目
2.思路
贪心问题+前缀和，首先我们要能想到挖矿的时候最多回头一次，或者不回头，符合贪心思想
通过前缀和数组来查询走到i距离时有多少个矿洞，用两个数组分别表示正负轴，但不能把0下标矿洞存储进去，要不然会重复计算0下标(有回头的情况)
3.代码
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int m = scan.nextInt();
int[] a1 = new int[1000001];
int[] a2 = new int[1000001];
int a0 = 0;
for(int i = 0;i<n;i++)
{
int cnt = scan.nextInt();
if(cnt>0)
a1[cnt]++;
if(cnt<0)
a2[-cnt]++;
if(cnt==0)
a0++;
}
int[] sum1 = new int[1000001];//前缀和数组
int[] sum2 = new int[1000001];
for(int i = 1;i<=1000000;i++)
{
sum1[i] = sum1[i-1] + a1[i];
sum2[i] = sum2[i-1] + a2[i];
}
int max = Math.max(sum1[m],sum2[m]);//一直向一个方向走
for(int i = 1;i<=1000000;i++)
{
if(m-2*i>0) {
max = Math.max(max, sum1[i] + sum2[m - 2 * i]);//走到i位置处回头
max = Math.max(max, sum2[i] + sum1[m - 2 * i]);
}
}
if(a0==1) max++;
System.out.println(max);
}
}八.回文字符串
1.题目
2.思路
就是kmp匹配算法，暴力就行了，数据范围很小
3.代码
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
scan.nextLine();
for(int k = 0;k<n;k++)
{
char[] s = scan.nextLine().toCharArray();
//首先判断是否是回文字符串
int left = 0;
int right = s.length-1;
boolean tmp = false;
while(left<=right)
{
if(s[left]==s[right])
{
left++;
right--;
}
else
{
if(s[left]=='l'||s[left]=='q'||s[left]=='b')
left++;
else if(s[right]=='l'||s[right]=='q'||s[right]=='b')
right--;
else
{
System.out.println("No");
tmp = true;
break;
}
}
}
if(tmp) continue;
else System.out.println("Yes");
}
scan.close();
}
}