本文介绍了用于跟踪HackerRank问题的算法/代码的改进的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我知道,SO不是一个家庭作业的地方,因此,它非常针对问题范围。

I'm aware, SO is not a place for homework and hence, being very specific to the scope of question.

我试图在HackerRank:。问题语句非常简单,我实现了以下代码:

I was trying to solve this problem on HackerRank: Array Manipulation - Crush. The problem statement is quite simple and I implemented following code:

function arrayManipulation(n, queries) {
  const arr = new Array(n).fill(0)
  for (let j = 0; j < queries.length; j++) {
    const query = queries[j];
    const i = query[0] - 1;
    const limit = query[1];
    const value = query[2];
    while (i < limit) {
      arr[i++] += value;
    }
  }
  return Math.max.apply(null, arr);
}

现在,它可以正常工作一半测试用例但由于以下消息而中断:由于超时7到13,由于超时 终止,因为时间限制为 1秒

Now, it works fine for half the test-cases but breaks with following message: Terminated due to timeout for test-cases 7 - 13 as the time limit is 1 sec.

问题是,我可以在哪些方面改进此代码。据我了解,使用当前的算法,范围不大(我可能错了),所以我该如何改进算法?

So the question is, what are the areas where I can improve this code. In my understanding, with current algo, there is not much scope (I may be wrong), so how can I improve algo?

注意:不使用 .map 之类的数组函数查找替代项。减少,因为 for 更快。另外,使用 Math.max.apply(context,array)可以更快地拥有自定义循环。

Note: Not looking for alternates using array functions like .map or .reduce as for is faster. Also, using Math.max.apply(context, array) as it is faster that having custom loop. Attaching references for them.

参考文献:




  • How might I find the largest number contained in a JavaScript array?
  • Javascript efficiency: 'for' vs 'forEach'

推荐答案

对这个问题的观察


  • 当我们从数组的开头到结尾进行迭代时,让我们保持一个代表当前值的运行总和。

  • 如果我们将每个操作分解为另外两个操作(abk)->(ak)和(b -k)与(ak)意味着将k添加到位置 a的运行总和中和(b -k)表示从位置 b 的总和中减去k。

  • 我们可以进行排序所有这些操作都首先通过它们的p位置,然后再加上它们的运算符(加减运算符),我们总是可以得到正确的结果。

  • Let's keep a running sum representing the current value when we iterate from start to end of the array.
  • If we break each operation into two other operation (a b k) -> (a k) and (b -k) with (a k) means adding k into the running sum at position a and (b -k) means subtracting k from the sum at position b.
  • We could sort all of these operations by first their position, then their operator (addition preceding subtraction) we could see that we could always obtain the correct result.

时间复杂度O(q log q),其中q是查询量。

Time complexty O (q log q) with q is the amount of queries.

示例:

a b k
1 5 3
4 8 7
6 9 1

我们将其分解为

(1 3) (5 -3) (4 7) (8 -7) (6 1) (9 -1)

排序它们:

(1 3) (4 7) (5 -3) (6 1) (8 -7) (9 -1)

然后依次进行:

Start sum = 0
-> (1 3)  -> sum = 3
-> (4 7)  -> sum = 10
-> (5 -3) -> sum = 7
-> (6 1)  -> sum = 8
-> (8 -7) -> sum = 1
-> (9 -1) -> sum = 0

最大和为10->问题的答案。

The max sum is 10 -> answer for the problem.

通过所有测试的我的Java代码 https://ideone.com/jNbKHa

My Java code which passed all tests https://ideone.com/jNbKHa

这篇关于用于跟踪HackerRank问题的算法/代码的改进的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-05 16:57
查看更多