正在接受编程测试，但没有获得模式算法

问题描述 投票：2回答：1

问题是有一排座位A-K的飞机，但第一排除外。该方法为您提供了在字符串“ 1C 2B 1J”中作为前席获得的座位。如果将四口之家组合在一起或在过道上平均分配，请找出它们的数量。

所以在

 A B C D E F G H J K    A B C D E F G H J K
  XOO    OOXX   XXX     OOX   OOOO   OXO
  XXX    OOOO   XXX     OOX   OOOO   OOO

返回应该是

                        OOX FFFF OXO
                        OXO FFFF OOO

应为两个，因为2个四口之家可以容纳。如果输入为（1，“”），则返回2的原因与给定的座位表相同。在这个算法中，我得到的比我应得的多。 

import java.lang.*;
import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.util.*;
//Available 4seatsections from B-E[1-4] F-J[5-9] with aisles else D-G[3-7]

class AirplaneFamilesNSeatFinder {
static int solution(int N, String S) {
    String[] seats = S.split(" ");
    int numberOfFamilySeats = 0;
    int[][] planeSeats = new int[N][10];
    Map<Integer, Integer> seatsMap = new HashMap<Integer, Integer>();

    int[][] takenSeats = new int[N][10];
    seatsMap = validSeats(S, N);
    List<Map.Entry<Integer, Integer>> list = new LinkedList<Map.Entry<Integer, Integer>> 
    (seatsMap.entrySet());
    Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>(){
        public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2)
        {
            return (o1.getValue()).compareTo(o2.getValue());
        }
    });
    for(int i = 0;i<N;i++) {
        for(int k=0;k<10;k++) {
            for(Map.Entry<Integer, Integer> seatAssigned : list) {
                int seat = seatAssigned.getKey();
                int row = seatAssigned.getValue();
                if(seat==i && row==k)
                    takenSeats[i][k] = 1;                   
            }
        }
    }
    int seatsNeeded = seats.length*4;
    if(seatsNeeded<(N*10)) {
        for(int i = 0;i<N;i++) {
            for(int k=0;k<10;k++) {
                if((k+1)<10) {
                    k=k+1;
                    boolean foundSeat = false;
                    System.out.println("Debug: " + foundSeat + " " + numberOfFamilySeats + " " + k);
                    if(k==1 && (k+3)<10 && takenSeats[i][k+1]!=1 && takenSeats[i][k+2]!=1 && 
       takenSeats[i][k+3]!=1&& takenSeats[i][k+4]!=1) {
                        foundSeat = true;
                    }else if(k==3 && (k+3)<10 && takenSeats[i][k+1]!=1 && takenSeats[i][k+2]!=1 && 
     takenSeats[i][k+3]!=1&& takenSeats[i][k+4]!=1) {
                        foundSeat = true;
                        takenSeats[i][3]==1
                    }else if(k==5 && (k+3)<10 && takenSeats[i][3]!=1 && takenSeats[i][k+1]!=1 && 
       takenSeats[i][k+2]!=1 && takenSeats[i][k+3]!=1&& takenSeats[i][k+4]!=1) {
                        foundSeat = true;
                    }
                    if(foundSeat) {
                        numberOfFamilySeats++;
                        i++;
                    }
                    System.out.println("Debug:foundSeat  " + foundSeat + " " + numberOfFamilySeats + 
       " " + k);
                    foundSeat = false;
                }
            }
        }

    } else {
        return 0;
    }


    return numberOfFamilySeats;
}

static Map<Integer, Integer> validSeats(String S, int N) {
    String[] seats = S.split(" ");
    int length = seats.length;
    Pattern p = Pattern.compile("-?\\d+");
    Map<Integer, Integer> tempSeatsMap = new HashMap<Integer, Integer>();
    String[] rowNames = {"A", "B", "C", "D", "E", "F", "G", "H", "J", "K"};
    for(int i = 0;i<length;i++) {
        for(int k = 0;k<rowNames.length;k++) {
            if(seats[i].contains(rowNames[k])) {
                Matcher m = p.matcher(seats[i]);
                Integer seat = 0;
                while (m.find()) {
                  seat =Integer.parseInt(m.group());
                }
                if(seat<=N) {
                    tempSeatsMap.put(seat, k);
                }
            }
        }
    }
    return tempSeatsMap;
}

public static void main(String[] args) {
    String s = "1A 2F 1C";
    System.out.println("Number of familes " + solution(3, s));
}

}
java algorithm maps
1个回答
1
投票

该代码有一些错误，也可以更容易实现：

  1. validSeats对于每行(1,2,...)仅返回传递的席位列表中列出的last席位(A,B,...)。因此，不考虑某些占用的座位。例如。对于席位列表1C 2B 1G 1E 2F 2D validSeats，只会找到席位1E和2D。这是由于使用Map类型引起的，该类型只能包含每个密钥一次。如果将键/值对（Map）设置为K1/V2，并且已经存在具有相同键Map#put的键/值对（Map#put），则旧值K1/V1被新值替换K1。这意味着先前找到的座位会丢失。为防止这种情况，必须更换V1型。一种可能性是填充后来使用的数组V2 direct，而不是通过Map -instance绕行。

    而且，也不必拆分通过的座位列表。相反，可以将正则表达式机制直接应用于传递的字符串。

    可能的实现方式是：

    int[][] takenSeats

  2. Map包含几个缺陷，例如：

    • private static int[][] validSeats(int numberOfRows, String seatList) { int[][] takenSeats = new int[numberOfRows][10]; Pattern p = Pattern.compile("\\d{1,2}-?[A-Z]"); Matcher m = p.matcher(seatList); while (m.find()) { String seat = m.group().replace("-", ""); // e.g. 12C char letter = seat.substring(seat.length() - 1, seat.length()).charAt(0); // 12 String row = seat.substring(0, seat.length() - 1); // C int letterIndex = letter > 'H' ? letter - 'A' - 1 : letter - 'A'; // Map ABC DEFG HJK -> 012 3456 789 int rowIndex = Integer.parseInt(row) - 1; // Map 123... -> 012... takenSeats[rowIndex][letterIndex] = 1; } return takenSeats; } 的填充不正确。对于上面的示例，使用1E（作为索引04）和2D（作为索引13），只有2E（作为索引14）设置。
    • 在代码中的多个位置使用了错误的索引。例如。对于情况solution，检查座位int[][] takenSeats，k = 1，takenSeats[i][k+1]和takenSeats[i][k+2]。但是，由于索引是从零开始的，因此必须检查位置takenSeats[i][k+3]，takenSeats[i][k+4]，takenSeats[i][k]和takenSeats[i][k+1]。
    • 没有考虑在same行中组合BCDE排除了组合DEFG。类似地，组合DEFG排除组合FGHJ。

    可能的替代实现为：

    takenSeats[i][k+2]

示例：

takenSeats[i][k+3]

[private static int solution(int numberOfRows, String seatList) { int numberOfFamilySeats = 0; int[][] takenSeats = validSeats(numberOfRows, seatList); for (int rowIndex = 0; rowIndex < numberOfRows; rowIndex++) { // Check each row for (int letterIndex = 1; letterIndex <= 5; letterIndex +=2) { // Check neighboring seats of B (->CDE), D (->EFG) and F (->GHJ) if (takenSeats[rowIndex][letterIndex] != 1 && takenSeats[rowIndex][letterIndex + 1] != 1 && takenSeats[rowIndex][letterIndex + 2] != 1 && takenSeats[rowIndex][letterIndex + 3] != 1) { if (letterIndex == 1) letterIndex = 3; // BCDE excludes DEFG else if (letterIndex == 3) letterIndex = 5; // DEFG excludes FGHJ numberOfFamilySeats++; // Found free family seat } } } return numberOfFamilySeats; } 表示已占用座位， A B C D E F G H J K 1 f f f f X 2 X X 3 X X f f f f 4 X f f f f (4 X f f f f ) alternative (doesn't change the number) 5 f f f f X (5 f f f f X ) alternative (doesn't change the number) 6 X f f f f f f f f 7 X X 表示家庭座位

X

输出：

f

更新：

要显示计算出的座位计划，必须在public static void main(String[] args) { String seatList = "1F 2D 2G 3C 3D 4B 5H 6A 7B 7F"; System.out.println("Number of families: " + solution(7, seatList)); } 中标记家庭座位，例如与Number of families: 6 （solution表示空闲，2表示最初被占用）：

0

在1中，private static int solution(int numberOfRows, String seatList) { int numberOfFamilySeats = 0; int[][] takenSeats = validSeats(numberOfRows, seatList); for (int rowIndex = 0; rowIndex < numberOfRows; rowIndex++) { // Check each row for (int letterIndex = 1; letterIndex <= 5; letterIndex +=2) { // Check neighboring seats of B (->CDE), D (->EFG) and F (->GHJ) if (takenSeats[rowIndex][letterIndex] != 1 && takenSeats[rowIndex][letterIndex + 1] != 1 && takenSeats[rowIndex][letterIndex + 2] != 1 && takenSeats[rowIndex][letterIndex + 3] != 1) { for (int familySeats = 0; familySeats < 4; familySeats++) { // Mark family seats as occupied <-- added takenSeats[rowIndex][letterIndex + familySeats] = 2; } if (letterIndex == 1) letterIndex = 3; // BCDE excludes DEFG else if (letterIndex == 3) letterIndex = 5; // DEFG excludes FGHJ numberOfFamilySeats++; // Found free family seat } } } printSeatPlan(takenSeats); // Print seat plan <-- added return numberOfFamilySeats; } 的内容以适当的格式显示，简单地用printSeatPlan或更详细地显示，例如。与

takenSeats
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.