• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Leetcode-335 – Path crossing

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

You are given an integer array distance.

Starting from the point (0,0) on the X-y plane, move first north distance[0] m, then west Distance [1] m, south Distance [2] m, and east Distance [3] m, and keep moving. In other words, your position changes counterclockwise after each move.

Determine whether your paths intersect. If it intersects, return true; Otherwise, return false.

 

Example 1:

Input: distance = [2,1, 2] Output: trueCopy the code

Example 2:

Input: distance = [1,2,3,4] output: falseCopy the code

Example 3:

Input: distance = [1,1,1,1] output: trueCopy the code

Tip:

  • 1 <= distance.length <=
    1 0 5 10^5
  • 1 <= distance[i] <=
    1 0 5 10^5

Idea 1: violent search

  • Put each point into the map and judge the result
  • Hey TLE
class Solution {
  public boolean isSelfCrossing(int[] distance) {
            Set<String> set = new HashSet<>();
            set.add("0, 0");
            int x = 0, y = 0;
            for (int i = 0; i < distance.length; i++) {
                int temp = i % 4;
                for (int j = 1; j <= distance[i]; j++) {
                    StringBuilder sb = new StringBuilder();
                    switch (temp) {
                        case 0:
                            sb.append(x).append(",").append(y + j);
                            break;
                        case 1:
                            sb.append(x - j).append(",").append(y);
                            break;
                        case 2:
                            sb.append(x).append(",").append(y - j);
                            break;
                        case 3:
                            sb.append(x + j).append(",").append(y);
                            break;
                    }
                    if (set.contains(sb.toString())) {
                        return true;
                    }
                    set.add(sb.toString());
                }
                switch (temp) {
                    case 0:
                        y += distance[i];
                        break;
                    case 1:
                        x -= distance[i];
                        break;
                    case 2:
                        y -= distance[i];
                        break;
                    case 3:
                        x += distance[i];
                        break; }}return false; }}Copy the code
  • Time complexity O(
    ∑ 0 n n u m \sum_0^nnum     )
  • Space complexity O(
    ∑ 0 n n u m \sum_0^nnum     )

Idea 2: Look for patterns

  • Woo Woo abstract drawing ability is too ridiculous
class Solution {
    public boolean isSelfCrossing(int[] d) {
        int n = d.length;
        if (n < 4) return false;
        for (int i = 3; i < n; i++) {
            if (d[i] >= d[i - 2] && d[i - 1] <= d[i - 3]) return true;
            if (i >= 4 && d[i - 1] == d[i - 3] && d[i] + d[i - 4] >= d[i - 2]) return true;
            if (i >= 5 && d[i - 1] <= d[i - 3] && d[i - 2] > d[i - 4] && d[i] + d[i - 4] >= d[i - 2] && d[i - 1] + d[i - 5] >= d[i - 3]) return true;
        }
        return false; }}Copy the code
  • Time complexity O(
    n n     )
  • Space complexity O(
    1 1     )