071 【整数编码】
实现一种整数编码方法，使得待编码的数字越小，编码后所占用的字节数越小。
编码规则如下：
1、编码时7位一组，每个字节的低7位用于存储待编码数字的补码。
2、字节的最高位表示后续是否还有字节，置1表示后面还有更多的字节，置0表示当前字节为最后一个字节。
3、采用小端序编码，低位和低字节放在低地址上。
3、编码结果按16进制数的字符格式输出，小写字母需转换为大写字母。
输入描述:
输入的为一个字符串表示的非负整数
输出描述:
输出一个字符串，表示整数编码的16进制码流
示例1
输入
0
输出
00
说明
输出的16进制字符，不足两位的前面补0，如00、01、02。
示例2
输入
100
输出
64
说明
100的二进制表示为0110 0100，只需要一个字节进行编码；
字节的最高位置0，剩余7位存储数字100的低7位（110 0100），所以编码后的输出为64。
示例3
输入
1000
输出
E807
说明
1000的二进制表示为0011 1110 1000，至少需要两个字节进行编码；
第一个字节最高位置1，剩余的7位存储数字1000的第一个低7位（110 1000），所以第一个字节的二进制为1110 1000，即E8；
第二个字节最高位置0，剩余的7位存储数字1000的第二个低7位（000 0111），所以第一个字节的二进制为0000 0111，即07；
采用小端序编码，所以低字节E8输出在前，高字节07输出在后。
备注:
待编码的数字取值范围为[0, 1<<64 - 1]
public class ZT71 {
public static void main(String[] args) {
char[] arr = {'A','B','C','D','E','F','G','H','I','J','K','L',
'M','N','O','P','K','R','S','T','U','V','W','X','Y','Z'};
Scanner sc = new Scanner(System.in);
int input = sc.nextInt();//1000
String str = Integer.toBinaryString(input);//11 1110 1000
boolean flag = false;
StringBuilder sb = new StringBuilder();
while (str.length() > 0){//先找到低7位
if (str.length() > 7){
flag = true;
}else {//2进制不足7位时补0
flag = false;
int mid = 7 - str.length();
for (int i = 0; i < mid; i++) {
str = "0" + str;
}
}
String sub = str.substring(str.length() - 7);
str = str.substring(0,str.length() - 7);
if (flag){
sub = "1" + sub;
}else {
sub = "0" + sub;
}
String res = Integer.toHexString(Integer.parseInt(sub, 2));
if (res.length()<2){//16进制不足2位补0
res = "0" + res;
}
for (int i = 0; i < res.length(); i++) {
char ch = res.charAt(i);
if (ch>= 'a' && ch<= 'z'){
ch = arr[ch - 'a'];
}
sb.append(ch);
}
}
//每个字符如果是小写要转成大写
System.out.println(sb);
}
}
善用API之：string.toUpperCase() 直接将小写改成大写
072 【整数对最小和】
给定两个整数数组array1、array2，数组元素按升序排列。假设从array1、array2中分别取出一个元素可构成一对元素，现在需要取出k对元素，并对取出的所有元素求和，计算和的最小值
注意：两对元素如果对应于array1、array2中的两个下标均相同，则视为同一对元素。
输入描述:
输入两行数组array1、array2，每行首个数字为数组大小size(0 < size <= 100);
0 < array1[i] <= 1000
0 < array2[i] <= 1000
接下来一行为正整数k
0 < k <= array1.size() * array2.size()
输出描述:
满足要求的最小和
示例1
输入
3 1 1 2
3 1 2 3
2
输出
4
说明
用例中，需要取2对元素
取第一个数组第0个元素与第二个数组第0个元素组成1对元素[1,1];
取第一个数组第1个元素与第二个数组第0个元素组成1对元素[1,1];
求和为1+1+1+1=4，为满足要求的最小和
public class ZT72 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] str1 = sc.nextLine().split(" ");
String[] str2 = sc.nextLine().split(" ");
int count = Integer.parseInt(sc.nextLine());
List<Integer> list = new ArrayList<>();
for (int i = 0; i < str1.length; i++) {
for (int j = 0; j < str2.length; j++) {
list.add(Integer.parseInt(str1[i]) + Integer.parseInt(str2[j]));
}
}
Collections.sort(list);
int res = 0;
for (int i = 0; i < count; i++) {
res += list.get(i);
}
System.out.println(res);
}
}
073 【整型数组按个位值排序】
给定一个非空数组（列表），其元素数据类型为整型，请按照数组元素十进制最低位从小到大进行排序，十进制最低位相同的元素，相对位置保持不变。
当数组元素为负值时，十进制最低位等同于去除符号位后对应十进制值最低位。
输入描述:
给定一个非空数组，其元素数据类型为32位有符号整数，数组长度[1, 1000]
输出描述:
输出排序后的数组
示例1
输入
1,2,5,-21,22,11,55,-101,42,8,7,32
输出
1,-21,11,-101,2,22,42,32,5,55,7,8
public class ZT73 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] splits = sc.nextLine().split(",");
Map<Integer, List<Integer>> map = new HashMap<>();
for (int i = 0; i < splits.length; i++) {
int abs = Math.abs(Integer.parseInt(splits[i]));
int res = abs % 10;
List<Integer> list = map.getOrDefault(res, new ArrayList<>());
list.add(Integer.parseInt(splits[i]));
map.put(res,list);
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10; i++) {
List<Integer> list = map.get(i);
if (list!= null){
for (int j = 0; j < list.size(); j++) {
sb.append(list.get(j)).append(",");
}
}
}
sb.deleteCharAt(sb.length()-1);
System.out.println(sb);
}
}
074 【执行时长】
为了充分发挥GPU算力，需要尽可能多的将任务交给GPU执行，现在有一个任务数组，数组元素表示在这1秒内新增的任务个数且每秒都有新增任务，假设GPU最多一次执行n个任务，一次执行耗时1秒，在保证GPU不空闲情况下，最少需要多长时间执行完成
输入描述:
第一个参数为GPU一次最多执行的任务个数，取值范围[1, 10000]
第二个参数为任务数组长度，取值范围[1, 10000]
第三个参数为任务数组，数字范围[1, 10000]
输出描述:
执行完所有任务最少需要多少秒
示例1
输入
3
5
1 2 3 4 5
输出
6
说明
一次最多执行3个任务，最少耗时6s
示例2
输入
4
5
5 4 1 1 1
输出
5
说明
一次最多执行4个任务，最少耗时5s
public class ZT74 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int bing = Integer.parseInt(sc.nextLine());
int times = Integer.parseInt(sc.nextLine());
String[] inputs = sc.nextLine().split(" ");
int left = 0;
for (int i = 0; i < times; i++) {
int th = Integer.parseInt(inputs[i]);
left = Math.max(0,left + th - bing);
}
int res = times;
if (left % bing == 0){
res += left / bing;
}else {
res += left / bing + 1;
}
System.out.println(res);
}
}
075 【字符串变换最小字符串】
给定一个字符串s，最多只能进行一次变换，返回变换后能得到的最小字符串（按照字典序进行比较）。
变换规则：交换字符串中任意两个不同位置的字符。
输入描述:
一串小写字母组成的字符串s
输出描述:
按照要求进行变换得到的最小字符串
示例1
输入
abcdef
输出
abcdef
说明
abcdef已经是最小字符串，不需要交换
示例2
输入
bcdefa
bacdefa
输出
acdefb
aacdefb[abcdefa排序更大]
说明
a和b进行位置交换，可以等到最小字符串
备注:
s是都是小写字符组成
1<=s.length<=1000
public class ZT75 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
char[] chars = input.toCharArray();
Arrays.sort(chars);//最优解
String str = input;
for (int i = 0; i < input.length(); i++) {
if (chars[i] == input.charAt(i)) {
continue;
}else {
char aChar = chars[i];
int i1 = input.lastIndexOf(String.valueOf(aChar));
//i1 和i对调顺序即可
str = input.substring(0,i) + aChar + input.substring(i+1,i1) + input.charAt(i) + input.substring(i1+1);
break;
}
}
System.out.println(str);
}
}
076 【字符串分割】
给定一个非空字符串S，其被N个‘-’分隔成N+1的子串，给定正整数K，要求除第一个子串外，其余的子串每K个字符组成新的子串，并用‘-’分隔。对于新组成的每一个子串，如果它含有的小写字母比大写字母多，则将这个子串的所有大写字母转换为小写字母；反之，如果它含有的大写字母比小写字母多，则将这个子串的所有小写字母转换为大写字母；大小写字母的数量相等时，不做转换。
输入描述:
输入为两行，第一行为参数K，第二行为字符串S。
输出描述:
输出转换后的字符串。
示例1
输入
3
12abc-abCABc-4aB@
输出
12abc-abc-ABC-4aB-@
说明
子串为12abc、abCABc、4aB@，第一个子串保留，后面的子串每3个字符一组为abC、ABc、4aB、@，abC中小写字母较多，转换为abc，ABc中大写字母较多，转换为ABC，4aB中大小写字母都为1个，不做转换，@中没有字母，连起来即12abc-abc-ABC-4aB-@
示例2
输入
12
12abc-abCABc-4aB@
输出
12abc-abCABc4aB@
说明
子串为12abc、abCABc、4aB@，第一个子串保留，后面的子串每12个字符一组为abCABc4aB@，这个子串中大小写字母都为4个，不做转换，连起来即12abc-abCABc4aB@
public class ZT76 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = Integer.parseInt(sc.nextLine());
String[] split = sc.nextLine().split("-");
List<String> listStr = new ArrayList<>();
StringBuilder temp = new StringBuilder();
for (int i = 1; i < split.length; i++) {
temp.append(split[i]);
}
String tem = temp.toString();
while (tem.length()>0){
if (tem.length() >= count){//截取
listStr.add(tem.substring(0,count));
tem = tem.substring(count);
}else {
listStr.add(tem);
tem = "";
}
}
StringBuilder sb= new StringBuilder();
sb.append(split[0]).append("-");
for (int i = 0; i < listStr.size(); i++) {
String s1 = listStr.get(i);
sb.append(reBalance(s1)).append("-");
}
sb.deleteCharAt(sb.length() -1 );
System.out.println(sb);
}
private static String reBalance(String str){
int xiao = 0;
int da = 0;
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
if (ch>= 'a' && ch<= 'z'){
xiao++;
}else if (ch >= 'A' && ch <= 'Z'){
da++;
}
}
if (xiao > da ){
return str.toLowerCase();
}else if (da > xiao){
return str.toUpperCase();
}else {
return str;
}
}
}
077 【字符串加密】
给你一串未加密的字符串str，通过对字符串的每一个字母进行改变来实现加密，加密方式是在每一个字母str[i]偏移特定数组元素a[i]的量，数组a前三位已经赋值：a[0]=1,a[1]=2,a[2]=4。当i>=3时，数组元素a[i]=a[i-1]+a[i-2]+a[i-3]，
例如：原文 abcde 加密后 bdgkr，其中偏移量分别是1,2,4,7,13。
输入描述:
第一行为一个整数n（1<=n<=1000），表示有n组测试数据，每组数据包含一行，原文str（只含有小写字母，0<长度<=50）。
输出描述:
每组测试数据输出一行，表示字符串的密文
示例1
输入
1
xy
输出
ya
说明
第一个字符x偏移量是1，即为y，第二个字符y偏移量是2，即为a
示例2
输入
2
xy
abcde
输出
ya
bdgkr
说明
第二行输出字符偏移量分别为1、2、4、7、13
备注:
解答要求
时间限制：2000ms,内存限制：64MB
public class ZT77 {
private static int[] arrOff = new int[50];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int count = Integer.parseInt(sc.nextLine());
char[] arr = {'a','b','c','d','e','f','g','h','i','j','k','l','m',
'n','o','p','q','r','s','t','u','v','w','x','y','z'};
arrOff[0] = 1;
arrOff[1] = 2;
arrOff[2] = 4;
for (int i = 3; i < 50; i++) {
arrOff[i] = arrOff[i-1] + arrOff[i-2] + arrOff[i-3];
}
for (int i = 0; i < count; i++) {
System.out.println(handleStr(sc.nextLine(),arr));
}
}
public static String handleStr(String str,char[] arr){
StringBuilder sb = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
int offset = arrOff[i];
ch = arr[(ch -'a' + offset) % 26];
sb.append(ch);
}
return sb.toString();
}
}
078 【字符串筛选排序】
输入一个由n个大小写字母组成的字符串，按照Ascii码值从小到大的排序规则，查找字符串中第k个最小ascii码值的字母（k>=1），输出该字母所在字符串的位置索引(字符串的第一个字符位置索引为0）。
k如果大于字符串长度，则输出最大ascii值的字母所在字符串的位置索引，如果有重复的字母，则输出字母的最小位置索引。
输入描述:
第一行输入一个由大小写字母组成的字符串
第二行输入k，k必须大于0，k可以大于输入字符串的长度
输出描述:
输出字符串中第k个最小ascii码值的字母所在字符串的位置索引。k如果大于字符串长度，则输出最大ascii值的字母所在字符串的位置索引，如果第k个最小ascii码值的字母存在重复，则输出该字母的最小位置索引。
示例1
输入
AbCdeFG
3
输出
5
说明
根据ascii码值排序，第3个最小ascii码值的字母为F，F在字符串中的位置索引为5（0为字符串的第一个字母位置索引）
示例2
输入
fAdDAkBbBq
4
输出
6
说明
根据ascii码值排序，前4个字母为AABB ，由于B重复，则只取B的（第一个）最小位置索引6 ，而不是第二个B的位置索引8
public class ZT78 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.nextLine();
int turn = Integer.parseInt(sc.nextLine());
char[] chars = input.toCharArray();
Arrays.sort(chars);
char ch = ' ';
if (turn > chars.length){
ch = chars[chars.length-1];
System.out.println(input.lastIndexOf(String.valueOf(ch)));
}else {
ch = chars[turn-1];
System.out.println(input.indexOf(ch));
}
}
}
079 【字符串统计】
给定两个字符集合，一个为全量字符集，一个为已占用字符集。已占用的字符集中的字符不能再使用，要求输出剩余可用字符集。
输入描述:
1、输入为一个字符串，一定包含@符号。@前的为全量字符集，@后的字为已占用字符集。
2、已占用字符集中的字符一定是全量字符集中的字符。字符集中的字符跟字符之间使用英文逗号分隔。
3、每个字符都表示为字符加数字的形式，用英文冒号分隔，比如a:1，表示1个a字符。
4、字符只考虑英文字母，区分大小写，数字只考虑正整形，数量不超过100。
5、如果一个字符都没被占用，@标识仍然存在，例如a:3,b:5,c:2@
输出描述:
输出可用字符集，不同的输出字符集之间回车换行。
注意，输出的字符顺序要跟输入一致。不能输出b:3,a:2,c:2
如果某个字符已全被占用，不需要再输出。
示例1
输入
a:3,b:5,c:2@a:1,b:2
输出
a:2,b:3,c:2
说明
全量字符集为3个a，5个b，2个c。
已占用字符集为1个a，2个b。
由于已占用字符不能再使用，因此，剩余可用字符为2个a，3个b，2个c。
因此输出a:2,b:3,c:2
public class ZT79 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] split = sc.nextLine().split("@");
if (split.length<2){
System.out.println(split[0]);
return;
}
List<String> list = new ArrayList<>();
Map<String,Integer> map = new HashMap<>();
String[] full = split[0].split(",");
for (int i = 0; i < full.length; i++) {
String[] dan = full[i].split(":");
list.add(dan[0]);
map.put(dan[0],Integer.parseInt(dan[1]));
}
String[] used = split[1].split(",");
for (int i = 0; i < used.length; i++) {
String[] dan = used[i].split(":");
int fullCount = map.get(dan[0]);
if (fullCount > Integer.parseInt(dan[1])){
map.put(dan[0],fullCount - Integer.parseInt(dan[1]));
}else {
map.remove(dan[0]);
list.remove(dan[0]);
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < list.size(); i++) {
String tem = list.get(i);
int left = map.get(tem);
sb.append(tem).append(":").append(left).append(",");
}
sb.deleteCharAt(sb.length()-1);
System.out.println(sb);
}
}
080 【字符串序列判定】
输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。判定S是否是L的有效字串。
判定规则：S中的每个字符在L中都能找到（可以不连续），且S在Ｌ中字符的前后顺序与S中顺序要保持一致。（例如，S="ace"是L="abcde"的一个子序列且有效字符是a、c、e，而"aec"不是有效子序列，且有效字符只有a、e）
输入描述:
输入两个字符串S和L，都只包含英文小写字母。S长度<=100，L长度<=500,000。
先输入S，再输入L，每个字符串占一行。
输出描述:
S串最后一个有效字符在L中的位置。（首位从0开始计算，无有效字符返回-1）
示例1
输入
ace
babcde
输出
5
示例2
输入
fgh
abcde
输出
-1
public class ZT80 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String target = sc.nextLine();
String search = sc.nextLine();
int idx = 0;
for (int i = 0; i < target.length(); i++) {
char ch = target.charAt(i);
if (search.contains(String.valueOf(ch))){
int i1 = search.indexOf(String.valueOf(ch));
idx += i1;
search = search.substring(i1+1);
}else {
System.out.println(-1);
return;
}
}
System.out.println(idx + target.length() - 1);
}
}
