SENI #021
SENI #021
SENI adalah kegiatan yang diprakarsai oleh
由左耳朵耗子--陈皓: Kerjakan setidaknya satu pertanyaan algoritma leetcode setiap minggu, baca dan komentari setidaknya satu artikel teknis berbahasa Inggris, pelajari setidaknya satu keterampilan teknis, dan bagikan artikel yang berisi opini dan pemikiran. (Artinya, Algoritma, Review, Tip, dan Share disebut sebagai SENI) dan bertahan setidaknya selama satu tahun.
SENI 021
Ini adalah pasal 21
Pertanyaan algoritma algoritma
149. Poin Maks pada Satu Garis
Kesulitan Sulit
Diketahui n titik pada bidang 2D, tentukan jumlah maksimum titik yang terletak pada garis lurus yang sama.
Contoh 1:
Contoh 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
Solusi
Bahasa: C
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* }
*/
int maxPoints(struct Point* points, int pointsSize) {
}
Pikiran pertama saya ketika melihat topik ini adalah menghitung kemiringan dan menggunakan angka ganda untuk menyatakan kemiringan. Implementasi pertama adalah sebagai berikut:
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);//继续处理右边的 ，这里是一个递归的过程
}
Implementasi di atas tidak dapat lolos jika kasus uji memiliki poin yang sama, karena situasi poin yang sama tidak dipertimbangkan. Cara di atas adalah menghitung kemiringan semua titik, kemudian mengurutkannya untuk mengetahui keadaan panjang lereng, kemudian menguraikan berapa kali kemiringan tersebut muncul untuk menghitung jumlah titik panjang.
Salah satu kelemahan dari ide implementasi ini adalah pertama-tama menghitung kemiringan semua titik dan kemudian melakukan penghitungan. Hal ini membuat lebih sulit untuk menangani titik duplikat.
Perbaikan pada metode ini adalah dengan menghitung kemiringan garis lurus antara setiap titik dengan titik lainnya, kemudian mencari titik yang paling optimal. Implementasinya adalah sebagai berikut:
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;
}
Implementasi di atas gagal ketika kasus uji [[0,0],[94911151,94911150],[94911152,94911151]], karena double mewakili kemiringan, dan kemiringan ketiga titik tersebut sama. Namun ketiga titik tersebut tidak berada pada satu garis lurus.
[[0,0],[94911151,94911150],[94911152,94911151]] Kasus uji ini seharusnya ditambahkan nanti. Beberapa kode bahasa C yang ditemukan di area komentar tidak dapat lulus uji kasus ini.
Kesulitan dari soal ini adalah bagaimana cara menyatakan kemiringan?
Belakangan, saya menemukan bahwa mengubah kemiringan yang dinyatakan dalam ganda menjadi ganda panjang dapat melewati semua kasus uji.
Faktanya, representasi ganda yang panjang bukanlah representasi perkiraan, dan mungkin ada beberapa tombol yang tidak dapat dilewati. Kemiringan pertanyaan ini harus dinyatakan dalam pecahan.
Kode lengkapnya adalah sebagai berikut:
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;
}
Ulasan
https://dandan2009.github.io/2018/12/28/exposing-NSDictionary/
TIPS
Ada banyak metode konfigurasi di situs konfigurasi Reveal, seperti ini: https://www.cnblogs.com/somethingWithiOS/p/6594496.html， Konfigurasinya merepotkan dan memerlukan perubahan file proyek. Berikut adalah metode sederhana.
Metode konfigurasi pod hanya satu baris tanpa mengubah file proyek:
pod ‘RevealServer’, :konfigurasi => [‘Debug’], :path => ‘./RevealServer’
:configurations berarti hanya valid dalam debug
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
Untuk demo selengkapnya, lihat: https://github.com/dandan2009/RevealServerDemo
Bagikan
Tidak cukup waktu, landasan lemah, algoritma pembelajaran non-teknis:
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