od笔试记录
笔试回顾总结
- 一 最小字典序
- 二 第k长的连续子串的长度
- 三 两个人均分积木重量
一 最小字典序
问题：给定一个字符串（仅包含小写字母），只允许交换一次两个任意位置的字符，输出这样交换的最小的字符串。
要求：仅允许一次交换
100%通过。
输入：
abcdfe
输出：
abcdef
输入：
aaaafhd
输出：
aaaadhf
思路：将字符串分为字符数组进行排序，将排序后的数组与原数组对比，出现不同时就是交换的下标，首相更新的那个钱下表为排序后当前下标的字符，关键是和那个位置的字符交换，因为是和排序后的字符比较，所以要交换的字符肯定大于原字符串中当前下标的字符，所以为了使得字符串的字典序最小（从左到右字母依次变大），要从字符串末位开始寻找（这里让我头疼了半天）。
package HuaWeiOD;
import java.util.Arrays;
import java.util.Scanner;
/**
* @ClassName Problem11
* @Description TODO
* @Author shenxinyuan
* @Date 2022/8/27 $ {TIME}
* @Version 1. 0
**/
public class Problem1 {
//100%
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
String str = scan.next();
char[] chars = new char[str.length()];
char[] ret = new char[str.length()];
for (int i = 0; i < str.length(); i++) {
chars[i] = str.charAt(i);
ret[i] = str.charAt(i);
}
Arrays.sort(chars); //最小字典序 chars
for (int i = 0; i < ret.length; i++) {
if (ret[i] != chars[i]) {
char tmp = ret[i];
ret[i] = chars[i];
for(int j =ret.length-1;j>=i+1;j--){ //很关键 要倒序寻找那个字符，保证一次交换的情况下整个串的字典序是最小
if(ret[j] == chars[i]){
ret[j] = tmp;
break;
}
}
break;
}
}
for(int i =0;i<ret.length;i++){
System.out.print(ret[i]);
}
}
}
二 第k长的连续子串的长度
这个题目仅仅通过了70%
问题：给定一个字符串，字符串（仅包含大写字母）中存在有相同字符的连续字串，再输入一个数字k，输出字符串中第k长的有重复字符的字串长度。
要求：同一个字母值计算呢一个重复字串的最大长度。还有，如果k的值大于含有重复字符的字串的数量，输出-1。
输入：
AAAAHHHBBCDHHHH
3
输出：
2
解释：
H字符出现了两个字串，仅计算最长的长度4，长度为3的字串跳过，因此结果为BB串，长度为2
思路：用字符数组记录包含重复字符的最长字串的长度（每一个字母只能记录最长字串长度的数值），最后排序，输出对应第k大的字串长度
package HuaWeiOD;
/**
* @ClassName Problem22
* @Description TODO
* @Author shenxinyuan
* @Date 2022/8/27 $ {TIME}
* @Version 1. 0
**/
import java.util.*;
public class Problem22 {
//70%
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int[] arr = new int[90];
String str = scan.next();
int k = scan.nextInt();
int tmp = 1;
arr[str.charAt(0)]++;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == str.charAt(i - 1)) {
tmp++;
} else {
tmp = 1;
}
//以下代码块每次循环都执行 也许是这里导致剩余的30用例没有通过
{
if (arr[str.charAt(i)] != 0) {
//如果是相同字母，更新长度
arr[str.charAt(i)] = Math.max(tmp, arr[str.charAt(i)]);
} else {
//没有出现过最长连续字串，直接记录
arr[str.charAt(i)] = tmp;
}
}
}
int num = 0; //记录字串数目
for (int i = 0; i < arr.length; i++) {
if (arr[i] > 0) {
num++;
}
}
//升序
Arrays.sort(arr);
System.out.println(num >= k ? arr[arr.length - k] : -1);
}
}
三 两个人均分积木重量
没来得及调试通过。自测符合预期。
问题：koko和它的兄弟的积木重量必须一样，否则koko会哭泣，按照koko的理解两个数字的加法为：两个数字的二进制对应相加的过程中不计权重（也就是每一位符合异或的计算方法）。例如：5 + 6 =11
koko的计算方式为
0101
+ 0110
= 0011 (十进制的3，也就是koko认为5+6=3)
要求：koko认为两个人的积木重量“相同”的情况下，另一个人可以获得的最大重量
输入：
3
3 5 6
输出：
11
解释：
koko认5+6“等于”3,此时koko拿3个，另一个人那5+6实际上是11个，输出结果为11
思路：首先要实现新的koko的计算方式，plus方法实现如下。然后要计算给定数组的全部子集，buildSubSet实现方法如下。在遍历全部子集比较记录koko认为重量相同的情况下：它的兄弟可获得的最大的实际重量。
package HuaWeiOD;
/**
* @ClassName Problem3
* @Description TODO
* @Author shenxinyuan
* @Date 2022/8/27 $ {TIME}
* @Version 1. 0
**/
import com.sun.org.apache.xpath.internal.operations.Plus;
import org.junit.Test;
import java.lang.reflect.Array;
import java.util.*;
import static HuaWeiOD.ZiJi.buildSubSet;
public class Problem3 {
/* 测试用例：
输入：
3
3 5 6
输出：
11
5 + 6 = 11
但是koko认为 5+6=3 认为两个人的重量“相同”的情况下11最大
*/
//相当于按照新的加法运算方式，计算最大的分段和
public static void main(String args[]) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] arr = new int[n];
for(int i =0;i<n;i++){
arr[i] = scan.nextInt();
}
int newSuma = 0;
int newSumb = 0;
int max =0;
int suma = 0;
int sumb = 0;
//全集
List<List<Integer>> res = buildSubSet(arr);
for(int i =0;i<res.size();i++){
List<Integer> tmp = res.get(i);
for(int j =0;j<arr.length;j++){
if(tmp.contains(arr[j])){
newSuma = plus(newSuma,arr[j]);
suma += arr[j];
}else {
newSumb = plus(newSumb,arr[j]);
sumb += arr[j];
}
}
if(newSuma!=0&&newSuma==newSumb){
max = Math.max(Math.max(suma,sumb),max);
System.out.println("max = " + max);
System.out.println("newSuma = " + newSuma);
System.out.println("----------------");
}
newSuma = 0;
newSumb = 0;
suma =0;
sumb=0;
}
System.out.println(max);
}
//自测成功
@Test
public void test(){
System.out.println("plus(5,6) = " + plus(5, 6));
// System.out.println("plus(3,5) = " + plus(3, 5));
}
//按照koko的加法运算方式（即二进制加法情况加不做加权，新的二进制位是连个二进制位的异或）
public static int plus(int a, int b) {
StringBuilder tmp = new StringBuilder();
String stra = Integer.toBinaryString(a);
String strb = Integer.toBinaryString(b);
//记录最小的二进制位长度
int length = Math.min(stra.length(), strb.length());
for (int i = 0; i < length; i++) {
//新的二进制位是连个二进制位的异或
tmp.insert(0,Integer.parseInt(String.valueOf(stra.charAt(stra.length()-1-i))) ^ Integer.parseInt(String.valueOf(strb.charAt(strb.length()-1-i))));
}
//多余的二进制位头插如string
int k = stra.length() > length ? stra.length() : strb.length();
String kk = stra.length() > length ? stra : strb;
for (int i = length; i < k; i++) {
tmp.insert(0, kk.charAt(kk.length()-1-i));
}
//计算新的二进制串的十进制数值
int res = 0;
for (int i = tmp.length() - 1; i >= 0; i--) {
//方式一：自定义逻辑 二进制串转为十进制数值
int num = (int) (Integer.parseInt(String.valueOf(tmp.charAt(i))) * Math.pow(2, tmp.length() - i - 1));
res += num;
//方式二：API实现 二进制串转为十进制数值
// res = Integer.parseInt(tmp.toString(),2);
}
return res;
}
public static List<List<Integer>> buildSubSet(int[] nums){
List<List<Integer>> result = new ArrayList<>();
//先添加一个空集
result.add(new ArrayList<>());
for (int i = 0;i<nums.length;i++){
//获取当前子集个数
int size = result.size();
//依次取出当前子集并为每一子集添加元素nums[i]
//最后再添加回result
for (int j = 0;j<size;j++){
List<Integer> clone = new ArrayList<>(result.get(j));
clone.add(nums[i]);
result.add(clone);
}
}
return result;
}
}