记录一道科大讯飞的Java后端开发面试题

记录一道科大讯飞的Java后端开发面试题

题目大概描述

存在n个人，每个人有一个业务能力值和一个交流能力值。对其分为两组，分组后两组的业务能力和 与 交流能力和 想同。

大致思路

因为是两个维度，所以先看第一个维度业务
我是用回溯法确定分为两组后，两组的业务和相同的所有情况。
然后遍历上面的情况，寻找交流能力相同的情况，遇到就输出

代码

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * *
 * @create: 2023-12-16 19:33
 **/
public class Teest {
    

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = Integer.parseInt(in.nextLine());
        int[][] peo = new int[n][2];

        int index = 0;

        for (int i = 0; i < n; i++) {
            String s = in.nextLine();
            String[] sArr = s.split(" ");
            int[] temp = new int[2];
            temp[0] = Integer.parseInt(sArr[0]);
            temp[1] = Integer.parseInt(sArr[1]);
            peo[index++] = temp;
        }
        List<List<Integer>> lists = setGroup(n, peo);
        for (int i = 0; i < lists.size(); i++) {
            for (int j = 0; j < lists.get(i).size(); j++) {
                System.out.print(lists.get(i).get(j)+" ");
            }
            System.out.println();
        }
    }
    static List<List<Integer>> endRes = new ArrayList<>();
    static List<Integer> resIndex = new ArrayList<>();

    /**
     * @return: List<Integer>
     * @param n
     * @param persons :persons[i] 代表每一个人的业务能力和沟通能力
    */
    public static List<List<Integer>> setGroup(int n,int[][] persons){
        //应该按照第一个维度：业务能力，
        // 按照业务能力找出其相等的所有分组，
        // 然后再按照沟通能力筛选
        List<List<Integer>> res = new ArrayList<>();
        if(n != persons.length){
            List temp = new ArrayList();
            temp.add(-1);
            res.add(temp);
            return res;
        }
        //1. check
        int ywsum = 0;
        for (int i = 0; i < persons.length; i++) {
            ywsum += persons[i][0];
        }
        if(ywsum % 2 != 0){
            List temp = new ArrayList();
            temp.add(-1);
            res.add(temp);
            return res;
        }else{
            ywsum /=2;
        }
        //check
        int jlsum = 0;
        for (int i = 0; i < persons.length; i++) {
            jlsum += persons[i][1];
        }
        if(jlsum % 2 != 0){
            List temp = new ArrayList();
            temp.add(-1);
            res.add(temp);
            return res;
        }else{
            jlsum /=2;
        }

        //2.按照业务能力找出其业务能力之和为 ywsum 的所有组合
        //使用回溯算法
        tracingBack(ywsum,0,persons,0);
        //3.这时endRes中应该是满足要求的分组的索引
        int middle = 0;
        for (int i = 0; i < endRes.size(); i++) {
            for (int j = 0; j < endRes.get(i).size(); j++) {
                int temp = endRes.get(i).get(j);

                middle += persons[temp][1];
            }
            if(middle == jlsum){
                //找到了分组
                //1.第一组的人数和第二组的人数
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(endRes.get(i).size());
                temp.add(n-endRes.get(i).size());
                res.add(temp);
                //2.第一个小组的成员，从index=1开始
                ArrayList<Integer> temp2 = new ArrayList<>();
                for (int j = 0; j < endRes.get(i).size(); j++) {
                    int ind = endRes.get(i).get(j);
                    temp2.add(ind+1);
                }
                res.add(temp2);

                //3.第二个小组的成员，
                ArrayList<Integer> temp3 = new ArrayList<>();
                for (int j = 1; j <= n; j++) {
                    if(!temp2.contains(j)){
                        temp3.add(j);
                    }
                }
                res.add(temp3);
            }
        }
        return res;
    }

    /**
     * @param target 目标值
     * @param sum 我们计算的
     * @param persons
     * @param beginIndex 初始索引为0
    */
    public static void tracingBack(int target,int sum, int[][] persons,int beginIndex){

        if(sum>=target){
            if(sum == target){
                endRes.add(new ArrayList<>(resIndex));
            }
            return ;
        }re

        for (int i = beginIndex; i < persons.length; i++) {

            //加入的是索引
            resIndex.add(i);
            sum += persons[i][0];
            tracingBack(target,sum,persons,i+1);
            int temp = resIndex.get(resIndex.size() - 1);
            sum -= persons[temp][0];
            resIndex.remove(resIndex.size() - 1);

        }
    }
}

遗憾的是

我最后的写main函数时，定义了一个二维数组，但是没有将每一个人加入数组，最后时间剩几秒了，没来得及修改，太遗憾了，希望大家平时多尝试一下ACM的模式，不要习惯了Leetcode的模式