LeetCode-514

题目

结果

代码

究极爆内存法

class Status {
    public static String ring;
    public static String key;

    private final int steps;
    private final int position;
    private final int index;
    private final char target;

    // 用于根节点的构造函数
    public Status(String ring, String key) {
        Status.ring = ring;
        Status.key = key;
        this.steps = 0;
        this.position = 0;
        this.index = 0;
        this.target = key.charAt(0);
    }

    // 用于一般节点的构造函数
    public Status(int steps, int position, int index) {
        this.steps = steps;
        this.position = position;
        this.index = index;
        if (this.index == key.length()) {
            this.target = '!';
        } else {
            this.target = key.charAt(index);
        }
    }

    public Status clockWise() {
        // 如果走到了路的尽头
        if (this.target == '!') {
            return null;
        }

        // 顺时针寻找目标
        int i = position;
        int step = 0;
        do {
            if (i == ring.length()) {
                i -= ring.length();
            }
            if (ring.charAt(i) == this.target) {
                return new Status(this.steps + step + 1, i, index + 1);
            }
            i++;
            step++;
        } while (i != position);
        throw new RuntimeException("404 Not found");
    }

    public Status counterClockWise() {
        // 如果走到了路的尽头
        if (this.target == '!') {
            return null;
        }

        // 逆时针寻找目标
        int i = position;
        int step = 0;
        do {
            if (i == -1) {
                i += ring.length();
            }
            if (ring.charAt(i) == this.target) {
                return new Status(this.steps + step + 1, i, index + 1);
            }
            i--;
            step++;
        } while (i != position);
        throw new RuntimeException("404 Not found");
    }

    public char getTarget() {
        return this.target;
    }

    public int getSteps() {
        return steps;
    }
}

超时了，不过我感觉思路是对的，也对了很多测试样例。今天懒得再动脑了，择日再做这道题吧。

复杂度

时间复杂度：O（）

空间复杂度：O（）