算法题目整合5

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

思路：$dp[i][j]$表示前$i$组卡牌组合之和对3取余后答案为$j$的方案数（其中$j=0,1,2$）。而由于一张卡牌有两种组成方案，所以我们用$k$来表示卡牌的正面和反面。
所以：先遍历卡牌数量，每次遍历卡牌时遍历可能的取余答案$j$，最后还要遍历卡牌正反面。
而$sum$表示当前卡牌正面（或反面）加上上一个取余结果再对3取余的值，举个例子，比如说$cards[i-1][0]=1$，表示当前卡牌正面为1，当遍历的$j=1$时，$sum=1+1=2$，因此
$$dp[i][sum]=dp[i-1][j]$$
即前$i$组卡牌组合之和对3取余后答案为$sum$的方案数等于前$i-1$组卡牌组合之和答案为$j$的方案数（因为还加上了自身，即sum=(j + cards[i-1][k]) % 3），由于不同的取余方案搭配上正反面的组合，共有6中结果，所以在$\mathrm{mod}3$的意义上肯定免不了重复的问题，因此还需要将结果进行累加：
$$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);}
}