题目1:天弃之子
标题:天弃之子
时间限制: 3秒 内存限制: 262144k 语言限制:不限
有一款游戏,过关的方式是按按钮。游戏一共有几关,每一关有a[i]
个按钮,其中只有唯一一个按钮是可以通关的,按下其他的按钮游戏就会失败。
好在这个游戏可以重来,而且由于设计者的疏忽,每一关的通关按钮是不变的,所以你可以记住前几关的按钮,重来时就可以直接通关。
但是你的运气似乎用在了其他地方,你使用了最多的按按钮次数才成功通关。求这个最多的按按钮次数吧!
解题思路
题目提炼: 游戏共有n关,每一关有a[i]个按钮,其中只有一个可以过关,选择错误就会重新开开始,玩家可以通过试错记住正确的按钮。
问玩家运气最差时(每一.关都要试a[i]次才过关)共需要按多少次按钮才能通关。
这道题最重要的环节就是读懂题目,从题意中分析出:每一关都要试a[i]次。 之后就比较容易了。
对于每一关来说,都要进行a[i]-1
次失败
每次失败要先通过前面的i-1
关,再算上当前这关,需要按i
次按钮
所以往答案里累加(a[i]-1)*i
最后再算上最终成功的那一次,通过n关需要按n次按钮即可
代码(两种写法)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param buttons int整型一维数组
* @return long长整型
* 没有转long就会报错,所以一定要转。
*/
public long findMaxButtons (int[] buttons) {
// write code here
long count = 0;
for(int i =0;i<buttons.length;i++){
if(buttons[i]==1) {
count += 1;
continue;
}
else{
long tmp = (i+1)*(buttons[i]-1)+1;
count+=tmp;
}
}
return count;
}
}
public long findMinButtons2(int[] a){
long res = a.length;
for (int i = 0; i < a.length; i++) {
res+=(long) (a[i]-1)*(i+1);
}
return res;
}
题目2:刷墙
解题思路
思路:枚举+前缀和
前缀和不懂的可以看一下下图。
题目提炼:一个长度为n的01串,要把串变成某个位置及其左边全是1,右边全是0至少要修改几个字符
把【1,i】这个区间内的数全变成1的次数,等于这个区间内0的个数
把【i+1,n】这个区间内的数全变成0的次数,等于这个区间1的个数
所以我们只要去枚举每一位要转变的次数,取最小的那个值即可。
为了简化时间复杂度,我们可以预处理前缀和
s
u
m
[
i
]
sum[i]
sum[i]为
[
1
,
i
]
[1,i]
[1,i]中的个数
然后就可以在O(1)的时间复杂度内求出每个分界点要变化的数的个数,更新答案即可。
代码
import java.util.Scanner;
/**
* Author:Viper
* Data:2021/3/18
* description:
*/
public class shuaqiang {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
//开始连一个空格,使得s.charAt(0)为空,数组从1开始,方便计算。
String s = ' '+sc.next();
int[] sum = new int[n+1];
for (int i = 1; i <=n ; i++) {
sum[i]=sum[i-1]+s.charAt(i)-'0';
}
int res = n;
for(int i=0;i<=n;i++){
// [1,i]中0的个数为i-sum[i]
// [i+1, n]中‘1’的个数为sum[n]-sum[i]
res = Math.min(res,i-sum[i]+sum[n]-sum[i]);
}
}
}
题目3:胜者为王
标题:胜者为王
时间限制:1秒 内存限制: 262144k |语言限制:不限
小明,小王,小李三人正在进行一个游戏。游戏有n个回合,每个人都有一个字符串,三人的字符串长度相等。
每个回合他们必须更改自己字符串中的一个字母。最后每个人的分数是字自己的字符串中出现字符最多的字母的数量。
分数最高者获胜,输出获胜者名字,小明获胜输出xiaoming,小王获胜输出xiaowang,小李获胜输出xiaoli,如果有两个或者两个以上相同的最高分输出draw.
输出描述:输出一行一个字符串,表示游戏结果。
示例:
输入
7
treasurehunt
threefriends
hicodeforces
输出
xiaowang
解题思路
**题目提取:**三个人各自拥有一个字符串,他们的字符串长度相等,游戏进行n,回合,每回合每个人必须修改自己字符串中的一个字母,每个人最终得分是他字符串中出现次数最多的字母数量,判断谁最终得分最多。
本题可以采用贪心,选择每个人出现最多的一个字母,并且尽量将其他字母改为这个字母。
设出现次数最多的字母数量是X,再进行n回合,这个字母就可以有min(x+n,len)个
。
代码
import java.util.Arrays;
import java.util.Scanner;
/**
* Author:Viper
* Data:2021/3/18
* description:
*/
public class shengzheweiwang {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String a = sc.next();
String b = sc.next();
String c = sc.next();
int[] cnt = new int[256];
int x = 0, y = 0, z = 0;
for (int i = 0; i < a.length(); i++) {
x = Math.max(x, ++cnt[a.charAt(i)]);
}
Arrays.fill(cnt, 0);
for (int i = 0; i < a.length(); i++) {
y = Math.max(y, ++cnt[b.charAt(i)]);
}
Arrays.fill(cnt, 0);
for (int i = 0; i < a.length(); i++) {
z = Math.max(z, ++cnt[c.charAt(i)]);
}
int len = a.length();
x = Math.min(x + n, len);
y = Math.min(y + n, len);
z = Math.min(z + n, len);
if (x > y && x > z) System.out.println("xiaoming");
else if (y > x && y > z) System.out.println("xiaowang");
else if (z > x && z > y) System.out.println("xiaoli");
else System.out.println("draw");
}
}