ARTES #021
ARTES #021
ARTES es una actividad iniciada por
由左耳朵耗子--陈皓: Haga al menos una pregunta sobre el algoritmo leetcode cada semana, lea y comente al menos un artículo técnico en inglés, aprenda al menos una habilidad técnica y comparta un artículo con opiniones y pensamientos. (Es decir, Algoritmo, Revisión, Sugerencia y Compartir se denominan ARTS) y persisten durante al menos un año.
##ARTES 021 este es el articulo 21
Pregunta sobre el algoritmo del algoritmo
149. Puntos máximos en una línea
Dificultad Difícil
Dados n puntos en un plano 2D, encuentre el número máximo de puntos que se encuentran en la misma línea recta.
Ejemplo 1:
Ejemplo 2:
Input: [[1,1],[2,2],[3,3]]
Output: 3
Explanation:
^
|
| o
| o
| o
+------------->
0 1 2 3 4
Input: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
Output: 4
Explanation:
^
|
| o
| o o
| o
| o o
+------------------->
0 1 2 3 4 5 6
Solución
Idioma: C
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* }
*/
int maxPoints(struct Point* points, int pointsSize) {
}
Lo primero que pensé cuando vi este tema fue calcular la pendiente y usar el doble para representar la pendiente. La primera implementación fue la siguiente:
int maxPoints11(struct point* points, int pointsSize) {
if (pointsSize == 0 || pointsSize == 1) {
return pointsSize;
}
double* averageOfLevels = (double*)malloc(sizeof(double) * (pointsSize * (pointsSize -1) / 2));
int index = 0;
for (int i = 0; i< pointsSize; i++) {
struct point pi = points[i];
for (int j = i+1; j< pointsSize; j++) {
struct point pj = points[j];
double x = pi.x - pj.x;
double y = pi.y - pj.y;
if (x ==0) {
averageOfLevels[index++] =INT_MAX;
}
else{
averageOfLevels[index] = ((double)y)/x;
index++;
}
}
}
//问题转换为数组中x最多相等的元素的个数
//先排序 使用快排
quicksort98(averageOfLevels, 0, index-1);
int max = 0;
int temp = 1;
double pd ;
double ld = INT_MIN;
for (int i = 0; i < index-1; i++) {
pd = averageOfLevels[i];
ld = averageOfLevels[i +1];
if (pd == ld) {
temp++;
}else{
if (temp > max) {
max = temp;
}
temp=1;
}
}
if (temp > max) {
max = temp;
}
//分界位n*(n-1)
int i = 1;
for (;i*(i-1)/2 <=max ; i++) {
if (i*(i-1)/2 ==max) {
break;
}
}
free(averageOfLevels);
return i;
}
void quicksort98(double* a, int left, int right) {
int i, j;
double t, temp;
if(left > right)
return;
temp = a[left]; //temp中存的就是基准数
i = left;
j = right;
while(i != j) { //顺序很重要，要先从右边开始找
while(a[j] >= temp && i < j)
j--;
while(a[i] <= temp && i < j)//再找右边的
i++;
if(i < j)//交换两个数在数组中的位置
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位
a[left] = a[i];
a[i] = temp;
quicksort98(a,left, i-1);//继续处理左边的，这里是一个递归的过程
quicksort98(a,i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
La implementación anterior no puede pasar cuando el caso de prueba tiene puntos iguales, porque no se considera la situación de puntos iguales. Lo anterior es calcular las pendientes de todos los puntos, luego ordenarlas para conocer la situación de las pendientes largas y luego descomponer el número de veces que aparece la pendiente para calcular el número de puntos largos.
Una desventaja de esta idea de implementación es que primero calcula la pendiente de todos los puntos y luego realiza el cálculo. Esto hace que sea más difícil lidiar con puntos duplicados.
Una mejora de este método es calcular la pendiente de la línea recta entre cada punto y otros puntos y luego encontrar el punto más óptimo. La implementación es la siguiente:
int maxPoints(struct Point* points, int pointsSize){
if (pointsSize == 0 || pointsSize == 1) {
return pointsSize;
}
double* averageOfLevels = (double*)malloc(sizeof(double) * (pointsSize * (pointsSize -1) / 2));
int max = 0;
for (int i = 0; i< pointsSize; i++) {
struct Point pi = points[i];
int smaple = 0;
int index = 0;
for (int j = 0; j< pointsSize; j++) {
if (i==j) {
continue;
}
struct Point pj = points[j];
double x = pi.x - pj.x;
double y = pi.y - pj.y;
if (x ==0) {
if (y==0) {//同一个点
smaple++;
}
else{
averageOfLevels[index++] =INT_MAX;
}
}
else{
averageOfLevels[index] = ((double)y)/x;
index++;
}
}
quicksort98(averageOfLevels, 0, index-1);
int temp = 1;
int maxtemp = 0;
double pd ;
double ld = INT_MIN;
for (int i = 0; i < index-1; i++) {
pd = averageOfLevels[i];
ld = averageOfLevels[i +1];
if (pd == ld) {
temp++;
}else{
if (temp > maxtemp) {
maxtemp = temp;
}
temp=1;
}
}
if (temp > maxtemp) {
maxtemp = temp;
}
if (index >0) {
maxtemp++;
}
maxtemp = maxtemp+ smaple;
if ( maxtemp > max) {
max = maxtemp;
}
free(averageOfLevels);
averageOfLevels = (double*)malloc(sizeof(double) * (pointsSize * (pointsSize -1) / 2));
}
free(averageOfLevels);
return max;
}
La implementación anterior falla cuando el caso de prueba es [[0,0], [94911151,94911150], [94911152,94911151]], porque el doble representa la pendiente y las pendientes de estos tres puntos son las mismas. Pero estos tres puntos no están en línea recta.
[[0,0],[94911151,94911150],[94911152,94911151]] Este caso de prueba debería haberse agregado más tarde. Varios códigos de lenguaje C encontrados en el área de comentarios no pudieron pasar este caso de prueba.
La dificultad de este problema es ¿cómo expresar la pendiente?
Más tarde, descubrí que cambiar la pendiente expresada en doble a doble largo puede pasar todos los casos de prueba.
De hecho, la doble representación larga no es una representación aproximada y puede haber algunos botones que no se puedan pasar. La pendiente de esta pregunta debe expresarse como una fracción.
El código completo es el siguiente:
void quicksort98(long double* a, int left, int right) {
int i, j;
long double t, temp;
if(left > right)
return;
temp = a[left]; //temp中存的就是基准数
i = left;
j = right;
while(i != j) { //顺序很重要，要先从右边开始找
while(a[j] >= temp && i < j)
j--;
while(a[i] <= temp && i < j)//再找右边的
i++;
if(i < j)//交换两个数在数组中的位置
{
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位
a[left] = a[i];
a[i] = temp;
quicksort98(a,left, i-1);//继续处理左边的，这里是一个递归的过程
quicksort98(a,i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
int maxPoints(struct Point* points, int pointsSize){
if (pointsSize == 0 || pointsSize == 1) {
return pointsSize;
}
long double* averageOfLevels = (long double*)malloc(sizeof(long double) * (pointsSize * (pointsSize -1) / 2));
int max = 0;
for (int i = 0; i< pointsSize; i++) {
struct Point pi = points[i];
int smaple = 0;
int index = 0;
for (int j = 0; j< pointsSize; j++) {
if (i==j) {
continue;
}
struct Point pj = points[j];
long double x = pi.x - pj.x;
long double y = pi.y - pj.y;
if (x ==0) {
if (y==0) {//同一个点
smaple++;
}
else{
averageOfLevels[index++] =INT_MAX;
}
}
else{
averageOfLevels[index] = ((long double)y)/x;
index++;
}
}
quicksort98(averageOfLevels, 0, index-1);
int temp = 1;
int maxtemp = 0;
long double pd ;
long double ld = INT_MIN;
for (int i = 0; i < index-1; i++) {
pd = averageOfLevels[i];
ld = averageOfLevels[i +1];
if (pd == ld) {
temp++;
}else{
if (temp > maxtemp) {
maxtemp = temp;
}
temp=1;
}
}
if (temp > maxtemp) {
maxtemp = temp;
}
if (index >0) {
maxtemp++;
}
maxtemp = maxtemp+ smaple;
if ( maxtemp > max) {
max = maxtemp;
}
free(averageOfLevels);
averageOfLevels = (long double*)malloc(sizeof(long double) * (pointsSize * (pointsSize -1) / 2));
}
free(averageOfLevels);
return max;
}
Revisión
https://dandan2009.github.io/2018/12/28/exposing-NSDictionary/
CONSEJOS
Hay muchos métodos de configuración en el sitio web de configuración de Reveal, como este: https://www.cnblogs.com/somethingWithiOS/p/6594496.html， La configuración es problemática y requiere cambiar el archivo del proyecto. Aquí tienes un método sencillo.
El método de configuración del pod es solo una línea sin modificar el archivo del proyecto:
pod ‘RevealServer’, :configuraciones => [‘Depurar’], :ruta => ‘./RevealServer’
:configuraciones significa que solo es válido bajo depuración
Pod::Spec.new do |s|
s.name = "RevealServer"
s.version = "15.3.3"
s.summary = "RevealServer sdk"
s.description = <<-DESC
RevealServer
DESC
s.homepage = "http://www.baidu.com"
s.license = "MIT"
s.author = { "zzz 2019-1-5" => "" }
s.platform = :ios, "7.0"
s.ios.deployment_target = "7.0"
s.source = { :git => "http://www.baidu.com" }
s.source_files = "RevealServer.framework/**/*.h"
s.vendored_frameworks = 'RevealServer.framework'
end
Para ver la demostración completa, consulte: https://github.com/dandan2009/RevealServerDemo
Compartir
Poco tiempo, base débil, algoritmo de aprendizaje no técnico:
What to read next
Want more posts about ARTS?
Posts in the same category are usually the best next step for reading more on this topic.
View same categoryWant to keep following #iOS?
Tags are useful for related tools, specific problems, and similar troubleshooting notes.
View same tagWant to explore another direction?
If you are not sure what to read next, return to the homepage and start from categories, topics, or latest updates.
Back home