- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我刚刚在 Codility,遇到了一个任务,我找不到目标 O(n) 效率的解决方案;我的解决方案运行时间为 O(n2)。如果有人能给我一些关于如何让它运行得更快的提示,我将非常高兴。这是任务。
给定一个由N个整数组成的非空零索引数组A。
monotonic_pair 是一对整数 (P, Q),满足 0 ≤ P ≤ Q < N 且 A[P] ≤ A[Q]。
目标是找到索引相距最远的单调对。更准确地说,我们应该最大化 Q − P 的值。仅找到距离就足够了。
例如,考虑这样的数组 A:
A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2
有十一个单调对:(0,0), (0, 2), (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3), (3, 4), (4, 4), (5, 5)。最大的距离是 3,在对 (1, 4) 中。
写一个函数:
class Solution { public int solution(int[] A);
给定一个包含 N 个整数的非空零索引数组 A,返回任何 monotonic_pairs 中的最大距离。
例如,给定:
A[0] = 5
A[1] = 3
A[2] = 6
A[3] = 3
A[4] = 4
A[5] = 2
函数应该返回 3,如上所述。
假设:
N为[1..300,000]范围内的整数;数组 A 的每个元素都是 [−1,000,000,000..1,000,000,000] 范围内的整数。复杂性:
预期的最坏情况时间复杂度为 O(N);预期的最坏情况空间复杂度为 O(N),超出输入存储(不包括输入参数所需的存储)。可以修改输入数组的元素。
我的第一个想法解决方案(在 O(n2) 中运行):
public static int solution(int[] A) {
int max = 0;
for(int i=0; i<A.length-1; i++) {
for(int j=i+1; j<A.length; j++) {
if(A[j] >= A[i] &&
(j - i) >= max) {
max = j - i;
}
}
}
return max;
}
最佳答案
MarcinLe 的比 n^2 好,但仍然在 nlogn 中运行。您可以通过不每次都进行登录查找来进行优化。相反,同时向前迭代最大数组和输入 A[] 数组以保证线性时间。
int[] top = new int[A.length];
int max = -Integer.MAX_VALUE;
for (int i=A.length-1; i>=0; i--) {
if (A[i] > max) max = A[i];
top[i] = max;
}
int best = 0;
int curMaxIndex = 0;
for (int i=0; i<A.length; i++) {
while(curMaxIndex < top.length && top[curMaxIndex] >= A[i])
curMaxIndex++;
if((curMaxIndex - 1 - i) > best)
best = curMaxIndex - 1 - i
}
return best;
关于java - 单调对 - Codility,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23113268/
试图了解 Codility NailingPlanks 的解决方案。 问题链接: https://app.codility.com/programmers/lessons/14-binary_sear
我遇到了这个 codility 测试,问题是发现函数中的错误并调整它以使其正常工作。 传递给函数的数组是{1,3,3},K =2。如果在数组中找不到 K,该函数应该返回 false,但它返回 true
我有一个 Codility 测试即将进行。我试图通过使用 LONG 而不是 INT 在代码中找到一个修改来避免 EXTREME LARGE NUMBERS ERROR...但这没有用。 有人试过使用
昨晚我在 Codility 上查看了 Equi 演示任务,并为以下功能获得了 12/100 分: function solution(A) { var n = A.length; va
这是我对计数半素数可修正性问题的解决方案,它适用于中小型输入,但会导致大型测试用例的段错误。 https://codility.com/demo/results/demo8JU794-FC7/ 这通常
问题: 给定一串数字,计算是任何回文的字谜的子词(一致的子序列)的数量。 例子: 对于输入字符串“02002”,结果应该是 11,即: “0”、“2”、“0”、“0”、“2”、“00”、“020”、“
我正在 codility.com 上执行排列任务。目标基本上是检查数组是否作为与排列大小完全匹配的一个元素传递。 IE。对于 array size N,它应该包含值 1,2,3...N,每个值恰好一次
我做了 codility 演示测试“NumberOfDiscIntersections”: https://codility.com/programmers/lessons/4 我有:性能 = 100
这个问题在这里已经有了答案: Finding minimal absolute sum of a subarray (11 个答案) 关闭 4 年前。 您好,我参加了两次 Codility 测试,得
我刚刚在 Codility,遇到了一个任务,我找不到目标 O(n) 效率的解决方案;我的解决方案运行时间为 O(n2)。如果有人能给我一些关于如何让它运行得更快的提示,我将非常高兴。这是任务。 给定一
我的解决方案在 Codility 上的正确率仅为 40%。 我做错了什么? Here是测试结果(https://codility.com/demo/results/trainingU7KSSG-YNX
Codality 有一种有趣的命名方式。例如:他们说“领导者”而不是多数元素。 他们描述了一种技术here称为 Caterpillar method.这项技术的真正技术名称是什么? (我猜是回溯,但我
这个问题在这里已经有了答案: Counting palindromic substrings in O(n) (3 个答案) 关闭 9 年前。 在这个问题中,我们只考虑由小写英文字母 (a−z) 组
所以我决定试试 Codility .第一个任务 - FrogJmp太简单了,但令我惊讶的是我得到了 44%。解决方案,即使是正确的,在性能方面显然也是 Not Acceptable 。 原始解决方案:
我一直在努力解决以下任务: 你有 N 个计数器,初始设置为 0,你可以对它们进行两种可能的操作: increase(X) − counter X is increased by 1,
我试过这个 Codility 测试:MinAbsSum。 https://codility.com/programmers/lessons/17-dynamic_programming/min_abs
我正在尝试找到 a codility question on minimum slice of a subarray 的解决方案,并且我使用 Kadane 算法的修改版本设计了一个解决方案。我目前得到
任务是: 给出了一个非空的零索引字符串 S。字符串 S 由大写英文字母 A、C、G、T 集合中的 N 个字符组成。 这个字符串实际上代表一个DNA序列,大写字母代表单个核苷酸。 你还得到了由 M 个整
我需要一些帮助来解决这个 codility 挑战的算法: 编写一个函数,给定三个整数 A、B 和 K,返回 [A..B] 范围内可被 K 整除的整数个数。例如,对于 A = 6,B = 11 和 K
我使用 Scala 编写了 Codility 上 TapeEquilibrium 问题的解决方案。我已经尝试了许多不同负载的测试输入,当我使用 Codility Develipment 环境和 ecl
我是一名优秀的程序员,十分优秀!