201809-3 元素选择器（100分）

1、首先标签选择器和id选择器是很简单的，只需要注意标签大小写不敏感，id大小写敏感就可以拿到50分了

2、难的是后代选择器，按照题目给的思路，先找到所有满足最后一个选择器的元素列表，然后遍历这些元素，如果存在父级元素满足条件则继续搜索，否则说明这个元素不匹配选择器，将其移除。最后剩下的元素就是答案啦。

PS：作为一个人工智障，我不得不吐槽下我自己，这道题的考试的时候只拿了10分?。当时看题的时候自以为聪明，觉得题目给的后代选择器的筛选办法太费劲了，应该从第一个选择器开始筛选其子元素，惨痛的经验告诉我，还是少相信自己。

100分java代码如下

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

public class Main {
    static class Element implements Comparable<Element> {
        public String name;
        public String id;
        public int index;
        public int points;
        public List<Element> parents;

        public Element(String name, String id, int index, int points) {
            this.name = name.toLowerCase();
            this.id = id;
            this.index = index;
            this.points = points;
            this.parents = new ArrayList<>();
        }

        public static Element getElement(String line, int index) {
            String[] data = line.split(" ");
            String name = data[0];
            int points = name.lastIndexOf(".") + 1;
            name = name.substring(points);
            if (data.length == 1) {
                return new Element(name, "", index, points);
            } else {
                return new Element(name, data[1], index, points);
            }
        }

        @Override
        public int compareTo(Element o) {
            return this.index - o.index;
        }
    }

    private static List<Element> elements = new ArrayList<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] firstLine = scanner.nextLine().split(" ");
        int m = Integer.parseInt(firstLine[0]);
        int n = Integer.parseInt(firstLine[1]);
        for (int i = 0; i < m; i++) {
            elements.add(Element.getElement(scanner.nextLine(), i + 1));
        }
        List<String> queries = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            queries.add(scanner.nextLine());
        }
        scanner.close();


        for (String query : queries) {
            if (query.contains(" ")) {
                String[] selectors = query.split(" ");
                List<Element> children = getElements(selectors[selectors.length - 1]);
                List<Element> remove = new ArrayList<>();

                for (Element child : children) {
                    List<Element> currChildren = new ArrayList<>();
                    currChildren.add(child);
                    for (int i = selectors.length - 2; i >= 0; i--) {
                        String selector = selectors[i];
                        List<Element> parents = new ArrayList<>();
                        for (Element currChild : currChildren) {
                            parents.addAll(findValidParents(currChild, selector));
                        }

                        currChildren.clear();
                        currChildren.addAll(parents);

                        if(currChildren.size() == 0){
                            remove.add(child);
                            break;
                        }
                    }
                }

                children.removeAll(remove);
                printResult(children);
            } else {
                printResult(getElements(query));
            }
        }
    }


    private static List<Element> findValidParents(Element child, String selector) {
        List<Element> parents = new ArrayList<>();
        boolean isId = selector.startsWith("#");
        for (int i = child.index - 2; i >= 0; i--) {
            Element element = elements.get(i);
            if (element.points < child.points && isElementMatchSelector(element, selector, isId)) {
                parents.add(element);
            }
        }
        return parents;
    }

    private static List<Element> getElements(String selector) {
        List<Element> results = new ArrayList<>();
        boolean isId = selector.startsWith("#");
        for (Element element : elements) {
            if (isElementMatchSelector(element, selector, isId))
                results.add(element);
        }
        return results;
    }

    private static boolean isElementMatchSelector(Element element, String selector, boolean isId) {
        return (isId && element.id.equals(selector)) || (!isId && element.name.equals(selector.toLowerCase()));
    }

    private static void printResult(List<Element> results) {
        StringBuffer stringBuffer = new StringBuffer(results.size() + " ");
        for (Element element : results) {
            stringBuffer.append(element.index + " ");
        }
        System.out.println(stringBuffer.toString());
    }
}