Problem:
Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
Solution:
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point> &points) {
int max_count = 0;
int size = points.size();
if (size < 3)
return size;
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
int slope;
bool slope_inf = false;
if (points[j].x - points[i].x != 0)
slope = (points[j].y - points[i].y)/(points[j].x - points[i].x);
else {
slope_inf = true;
}
int count = 0;
for (int k = 0; k < size; k++) {
int temp_slope;
bool temp_slope_inf = false;
if (points[k].x - points[i].x != 0)
temp_slope = (points[k].y - points[i].y)/(points[k].x - points[i].x);
else {
temp_slope_inf = true;
}
if (same(points[k], points[i]) ||
(temp_slope == slope) ||
((temp_slope_inf == true) && (slope_inf == true)) ) {
count++;
}
}
max_count = max(max_count, count);
count = 0;
}
}
return max_count;
}
bool same(Point i, Point j) {
if ((i.x == j.x) && (i.y == j.y))
return true;
return false;
}
};
================= Real easy one ===============
Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < version2 return -1, otherwise return 0.
Solution:
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
class Solution {
public:
int maxPoints(vector<Point> &points) {
int max_count = 0;
int size = points.size();
if (size < 3)
return size;
for (int i = 0; i < size; i++) {
for (int j = i + 1; j < size; j++) {
int slope;
bool slope_inf = false;
if (points[j].x - points[i].x != 0)
slope = (points[j].y - points[i].y)/(points[j].x - points[i].x);
else {
slope_inf = true;
}
int count = 0;
for (int k = 0; k < size; k++) {
int temp_slope;
bool temp_slope_inf = false;
if (points[k].x - points[i].x != 0)
temp_slope = (points[k].y - points[i].y)/(points[k].x - points[i].x);
else {
temp_slope_inf = true;
}
if (same(points[k], points[i]) ||
(temp_slope == slope) ||
((temp_slope_inf == true) && (slope_inf == true)) ) {
count++;
}
}
max_count = max(max_count, count);
count = 0;
}
}
return max_count;
}
bool same(Point i, Point j) {
if ((i.x == j.x) && (i.y == j.y))
return true;
return false;
}
};
================= Real easy one ===============
int compareVersion(string version1, string version2) {
for (int i = 0, j = 0; i < version1.size() || j < version2.size(); ++i, ++j) {
int num1 = 0, num2 = 0;
while (version1[i] != '.' && i < version1.size())
num1 = num1 * 10 + (version1[i++] - '0');
while (version2[j] != '.' && j < version2.size())
num2 = num2 * 10 + (version2[j++] - '0');
if (num1 > num2)
return 1;
if (num1 < num2)
return -1;
}
return 0;
}
No comments:
Post a Comment