文章目录
- 118. 小 y 删数字
- 119. 小红的字符串切割
- 120. 小红的数字匹配
- 115. 组装手机
- 116. 小欧的卡牌
- 111. 构造二阶行列式
- 112. 挑战boss
118. 小 y 删数字
题目描述
给定一个长度为 n 的数组,数组元素为 a1, a2, . . , an,每次能删除任意 a 的任意一位,求将所有数字变成 0 最少需要几步。
例如 103 若删除第 1 位则变成 3; 若删除第 2 位则变成13; 若删除第 3 位则变成 10。
输入描述
输入描述第一行一个正整数 n 代表数组长度。接下来一行 n 个数第 j 个数代表 a。
输出描述
输出一行一个数代表答案。
输入示例
5
10 13 22 100 30
输出示例
7
提示信息
数据范围:
1 ≤ n ≤ 10^5。 0 ≤ ai ≤ 10^9
就是找0的个数。
import java.util.*;
class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();String s = sc.nextLine();String[] nums = s.split(" ");int cnt = 0, len = 0;for(String num : nums){char[] ch = num.toCharArray();for(int i = 0; i < ch.length; i++){if(ch[i] == '0') cnt++;len++;}}System.out.println(len - cnt);}
}
119. 小红的字符串切割
题目描述
小红拿到了一个字符串,她希望你帮她切割成若干子串,满足以下两个条件:
1. 子串长度均为不小于 3 的奇数。
2. 子串内部的字符全部相同。
输入描述
第一行输入一个正整数n,代表字符串长度。第二行输入一个字符串,仅由小写字母组成。
输出描述
如果无解,请输出-1。否则按顺序输出若干个字符串,用空格隔开。
输入示例
11
aaabbbbbbbb
输出示例
aaa bbb bbbbb
提示信息
在样例中,长度为 8 的 bbb..b 子串在样例输出中被分为了 bbb 和 bbbbb,在只要满足题目给定的条件下,将其分为 bbbbb 和 bbb 也对。
也就是输出还可以为:
aaa bbbbb bbb
数据范围:
1 < n ≤ 200000
思路:利用left和right记录连续相同的字符串索引,计算长度len,如果是0,1,2,4这种情况直接输出-1并return。如果是奇数直接输出,如果是偶数的话,可以拆成3和len-3两个部分。
import java.util.*;
class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();String s = sc.nextLine();int left = 0, right = 1;String res = "";int count = 1;while(right < n){if(right < n && s.charAt(right) == s.charAt(left)){right++;}else{int len = right - left;if(len < 3 || len == 4){System.out.println("-1");return;}else{if(len % 2 != 0){String tempt = s.substring(left, right);res = res + tempt + " ";}else{String tempt1 = s.substring(left, left + 3);String tempt2 =s.substring(left + 3, right);res = res + tempt1 + " " + tempt2 + " ";}}left = right;right++;}}int len = right - left;if(len < 3 || len == 4){System.out.println("-1");return;}else {if(len % 2 != 0){res = res + s.substring(left, right);System.out.println(res);return;}else{res = res + s.substring(left, left + 3) + " ";res = res + s.substring(left + 3, right);System.out.println(res);return;}}}
}
120. 小红的数字匹配
题目描述
定义一个 “模板串“ 为一个由数字字符和 "?" 组成的字符串。
我们可以通过将问号替换成数字字符来得到正整数。
显然,一个模板串可能会和多个正整数匹配。
例如: "1?2"可以和 102 或者 132 等正整数匹配。
请注意,匹配的正整数不能包含前导零,例如"??1"可以匹配101,但不能匹配 001。
小红拿到了一个模板串,她想知道,和这个模板串匹配的正整数中,第 k 小的是多少?
输入描述
第一行输入一个正整数 t,代表询问次数。接下来的 2 * t 行,每两行为一次询问: 第一行输入一个字符串,仅由数字字符和 '?' 组成。第二行输入一个正整数 k,代表询问的是第 k 小。
输出描述
输出 t 行,每行输出一个答案。如果一共都没有k个匹配的正整数,则输出 -1。否则输出第小的匹配的正整数。
输入示例
4
??1
1
22?
100000000
2??
3
000???
1
输出示例
101
-1
202
-1
提示信息
数据范围: 1 ≤ t ≤ 10^4 1 ≤ k ≤ 10^9 字符串长度不超过 30。
思路:??11??的最小值是101100,求其第4554小即在从后数的四个问号位置分别加上‘3’,‘5’,‘5’,‘4’即可,即551153;
字符串可以直接加减,需要注意边界条件的判断,如果'1'+9
会导致答案变成':'
,所以需要判断if(ch[0] > '9'){//输出-1并继续循环}
。
import java.util.*;
class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();sc.nextLine();while(n > 0){String num = sc.nextLine();if(num.charAt(0) == '0'){System.out.println(-1);sc.nextLine();n--;continue;}int[] index = new int[num.length()];int cnt = 0;char[] ch = num.toCharArray();for(int i = 0; i < ch.length; i++){if(i == 0 && ch[i] == '?'){ch[i] = '1';index[cnt++] = i;}else if(ch[i] == '?'){ch[i] = '0';index[cnt++] = i;}}int k = Integer.parseInt(sc.nextLine());if(k == 1){String res = String.valueOf(ch);System.out.println(res);}else if(k > Math.pow(10, cnt)){System.out.println(-1);n--;continue;}else{int add = k - 1;while(cnt > 0){ch[index[--cnt]] += add % 10;add /= 10;}if (ch[0] > '9'){System.out.println(-1);n--;continue;}for(char c : ch){System.out.print(c);}System.out.println();}n--;}}
}
115. 组装手机
题目描述
小欧是手机外壳供应商,小蕊是手机零件供应商。
小欧已经生产了 n 个手机外壳,第 i 个手机外壳售价 ai 元,小蕊生产了 n 个手机零件,第 i 个手机零件售价 bi 元。
在组装手机中,一个手机外壳与一个手机零件可以组装成一个手机,手机的售价为手机外壳售价与手机零件售价之和。
他们需要选出一些外壳和零件,配对形成若干部手机,要求这些手机的售价全部相同。
小欧想知道他们最多可以组装多少部手机?
输入描述
第一行一个整数 n (1 <= n <= 1000)
第二行 n 个整数 ai (1 <= ai <= 1000)
第三行 n 个整数 bi (1 <= bi <= 1000)
输出描述
一行一个整数,表示最大数量。
输入示例
4
1 2 3 4
1 2 4 5
输出示例
3
利用set来存储所有可能的和,并且用map进行查询和结果的计算。在mapA里面查找x,再在mapB里面查找y,使得x+y=set[i]
,这就是基本思路。
import java.util.*;
class Main{public static void main (String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];int[] b = new int[n];Map<Integer, Integer> mapA = new HashMap<>();Map<Integer, Integer> mapB = new HashMap<>();for (int i = 0; i < n; i++) {a[i] = sc.nextInt();mapA.put(a[i], mapA.getOrDefault(a[i], 0) + 1);}for (int i = 0; i < n; i++) {b[i] = sc.nextInt();mapB.put(b[i], mapB.getOrDefault(b[i], 0) + 1);}Set<Integer> set = new HashSet<>();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {set.add(a[i]+b[j]);}}int res = 0;int temp = 0;for (int i : set) {Set<Integer> keysA = mapA.keySet();for (int j : keysA) {if (mapB.containsKey(i-j)) {temp += Math.min(mapA.get(j), mapB.get(i-j));}}res = Math.max(res, temp);temp = 0;}System.out.println(res);}
}
116. 小欧的卡牌
题目描述
小欧有 n 张卡牌,第 i 张卡牌的正面写了个数字 ai,背面写了个数字 bi。
小欧对于每张卡牌可以选择一面向上,她希望最终向上的数字之和为 3 的倍数。
你能告诉小欧有多少方案吗?由于答案过大,请对 10 ^ 9 + 7 取模.
输入描述
第一行输入一个正整数 n,代表卡牌数量。
接下来的 n 行,每行输入两个正整数 ai 和 bi,代表第 i 张卡牌的正面和背面的数字. 1 <= n <= 10^5 1 <= ai,bi <= 10^9
输出描述
一个整数,代表方案数对 10^9 + 7 取模的值
输入示例
3
1 2
2 3
3 2
输出示例
3
思路: d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i组卡牌组合之和对3取余后答案为 j j j的方案数(其中 j = 0 , 1 , 2 j=0,1,2 j=0,1,2)。而由于一张卡牌有两种组成方案,所以我们用 k k k来表示卡牌的正面和反面。
所以:先遍历卡牌数量,每次遍历卡牌时遍历可能的取余答案 j j j,最后还要遍历卡牌正反面。
而 s u m sum sum表示当前卡牌正面(或反面)加上上一个取余结果再对3取余的值,举个例子,比如说 c a r d s [ i − 1 ] [ 0 ] = 1 cards[i-1][0]=1 cards[i−1][0]=1,表示当前卡牌正面为1,当遍历的 j = 1 j=1 j=1时, s u m = 1 + 1 = 2 sum=1+1=2 sum=1+1=2,因此
d p [ i ] [ s u m ] = d p [ i − 1 ] [ j ] dp[i][sum]=dp[i-1][j] dp[i][sum]=dp[i−1][j]
即前 i i i组卡牌组合之和对3取余后答案为 s u m sum sum的方案数等于前 i − 1 i-1 i−1组卡牌组合之和答案为 j j j的方案数(因为还加上了自身,即sum=(j + cards[i-1][k]) % 3
),由于不同的取余方案搭配上正反面的组合,共有6中结果,所以在 m o d 3 \mod 3 mod3的意义上肯定免不了重复的问题,因此还需要将结果进行累加:
d p [ i ] [ s u m ] = d p [ i ] [ s u m ] + d p [ i − 1 ] [ j ] ) ; dp[i][sum] = dp[i][sum] + dp[i - 1][j]); dp[i][sum]=dp[i][sum]+dp[i−1][j]);
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int mod = 1000000007;int n = scanner.nextInt();int[][] cards = new int[n][2];for (int i = 0; i < n; i++) {cards[i][0] = scanner.nextInt();cards[i][1] = scanner.nextInt();}int[][] dp = new int[n + 1][3];dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j < 3; j++) {for (int k = 0; k < 2; k++) {int sum = (j + cards[i-1][k]) % 3;dp[i][sum] = (dp[i][sum] + dp[i - 1][j]) % mod;}}}System.out.println(dp[n][0]);}
}
111. 构造二阶行列式
题目描述
小欧希望你构造一个二阶行列式,满足行列式中每个数均为不超过 20 的正整数,且行列式的值恰好等于x。你能帮帮她吗?
输入描述
一个正整数x。-1000 <= x <= 1000
输出描述
如果无解,请输出-1。否则输出任意合法行列式即可(输出两行,每行输出两个不超过20的正整数)。
输入示例
2
输出示例
3 2
5 4
提示信息
输出:
3 4
7 10
也是满足条件的。
直接暴力搜索即可。最多也只是搜索20^4次
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();for (int a = 1; a <= 20; a++) {for (int b = 1; b <= 20; b++) {for (int c = a; c <= 20; c++) {for (int d = b; d <= 20; d++) {if(a * d - b * c == n){System.out.print(a + " " + b);System.out.println();System.out.print(c + " " + d);return;}}}}}System.out.println(-1);}
}
112. 挑战boss
题目描述
小欧正在一个回合制格斗游戏中挑战一个boss。已知游戏的0/3机制如下:
每回合小欧先手攻击boss,然后boss攻击小欧,此时1回合结束。
小欧有时可以闪避boss的攻击,当闪避成功时这回合将不受boss的伤害。
小欧攻击boss时可以攒“连击点”,她攻击造成的伤害为a+kb,其中a为基础攻击力,b为基础连击伤害,k为连击次数。
小欧每次攻击后会让连击次数加1,但当小欧受到伤害后会重置连击次数为0。
小欧想知道,她最终共对boss造成了多少伤害?
输入描述
第一行输入三个正整数n,a,b,代表回合的数量,小欧基础攻击力,小欧的基础连击伤害。
第二行输入一个长度为n的字符串,字符串仅由o和x组成,其中o代表本回合闪避成功,x代表本回合闪避失败。
1<=n,a,b<=10^5
输出描述
一个正整数,代表小欧造成的伤害总和。
输入示例
3 5 2
oxo
输出示例
17
提示信息
第一回合攻击,连击次数为0,造成5点伤害。攻击后连击次数变成1。小欧闪避成功。
第二回合攻击,连击次数为1,造成7点伤害。攻击后连击次数变成2,小欧闪避失败,连击次数为0。
第三回合攻击,连击次数为0,造成5点伤害。攻击后连击次数变成1。小欧闪避成功。
总共造成17点伤害。
阅读理解题,很简单。
import java.util.Scanner;
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int a = scanner.nextInt();int b = scanner.nextInt();scanner.nextLine();String s = scanner.nextLine();int res = 0, count = 0;for (int i = 0; i < n; i++) {if (i == 0){res += a;if (s.charAt(i) == 'o'){count++;}}else{res += a + b * count;if (s.charAt(i) == 'o'){count++;}else{count = 0;}}}System.out.println(res);}
}