计算相交圆盘数量的algorithm
给定一个N整数的数组A ，我们在2D平面中绘制N圆盘，使得第i个圆盘以(0,i)中心，半径为A[i] 。 如果第k个和第j个盘至less有一个公共点，我们说第k个盘和第j个盘相交。
写一个函数
int number_of_disc_intersections(int[] A);
给出如上所述的描述N盘的arraysA返回交叉盘对的数量。 例如，给定N=6和
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0
有11对相交的光盘：
0th and 1st 0th and 2nd 0th and 4th 1st and 2nd 1st and 3rd 1st and 4th 1st and 5th 2nd and 3rd 2nd and 4th 3rd and 4th 4th and 5th
所以函数应该返回11.如果交叉对的数量超过10,000,000，函数应该返回-1。 函数可以假设N不超过10,000,000。
所以你想find区间的交集数[iA[i], i+A[i]] 。
维护一个包含iA[i]的有序数组（也有一些额外的空间，其值为i+A[i] ）。
现在从最左边的区间开始走数组X（即最小的iA[i] ）。
对于当前时间间隔，执行二进制search以查看区间的右端点（即i+A[i] ）将会走向哪里（称为等级）。 现在你知道它与左边的所有元素相交。
增加一个计数器与排名和减去当前位置（假设一个索引），因为我们不想加倍计数区间和自我交集。
O（nlogn）时间， O（n）空间。
O（N）复杂度和O（N）内存解决scheme。
private static int Intersections(int[] a) { int result = 0; int[] dps = new int[a.length]; int[] dpe = new int[a.length]; for (int i = 0, t = a.length - 1; i < a.length; i++) { int s = i > a[i]? i - a[i]: 0; int e = t - i > a[i]? i + a[i]: t; dps[s]++; dpe[e]++; } int t = 0; for (int i = 0; i < a.length; i++) { if (dps[i] > 0) { result += t * dps[i]; result += dps[i] * (dps[i] - 1) / 2; if (10000000 < result) return -1; t += dps[i]; } t -= dpe[i]; } return result; }
好吧，我把FalkHüffner的想法改编成了C ++，并且改变了范围。 与上面所写的相反，没有必要超出数组的范围（不pipe数值有多大）。 在Codility这个代码收到100％。 谢谢你福尔克你的好主意！
int number_of_disc_intersections ( const vector<int> &A ) { int sum=0; vector<int> start(A.size(),0); vector<int> end(A.size(),0); for (unsigned int i=0;i<A.size();i++){ if ((int)i<A[i]) start[0]++; else start[iA[i]]++; if (i+A[i]>=A.size()) end[A.size()-1]++; else end[i+A[i]]++; } int active=0; for (unsigned int i=0;i<A.size();i++){ sum+=active*start[i]+(start[i]*(start[i]-1))/2; if (sum>10000000) return -1; active+=start[i]-end[i]; } return sum; }
这甚至可以在线性时间内完成。 事实上，如果忽略每个点都有一个中心间隔的事实，那么把它当作一组间隔的起点和终点就变得更容易了。 然后你可以从左边扫描它（Python代码为了简单起见）：
from collections import defaultdict a = [1, 5, 2, 1, 4, 0] start = defaultdict(int) stop = defaultdict(int) for i in range(len(a)): start[i - a[i]] += 1 stop[i + a[i]] += 1 active = 0 intersections = 0 for i in range(-len(a), len(a)): intersections += active * start[i] + (start[i] * (start[i] - 1)) / 2 active += start[i] active -= stop[i] print intersections
这是一个O（N）时间， O（N）空间algorithm，需要在整个arrays中进行3次运算，不需要sorting， validation得分为100％ ：
你对成对的光盘感兴趣。 每对包括一张光盘的一面和另一张光盘的另一面。 因此，如果我们处理每张光盘的一面，我们将不会有重复的对。 让我们来左右两边（我在思考它的同时旋转了空间）。
重叠是由于右侧与另一个光盘直接在中心重叠（所以对的半径与半径有关，要注意arrays的长度），还是由于左侧的数量存在于最右边缘。
所以我们创build一个数组，其中包含每个点左侧的数量，然后它是一个简单的总和。
C代码：
int solution(int A[], int N) { int C[N]; int a, S=0, t=0; // Mark left and middle of disks for (int i=0; i<N; i++) { C[i] = -1; a = A[i]; if (a>=i) { C[0]++; } else { C[ia]++; } } // Sum of left side of disks at location for (int i=0; i<N; i++) { t += C[i]; C[i] = t; } // Count pairs, right side only: // 1. overlaps based on disk size // 2. overlaps based on disks but not centers for (int i=0; i<N; i++) { a = A[i]; S += ((a<Ni) ? a: Ni-1); if (i != N-1) { S += C[((a<Ni) ? i+a: N-1)]; } if (S>10000000) return -1; } return S; }
python100/100（testing）编码，O（nlogn）时间和O（n）空间。
这里是@anisyboiler的@ Aryabhatta方法的Python实现，带有注释和示例。 充分相信原作者，任何错误/措辞不佳完全是我的错。
from bisect import bisect_right def number_of_disc_intersections(A): pairs = 0 # create an array of tuples, each containing the start and end indices of a disk # some indices may be less than 0 or greater than len(A), this is fine! # sort the array by the first entry of each tuple: the disk start indices intervals = sorted( [(iA[i], i+A[i]) for i in range(len(A))] ) # create an array of starting indices using tuples in intervals starts = [i[0] for i in intervals] # for each disk in order of the *starting* position of the disk, not the centre for i in range(len(starts)): # find the end position of that disk from the array of tuples disk_end = intervals[i][1] # find the index of the rightmost value less than or equal to the interval-end # this finds the number of disks that have started before disk i ends count = bisect_right(starts, disk_end ) # subtract current position to exclude previous matches # this bit seemed 'magic' to me, so I think of it like this... # for disk i, i disks that start to the left have already been dealt with # subtract i from count to prevent double counting # subtract one more to prevent counting the disk itsself count -= (i+1) pairs += count if pairs > 10000000: return -1 return pairs
工作示例：给定[3，0，1，6]磁盘半径将如下所示：
disk0 ------- start= -3, end= 3 disk1 . start= 1, end= 1 disk2 --- start= 1, end= 3 disk3 ------------- start= -3, end= 9 index 3210123456789 (digits left of zero are -ve) intervals = [(-3, 3), (-3, 9), (1, 1), (1,3)] starts = [-3, -3, 1, 1] the loop order will be: disk0, disk3, disk1, disk2 0th loop: by the end of disk0, 4 disks have started one of which is disk0 itself none of which could have already been counted so add 3 1st loop: by the end of disk3, 4 disks have started one of which is disk3 itself one of which has already started to the left so is either counted OR would not overlap so add 2 2nd loop: by the end of disk1, 4 disks have started one of which is disk1 itself two of which have already started to the left so are either counted OR would not overlap so add 1 3rd loop: by the end of disk2, 4 disks have started one of which is disk2 itself two of which have already started to the left so are either counted OR would not overlap so add 0 pairs = 6 to check: these are (0,1), (0,2), (0,2), (1,2), (1,3), (2,3),
我用这个C ++实现了100个100：
#include <map> #include <algorithm> inline bool mySortFunction(pair<int,int> p1, pair<int,int> p2) { return ( p1.first < p2.first ); } int number_of_disc_intersections ( const vector<int> &A ) { int i, size = A.size(); if ( size <= 1 ) return 0; // Compute lower boundary of all discs and sort them in ascending order vector< pair<int,int> > lowBounds(size); for(i=0; i<size; i++) lowBounds[i] = pair<int,int>(iA[i],i+A[i]); sort(lowBounds.begin(), lowBounds.end(), mySortFunction); // Browse discs int nbIntersect = 0; for(i=0; i<size; i++) { int curBound = lowBounds[i].second; for(int j=i+1; j<size && lowBounds[j].first<=curBound; j++) { nbIntersect++; // Maximal number of intersections if ( nbIntersect > 10000000 ) return -1; } } return nbIntersect; }
一个Python的答案
from bisect import bisect_right def number_of_disc_intersections(li): pairs = 0 # treat as a series of intervals on the y axis at x=0 intervals = sorted( [(i-li[i], i+li[i]) for i in range(len(li))] ) # do this by creating a list of start points of each interval starts = [i[0] for i in intervals] for i in range(len(starts)): # find the index of the rightmost value less than or equal to the interval-end count = bisect_right(starts, intervals[i][1]) # subtract current position to exclude previous matches, and subtract self count -= (i+1) pairs += count if pairs > 10000000: return -1 return pairs
Java 2 * 100％。
result被宣布为只有一个情况下，编码没有testing，即一个点50k * 50k的交点。
class Solution { public int solution(int[] A) { int[] westEnding = new int[A.length]; int[] eastEnding = new int[A.length]; for (int i=0; i<A.length; i++) { if (iA[i]>=0) eastEnding[iA[i]]++; else eastEnding[0]++; if ((long)i+A[i]<A.length) westEnding[i+A[i]]++; else westEnding[A.length-1]++; } long result = 0; //long to contain the case of 50k*50k. codility doesn't test for this. int wests = 0; int easts = 0; for (int i=0; i<A.length; i++) { int balance = easts*wests; //these are calculated elsewhere wests++; easts+=eastEnding[i]; result += (long) easts*wests - balance - 1; // 1 stands for the self-intersection if (result>10000000) return -1; easts--; wests-= westEnding[i]; } return (int) result; } }
count = 0 for (int i = 0; i < N; i++) { for (int j = i+1; j < N; j++) { if (i + A[i] >= j - A[j]) count++; } }
这是O(N^2)非常慢，但它的作品。
这是一个ruby解决scheme，编码100/100。 我现在发布它，因为我发现很难遵循已经发布的ruby答案。
def solution(a) end_points = [] a.each_with_index do |ai, i| end_points << [i - ai, i + ai] end end_points = end_points.sort_by { |points| points[0]} intersecting_pairs = 0 end_points.each_with_index do |point, index| lep, hep = point pairs = bsearch(end_points, index, end_points.size - 1, hep) return -1 if 10000000 - pairs + index < intersecting_pairs intersecting_pairs += (pairs - index) end return intersecting_pairs end # This method returns the maximally appropriate position # where the higher end-point may have been inserted. def bsearch(a, l, u, x) if l == u if x >= a[u][0] return u else return l - 1 end end mid = (l + u)/2 # Notice that we are searching in higher range # even if we have found equality. if a[mid][0] <= x return bsearch(a, mid+1, u, x) else return bsearch(a, l, mid, x) end end
100/100 c＃
class Solution { class Interval { public long Left; public long Right; } public int solution(int[] A) { if (A == null || A.Length < 1) { return 0; } var itervals = new Interval[A.Length]; for (int i = 0; i < A.Length; i++) { // use long to avoid data overflow (eg. int.MaxValue + 1) long radius = A[i]; itervals[i] = new Interval() { Left = i - radius, Right = i + radius }; } itervals = itervals.OrderBy(i => i.Left).ToArray(); int result = 0; for (int i = 0; i < itervals.Length; i++) { var right = itervals[i].Right; for (int j = i + 1; j < itervals.Length && itervals[j].Left <= right; j++) { result++; if (result > 10000000) { return -1; } } } return result; } }
这得到了100/100在C＃
class CodilityDemo3 { public static int GetIntersections(int[] A) { if (A == null) { return 0; } int size = A.Length; if (size <= 1) { return 0; } List<Line> lines = new List<Line>(); for (int i = 0; i < size; i++) { if (A[i] >= 0) { lines.Add(new Line(i - A[i], i + A[i])); } } lines.Sort(Line.CompareLines); size = lines.Count; int intersects = 0; for (int i = 0; i < size; i++) { Line ln1 = lines[i]; for (int j = i + 1; j < size; j++) { Line ln2 = lines[j]; if (ln2.YStart <= ln1.YEnd) { intersects += 1; if (intersects > 10000000) { return -1; } } else { break; } } } return intersects; } } public class Line { public Line(double ystart, double yend) { YStart = ystart; YEnd = yend; } public double YStart { get; set; } public double YEnd { get; set; } public static int CompareLines(Line line1, Line line2) { return (line1.YStart.CompareTo(line2.YStart)); } }
}
感谢Falk的好主意！ 这是一个利用稀疏的ruby实现。
def int(a) event = Hash.new{|h,k| h[k] = {:start => 0, :stop => 0}} a.each_index {|i| event[i - a[i]][:start] += 1 event[i + a[i]][:stop ] += 1 } sorted_events = (event.sort_by {|index, value| index}).map! {|n| n[1]} past_start = 0 intersect = 0 sorted_events.each {|e| intersect += e[:start] * (e[:start]-1) / 2 + e[:start] * past_start past_start += e[:start] past_start -= e[:stop] } return intersect end puts int [1,1] puts int [1,5,2,1,4,0]
#include <stdio.h> #include <stdlib.h> void sortPairs(int bounds[], int len){ int i,j, temp; for(i=0;i<(len-1);i++){ for(j=i+1;j<len;j++){ if(bounds[i] > bounds[j]){ temp = bounds[i]; bounds[i] = bounds[j]; bounds[j] = temp; temp = bounds[i+len]; bounds[i+len] = bounds[j+len]; bounds[j+len] = temp; } } } } int adjacentPointPairsCount(int a[], int len){ int count=0,i,j; int *bounds; if(len<2) { goto toend; } bounds = malloc(sizeof(int)*len *2); for(i=0; i< len; i++){ bounds[i] = ia[i]; bounds[i+len] = i+a[i]; } sortPairs(bounds, len); for(i=0;i<len;i++){ int currentBound = bounds[i+len]; for(j=i+1;a[j]<=currentBound;j++){ if(count>100000){ count=-1; goto toend; } count++; } } toend: free(bounds); return count; }
Java中上述的思想的实现：
public class DiscIntersectionCount { public int number_of_disc_intersections(int[] A) { int[] leftPoints = new int[A.length]; for (int i = 0; i < A.length; i++) { leftPoints[i] = i - A[i]; } Arrays.sort(leftPoints); // System.out.println(Arrays.toString(leftPoints)); int count = 0; for (int i = 0; i < A.length - 1; i++) { int rpoint = A[i] + i; int rrank = getRank(leftPoints, rpoint); //if disk has sifnificant radius, exclude own self if (rpoint > i) rrank -= 1; int rank = rrank; // System.out.println(rpoint+" : "+rank); rank -= i; count += rank; } return count; } public int getRank(int A[], int num) { if (A==null || A.length == 0) return -1; int mid = A.length/2; while ((mid >= 0) && (mid < A.length)) { if (A[mid] == num) return mid; if ((mid == 0) && (A[mid] > num)) return -1; if ((mid == (A.length - 1)) && (A[mid] < num)) return A.length; if (A[mid] < num && A[mid + 1] >= num) return mid + 1; if (A[mid] > num && A[mid - 1] <= num) return mid - 1; if (A[mid] < num) mid = (mid + A.length)/2; else mid = (mid)/2; } return -1; } public static void main(String[] args) { DiscIntersectionCount d = new DiscIntersectionCount(); int[] A = //{1,5,2,1,4,0} //{0,0,0,0,0,0} // {1,1,2} {3} ; int count = d.number_of_disc_intersections(A); System.out.println(count); } }
以下是代码编码为100的PHP代码：
$sum=0; //One way of cloning the A: $start = array(); $end = array(); foreach ($A as $key=>$value) { $start[]=0; $end[]=0; } for ($i=0; $i<count($A); $i++) { if ($i<$A[$i]) $start[0]++; else $start[$i-$A[$i]]++; if ($i+$A[$i] >= count($A)) $end[count($A)-1]++; else $end[$i+$A[$i]]++; } $active=0; for ($i=0; $i<count($A);$i++) { $sum += $active*$start[$i]+($start[$i]*($start[$i]-1))/2; if ($sum>10000000) return -1; $active += $start[$i]-$end[$i]; } return $sum;
但是我不明白这个逻辑。 这只是从上面转换的C ++代码。 伙计们，你能详细说说你在这里做什么吗？
93％的分数http://codility.com/demo/results/demoUWFUDS-6XY/只有一个testing不起作用，为什么？;
// you can also use includes, for example: #include <algorithm> #include <map> inline bool mySortFunction(pair<int,int> p1, pair<int,int> p2) { return ( p1.first < p2.first ); } int solution ( const vector<int> &A ) { int i, size = A.size(); if ( size <= 1 ) return 0; // Compute lower boundary of all discs and sort them in ascending order vector< pair<int,int> > lowBounds(size); for(i=0; i<size; i++) lowBounds[i] = pair<int,int>(iA[i],i+A[i]); sort(lowBounds.begin(), lowBounds.end(), mySortFunction); // Browse discs long nbIntersect = 0; for(i=0; i<size; i++) { int curBound = lowBounds[i].second; for(int j=i+1; j<size && lowBounds[j].first<=curBound; j++) { nbIntersect++; // Maximal number of intersections if ( nbIntersect > 10000000 ) return -1; } } return nbIntersect; }
我试图把这个限制放在大于100000的情况下，在这种情况下，我忽略了一点，所以我们不清楚他们做了什么失败的testing。
Aryabhatta（二进制search解决scheme）描述的100/100 C＃实现。
using System; class Solution { public int solution(int[] A) { return IntersectingDiscs.Execute(A); } } class IntersectingDiscs { public static int Execute(int[] data) { int counter = 0; var intervals = Interval.GetIntervals(data); Array.Sort(intervals); // sort by Left value for (int i = 0; i < intervals.Length; i++) { counter += GetCoverage(intervals, i); if(counter > 10000000) { return -1; } } return counter; } private static int GetCoverage(Interval[] intervals, int i) { var currentInterval = intervals[i]; // search for an interval starting at currentInterval.Right int j = Array.BinarySearch(intervals, new Interval { Left = currentInterval.Right }); if(j < 0) { // item not found j = ~j; // bitwise complement (see Array.BinarySearch documentation) // now j == index of the next item larger than the searched one j = j - 1; // set index to the previous element } while(j + 1 < intervals.Length && intervals[j].Left == intervals[j + 1].Left) { j++; // get the rightmost interval starting from currentInterval.Righ } return j - i; // reduce already processed intervals (the left side from currentInterval) } } class Interval : IComparable { public long Left { get; set; } public long Right { get; set; } // Implementation of IComparable interface // which is used by Array.Sort(). public int CompareTo(object obj) { // elements will be sorted by Left value var another = obj as Interval; if (this.Left < another.Left) { return -1; } if (this.Left > another.Left) { return 1; } return 0; } /// <summary> /// Transform array items into Intervals (eg. {1, 2, 4} -> {[-1,1], [-1,3], [-2,6]}). /// </summary> public static Interval[] GetIntervals(int[] data) { var intervals = new Interval[data.Length]; for (int i = 0; i < data.Length; i++) { // use long to avoid data overflow (eg. int.MaxValue + 1) long radius = data[i]; intervals[i] = new Interval { Left = i - radius, Right = i + radius }; } return intervals; } }
Codility的 100％得分。
这里是对C＃ Толя 解决scheme的改编：
public int solution(int[] A) { long result = 0; Dictionary<long, int> dps = new Dictionary<long, int>(); Dictionary<long, int> dpe = new Dictionary<long, int>(); for (int i = 0; i < A.Length; i++) { Inc(dps, Math.Max(0, i - A[i])); Inc(dpe, Math.Min(A.Length - 1, i + A[i])); } long t = 0; for (int i = 0; i < A.Length; i++) { int value; if (dps.TryGetValue(i, out value)) { result += t * value; result += value * (value - 1) / 2; t += value; if (result > 10000000) return -1; } dpe.TryGetValue(i, out value); t -= value; } return (int)result; } private static void Inc(Dictionary<long, int> values, long index) { int value; values.TryGetValue(index, out value); values[index] = ++value; }
这是一个双向C ++解决scheme，不需要任何库，二进制search，sorting等。
int solution(vector<int> &A) { #define countmax 10000000 int count = 0; // init lower edge array vector<int> E(A.size()); for (int i = 0; i < (int) E.size(); i++) E[i] = 0; // first pass // count all lower numbered discs inside this one // mark lower edge of each disc for (int i = 0; i < (int) A.size(); i++) { // if disc overlaps zero if (i - A[i] <= 0) count += i; // doesn't overlap zero else { count += A[i]; E[i - A[i]]++; } if (count > countmax) return -1; } // second pass // count higher numbered discs with edge inside this one for (int i = 0; i < (int) A.size(); i++) { // loop up inside this disc until top of vector int jend = ((int) E.size() < (long long) i + A[i] + 1 ? (int) E.size() : i + A[i] + 1); // count all discs with edge inside this disc // note: if higher disc is so big that edge is at or below // this disc center, would count intersection in first pass for (int j = i + 1; j < jend; j++) count += E[j]; if (count > countmax) return -1; } return count; }
我在斯威夫特的回答; 获得100％的分数。
import Glibc struct Interval { let start: Int let end: Int } func bisectRight(intervals: [Interval], end: Int) -> Int { var pos = -1 var startpos = 0 var endpos = intervals.count - 1 if intervals.count == 1 { if intervals[0].start < end { return 1 } else { return 0 } } while true { let currentLength = endpos - startpos if currentLength == 1 { pos = startpos pos += 1 if intervals[pos].start <= end { pos += 1 } break } else { let middle = Int(ceil( Double((endpos - startpos)) / 2.0 )) let middlepos = startpos + middle if intervals[middlepos].start <= end { startpos = middlepos } else { endpos = middlepos } } } return pos } public func solution(inout A: [Int]) -> Int { let N = A.count var nIntersections = 0 // Create array of intervals var unsortedIntervals: [Interval] = [] for i in 0 ..< N { let interval = Interval(start: iA[i], end: i+A[i]) unsortedIntervals.append(interval) } // Sort array let intervals = unsortedIntervals.sort { $0.start < $1.start } for i in 0 ..< intervals.count { let end = intervals[i].end var count = bisectRight(intervals, end: end) count -= (i + 1) nIntersections += count if nIntersections > Int(10E6) { return -1 } } return nIntersections }
C＃解决scheme100/100
using System.Linq; class Solution { private struct Interval { public Interval(long @from, long to) { From = @from; To = to; } public long From { get; } public long To { get; } } public int solution(int[] A) { int result = 0; Interval[] intervals = A.Select((value, i) => { long iL = i; return new Interval(iL - value, iL + value); }) .OrderBy(x => x.From) .ToArray(); for (int i = 0; i < intervals.Length; i++) { for (int j = i + 1; j < intervals.Length && intervals[j].From <= intervals[i].To; j++) result++; if (result > 10000000) return -1; } return result; } }
ruby解决scheme。 得分100％。
def solution(a) # write your code in Ruby 2.2 open = Hash.new close = Hash.new (0..(a.length-1)).each do |c| r = a[c] open[ cr ] ? open[ cr ]+=1 : open[ cr ]=1 close[ c+r ] ? close[ c+r ]+=1 : close[ c+r ]=1 end open_now = 0 intersections = 0 open.merge(close).keys.sort.each do |v| intersections += (open[v]||0)*open_now open_now += (open[v]||0) - (close[v]||0) if(open[v]||0)>1 # sum the intersections of only newly open discs intersections += (open[v]*(open[v]-1))/2 return -1 if intersections > 10000000 end end intersections end
具有O(N*log(N))时间复杂度和O(N)空间复杂度的C＃100/100。
主要观点：
- 做2个sorting的数组：左点和右点。
- 将这些数组合并成一个布尔数组，其中
true表示“打开”，false表示“closures”间隔。 - 运行布尔数组并计算打开的时间间隔，将它们相加。
_
public int solution(int[] A) { var sortedStartPoints = A.Select((value, index) => (long)index-value).OrderBy(i => i).ToArray(); var sortedEndPoints = A.Select((value, index) => (long)index+value).OrderBy(i => i).ToArray(); // true - increment, false - decrement, null - stop var points = new bool?[2*A.Length]; // merge arrays for(int s=0, e=0, p=0; p < points.Length && s < sortedStartPoints.Length; p++) { long startPoint = sortedStartPoints[s]; long endPoint = sortedEndPoints[e]; if(startPoint <= endPoint) { points[p] = true; s++; } else { points[p] = false; e++; } } int result = 0; int opened = 0; // calculate intersections foreach(bool? p in points.TakeWhile(_ => _.HasValue)) { if(result > 10000000) return -1; if(p == true) { result += opened; opened++; } else { opened--; } } return result; }
One for the copy-paste kids out there:
function number_of_disc_intersections ( $A ) { $intersects = array(); $len = count($A); foreach($A as $i => $r ){ if( $r > 0 ){ $range = array(); if( $i > 0 ){ $range = range(max(0, $i-$r), max(0,$i-1)); } if( $i < $len ){ $range = array_merge( $range, range($i+1, min($len-1, $i+$r))); } foreach($range as $j){ $intersects[] = array(min($i,$j), max($i,$j)); } } if( count($intersects) > 100000000 ){ return -1; } } return array_unique($intersects, SORT_REGULAR); }
You will get 100/100 for the below solution in Java language
if (A == null || A.length < 2) { return 0; } int[] B = Arrays.copyOf(A, A.length); Arrays.sort(B); int biggest = B[A.length - 1]; int intersections = 0; for (int i = 0; i < A.length; i++) { for (int j = i + 1; j < A.length; j++) { if (j - biggest > i + A[i]) { break; } if (j - A[j] <= i + A[i]) { intersections++; } if (intersections > 10000000) { return -1; } } } return intersections;
JavaScript 2016
JavaScript version of Aryabhattas. I've changed it a bit making it more JS and more efficient performance wise and also added comments to explain what the algorithm does. 希望这可以帮助。
function solution(A) { var result = 0, len = A.length, dps = new Array(len).fill(0), dpe = new Array(len).fill(0), i, active = len - 1, s, e; for (i = 0; i < len; i++) { // adds to the begin array how many discs begin at the specific position given if (i > A[i]) s = i - A[i]; else s = 0; // adds to the end array the amount of discs that end at this specific position if (active - i > A[i]) e = i + A[i] else e = active; // a disc always begins and ends somewhere, s and e are the starting and ending positions where this specific disc for the element in A at position i reside dps[s] += 1; dpe[e] += 1; } // no discs are active as the algorithm must calculate the overlaps first, then the discs can be made active, hence why it begins with 0 active active = 0; for (i = 0; i < len; i++) { if (dps[i] > 0) { // new discs has entered the zone, multiply it with the current active discs as the new discs now overlap with the older active ones result += active * dps[i]; // new discs must also be counted against each other and not just the ones which were active prior result += dps[i] * (dps[i] - 1) / 2; // assignment rules if (10000000 < result) return -1; // add new discs to the active list that have started at this position active += dps[i]; } // remove discs as they have ended at this position active -= dpe[i]; } // return the result return result; } var A = [1, 5, 2, 1, 4, 0]; // should return 11 console.log(solution(A));
