这个问题是在Amazon.com面试的在线测试中提出的。确切的问题是:
给出一个测试结果列表(每个都有测试日期、学生ID和学生分数),返回每个学生的最终分数。学生的期末成绩是根据他/她5个最高考试分数的平均值计算出来的。你可以假设每个学生至少有5个考试成绩。
在解决方案中使用以下框架
class TestResult{
int studentId;
Date testDate;
int testScore;
}
public Map<Integer, Double> getFinalScores(List<TestResult> result
因此,当我在处理编程竞赛(ACM ICPC等)中的一些实践问题时,人们经常可以采用O(N^2)解决方案,甚至更糟,并使用堆(C++中的priority_queue)或use来降低复杂性。(作为某种优化,在注意到模式中的“某些东西”之后)
例如,在“滑动窗口最大值”问题中,这几乎是:
For each window of size K in an array of size N, compute the maximum.
这里有一个简单的O(NK)算法,一个相当简单的O(nlogn)解决方案(甚至我都可以看到,使用一个堆)和一个O(N)解决方案,使用一个双端队列。
这些原则似乎是基于“丢弃”无用
我最近想出了一个解决英国变化问题的朴素(+ +)解决方案(即有多少个硬币组合可以产生一个给定的总数)。我现在有了,但仍然对解决以下两种解决方案的时间和空间复杂性感兴趣。
最坏解
此解决方案递归地尝试将针对自身的每个数字和每个其他数字组合在一起,从而导致大量重复工作。我认为这是O(n^n)时间,并且不确定如何度量空间复杂性(但它很大,因为我们存储每个结果)。有什么想法?
var makeChange = function(total){ // in pence
var allSets = new Set();
var coins = [1,2,5,10,20,50,100,200];