josemontesp
BAN USERA solution in Javascript
'use strict';
/*
This is a O(n^2) time solution and O(n) in memory.
The algorithm is:
1. consider each point as the origin.
2. calculate the slope (y/x) of every point relative to this temporal origin
3. count the amount of times the most common slope repeats
4. return the highest count
*/
class Point{
constructor(x,y){
this.x = x;
this.y = y;
}
}
function slope(origin, point){
return (point.y - origin.y)/(point.x - origin.x); //Can be a float, +-Infinity, or NaN(when origin = point)
}
function maxNumberOfPointsInARect(points){
var result = 0;
points.map(origin=>{
var maxCount = 0; // max count for that particular origin
var counts = {}; // hash to count slopes repetitions more efficiently
var slopes = points.map(p=>slope(origin, p)); //slopes of all points relative to alternative origin point.
slopes.map(slope=>{ // counting number of repetitions for each slope
if (counts[slope])
counts[slope]++;
else
counts[slope] = 1;
maxCount = Math.max(maxCount, counts[slope]);
});
maxCount += counts[NaN]; // counting for the repetitions of the origin (at least one will be NaN because we are comparing origin against itself)
result = Math.max(result, maxCount);
});
return result;
}
//testing
var testPoints = [[1,2], [1,2], [1,2], [2,3], [2,3], [3,4], [3,4], [4,5], [4,5], [0,1], [0,1], [-1,0], [-1,0], [5,1]];
var r = maxNumberOfPointsInARect(testPoints.map(p=>new Point(...p))); // spread operator
console.log(r);
A solution in Javascript with O(N^2) time
//Returns true if the first i chars of the string match the last i chars of the string
function matchesFirstAndLastChars(S,i){
return S.slice(0, i+1) === S.slice(-1*(i+1));
}
//Removes one chunk at beginning and end of S
function removeLeadingAndTrailingChunk(S){
for (var i = 0; i < Math.floor(S.length/2); i++){
if (matchesFirstAndLastChars(S, i)){
return S.slice(i+1,S.length - 1 - i);
}
}
return S;
}
// Solution recursive function O(N^2)
function ChunkedPalindromeLength(S){
if (S.length === 0) return 0;
var shortened = removeLeadingAndTrailingChunk(S);
if (shortened === S) return 1;
return ChunkedPalindromeLength(shortened) + 2;
}
I found 3 solutions. The best one is the iterative solution. Written in Javascript
- josemontesp January 21, 2017