<p>我猜这个问题是典型的二进制搜索。我不认为你的解决方案会通过“在线评判”,因为时间复杂度很高(你的分析可能是正确的)。但是,您可以测试您的解决方案</p>
<p>在面试环境中,他们所寻找的是最有效的算法,你通常可以在讨论小组中找到。他们甚至不想知道任何关于暴力算法的事情,除非这个问题可能太难了</p>
<p>这可能是O(N logn)时间和恒定内存:</p>
<h3>Python</h3>
<pre><code>from typing import List
class Solution:
def shipWithinDays(self, weights: List[int], d: int) -> int:
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = lo + ((hi - lo) >> 1) # or mid = (lo + hi) // 2 || mid = lo + (hi - lo) // 2
cur, required = 0, 1
for weight in weights:
if cur + weight > mid:
required += 1
cur = 0
cur += weight
if required > d:
lo = -~mid # simply lo = mid + 1
else:
hi = mid
return lo
</code></pre>
<h3>Java</h3>
<pre><code>class Solution {
public int shipWithinDays(int[] weights, int d) {
int lo = 0;
int hi = 0;
for (int weight : weights) {
lo = Math.max(lo, weight);
hi += weight;
}
while (lo < hi) {
int mid = lo + ((hi - lo) >> 1);
int required = 1;
int cur = 0;
for (int weight : weights) {
if (cur + weight > mid) {
required += 1;
cur = 0;
}
cur += weight;
}
if (required > d)
lo = -~mid;
else
hi = mid;
}
return lo;
}
}
</code></pre>
<h3>C++</h3>
<pre><code>class Solution {
public:
int shipWithinDays(vector<int> &weights, int d) {
int lo = 0;
int hi = INT_MAX;
for (int weight : weights)
lo = max(lo, weight);
while (lo < hi) {
int mid = lo + ((hi - lo) >> 1);
int required = 1;
int cur = 0;
for (int index = 0; index < weights.size() && required <= d; cur += weights[index++])
if (cur + weights[index] > mid)
cur = 0, required++;
if (required > d)
lo = -~mid;
else
hi = mid;
}
return lo;
}
};
</code></pre>
<hr/>
<p>我建议在面试时把注意力集中在干净的代码上。您很可能不需要编写t(N)。你可以告诉面试官你的时间/空间复杂性是什么。在采访中,强调“大o”通常不是一个好主意,因为他们可能有不同的观点,更不用说他们寻求实际的大o分析</p>
<p>我建议快速通过bio-o部分。如果面试官会有后续问题,你可以进一步展开</p>
<p>如果你的强项是bio-o,也许你可以花点时间在上面。通常最重要的是算法、数据结构和系统设计/架构</p>
<h3>参考</h3>
<p>这些是<a href="https://leetcode.com/lee215/" rel="nofollow noreferrer">lee215</a>的解决方案,顺便说一句,他们设计了一些LeetCode的问题,并且通常在LeetCode的讨论面板上发布最有效的解决方案</p>
<p><a href="https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/" rel="nofollow noreferrer">LeetCode 1011</a></p>