lines

lines选编

149. Max Points on a Line

return the maximum number of points that lie on the same straight line.

Approach 1: Enumeration

Therefore, it is not wise to use the float/double value to represent a unique slope, since they are not accurate.

To circumvent the above issue, one could use a pair of co-prime integers to represent unique slope.

As a reminder, two integers are co-primes, if and only if their greatest common divisor is 1.

注意： 有现成的Pair可以用

/*
 * Copyright (c) 2010, 2015, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package javafx.util;

import java.io.Serializable;
import javafx.beans.NamedArg;

 /**
  * <p>A convenience class to represent name-value pairs.</p>
  * @since JavaFX 2.0
  */
public class Pair<K,V> implements Serializable{

    /**
     * Key of this <code>Pair</code>.
     */
    private K key;

    /**
     * Gets the key for this pair.
     * @return key for this pair
     */
    public K getKey() { return key; }

    /**
     * Value of this this <code>Pair</code>.
     */
    private V value;

    /**
     * Gets the value for this pair.
     * @return value for this pair
     */
    public V getValue() { return value; }

    /**
     * Creates a new pair
     * @param key The key for this pair
     * @param value The value to use for this pair
     */
    public Pair(@NamedArg("key") K key, @NamedArg("value") V value) {
        this.key = key;
        this.value = value;
    }

    /**
     * <p><code>String</code> representation of this
     * <code>Pair</code>.</p>
     *
     * <p>The default name/value delimiter '=' is always used.</p>
     *
     *  @return <code>String</code> representation of this <code>Pair</code>
     */
    @Override
    public String toString() {
        return key + "=" + value;
    }

    /**
     * <p>Generate a hash code for this <code>Pair</code>.</p>
     *
     * <p>The hash code is calculated using both the name and
     * the value of the <code>Pair</code>.</p>
     *
     * @return hash code for this <code>Pair</code>
     */
    @Override
    public int hashCode() {
        int hash = 7;
        hash = 31 * hash + (key != null ? key.hashCode() : 0);
        hash = 31 * hash + (value != null ? value.hashCode() : 0);
        return hash;
    }

     /**
      * <p>Test this <code>Pair</code> for equality with another
      * <code>Object</code>.</p>
      *
      * <p>If the <code>Object</code> to be tested is not a
      * <code>Pair</code> or is <code>null</code>, then this method
      * returns <code>false</code>.</p>
      *
      * <p>Two <code>Pair</code>s are considered equal if and only if
      * both the names and values are equal.</p>
      *
      * @param o the <code>Object</code> to test for
      * equality with this <code>Pair</code>
      * @return <code>true</code> if the given <code>Object</code> is
      * equal to this <code>Pair</code> else <code>false</code>
      */
     @Override
     public boolean equals(Object o) {
         if (this == o) return true;
         if (o instanceof Pair) {
             Pair pair = (Pair) o;
             if (key != null ? !key.equals(pair.key) : pair.key != null) return false;
             if (value != null ? !value.equals(pair.value) : pair.value != null) return false;
             return true;
         }
         return false;
     }
 }

注意：

• 分别考察穿过每一点的直线的最大点数

• 无需考虑某一点之前的点

  例如, 若考察点1时，若点1, 点2同线，且点1,点0同线，则点0，点2必同线，已在之前考察过

import javafx.util.Pair;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class LeetCode149 {


    Map<Pair<Integer,Integer>, Integer> map=new HashMap<>();
    int horizontals=0;

    Pair<Integer,Integer> getLine(int dx, int dy){
        if(dy==0){
            Pair<Integer,Integer> line=new Pair<>(Integer.MAX_VALUE,Integer.MAX_VALUE);
            return line;
        }
        if(dx<0){
            dx=-dx;
            dy=-dy;
        }
        int gcd=BigInteger.valueOf(dx).gcd(BigInteger.valueOf(dy)).intValue();
        return new Pair<>(dx/gcd,dy/gcd);
    }

    public int maxPoints(int[][] points) {
        int n=points.length;
        if(n<3){
            return n;
        }
        int res=2;
        for (int i = 0; i < n - 1; i++) {
            horizontals=1;
            map.clear();
            //[0,1], [0,2], [0,3]
            //[1,2], [1,3]
            for (int j = i+1; j < n; j++) {
                int dx=points[i][0]-points[j][0];
                int dy=points[i][1]-points[j][1];
                if(dx==0){
                    horizontals++;
                    continue;
                }
                Pair<Integer,Integer> line=getLine(dx,dy);
                map.put(line,map.getOrDefault(line,1)+1);
                res=Math.max(res,map.get(line));
            }
            res=Math.max(res,horizontals);
        }
        return res;
    }
}

import java.math.BigInteger;

class Solution {
    int[][] points;
    int n;
    HashMap<Pair<Integer, Integer>, Integer> lines = new HashMap<Pair<Integer, Integer>, Integer>();
    int horizontal_lines;

    /**
     * To avoid the precision issue with float/double numbers, using a pair of co-prime numbers to
     * represent the slope.
     */
    private Pair<Integer, Integer> slope_coprime(int x1, int y1, int x2, int y2) {
        int deltaX = x1 - x2, deltaY = y1 - y2;
        if (deltaX == 0)
            return new Pair<>(0, 0);
        else if (deltaY == 0)
            return new Pair<>(Integer.MAX_VALUE, Integer.MAX_VALUE);
        else if (deltaX < 0) {
            deltaX = -deltaX;
            deltaY = -deltaY;
        }
        Integer gcd = BigInteger.valueOf(deltaX).gcd(BigInteger.valueOf(deltaY)).intValue();

        return new Pair<Integer, Integer>(deltaX / gcd, deltaY / gcd);
    }

    public Pair<Integer, Integer> add_line(int i, int j, int count, int duplicates) {
        /*
         * Add a line passing through i and j points. Update max number of points on a line
         * containing point i. Update a number of duplicates of i point.
         */
        // rewrite points as coordinates
        int x1 = points[i][0];
        int y1 = points[i][1];
        int x2 = points[j][0];
        int y2 = points[j][1];
        // add a duplicate point
        if ((x1 == x2) && (y1 == y2))
            duplicates++;
        // add a horisontal line : y = const
        else if (y1 == y2) {
            horizontal_lines += 1;
            count = Math.max(horizontal_lines, count);
        }
        // add a line : x = slope * y + c
        // only slope is needed for a hash-map
        // since we always start from the same point
        else {
            Pair<Integer, Integer> slope = this.slope_coprime(x1, y1, x2, y2);
            lines.put(slope, lines.getOrDefault(slope, 1) + 1);
            count = Math.max(lines.get(slope), count);
        }
        return new Pair(count, duplicates);
    }

    public int max_points_on_a_line_containing_point_i(int i) {
        /*
         * Compute the max number of points for a line containing point i.
         */
        // init lines passing through point i
        lines.clear();
        horizontal_lines = 1;
        // One starts with just one point on a line : point i.
        int count = 1;
        // There is no duplicates of a point i so far.
        int duplicates = 0;

        // Compute lines passing through point i (fixed)
        // and point j.
        // Update in a loop the number of points on a line
        // and the number of duplicates of point i.
        for (int j = i + 1; j < n; j++) {
            Pair<Integer, Integer> p = add_line(i, j, count, duplicates);
            count = p.getKey();
            duplicates = p.getValue();
        }
        return count + duplicates;
    }


    public int maxPoints(int[][] points) {

        this.points = points;
        // If the number of points is less than 3
        // they are all on the same line.
        n = points.length;
        if (n < 3)
            return n;

        int max_count = 1;
        // Compute in a loop a max number of points
        // on a line containing point i.
        for (int i = 0; i < n - 1; i++)
            max_count = Math.max(max_points_on_a_line_containing_point_i(i), max_count);
        return max_count;
    }
}

356. Line Reflection

思路：

1. 先存入每个点
2. 再考察每个点的reflection是否存在

public boolean isReflected(int[][] points) {
    Set<String> set=new HashSet<>();
    int min=Integer.MAX_VALUE;
    int max=Integer.MIN_VALUE;
    for (int[] point : points) {
        min=Math.min(min,point[0]);
        max=Math.max(max,point[0]);
        set.add(point[0]+","+point[1]);
    }
    for (int[] point : points) {
        int rx=min+max-point[0];
        if(!set.contains(rx+","+point[1])){
            return false;
        }
    }
    return true;
}

2152. Minimum Number of Lines to Cover Points

2280. Minimum Lines to Represent a Line Chart

1232. Check If It Is a Straight Line

public boolean checkStraightLine(int[][] coordinates) {
    //(y2-y1)/(x2-x1)=(y3-y2)/(x3-x2)
    //(y2-y1)(x3-x2)=(y3-y2)(x2-x1)
    int n=coordinates.length;
    for (int i = 2; i < n; i++) {
        int[] a=coordinates[i-2];
        int[] b=coordinates[i-1];
        int[] c=coordinates[i];
        if((b[1]-a[1])*(c[0]-b[0])!=(c[1]-b[1])*(b[0]-a[0])){
            return false;
        }
    }
    return true;
}