Заданными точками на 2D плоскость, найти линию, проходящую через наибольшее количество очков


Может кто-нибудь дать некоторые отзывы с точки зрения дизайна ОО и стиль кодирования на следующие коды:

Вопрос: дано N точек на 2D плоскости, найти строку с максимальным количеством точек, которые находятся на нем. Аналогично https://leetcode.com/problems/max-points-on-a-line/description/. Мне дали интерфейс точки, пустые строки класс, пустой класс решение и попросили заполнить несколько функций.

Мои коды:

public interface Point
{
  public double getX();
  public double getY();
}

public class Line
{ // added by myself.
  private Point p1, p2;
  public Line(Point p1, Point p2) {
    this.p1 = p1;
    this.p2 = p2;
  }
}


public class Solution
{
  // Write the function here
  public Line maxPointsLine(Point[] points) {
    if(points == null) return null;
    if(points.length==1) return new Line(points[0], new Point(p));//
    Map<Double, Integer> map = new HashMap<>();// O(n), n = points.length. n-1
    Line result;
    int maxPoints = 0;
    for(int i = 0; i < points.length; i++) { // One Point
      map.clear();
      int overlap =0;
      int countSameX = 1;
      for(int j = i+1; j < points.length; j++) { // the second Point
        double x = points[j].getX() - points[i].getX(); // x intersect
        double y = points[j].getY() - points[i].getY(); // intersect on y coordinate

        if(x==0 && y==0) {
          overlap++;
        }
        if(points[j].getX()==points[i].getX()) {// slope is infi,
          // slope (1) finite, (2) infinite,
          countSameX++;
          continue;
        }
        double slope = y/x;
        if(map.contains(slope)) map.put(slope, map.get(slope)+1);
        else map.put(slope, 2);
        if(map.get(slope)+overlap > maxPoints) { // each line slope and points[i]
          // update result and maxPoints
          maxPoints = map.get(slope)+overlap;
          result = new Line(points[i], points[j]);
        }
      }
      if(countSameX>maxPoints) { // line parallel to Y coordinate
        // update result and maxPoints
        maxPoints = countSameX;
        result = new Line(points[i], points[j]);
      }
    }
    return result;// null
  }
}

В приведенном выше коде я добавил некоторые комментарии, основанные на вопросы, которые я спросил.

(Я этот вопрос кодирования давно. просто пришло в голову. ) На самом деле, интервьюер сказал мне, что didn’t have good coding style and lack of OO design. предложения приветствуются для меня. Спасибо.

Кстати, что касается стиля кодирования, есть плагины такие стандарты, как https://google.github.io/styleguide/javaguide.html. Я просто не исправить проблемы стиля написания кода вручную из-за нехватки времени.

Что же касается дизайна ОО, мне дали пустые классы. Я просто добавил некоторые функции, чтобы решить проблему, который мне дали.

Я действительно не нашел никаких серьезных проблем в мои коды. Смущен и расстроен.



Комментарии
2 ответа


Отказ от ответственности
Я на C# разработчика, а не для Java разработчиков. Вполне возможно, я делаю мелкие синтаксические ошибки в этом ответе, но намерение ответ спорить о намерении ООП, не точный синтаксис Явы.

Приверженность ООП - часть 1

Кроме того, определен Line и Point класс, нет ООП подход в данном решении. Это самый большой красный флаг:

public class Solution

Если ваше решение реализовано в одном классе, то это не очень хорошая объектно-ориентированное программирование. Вы ожидаете ООП решение для сбора классов.

Когда вы начинаете с ООП, первое, что вы должны сделать, это разделить обязанности. Как вы поставили все в один класс с одним методом; это подразумевает, что вы думаете, что есть только одна ответственность. Я не согласен. Есть несколько независимых частей логики, необходимые для этой проблемы:


  • Определение сеть по поставкам двух точках (точки А и Б => линия АВ)

  • Проверки, если другая точка находится на той же линии (С и прямой АВ => логическое)

  • Отслеживание, какие точки находятся на одной линии.

  • Тестирование всей коллекции очков, чтобы найти строку с самым большим количеством точек.

4 ответственность предполагает, что вы, вероятно, понадобится по крайней мере 4-х классов, каждая из которых содержит одну ответственность.
Примечание: это теоретическая оценка. Вопрос в интервью-это просто ради примера, поэтому многие из них могут, возможно, быть сокращенной. Я могу определенно видеть аргумент для объединения двух последних абзацах.

Мы вернемся к этому моменту, когда мы обращаемся к самой математике.


Стиль кодирования

Я не понимаю ваш подход. Я уже немного подзабыл математику на протяжении многих лет, но мне кажется, самая большая проблема здесь-это ваш стиль кодирования. Это ужасно нечитабельно. Некоторые примеры:


  • Есть одна пустая строка в весь ваш метод.

Это не реально сделать вещи легко читаемым. Разрывы строк не влияет на производительность программы, поэтому свободно использовать их. Отдельные более мелкие логические "главам", такие как объявления, инициализации и блок логики (if, forи т. д.)

В вашу защиту, гид по стилю, на которые вы ссылались также, кажется, чтобы избежать разрывов. Однако, их код обычно состоит из очень краткие и очень простые примеры.
Как видите, "реальный" код не так аккуратно, как пример кода. Вам нужно больше обращать внимание на читабельность, если код становится более сложным (в алфавитно-цифровом порядке, не обязательно логически).


  • Ваши комментарии не всегда полезно

Некоторые примеры:

Map<Double, Integer> map = new HashMap<>();// O(n), n = points.length. n-1

if(points[j].getX()==points[i].getX()) {// slope is infi,
// slope (1) finite, (2) infinite,

В догадку, я бы сказал, что ты написал эти комментарии для себя в течение развития. И это нормально, я тоже.

Но попробуйте поставить себя на мое место сейчас. Я смотрю на ваш код, и все, что я вижу, если куча сложной математической логики. Нет никаких объяснений о намерении алгоритма, и те замечания, которые делают вещи более запутанной, чем объяснять это.

Это не должно быть сделано через комментарии (внешней документации требует больше усилий, но может быть полезно); но комментарии-это просто первая попытка документирования кода.


  • Вы определили Line класс, но вы не используете его, пока после того, как вы установили, что данная пара точек определяет строку с наибольшим количеством очков на нем.

Это ставит телегу впереди лошади. Вы должны использовать Line класс для обработки логикой проверять, находится ли точка на нем.

Вы, по сути, "липовые" ООП, поставив результат вашей (не ООП метод) в классе, при этом оставляя лишен метод реальных принципов ООП.


Математика

Я вижу намеки, что вы понимаете математической стороне дела. Вы, например, избегать симметрии ловушки (проверка,B, А B,а).

Расчет уклона-это умный подход. Я бы решить это по-другому, т. е. путем расчета уравнения линии АБ (y = ax + bможно по сути определить линию по хранению ценностей a и b), а затем тестирование, чтобы увидеть, если другие точки соответствуют уравнения.

Я собираюсь использовать ваш подход (расчет уклона), но я перетасовке подход. Я пытаюсь сосредоточиться на простых принципов ООП.


Приверженность ООП - часть 2

Вот мой контрпредложений для лучшего ООП подход:


  • Взять два очка (точно так же, как он, избегая симметричные операции)

  • Определить линию, основанную на этих двух точках.

  • Хранить две точки в список (вместо двух отдельных полей)

  • Для всех остальных точек, проверить, если они находятся на одной линии.


    • Если это так, то добавьте этот пункт в список точку на линии.


  • Магазин на линии для последующего извлечения

  • В конце концов, взять линию с самым длинным список точек.

Вы найдете, что лежащие в основе математики, точно так же, как и ваша, но порядок операций изменен на более обособляется конструкция:


  • Мы содержим линии-определенной логики в линии класса.

  • Мы можем разделить общей логики (начиная от данной пары АБ) от внутренней логики (проверка всех других точек, чтобы увидеть, если они находятся на АБ).

Быстрый пример реализации:

Взять два очка (точно так же, как он, избегая симметричные операции).

List<Line> listOfLines = new List<Line>();
for(int a = 0; a < points.length; a++) //point A
{
for(int b = a+1; b < points.length; b++) // point B
{

Определить линию, основанную на этих двух точках.

var lineAB = new Line(points[a], points[b]);

Магазин на линии для последующего извлечения

listOfLines.Add(lineAB);

Заметьте Line класс:

public class Line
{
public List<Point> Points;
public Line(Point a, Point b) {
this.Points = new List<Point>();
this.Points.Add(a);
this.Points.Add(b);
}
}

Для всех остальных точек, проверить, если они находятся на одной линии. Если это так, то добавьте этот пункт в список точку на линии.

for(int c = b+1 ; c < points.length ; c++) //point C
{
if(lineAB.ContainsPoint(points[c])
{
lineAB.Points.Add(points[c]);
}
}

Обратите внимание на методы в Line класс:

public bool ContainsPoint(Point c)
{
var a = this.Points[0];
var b = this.Points[1];

//If all X values are equal, they are on the same line:
if(a.GetX() == b.GetX() && a.GetX() == c.GetX())
return true;

//If all Y values are equal, they are on the same line:
if(a.GetY() == b.GetY() && a.GetY() == c.GetY())
return true;

//If AB and AC have the same slope, they are on the same line:
return CalculateSlope(a,b) == CalculateSlope(a,c);
}

private double CalculateSlope(Point p1, Point p2)
{
double xDiff = p2.GetX() - p1.GetX();
double yDiff = p2.GetY() - p1.GetY();

return yDiff / xDiff;
}

В конце концов, взять линию с самым длинным список точек:

Line lineWithMostPoints = null;

for (Line l : listOfLines) {
if (
lineWithMostPoints == null
|| l.Points.Length > lineWithMostPoints.Points.Length
)
lineWithMostPoints = l;
}

return lineWithMostPoints;


Резюме изменений

Это просто список быстрого огня, почему это переделанный пример использует намного больше ООП:


  • Большинство логики расчета действует в рамках небольших возможный блок, например, две точки, или линии и точки. В ходе этих расчетов, нет дополнительных хлопот от использования коллекций, тем самым облегчая нагрузку сложность кода.

  • Расчет склоны-это отдельный метод.

  • Логика (которая проверяет, если точка c лежит на прямой Ab) отделяется, и гораздо более понятный (по сравнению с хранением int countSameX и Map<Double, Integer> map а затем использовать их, чтобы вычислить ваш результат).

  • Комментарии объяснить, почему определенный код существует (ContainsPoint() хороший пример этого) и помочь с читабельностью.

  • Имена переменных были немного улучшилось. Твои не слишком плохо, но конденсируя все в один и тот же метод заставило вас страдать от постоянного имен переменных. Е. Г. обратите внимание, как ContainsPoint() относится к А,Б,в конкретную точку с конкретными значениями, но основная CalculateSlope() метод просто использует Р1 и Р2, потому что он не заботится о том, что вы прошли, B или C. использование отдельных методов дает возможность переименовать параметры, чтобы лучше удовлетворить за рамки текущего метода.

  • В целом, код самодокументируемым, чем раньше. Правда, более подробный, это легче понять намерение метода, глядя на ее тело.


    • Обратите внимание, что это не просто комментарии и имена переменных. Этот способ наименования дополнительных методов также помочь разделить логику в глав. Мне не нужно использовать комментарии, чтобы объяснить CalculateSlope() метод, как его имя, по своей сути раскрывает свои цели.



Улучшения еще добавить


  • В идеале, вы хотите сделать Points в Line класс частных, и добавить специфические методы, чтобы добавить дополнительные очки к нему и получить его длину.


    • Вы могли бы изменить ContainsPoint чтобы сразу добавить пункт, подходит ли он на линии. Переименовать метода по имени, если вы сделаете это!


  • Даже если ты пропускаешь простой симметрии ловушки (АБ,БА), есть подобная ошибка для строк с уже существующими точками (например, Абде, де).


    • Допустим, вы сначала проверьте линию АВ. Как выясняется, не на АВ, D и Е оба на АБ.

    • Несколько итераций спустя, ты проверяешь Лапшин. Исходя из ваших ранних расчетов, вы уже знаете, что E-это на BD. Вы на самом деле не нужно, чтобы проверить это снова, но текущий код до сих пор все равно.

    • Это незначительные показатели вещь, но его значение может увеличиваться по мере сбора точек увеличивается.

    • В идеале, когда вы начинаете проверять новую строку (например, Де), вы должны сначала проверить ваши существующие результаты для строки, которая содержит обе эти точки (например, линии АВ содержит точки А,Б,D,Е, поэтому она содержит информацию, которая имеет отношение к вам сейчас). Вместо того, чтобы создавать линию de, вы могли бы вместо того, чтобы производить расчет за АВ(+Де) - это уже более полное, чем новая линия де никогда не будет (как это не раз проверить а и Б, мы уже прошли те).


  • Подобный прирост производительности может быть сделано путем остановки итерации рано.


    • Скажем, у вас есть 26 очков (от A до Z). Ты теперь, начиная с вычислений для строк, где первая точка-Х.

    • В лучшем случае, эти расчеты могут только дать до 3 очков (Х,У,Z), поскольку расчеты не проверяет другие пункты снова.

    • Предположим, что у вас уже есть строка в вашей коллекции, которая имеет 5 точек на ней (АБВГД). Нет смысла делать дальнейшие расчеты, потому что даже если все остальные точки находятся на одной линии (АБВ), он будет содержать меньше очков, чем существующие линии с АБВГД.


  • Аналогично, если вы найдете линию с больше чем половиной из списка точек на ней (и вы проверили все пункты для обеспечения совместимости с этой линии), вы можете быть уверены, что это самая длинная линия представляется возможным, так как это невозможно для двух различных строк, чтобы поделиться более чем в одной точке.

Большинство из этих улучшений будет принять существующий код более сложным, что позволяет предположить либо отделяя его дальше, или документирование его лучше. Или, предпочтительно, оба.

0
ответ дан 6 марта 2018 в 01:03 Источник Поделиться

я думаю, что ваша задача заключалась в использовании данных классов Point и Lineи продлить их...

public class Line{

public Line (Point a, Point b);

public boolean contains(Point p);

}

таким образом, оставляя довольно простая задача в решении (и довольно легко читается)

Lines lines = getAllLines();//easily iterate over the permutated Point matrix

for(Line line: lines){
int amountOfPoints = 0;
for (Point p: points){
if (line.contains(p) {
amountOfPoint = amountOfPoint + 1;
}
}

Примечание

это просто объяснение, ОО-программирования, я не включают subtaks, например, как получить максимум из линий, или как contains() работает, но это, безусловно, дает подсказку о том, где вопросов направлен на...

0
ответ дан 6 марта 2018 в 10:03 Источник Поделиться