我正在尝试解决最新的codility.com问题（只是为了提高我的技能）。我试过分配，但没有超过30分，所以现在好奇我在解决方案中究竟缺少什么。
问题说
给出了由N个整数组成的非空零索引数组A.峰值是一个比其邻居更大的数组元素。更确切地说，它是指数P
0 < P < N − 1 and A[P − 1] < A[P] > A[P + 1]
例如，以下数组A：
A[0] = 1
A[1] = 5
A[2] = 3
A[3] = 4
A[4] = 3
A[5] = 4
A[6] = 1
A[7] = 2
A[8] = 3
A[9] = 4
A[10] = 6
A[11] = 2
恰好有四个峰：元素1,3,5和10。
您将前往一系列相对高度由阵列A表示的山脉。您必须选择应该带多少旗帜。目标是根据某些规则设置峰值上的最大标志数。
标志只能在峰值上设置。更重要的是，如果你取K标志，那么任何两个标志之间的距离应该大于或等于K.指数P和Q之间的距离是绝对值| P-Q |。
例如，给定由上面的数组A表示的山脉，N = 12，如果你采取：
> two flags, you can set them on peaks 1 and 5;
> three flags, you can set them on peaks 1, 5 and 10;
> four flags, you can set only three flags, on peaks 1, 5 and 10.
因此，在这种情况下，您最多可以设置三个标志。
编写一个函数，给定N个整数的非空零索引数组A，返回可在数组峰值上设置的最大标志数。例如，给定上面的数组
该函数应返回3，如上所述。
假使，假设：
N是[1..100,000]范围内的整数;
数组A的每个元素是[0..1,000,000,000]范围内的整数。
复杂：
预期的最坏情况时间复杂度是O（N）;预期的最坏情况空间复杂度是O（N），超出输入存储（不计入输入参数所需的存储）。
所以我根据我对问题的理解尝试了这段代码
var A = [1,5,3,4,3,4,1,2,3,4,6,2];
function solution(A) {
array = new Array();
for (i = 1; i < A.length - 1; i++) {
if (A[i - 1] < A[i] && A[i + 1] < A[i]) {
array.push(i);
}
}
//console.log(A);
//console.log(array);
var position = array[0];
var counter = 1;
var len = array.length;
for (var i = 0; i < len; i++) {
if (Math.abs(array[i+1] - position) >= len) {
position = array[i+1];
counter ++;
}
}
console.log("total:",counter);
return counter;
}
上面的代码适用于样本数组元素：[1,5,3,4,3,4,1,2,3,4,6,2]在索引处获取峰值：[1, 3, 5, 10]并在1, 5, and 10 (total 3)设置标志
但codility.com表示它在阵列上失败[7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7]我的代码在索引处得到峰值：[1, 4, 6, 8]并在1和6（总共2）设置标志，但coditity.com说它应该是3个标志。 （不知道为什么）我想念 - 理解这个问题吗？
请我只是寻找提示/算法。我知道这个问题已被某人提出并在私人聊天室中解决但在该页面上我试图获得该人的帮助，但成员却将我的帖子标记为不恰当的答案，所以我再次在这里提出问题。
P.S：您可以点击挑战自己在www.codility.com上试用您的代码！
缺少100％的PHP解决方案:)
function solution($A)
{
$p = array(); // peaks
for ($i=1; $i<count($A)-1; $i++)
if ($A[$i] > $A[$i-1] && $A[$i] > $A[$i+1])
$p[] = $i;
$n = count($p);
if ($n <= 2)
return $n;
$maxFlags = min(intval(ceil(sqrt(count($A)))), $n); // max number of flags
$distance = $maxFlags; // required distance between flags
// try to set max number of flags, then 1 less, etc... (2 flags are already set)
for ($k = $maxFlags-2; $k > 0; $k--)
{
$left = $p[0];
$right = $p[$n-1];
$need = $k; // how many more flags we need to set
for ($i = 1; $i<=$n-2; $i++)
{
// found one more flag for $distance
if ($p[$i]-$left >= $distance && $right-$p[$i] >= $distance)
{
if ($need == 1)
return $k+2;
$need--;
$left = $p[$i];
}
if ($right - $p[$i] <= $need * ($distance+1))
break; // impossible to set $need more flags for $distance
}
if ($need == 0)
return $k+2;
$distance--;
}
return 2;
}
这是一个100％的Java解决方案
class Solution {
public int solution(int[] A) {
int[] nextPeaks = nextPeaks(A);
int flagNumebr = 1;
int result = 0;
while ((flagNumebr-1)*flagNumebr <= A.length) {
int flagPos = 0;
int flagsTaken = 0;
while (flagPos < A.length && flagsTaken < flagNumebr) {
flagPos = nextPeaks[flagPos];
if (flagPos == -1) {
// we arrived at the end of the peaks;
break;
}
flagsTaken++;
flagPos += flagNumebr;
}
result = Math.max(result, flagsTaken);
flagNumebr++;
}
return result;
}
private boolean[] createPeaks(int[] A) {
boolean[] peaks = new boolean[A.length];
for (int i = 1; i < A.length-1; i++) {
if (A[i - 1] < A[i] && A[i] > A[i + 1]) {
peaks[i] = true;
}
}
return peaks;
}
private int[] nextPeaks (int[] A) {
boolean[] peaks = createPeaks(A);
int[] nextPeaks = new int[A.length];
// the last position is always -1
nextPeaks[A.length-1] = -1;
for (int i = A.length-2; i >= 0 ; i--) {
nextPeaks[i] = peaks[i] ? i : nextPeaks[i+1];
}
return nextPeaks;
}
}
C＃解决方案100％积分。
using System;
using System.Collections.Generic;
class Solution {
public int solution(int[] A) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
List<int> peaks = new List<int>();
for (int i = 1; i < A.Length - 1; i++)
{
if (A[i - 1] < A[i] && A[i + 1] < A[i])
{
peaks.Add(i);
}
}
if (peaks.Count == 1 || peaks.Count == 0)
{
return peaks.Count;
}
int leastFlags = 1;
int mostFlags = peaks.Count;
int result = 1;
while (leastFlags <= mostFlags)
{
int flags = (leastFlags + mostFlags) / 2;
bool suc = false;
int used = 0;
int mark = peaks[0];
for (int i = 0; i < peaks.Count; i++)
{
if (peaks[i] >= mark)
{
used++;
mark = peaks[i] + flags;
if (used == flags)
{
suc = true;
break;
}
}
}
if (suc)
{
result = flags;
leastFlags = flags + 1;
}
else
{
mostFlags = flags - 1;
}
}
return result;
}
}
100％工作的JS解决方案：
function solution(A) {
let peaks = [];
for (let i = 1; i < A.length - 1; i++) {
if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
peaks.push(i);
}
}
let n = peaks.length;
if (n <= 2) {
return n;
}
let maxFlags = Math.min(n, Math.ceil(Math.sqrt(A.length)));
let distance = maxFlags;
let rightPeak = peaks[n - 1];
for (let k = maxFlags - 2; k > 0; k--) {
let flags = k;
let leftPeak = peaks[0];
for (let i = 1; i <= n - 2; i++) {
if (peaks[i] - leftPeak >= distance && rightPeak - peaks[i] >= distance) {
if (flags === 1) {
return k + 2;
}
flags--;
leftPeak = peaks[i];
}
if (rightPeak - peaks[i] <= flags * (distance + 1)) {
break;
}
}
if (flags === 0) {
return k + 2;
}
distance--;
}
return 2;
}
int solution(int A[], int N) {
int i,j,k;
int count=0;
int countval=0;
int count1=0;
int flag;
for(i=1;i<N-1;i++)
{`enter code here`
if((A[i-1]<A[i]) && (A[i]>A[i+1]))
{
printf("%d %d\n",A[i],i);
A[count++]=i;
i++;
}
}
j=A[0];
k=0;
if (count==1 || count==0)
return count;
if (count==2)
{
if((A[1]-A[0])>=count)
return 2;
else
return 1;
}
flag=0;
// contval=count;
count1=1;
countval=count;
while(1)
{
for(i=1;i<count;i++)
{
printf("%d %d\n",A[i],j);
if((A[i]-j)>=countval)
{
printf("Added %d %d\n",A[i],j);
count1++;
j=A[i];
}
/* if(i==count-1 && count1<count)
{
j=A[0];
i=0;
count1=1;
}*/
}
printf("count %d count1 %d \n",countval,count1);
if (count1<countval)
{
count1=1;
countval--;
j=A[0];
}
else
{
break; }
}
return countval;
}
解决这个问题：
[P - Q] >= K）**我仍在寻找如何为此问题编写最佳优化代码
import java.util.Arrays;
import java.lang.Integer;
import java.util.ArrayList;
import java.util.List;
public int solution(int[] A)
{
ArrayList<Integer> array = new ArrayList<Integer>();
for (int i = 1; i < A.length - 1; i++)
{
if (A[i - 1] < A[i] && A[i + 1] < A[i])
{
array.add(i);
}
}
if (array.size() == 1 || array.size() == 0)
{
return array.size();
}
int sf = 1;
int ef = array.size();
int result = 1;
while (sf <= ef)
{
int flag = (sf + ef) / 2;
boolean suc = false;
int used = 0;
int mark = array.get(0);
for (int i = 0; i < array.size(); i++)
{
if (array.get(i) >= mark)
{
used++;
mark = array.get(i) + flag;
if (used == flag)
{
suc = true;
break;
}
}
}
if (suc)
{
result = flag;
sf = flag + 1;
}
else
{
ef = flag - 1;
}
}
return result;
}
这是一个具有更好的上层复杂性边界的解决方案：
O(sqrt(N) * log(N))O(1)（在原始输入存储上）from math import sqrt
def transform(A):
peak_pos = len(A)
last_height = A[-1]
for p in range(len(A) - 1, 0, -1):
if (A[p - 1] < A[p] > last_height):
peak_pos = p
last_height = A[p]
A[p] = peak_pos
A[0] = peak_pos
def can_fit_flags(A, k):
flag = 1 - k
for i in range(k):
# plant the next flag at A[flag + k]
if flag + k > len(A) - 1:
return False
flag = A[flag + k]
return flag < len(A) # last flag planted successfully
def solution(A):
transform(A)
lower = 0
upper = int(sqrt(len(A))) + 2
assert not can_fit_flags(A, k=upper)
while lower < upper - 1:
next = (lower + upper) // 2
if can_fit_flags(A, k=next):
lower = next
else:
upper = next
return lower
O(N)预处理（完成就地）：
A[i] := next peak or end position after or at position i
(i for a peak itself, len(A) after last peak)
如果我们可以种植k标志，那么我们当然也可以种植k' < k标志。如果我们不能种植k标志，那么我们当然也不能种植k' > k标志。我们总是可以设置0个标志。让我们假设我们不能设置X标志。现在我们可以使用二进制搜索来确切地找出可以种植多少个标志。
Steps:
1. X/2
2. X/2 +- X/4
3. X/2 +- X/4 +- X/8
...
log2(X) steps in total
通过之前完成的预处理，可以在k操作中执行测试是否可以种植O(k)标志的每个步骤：
总成本 - 最坏的情况 - 可以种植X - 1标志：
== X *（1/2 + 3/4 + ... +（2 ^ k - 1）/（2 ^ k）） == X *（log2（X） - 1 +（<1）） <= X * log（X）
使用X == N会起作用，并且很可能也是次线性的，但是不足以用于证明该算法的总上限在O(N)之下。
现在一切都取决于找到一个好的X，并且它自k标志采取k^2位置适合，似乎在sqrt(N)附近的某处可以找到标志数量的良好上限。
如果X == sqrt(N)或接近它的东西起作用，那么我们得到O(sqrt(N) * log(sqrt(N)))的上限，这绝对是次线性的，因为log(sqrt(N)) == 1/2 * log(N)上限相当于O(sqrt(N) * log(N))。
让我们来看看sqrt(N)周围所需标志数量的更精确上限：
k标志需要Nk := k^2 - k + 3标志k^2 - k + 3 - N = 0上求解方程k，我们发现如果k >= 3，那么任意数量的标志<=得到的k可以适合某个长度为N的序列而较大的那个不能;这个等式的解是1/2 * (1 + sqrt(4N - 11))N >= 9，我们知道我们可以为N >= 9设置3个标志==>，k = floor(1/2 * (1 + sqrt(4N - 11))) + 1是我们可以放入N的标志数量的严格上限N < 9，我们知道3是一个严格的上界，但这些情况并不关心我们找到大O算法的复杂性地板（1/2 *（1 + sqrt（4N - 11）））+ 1 == floor（1/2 + sqrt（N - 11/4））+ 1 <= floor（sqrt（N - 11/4））+ 2 <= floor（sqrt（N））+ 2
==> floor(sqrt(N)) + 2对于许多可以放入N元素的标志来说也是一个很好的严格上界+这个甚至对于N < 9也是如此，因此它可以在我们的实现中用作通用的严格上限
如果我们选择X = floor(sqrt(N)) + 2，我们得到以下总算法上限：
O((floor(sqrt(N)) + 2) * log(floor(sqrt(N)) + 2))
{floor(...) <= ...}
O((sqrt(N) + 2) * log(sqrt(N) + 2))
{for large enough N >= 4: sqrt(N) + 2 <= 2 * sqrt(N)}
O(2 * sqrt(N) * log(2 * sqrt(N)))
{lose the leading constant}
O(sqrt(N) * (log(2) + loq(sqrt(N)))
O(sqrt(N) * log(2) + sqrt(N) * log(sqrt(N)))
{lose the lower order bound}
O(sqrt(N) * log(sqrt(N)))
{as noted before, log(sqrt(N)) == 1/2 * log(N)}
O(sqrt(N) * log(N))
QED
我知道答案是由francesco Malagrino提供的，但我已经编写了自己的代码。对于阵列{1,5,3,4,3,4,1,2,3,4,6,2}和{7,10,4,5,7,4,6,1,4,3， 3,7}我的代码工作正常。当我在代码考试中使用我的代码时，我在{9,9,4,3,5,4,5,2,8,9,3,1}上失败了
我的回答是3个最大标志。我理解它的方式应该是3但是正确答案是2，而且对于francesco Malagrino的解决方案也是如此。
在我的代码中似乎有什么问题，为什么答案应该只是2峰4,6,9之间的距离遵循规则的事实。
private static int getpeak(int[] a) {
List<Integer> peak = new ArrayList<Integer>();
int temp1 = 0;
int temp2 = 0;
int temp3 = 0;
for (int i = 1; i <= (a.length - 2); i++) {
temp1 = a[i - 1];
temp2 = a[i];
temp3 = a[i + 1];
if (temp2 > temp1 && temp2 > temp3) {
peak.add(i);
}
}
Integer[] peakArray = peak.toArray(new Integer[0]);
int max = 1;
int lastFlag = 0;
for (int i = 1; i <= peakArray.length - 1; i++) {
int gap = peakArray[i] - peakArray[lastFlag];
gap = Math.abs(gap);
if (gap >= i+1) {
lastFlag = i;
max = max + 1;
}
}
return max;
}
这是一个100％得分的C ++解决方案
int test(vector<int> &peaks,int i,int n)
{
int j,k,sum,fin,pos;
fin = n/i;
for (k=0; k< i; k++)
{
sum=0;
for (j=0; j< fin; j++)
{ pos = j + k * fin;
sum=sum + peaks[ pos ];
}
if (0==sum) return 0;
}
return 1;
}
int solution(vector<int> &A) {
// write your code in C++98
int i,n,max,r,j,salir;
n = A.size();
vector<int> peaks(n,0);
if (0==n) return 0;
if (1==n) return 0;
for (i=1; i< (n-1) ; i++)
{
if ( (A[i-1] < A[i]) && (A[i+1] < A[i]) ) peaks[i]=1;
}
i=1;
max=0;
salir =0;
while ( ( i*i < n) && (0==salir) )
{
if ( 0== n % i)
{
r=test(peaks,i,n);
if (( 1==r ) && (i>max)) max=i;
j = n/i;
r=test(peaks,j,n);
if (( 1==r ) && (j>max)) max=j;
if ( max > n/2) salir =1;
}
i++;
}
if (0==salir)
{
if (i*i == n)
{
if ( 1==test(peaks,i,n) ) max=i;
}
}
return max;
}
C ++解决方案，检测到O（N）
#include <algorithm>
int solution(vector<int> &a) {
if(a.size() < 3) return 0;
std::vector<int> peaks(a.size());
int last_peak = -1;
peaks.back() = last_peak;
for(auto i = ++a.rbegin();i != --a.rend();i++)
{
int index = a.size() - (i - a.rbegin()) - 1;
if(*i > *(i - 1) && *i > *(i + 1))
last_peak = index;
peaks[index] = last_peak;
}
peaks.front() = last_peak;
int max_flags = 0;
for(int i = 1;i*i <= a.size() + i;i++)
{
int next_peak = peaks[0];
int flags = 0;
for(int j = 0;j < i && next_peak != -1;j++, flags++)
{
if(next_peak + i >= a.size())
next_peak = -1;
else
next_peak = peaks[next_peak + i];
}
max_flags = std::max(max_flags, flags);
}
return max_flags;
}
public int solution(int[] A) {
int p = 0;
int q = 0;
int k = 0;
for (int i = 0; i < A.length; i++) {
if (i > 0 && i < A.length && (i + 1) < A.length - 1) {
if (A[i] > A[i - 1] && A[i] > A[i + 1]) {
p = i;
if (i < A.length / 2)
k++;
}
if (i > 0 && i < A.length && (A.length - i + 1) < A.length) {
if (A[A.length - i] > A[A.length - i - 1]
&& A[A.length - i] > A[A.length - i + 1] ) {
q = A.length - i;
if (i < A.length / 2)
k++;
else {
if (Math.abs(p - q) < k && p != q)
k--;
}
}
}
}
}
return k;
}
import sys
def get_max_num_peaks(arr):
peaks = [i for i in range(1, len(arr)-1, 1) if arr[i]>arr[i-1] and arr[i]>arr[i+1]]
max_len = [1 for i in peaks]
smallest_diff = [0 for i in peaks]
smallest_diff[0] = sys.maxint
for i in range(1, len(peaks), 1):
result = 1
for j in range(0, i, 1):
m = min(smallest_diff[j], peaks[i]-peaks[j])
if smallest_diff[j]>0 and m>=max_len[j]+1:
max_len[i] = max_len[j]+1
smallest_diff[i] = m
result = max(result, max_len[i])
return result
if __name__ == "__main__":
result = get_max_num_peaks([7, 10, 4, 5, 7, 4, 6, 1, 4, 3, 3, 7])
print result
我用DP来解决这个问题。这是python代码：可以为结束于i的数组设置最大标志数，如果min（min_diff（0 ... j），j到i）不小于max_len，则可以在j上设置最大标志数（0 .. j）+1如果我错了或有O（N）解决方案，请纠正我
我提出了这个问题的算法，它既是O（N）又通过了所有的密码测试。主要思想是标志的数量不能超过N的平方根。因此，为了使总顺序保持线性，每次迭代应该小于N的平方根，这也就是标志本身的数量。
首先，我构建了一个数组nextPeak，它为A的每个索引提供索引后最接近的标志。然后，在第二部分中，我将来自N的根的所有可能数量的标志的f迭代回0，以找到可以在阵列上应用的最大标志数。在每次迭代中，我尝试应用标志并使用nextPeak数组在恒定时间内找到下一个峰值。
代码如下所示：
public int solution(int[] A){
if( A==null || A.length<3){
return 0;
}
int[] next = new int[A.length];
int nextPeak=-1;
for(int i =1; i<A.length; i++){
if(nextPeak<i){
for(nextPeak=i; nextPeak<A.length-1; nextPeak++){
if(A[nextPeak-1]<A[nextPeak] && A[nextPeak]>A[nextPeak+1]){
break;
}
}
}
next[i] = nextPeak;
}
next[0] = next[1];
int max = new Double(Math.sqrt(A.length)).intValue();
boolean failed = true ;
int f=max;
while(f>0 && failed){
int v=0;
for(int p=0; p<A.length-1 && next[p]<A.length-1 && v<f; v++, p+=max){
p = next[p];
}
if(v<f){
f--;
} else {
failed = false;
}
}
return f;
}