本文主要是介绍2023 E3 算法题第三题 （Appointment Slots），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
Task 3
There are N patients (numbered from 0 to N-1) who want to visit the doctor. The doctor has S possible appointment slots, numbered from 1 to S. Each of the patients has two preferences. Patient K would like to visit the doctor during either slot A[K] or slot B[K]. The doctor can treat only one patient during each slot.Is it possible to assign every patient to one of their preferred slots so that there will be at most one patient assigned to each slot?Write a function:class Solution { public boolean solution(int[] A, int[] B, int S); }1that, given two arrays A and B, both of N integers, and an integer S, returns true if it is possible to assign every patient to one of their preferred slots, one patient to one slot, and false otherwise.Examples:Given A = [1, 1, 3], B = [2, 2, 1] and S = 3, the function should return true. We could assign patients in the following way: [1, 2, 3], where the K-th element of the array represents the number of the slot to which patient K was assigned. Another correct assignment would be [2, 1, 3]. On the other hand, [2, 2, 1] would be an incorrect assignment as two patients would be assigned to slot 2.Given A = [3, 2, 3, 1], B = [1, 3, 1, 2] and S = 3, the function should return false. There are only three slots available, but there are four patients who want to visit the doctor. It is therefore not possible to assign the patients to the slots so that only one patient at a time would visit the doctor.Given A = [2, 5, 6, 5], B = [5, 4, 2, 2] and S = 8, the function should return true. For example, we could assign patients in the following way: [5, 4, 6, 2].
解法1
思路
代码
public class AppointmentSlots1 {public class Vistor{public boolean preferenceAVisited;public boolean preferenceBVisited;}public boolean solution1(int[] A, int[] B, int S){List<Vistor> vistors = new ArrayList();int[] slots = new int[S];Arrays.fill(slots, -1);for (int patientIndex =0 ; patientIndex < A.length; patientIndex ++){if (!this.assignPatientToSlot(A, B, slots, patientIndex, vistors)) {return false;}}for (Vistor vistor : vistors){System.out.println(vistor.preferenceAVisited + ":" + vistor.preferenceBVisited);}return true;}public boolean assignPatientToSlot(int[] A, int[] B, int[] slots, int patientIndex, List<Vistor> vistors){if (patientIndex==-1){return false;}if (A[patientIndex]> slots.length){return false;}// System.out.println(patientIndex + ";" + vistors.size());Vistor vistor = null;if (patientIndex +1< vistors.size()){vistor = vistors.get(patientIndex);}if (vistor == null){vistor = new Vistor();vistor.preferenceAVisited = true;vistors.add(vistor);if (slots[A[patientIndex]-1]==-1){slots[A[patientIndex]-1] = 1;return true;}else if (slots[B[patientIndex]-1]==-1){slots[B[patientIndex]-1] = 1;vistor.preferenceBVisited = true;return true;}else{vistors.remove(patientIndex);return this.assignPatientToSlot(A, B, slots, patientIndex-1, vistors);}}else if (!vistor.preferenceBVisited){vistor.preferenceBVisited = true;if (slots[B[patientIndex]-1]==-1){slots[B[patientIndex]-1] = 1;return true;}else{vistors.remove(patientIndex);return this.assignPatientToSlot(A, B, slots, patientIndex-1, vistors);}}else{return false;}}public static void main(String[] args) {AppointmentSlots1 appointmentSlots = new AppointmentSlots1();// Example usage:int[] A1 = {1, 1, 3};int[] B1 = {2, 2, 1};int S1 = 3;System.out.println("==============Starting case 1========");System.out.println(appointmentSlots.solution1(A1, B1, S1)); // Output: trueint[] A2 = {8, 2, 3, 1};int[] B2 = {1, 3, 1, 2};int S2 = 3;System.out.println("==============Starting Case 2========");System.out.println(appointmentSlots.solution1(A2, B2, S2)); // Output: falseint[] A3 = {2, 5, 6, 5};int[] B3 = {5, 4, 2, 2};int S3 = 8;System.out.println("==============Starting Case 3========");System.out.println(appointmentSlots.solution1(A3, B3, S3)); // Output: true 5 4 6 2int[] A4 = {1, 2, 1, 6, 8, 7, 8};int[] B4 = {2, 3, 4, 7, 7, 8, 7};int S4 = 10;System.out.println("==============Starting Case 4========");System.out.println(appointmentSlots.solution1(A4, B4, S4)); // Output: false}
}
解法2
思路
代码
public class AppointmentSlots2 {public boolean solution1(int[] arrayA, int[] arrayB, int S){int[][] combinedArray = combineArrays(arrayA, arrayB);Set set = new HashSet();// 打印组合后的二维数组for (int i = 0; i < combinedArray.length; i++) {set = new HashSet();
// System.out.println(Arrays.toString(combinedArray[i]));for (int j =0 ;j < combinedArray[i].length; j ++){if (combinedArray[i][j] >S){return false;}int previousSize = set.size();set.add(combinedArray[i][j]);int currentSize = set.size();if (previousSize== currentSize){break;}}if (set.size() == combinedArray[i].length){return true;}}return false;}public static int[][] combineArrays(int[] arrayA, int[] arrayB) {int length = arrayA.length;int rows = (int) Math.pow(2, length); // 计算新数组的行数int[][] result = new int[rows][length]; // 创建新的二维数组// 填充新数组for (int i = 0; i < rows; i++) {for (int j = 0; j < length; j++) {// 判断当前位是否为1if ((i >> j & 1) == 1) {result[i][j] = arrayB[j]; // 为1时取数组B的元素} else {result[i][j] = arrayA[j]; // 为0时取数组A的元素}}}return result;}public static void main(String[] args) {AppointmentSlots2 appointmentSlots = new AppointmentSlots2();// Example usage:int[] A1 = {1, 1, 3};int[] B1 = {2, 2, 1};int S1 = 3;System.out.println("==============Starting case 1========");System.out.println(appointmentSlots.solution1(A1, B1, S1)); // Output: trueint[] A2 = {8, 2, 3, 1};int[] B2 = {1, 3, 1, 2};int S2 = 3;System.out.println("==============Starting Case 2========");System.out.println(appointmentSlots.solution1(A2, B2, S2)); // Output: falseint[] A3 = {2, 5, 6, 5};int[] B3 = {5, 4, 2, 2};int S3 = 8;System.out.println("==============Starting Case 3========");System.out.println(appointmentSlots.solution1(A3, B3, S3)); // Output: true 5 4 6 2int[] A4 = {1, 2, 1, 6, 8, 7, 8};int[] B4 = {2, 3, 4, 7, 7, 8, 7};int S4 = 10;System.out.println("==============Starting Case 4========");System.out.println(appointmentSlots.solution1(A4, B4, S4)); // Output: false}}
这篇关于2023 E3 算法题第三题 （Appointment Slots）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
