ARTES #021
ARTES #021
ARTS é uma atividade iniciada por
由左耳朵耗子--陈皓: Faça pelo menos uma pergunta sobre o algoritmo leetcode toda semana, leia e comente pelo menos um artigo técnico em inglês, aprenda pelo menos uma habilidade técnica e compartilhe um artigo com opiniões e pensamentos. (Ou seja, Algoritmo, Revisão, Dica e Compartilhamento são chamados de ARTS) e persistem por pelo menos um ano.
ARTES 021
Este é o artigo 21
Pergunta sobre algoritmo de algoritmo
149. Máximo de pontos em uma linha
Dificuldade ** Difícil **
Dados n pontos em um plano 2D, encontre o número máximo de pontos que estão na mesma linha reta.
Exemplo 1:
Exemplo 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
Solução
Idioma: C
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* }
*/
int maxPoints(struct Point* points, int pointsSize) {
}
Meu primeiro pensamento quando vi este tópico foi calcular a inclinação e usar double para representar a inclinação. A primeira implementação foi a seguinte:
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);//继续处理右边的 ，这里是一个递归的过程
}
A implementação acima não pode passar quando o caso de teste possui pontos iguais, pois a situação de pontos iguais não é considerada. O acima é calcular as inclinações de todos os pontos, depois classificá-los para descobrir a situação das encostas longas e, em seguida, decompor o número de vezes que a inclinação aparece para calcular o número de pontos longos.
Uma desvantagem desta ideia de implementação é que ela primeiro calcula a inclinação de todos os pontos e depois realiza o cálculo. Isso torna mais difícil lidar com pontos duplicados.
Uma melhoria neste método é calcular a inclinação da linha reta entre cada ponto e outros pontos e, em seguida, encontrar o ponto ideal. A implementação é a seguinte:
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;
}
A implementação acima falha quando o caso de teste é [[0,0],[94911151,94911150],[94911152,94911151]], porque double representa a inclinação e as inclinações desses três pontos são iguais. Mas estes três pontos não estão em linha reta.
[[0,0],[94911151,94911150],[94911152,94911151]] Este caso de teste deveria ter sido adicionado posteriormente. Vários códigos da linguagem C encontrados na área de comentários não passaram neste caso de teste.
A dificuldade deste problema é como expressar a inclinação?
Mais tarde, descobri que alterar a inclinação expressa em double para long double pode passar em todos os casos de teste.
Na verdade, a representação dupla longa não é uma representação aproximada e pode haver alguns botões que não podem ser passados. A inclinação desta questão deve ser expressa como uma fração.
O código completo é o seguinte:
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;
}
Revisão
https://dandan2009.github.io/2018/12/28/exposing-NSDictionary/
DICAS
Existem muitos métodos de configuração no site de configuração do Reveal, como este: https://www.cnblogs.com/somethingWithiOS/p/6594496.html， A configuração é problemática e requer alteração do arquivo do projeto. Aqui está um método simples.
O método de configuração do pod é apenas uma linha sem modificar o arquivo do projeto:
pod ‘RevealServer’, :configurations => [‘Debug’], :path => ‘./RevealServer’
:configurations significa que só é válido em depuração
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 a demonstração completa, consulte: https://github.com/dandan2009/RevealServerDemo
Compartilhar
Tempo insuficiente, base fraca, algoritmo de aprendizagem não 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