20220820网易互联网笔试代码（3.2/4）
第一题
给你两个数a,b，把数当成字符串，可以从两个字符串中删除任意字符，问最少删除几次，使得a是b的倍数，或者b是a的倍数
思路
因为数的范围小于10^9，用DFS分别生成a,b删除可以得到的所有数的集合，并记录需要删除的次数。最后遍历两个集合求最小值
package wangyi;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Q1 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num1 = sc.nextInt();
int num2 = sc.nextInt();
String s1 = new StringBuilder(Long.toString(num1)).reverse().toString();
String s2 = new StringBuilder(Long.toString(num2)).reverse().toString();
Map<Integer,Integer> cnt1 = new HashMap<>();
Map<Integer,Integer> cnt2 = new HashMap<>();
getDDD(s1,0,0,cnt1,0);
getDDD(s2,0,0,cnt2,0);
int ans = s1.length()+s2.length()+1;
/* for (Integer val : cnt1.keySet()) {
System.out.println("key1:"+val+":"+cnt1.get(val));
}
for (Integer val : cnt2.keySet()) {
System.out.println("key1:"+val+":"+cnt2.get(val));
}*/
for (Integer key1 : cnt1.keySet()) {
for (Integer key2 : cnt2.keySet()) {
if(key1%key2 == 0 || key2%key1==0){
ans = Math.min(ans,cnt1.get(key1)+cnt2.get(key2));
}
}
}
System.out.println(ans==(s1.length()+s2.length()+1)?-1:ans);
}
public static void getDDD(String str,int p,int val,Map<Integer,Integer> map,int cnt){
if(str.length()==p){
if(val!=0){
map.put(val,str.length()-cnt);
}
return;
}
//不要当前元素
getDDD(str,p+1,val,map,cnt);
//要当前元素
val += (str.charAt(p)-'0')*(int)Math.pow(10,cnt);
getDDD(str,p+1,val,map,cnt+1);
}
}
第二题
长城，给你一个数组，你可以往任何一个位置上加一（次数不限），问最少加多少次可以让这个数组变成长城（长城的定义：任意一个数左右两个数字相等）
思路
计算奇数位置和偶数位置的最大值，确定他们的高度，如果相同得考虑是把奇数位置+1，还是偶数位置+1的问题
package wangyi;
import java.util.Scanner;
public class Q2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long arr[] = new long[n];
long firstMax=0,secondMax=0;
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
if(i%2==0) firstMax=Math.max(firstMax,arr[i]);
else secondMax=Math.max(secondMax,arr[i]);
}
if(firstMax == secondMax){
System.out.println(Math.min(minOps2(arr,firstMax+1,secondMax),minOps2(arr,firstMax,firstMax+1)));
}
else
System.out.println(minOps2(arr,firstMax,secondMax));
}
public static long minOps2(long arr[],long num1,long num2){
long ans = 0;
for (int i = 0; i < arr.length; i++) {
ans+=(i%2==0?num1-arr[i]:num2-arr[i]);
}
return ans;
}
}
第三题
red问题，给你一个字符串，里面只包含red三个字符，你每次可以把一个字符变成另一个字符，问你最少操作几次，可以使得字符串中好e最多。“好e的定义”：左边和右边必须是r和d，比如red和der。思路
（只过了60%）要使得好e最多，字符串是有规律的，比如redered，由一个r（或d）跟着一个e，那么下一个肯定是d（或r）。生成这样的字符串，和原字符串比较。
问题：奇数长度好像满足这规律，偶数长度很恶心，如果有大佬，请指教下。
package wangyi;
import java.util.*;
public class Q3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int n = str.length();
String re = construct(new StringBuilder(), new char[]{'r', 'd'}, 2*n);
String de = construct(new StringBuilder(), new char[]{'d', 'r'}, 2*n);
String er = construct(new StringBuilder("e"), new char[]{'r', 'd'}, 2*n);
String ed = construct(new StringBuilder("e"), new char[]{'d', 'r'}, 2*n);
if (n % 2 == 1) {
int ans = Math.min(minChange(str, re,0,n), minChange(str, de,0,n));
ans = Math.min(ans, minChange(str, er,0,n));
ans = Math.min(ans, minChange(str, ed,0,n));
System.out.println(ans);
} else {
int ans = Math.min(minChange(str, re,0,n), minChange(str, de,0,n));
ans = Math.min(ans, minChange(str, er,0,n));
ans = Math.min(ans, minChange(str, ed,0,n));
ans = Math.min(ans, minChange(str, re,1,n));
ans = Math.min(ans, minChange(str, de,1,n));
ans = Math.min(ans, minChange(str, er,1,n));
ans = Math.min(ans, minChange(str, ed,1,n));
ans = Math.min(ans, minChange(str, re,2,n));
ans = Math.min(ans, minChange(str, de,2,n));
ans = Math.min(ans, minChange(str, er,2,n));
ans = Math.min(ans, minChange(str, ed,2,n));
System.out.println(ans);
}
}
public static int minChange(String s1, String s2,int left,int right) {
int ans = 0;
for (int i = left; i < right; i++) {
if (s1.charAt(i) != s2.charAt(i)) ans++;
}
return ans;
}
public static String construct(StringBuilder sb, char order[], int n) {
int p = 0;
while (sb.length() < n) {
sb.append(order[p]);
p = (p + 1) % 2;
if (sb.length() < n) {
sb.append('e');
}
}
return sb.toString();
}
}
第四题
给你一个数组，定义三元组（i,j,k）为arr[i]==arr[k]并且arr[j]<arr[i]，问这样的三元组有多少个思路
（只过了60%）先计算每个数左边小于他的元素有多少个。然后再一次遍历，用哈希表存住每个元素的位置，这样下一个位置的相同的元素就可以计算三元组的个数了
package wangyi;
import java.util.*;
public class Q4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
int leftMinCnt[] = new int[n];
for (int i = 1; i < n; i++) {
for (int j = i-1; j >= 0; j--) {
if(arr[j]<arr[i]) leftMinCnt[i]++;
}
//System.out.println("i:"+i+"\tval:"+arr[i]+"\tleft:"+leftMinCnt[i]);
}
HashMap<Integer,List<Integer>> map = new HashMap();
int ans = 0;
for (int i = 0; i < n; i++) {
//应该可以优化的，map只存上一次的地址，然后加上一个元素的结果，不用每个相同元素的访问过去
List<Integer> list = map.getOrDefault(arr[i],new ArrayList<>());
for (int j = 0; j < list.size(); j++) {
ans+= (leftMinCnt[i]-leftMinCnt[list.get(j)]);
}
list.add(i);
map.put(arr[i],list);
}
System.out.println(ans);
}
}
