微软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;
    }
}

#笔试##微软笔试##微软##2023一起秋招吧##面经笔经#