微软20220819笔试（附JAVA代码）
感觉不是很难，等晚上笔试结束再贴一下自己的代码~
第一题
题目：
一个二维坐标系，给了两个数组X[],Y[]，(X[i],Y[i]）代表一个坑，现在有填坑的机器，宽度为W。每次可以沿着平行Y轴的方向修坑。问最少几次可以修完所有的坑。
思路：
类似力扣戳气球，贪心算法，每个坑都一定要修的，每次都选当前剩余的坑中第一个坑作为开始的起点x，这样以x+W以内的坑都能被修好，下次只要考虑X+W以外的坑的情况。
代码：
import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import java.util.*;
public class Q1 {
public static void main(String[] args) {
int X[] = new int[]{2,4,2,6,7,1};
Q1 q = new Q1();
System.out.println(q.solution(X,null,2));
}
//每次第一个点都要修复，假设为i，那[i,i+W] 必然要修复，修复完考虑[i+W+1,正无穷的]，又转换成刚才的问题，第一个点一定要修复
public int solution(int[] X, int[] Y, int W) {
if(X.length == 0) return 0;
Arrays.sort(X);
int end = X[0]+W;
int ans = 1;
int i = 1;
while(i < X.length){
System.out.println("当前坐标："+X[i]+"\t当前最大值:"+end);
if(X[i]<=end){
i++;
}
else{
ans++;
end = X[i]+W;
i++;
}
System.out.println("\tans:"+ans);
}
return ans;
}
}
第二题
题目
给定一个字符串S，只由字符'0'....'9'组成，求S中字符能组成的最大的回文串。
思路
也是贪心，先计算字符串中成对的字符的个数（0要特殊处理，因为如果其他数字没成对，0成对也必要，会有前导0的问题，比如"0000"的答案应该是0，而"0011"的答案应该是1001）
因为是回文串，先拼接左边的部分，最后将字符串反转再拼接到原字符串上即可。
然后每次都选择当前能成对的字符中最大值，如果是最后一位，根据情况可以选择单个字符中的最大值。
代码
import java.util.Random;
public class Q2 {
public static void main(String[] args) {
Q2 q = new Q2();
Random r = new Random();
for (int i = 0; i < 10; i++) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < 20; j++) {
sb.append(r.nextInt(10));
}
System.out.println(sb+":"+q.solution(sb.toString()));
}
}
public String solution(String S) {
// write your code in Java 8 (Java SE 8)
int nums[] = new int[10];
int n = S.length();
for (int i = 0; i < S.length(); i++) {
nums[S.charAt(i)-'0']++;
}
int pairs = 0;//计算相同数字的对数
for(int i = 9; i > 0; i--){
pairs+= (nums[i]/2);
System.out.println("nums["+i+"]"+nums[i]);
}
pairs+= (pairs>0? nums[0]/2 : 0);
System.out.println("nums[0]"+nums[0]);
//需要填的位数
boolean hasSingle =!(pairs*2==n);
int ansBit = pairs + (pairs*2==n?0:1);
StringBuilder ans = new StringBuilder();
for (int i = 0; i < ansBit; i++) {
for(int j = 9; j >= 0 ;j--){
if(nums[j]>=2){
ans.append(j);
nums[j]-=2;
break;
}
else if(nums[j]==1 && i==ansBit-1&&hasSingle){
ans.append(j);
nums[j]--;
break;
}
}
}
String reverse = new StringBuilder(ans).reverse().toString();
if(!hasSingle){
ans.append(reverse);
}
else{
ans.append(reverse.substring(1,reverse.length()));
}
return ans.toString();
}
}
第三题
题目
给定一个图，有N+1（0~N）个结点，N条边，任意两个结点都是联通的，现在0号结点是办公室，1到N号结点都分别住着一个人，他们都需要打车到办公室。一辆车最多可以坐5个人。每辆车每次从一个结点移动到相邻的节点都要费油1。求制定一个共乘计划，让所有的人到办公室所需的油最小。求最小油耗的值。
思路
后序遍历，从顶点和边的要求可以看出这是一棵树，问题可以转换为所有节点到根节点的最小油耗问题。要注意需要记录每个节点的人数，后面方便计算油耗。
代码
import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;
import sun.rmi.log.LogInputStream;
import java.util.HashMap;
import java.util.*;
public class Q3 {
public static void main(String[] args) {
// int A[] = new int[]{0,1,1};
//int B[] = new int[]{1,2,3};
// int A[] = new int[]{1,1,1,9,9,9,9,7,8};
// int B[] = new int[]{2,0,3,1,6,5,4,0,0};
int A[] = new int[]{0};
int B[] = new int[]{1};
Q3 q = new Q3();
System.out.println(q.solution(A,B));
}
public int solution(int[] A, int[] B) {
// write your code in Java 8 (Java SE 8)
//建图
int N = A.length;
HashMap<Integer,List<Integer>> Graph = new HashMap<Integer, List<Integer>>();
for (int i = 0; i <= N; i++) {
Graph.put(i,new ArrayList<>());
}
for (int i = 0; i < N; i++) {
List<Integer> list = Graph.getOrDefault(A[i],new ArrayList<>());
list.add(B[i]);
Graph.put(A[i],list);
list = Graph.getOrDefault(B[i],new ArrayList<>());
list.add(A[i]);
Graph.put(B[i],list);
}
//后续遍历
int visited[] = new int[N+1];//记录每个节点是否访问过
int cnt[] = new int[N+1];//记录每个节点的人数
return postOrder(visited,Graph,0,cnt);
}
public int postOrder(int[] visited,HashMap<Integer,List<Integer>> G, int v,int cnt[]){
visited[v] = 1;
List<Integer> list = G.getOrDefault(v,new ArrayList<>());
int cost = 0;
cnt[v] = 1;
System.out.println("节点:"+v);
//到当前节点的油耗等于 其他节点到他子节点的油耗和子节点到他的油耗之和
for(int num:list){
if(visited[num]==0){
//其他节点到子节点的油耗
cost += postOrder(visited,G,num,cnt);
System.out.println("添加上子节点"+num+"所需油耗,总油耗"+cost);
//子节点到他所需的油耗
cost += (cnt[num]+4)/5;
System.out.println("添加上子节点"+num+"到"+v+"所需油耗:"+(cnt[num]+4)/5+",总油耗"+cost);
//记录当前节点的人数
cnt[v] += cnt[num];
System.out.println("添加上子节点"+num+"人数:"+cnt[num]+",总人数"+cnt[v]);
}
}
System.out.println("节点"+v+"\t耗油:"+cost+"\t人数:"+cnt[v]);
return cost;
}
}
有被激励到