多米诺骨牌（模拟）

• 初始化数据结构：

  • 使用一个布尔数组 arr 来表示每个位置是否被占用。初始时所有位置均为 false（未占用）。
  • 使用一个 LinkedHashMap（命名为 queue）来记录最近的 R 操作的位置。这个结构可以保持插入顺序，方便后续处理。

• 遍历输入字符串：

  • 遍历每个字符，根据字符的类型（.、L、R）进行不同的处理：
    • .：表示空位，跳过。
    • L：
      • 如果 queue 为空（没有 R），将当前位置之前的所有位置标记为占用（true）。
      • 如果 queue 不为空，处理最近的 R：
        • 从 queue 中获取并移除最近的 R 的位置。
        • 计算从这个 R 到当前 L 之间的影响区域，并根据位置关系决定标记的方式。具体来说，如果 L 和 R 之间的距离是偶数，则需要跳过中间位置；如果是奇数，则可以直接标记所有位置为占用。
    • R：将当前索引加入 queue，以备后续处理。

• 处理剩余的 R：

  • 遍历完字符串后，如果 queue 中还有 R，取出第一个 R 的位置，将这个位置及其后所有位置标记为占用。

• 计算未占用的位置：

  • 遍历 arr 数组，统计未被占用的位置，并将它们的索引（1-based）加入结果队列。

• 构造结果字符串：

  • 如果没有未占用的位置，返回 "0"。
  • 否则，构造结果字符串，格式为 "count:pos1,pos2,..."，并返回。

import java.util.ArrayDeque;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Iterator;

public class Main {
    public static String solution(int num, String data) {
        boolean[] arr = new boolean[data.length()];
        LinkedHashMap<Character, Integer> queue = new LinkedHashMap<>();

        for (int i = 0; i < data.length(); i++) {
            switch (data.charAt(i)) {
                case '.':
                    break;
                case 'L':
                    if (queue.isEmpty()) {
                        for (int j = 0; j <= i; j++) {
                            arr[j] = true;
                        }
                    } else {
                        Iterator<Map.Entry<Character, Integer>> iterator = queue.entrySet().iterator();
                        Map.Entry<Character, Integer> firstEntry = iterator.next(); // 获取第一个条目
                        iterator.remove();

                        boolean skipTwo = false;
                        int top = firstEntry.getValue();
                        int extra = (i + top) / 2;
                        if ((i - top) % 2 != 0) {
                            skipTwo = true;
                        }
                        for (int j = top; j <= i; j++) {
                            if (skipTwo) {
                                arr[j] = true;
                            } else {
                                if (j != extra) {
                                    arr[j] = true;
                                }
                            }
                        }
                    }
                    break;
                case 'R':
                    queue.put('R', i);
                    break;
            }
        }

        // Check if the queue is not empty
        if (!queue.isEmpty()) {
            // Retrieve and remove the first entry
            Iterator<Map.Entry<Character, Integer>> iterator = queue.entrySet().iterator();
            Map.Entry<Character, Integer> firstEntry = iterator.next();
            iterator.remove(); // Pop the first entry

            if (firstEntry.getKey() == 'R') {
                int topValue = firstEntry.getValue();
                for (int j = topValue; j < arr.length; j++) {
                    arr[j] = true; // Set all subsequent elements to true
                }
            }
        }

        int count = 0;
        ArrayDeque<Integer> result = new ArrayDeque<>();
        for (int i = 0; i < data.length(); i++) {
            if (!arr[i]) {
                count++;
                result.add(i + 1); // 1-based index
            }
        }

        if (count == 0) {
            return "0"; // All positions are filled
        }

        StringBuilder resultString = new StringBuilder(count + ":");
        for (int pos : result) {
            resultString.append(pos).append(",");
        }

        resultString.setLength(resultString.length() - 1); // Remove the last comma
        return resultString.toString();
    }

    public static void main(String[] args) {
        // // You can add more test cases here
        System.out.println(solution(14, ".L.R...LR..L..").equals("4:3,6,13,14"));
        System.out.println(solution(5, "R....").equals("0"));
        System.out.println(solution(1, ".").equals("1:1"));
    }
}

原文地址：https://blog.csdn.net/2301_79140115/article/details/142520988

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！