携程 Java后端 2019.4.8笔试

第一题：
判断输入字母链表有没有环，无脑暴力了，没用到快慢指针。

public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);

    String line = cin.nextLine();
    String[] arr = line.split(",");

    boolean cycle = false;
    HashSet<String> set = new HashSet<>();

    for (int i = 0; i < arr.length; i++) {
        if (set.contains(arr[i])) {
            cycle = true;
        }
        set.add(arr[i]);
    }

    System.out.println(cycle);
}

第二题：
分段翻转链表

private static class Node {
    private String value;
    private Node next;

    public Node(String value) {
        this.value = value;
    }
}

public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);

    String line = cin.nextLine();
    String[] arr = line.substring(1, line.length() - 1).split(",");
    int k = cin.nextInt();

    // 头指针
    Node root = null;
    root = new Node("Head");

    // 构造链表
    Node ptr = root;
    for (int i = 0; i < arr.length; i++) {
        ptr.next = new Node(arr[i]);
        ptr = ptr.next;
    }

    if (k > 1 && arr.length > 1) {
        // 计算翻转次数
        int reverseNumber = arr.length / k;

        Node ptr0 = root;
        Node ptr1 = ptr0.next;
        Node ptr2 = ptr1.next;
        Node ptr3 = ptr2.next;
        for (int i = 0; i < reverseNumber; i++) {
            for (int j = 0; j <= k - 2; j++) {
                ptr2.next = ptr1;
                ptr1 = ptr2;
                ptr2 = ptr3;
                if (ptr2 != null) {
                    ptr3 = ptr2.next;
                } else {
                    ptr3 = null;
                }
            }
            ptr0.next.next = ptr2;
            Node temp = ptr0.next;
            ptr0.next = ptr1;

            ptr0 = temp;
            ptr1 = ptr0.next;
            ptr2 = ptr1 != null ? ptr1.next : null;
            ptr3 = ptr2 != null ? ptr2.next : null;
        }
    }

    print(root);

}

private static void print(Node root) {
    StringBuilder sb = new StringBuilder();
    sb.append("[");
    for (Node i = root.next; i != null; i = i.next) {
        sb.append(i.value).append(",");
    }
    sb.deleteCharAt(sb.length() - 1);
    sb.append("]");
    System.out.println(sb.toString());
}

第三题：
题意没看太明白，无脑暴力了。

public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);

    int n = cin.nextInt();
    String[] arr = new String[n];

    for (int i = 0; i < n; i++) {
        arr[i] = cin.next();
    }

    int[] countArr = new int[n];
    for (int i = 0; i < n; i++) {
        int count = 1;
        for (int j = 0; j < i; j++) {
            if (math(arr[j], arr[i])) {
                count++;
            }
        }
        countArr[i] = count;
    }

    for (int i = 0; i < n; i++) {
        print(arr[i], countArr[i]);
        System.out.print(" ");
    }
    System.out.println();
}

private static boolean math(String path1, String path2) {
    if (path1 == null || path2 == null) {
        return false;
    }

    if (path1.endsWith("/")) {
        path1 = path1.substring(0, path1.length() - 1);
    }

    if (path2.endsWith("/")) {
        path2 = path2.substring(0, path2.length() - 1);
    }

    return path1.equals(path2);
}

private static void print(String path, int count) {
    String[] pathArr = path.split("/");

    if (pathArr.length == 2) {
        System.out.print(1);
    } else if (pathArr.length == 3) {
        System.out.print(11);
    } else {
        StringBuilder sb = new StringBuilder();
        sb.append(1);
        for (int i = 0; i < pathArr.length - 3; i++) {
            sb.append(count);
        }
        sb.append(1);
        System.out.print(sb.toString());
    }
}

要疯，选择题赶上行测了，全程蒙圈，算法题看不懂题意，看来又凉凉了。