路径交叉

335. 路径交叉

给你一个整数数组 distance 。

从 X-Y 平面上的点 (0,0) 开始，先向北移动 distance[0] 米，然后向西移动 distance[1] 米，向南移动 distance[2] 米，向东移动 distance[3] 米，持续移动。也就是说，每次移动后你的方位会发生逆时针变化。

判断你所经过的路径是否相交。如果相交，返回 true ；否则，返回 false 。

示例 1：

输入：distance = [2,1,1,2]
输出：true

示例 2：

输入：distance = [1,2,3,4]
输出：false

示例 3：

输入：distance = [1,1,1,1]
输出：true

提示：

1 <= distance.length <= 10⁵
1 <= distance[i] <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: bool isSelfCrossing(vector<int>& distance) { } };

cpp 解法, 执行用时: 20 ms, 内存消耗: 18.6 MB, 提交时间: 2023-09-24 18:36:13

class Solution {
public:
    bool isSelfCrossing(vector<int>& distance) {
        int n = distance.size();
        for (int i = 3; i < n; ++i) {
            // 第 1 类路径交叉的情况
            if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) {
                return true;
            }

            // 第 2 类路径交叉的情况
            if (i == 4 && (distance[3] == distance[1]
                && distance[4] >= distance[2] - distance[0])) {
                return true;
            }

            // 第 3 类路径交叉的情况
            if (i >= 5 && (distance[i - 3] - distance[i - 5] <= distance[i - 1]
                && distance[i - 1] <= distance[i - 3]
                && distance[i] >= distance[i - 2] - distance[i - 4]
                && distance[i - 2] > distance[i - 4])) {
                return true;
            }
        }
        return false;
    }
    
    // solve 2
    bool isSelfCrossing2(vector<int>& distance) {
        int n = distance.size();

        // 处理第 1 种情况
        int i = 0;
        while (i < n && (i < 2 || distance[i] > distance[i - 2])) {
            ++i;
        }

        if (i == n) {
            return false;
        }

        // 处理第 j 次移动的情况
        if ((i == 3 && distance[i] == distance[i - 2])
            || (i >= 4 && distance[i] >= distance[i - 2] - distance[i - 4])) {
            distance[i - 1] -= distance[i - 3];
        }
        ++i;

        // 处理第 2 种情况
        while (i < n && distance[i] < distance[i - 2]) {
            ++i;
        }

        return i != n;
    }
};

golang 解法, 执行用时: 12 ms, 内存消耗: 7.4 MB, 提交时间: 2023-09-24 18:35:36

func isSelfCrossing(distance []int) bool {
    n := len(distance)

    // 处理第 1 种情况
    i := 0
    for i < n && (i < 2 || distance[i] > distance[i-2]) {
        i++
    }

    if i == n {
        return false
    }

    // 处理第 j 次移动的情况
    if i == 3 && distance[i] == distance[i-2] ||
        i >= 4 && distance[i] >= distance[i-2]-distance[i-4] {
        distance[i-1] -= distance[i-3]
    }
    i++

    // 处理第 2 种情况
    for i < n && distance[i] < distance[i-2] {
        i++
    }

    return i != n
}

// solve 2
func isSelfCrossing2(distance []int) bool {
    for i := 3; i < len(distance); i++ {
        // 第 1 类路径交叉的情况
        if distance[i] >= distance[i-2] && distance[i-1] <= distance[i-3] {
            return true
        }

        // 第 2 类路径交叉的情况
        if i == 4 && distance[3] == distance[1] &&
            distance[4] >= distance[2]-distance[0] {
            return true
        }

        // 第 3 类路径交叉的情况
        if i >= 5 && distance[i-3]-distance[i-5] <= distance[i-1] &&
            distance[i-1] <= distance[i-3] &&
            distance[i] >= distance[i-2]-distance[i-4] &&
            distance[i-2] > distance[i-4] {
            return true
        }
    }
    return false
}

javascript 解法, 执行用时: 64 ms, 内存消耗: 42.9 MB, 提交时间: 2023-09-24 18:35:08

/**
 * @param {number[]} distance
 * @return {boolean}
 */
var isSelfCrossing = function(distance) {
    const n = distance.length;
    for (let i = 3; i < n; ++i) {
        // 第 1 类路径交叉的情况
        if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) {
            return true;
        }

        // 第 2 类路径交叉的情况
        if (i === 4 && (distance[3] === distance[1]
            && distance[4] >= distance[2] - distance[0])) {
            return true;
        }

        // 第 3 类路径交叉的情况
        if (i >= 5 && (distance[i - 3] - distance[i - 5] <= distance[i - 1]
            && distance[i - 1] <= distance[i - 3]
            && distance[i] >= distance[i - 2] - distance[i - 4]
            && distance[i - 2] > distance[i - 4])) {
            return true;
        }
    }
    return false;
};

var isSelfCrossing2 = function(distance) {
    const n = distance.length;

    // 处理第 1 种情况
    let i = 0;
    while (i < n && (i < 2 || distance[i] > distance[i - 2])) {
        ++i;
    }

    if (i === n) {
        return false;
    }

    // 处理第 j 次移动的情况
    if ((i === 3 && distance[i] == distance[i - 2])
        || (i >= 4 && distance[i] >= distance[i - 2] - distance[i - 4])) {
        distance[i - 1] -= distance[i - 3];
    }
    ++i;

    // 处理第 2 种情况
    while (i < n && distance[i] < distance[i - 2]) {
        ++i;
    }

    return i !== n;
};

java 解法, 执行用时: 1 ms, 内存消耗: 49.9 MB, 提交时间: 2023-09-24 18:34:43

class Solution {
    public boolean isSelfCrossing(int[] distance) {
        int n = distance.length;

        // 处理第 1 种情况
        int i = 0;
        while (i < n && (i < 2 || distance[i] > distance[i - 2])) {
            ++i;
        }

        if (i == n) {
            return false;
        }

        // 处理第 j 次移动的情况
        if ((i == 3 && distance[i] == distance[i - 2])
            || (i >= 4 && distance[i] >= distance[i - 2] - distance[i - 4])) {
            distance[i - 1] -= distance[i - 3];
        }
        ++i;

        // 处理第 2 种情况
        while (i < n && distance[i] < distance[i - 2]) {
            ++i;
        }

        return i != n;
    }

    // solve 2
    public boolean isSelfCrossing2(int[] distance) {
        int n = distance.length;
        for (int i = 3; i < n; ++i) {
            // 第 1 类路径交叉的情况
            if (distance[i] >= distance[i - 2] && distance[i - 1] <= distance[i - 3]) {
                return true;
            }

            // 第 2 类路径交叉的情况
            if (i == 4 && (distance[3] == distance[1]
                && distance[4] >= distance[2] - distance[0])) {
                return true;
            }

            // 第 3 类路径交叉的情况
            if (i >= 5 && (distance[i - 3] - distance[i - 5] <= distance[i - 1]
                && distance[i - 1] <= distance[i - 3]
                && distance[i] >= distance[i - 2] - distance[i - 4]
                && distance[i - 2] > distance[i - 4])) {
                return true;
            }
        }
        return false;
    }
}

python3 解法, 执行用时: 56 ms, 内存消耗: 22.5 MB, 提交时间: 2023-09-24 18:34:06

class Solution:
    def isSelfCrossing(self, distance: List[int]) -> bool:
        n = len(distance)
        for i in range(3, n):
            # 第 1 类路径交叉的情况
            if (distance[i] >= distance[i - 2]
                    and distance[i - 1] <= distance[i - 3]):
                return True

            # 第 2 类路径交叉的情况
            if i == 4 and (distance[3] == distance[1]
                           and distance[4] >= distance[2] - distance[0]):
                return True

            # 第 3 类路径交叉的情况
            if i >= 5 and (distance[i - 3] - distance[i - 5] <= distance[i - 1] <= distance[i - 3]
                           and distance[i] >= distance[i - 2] - distance[i - 4]
                           and distance[i - 2] > distance[i - 4]):
                return True
        return False

    # solve 2
    def isSelfCrossing2(self, distance: List[int]) -> bool:
        n = len(distance)

        # 处理第 1 种情况
        i = 0
        while i < n and (i < 2 or distance[i] > distance[i - 2]):
            i += 1

        if i == n:
            return False

        # 处理第 j 次移动的情况
        if ((i == 3 and distance[i] == distance[i - 2])
                or (i >= 4 and distance[i] >= distance[i - 2] - distance[i - 4])):
            distance[i - 1] -= distance[i - 3]
        i += 1

        # 处理第 2 种情况
        while i < n and distance[i] < distance[i - 2]:
            i += 1

        return i != n

上一题

下一题

详情