Codility挑战
我正在尝试完成一个编程挑战，目的是提高我的编程技能，或者说是弥补我在这方面的不足。挑战的具体内容在这里。
在一个房间里，有 N 根绳子和 N 个重物。每根绳子都连接着一个重物（只在一端），而且每根绳子都有一个特定的耐久度——也就是它能承受的最大重量。房间的天花板上有一个钩子，绳子的另一端可以绑在这个钩子上。绳子也可以连接到其他重物上；也就是说，绳子和重物可以相互连接，形成一个链条。如果一根绳子上直接或间接连接的重物总重量超过了它的耐久度，这根绳子就会断。
我们知道要连接 N 根绳子的顺序。更具体地说，我们知道每根绳子的参数（耐久度和重物）以及每根绳子的连接位置。耐久度、重物和位置分别在三个长度为 N 的数组 A、B、C 中给出。对于每个 I（0 ≤ I < N）：A[I] 是第 I 根绳子的耐久度，B[I] 是连接到第 I 根绳子的重物，C[I]（满足 C[I] < I）是我们连接第 I 根绳子的目标位置；如果 C[I] 等于 -1，我们就连接到钩子上，否则就连接到与 C[I] 相关的第 C[I] 根绳子的重物上。我们的目标是找出在指定顺序下，最多可以连接多少根绳子，而不让任何一根绳子断。请写一个函数：def solution(A, B, C)，这个函数接收三个长度为 N 的数组 A、B、C，返回可以按照给定顺序连接的最大绳子数量。例如，给定以下数组：
A= [4,3,1] B = [2,2,1] C = [-1,0,1]这个函数应该返回 2，因为如果我们再连接第三根绳子，就会有一根绳子断掉，因为重物的总重量超过了它的耐久度（2 + 2 + 1 = 5，而 5 > 4）。
下面是我尝试的解决方案。我有一个辅助函数叫做 add_weights，如果添加最新的绳子不会导致其他绳子断掉，它会返回 True，否则返回 False。
def add_weights(A, ancestors, weights, weight, rope):
#add weight(int) to rope and ancestors
if (rope == -1):
return (True)
else:
weights[rope] += weight
if (A[rope] < weights[rope]):
print "Rope that breaks", rope
return False
ancestor = ancestors[rope]
print ancestor
add_weights(A, ancestors, weights, weight, ancestor)
def solution(A, B, C):
# write your code in Python 2.7
weights = {}
ancestors = {}
for i in range(len(B)):
weights[i] = B[i]
for i in range(len(C)):
#attaching rope i to rope x
x = C[i]
ancestors[i] = x
broke = add_weights(A, ancestors, weights, B[i], x)
if (not broke):
return i
return len(C)
问题是，在函数 solution 的第二次循环中（当我尝试添加第一根绳子时），变量 break 不知怎么的变成了 None，而我明明看到 add_weights 返回了 True。我也用调试工具测试过，所以我不太确定发生了什么。欢迎任何帮助。
4 个回答
忘了提一下：这个算法的时间复杂度是O(n)，还有一些空间复杂度是针对数组B2的。
int Solution (int[]A, int[] B, int[] C)
{
if (A==null || B==null || C==null)
return -1;
if (A.Length==0 || B.Length==0 || C.Length==0)
return -1;
if (A.Length != B.Length && A.Length != C.Length)
return -1;
var bLen=B.Count();
var B2 = new int[bLen];
for (int i = 0; i < bLen; i++)
B2[i]=(i==0? 0 : B2[i-1]) + B[i]; //cumulative sum
var ret=-1;
var skip=0;
for (int i = 0; i < A.Length; i++)
{
skip=C[i]+1;
if (A[i] - (B2[bLen-1] - (skip>0 ? B2[skip-1] : 0)) < 0)
{
ret=bLen-skip-1;
break;
}
}
return ret;
}
我没时间把这个翻译成Python，不过你可以通过看看这段JS代码来了解大概意思：
function keysOrderedByValues(array) {
var result = [];
for (var i = 0; i < array.length; i++) {
result[array[i] + 1] = i;
}
return result;
}
function findFirstPositiveElem(array) {
for (var i = 0; i < array.length; i++) {
if (array[i]>0) {
return i;
}
}
return null;
}
function accumulativeArray(array) {
var result = [];
var sum = 0;
for (var i = 0; i < array.length; i++) {
sum = sum + array[i];
result.push(sum);
}
return result;
}
Array.prototype.indexedByArray = function(array) {
result = [];
for (var i = 0; i < array.length; i++) {
result.push(this[array[i]])
}
return result;
}
function test(ds, ws, ords) {
return findFirstPositiveElem(ws.indexedByArray(keysOrderedByValues(ords)), ds);
}
console.log(test([4,3,1], [2,2,1], [-1,0,1]))
这是我第一个解决方案，复杂度是O(N**2)，它的做法就是遍历所有的绳子，然后把每根绳子的重量减少到与它连接的绳子相同。
def solution(A, B, C):
num_ropes = len(C)
for i in range(num_ropes):
node = i
while(node != -1):
A[node] -= B[i]
if A[node] < 0:
return i
node = C[node]
return num_ropes
这是O(N*log(N))的解决方案，原理是它不是遍历所有的绳子，而是遍历那些有相同张力的绳子组。
def solution(A, B, C):
num_ropes = len(C)
for i in range(num_ropes):
A[i] -= B[i]
if A[i] < 0:
return i
pre_node = C[i]
while pre_node != -1:
A[pre_node] -= B[i]
if A[pre_node] < 0:
return i
if A[pre_node] <= A[i]:
C[i] = pre_node
A[i] = A[pre_node]
pre_node = C[pre_node]
return num_ropes
可以通过最后这部分进行测试，或者在这个链接上测试：https://app.codility.com/programmers/challenges/sulphur2014/
if __name__ == '__main__':
A = [5, 3, 6, 3, 3]
B = [2, 3, 1, 1, 2]
C = [-1, 0, -1, 0, 3]
assert solution(A, B, C) == 3
A = [4, 3, 1]
B = [2, 2, 1]
C = [-1, 0, 1]
assert solution(A, B, C) == 2
在编程中，有时候我们需要处理一些数据，比如从一个地方获取数据，然后在另一个地方使用这些数据。这个过程就像是把水从一个水桶倒到另一个水桶里。
有些时候，我们会遇到一些问题，比如数据的格式不对，或者我们想要的数据没有被正确地获取到。这就像是你想要的水桶里没有水，或者水的颜色和你想要的不一样。
为了避免这些问题，我们可以使用一些工具和方法来确保我们获取到的数据是正确的。这就像是使用一个过滤器来确保水是干净的，或者使用一个量杯来确保我们倒出的水量是准确的。
总之，处理数据就像是管理水的流动，我们需要确保每一步都是正确的，这样才能得到我们想要的结果。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Exercise5_DurablityofRopes
{
class Program
{
static int[] A_Durability = new int[] { 15, 6, 2,3,1 };
static int[] B_Weight = new int[] { 2, 1, 2,3,1 };
static int[] C_Position = new int[] { -1, 0, 1 ,2,3};
static int no_of_ropes_attached = 0;
static int maxropeattached = 0;
static void Main(string[] args)
{
// first position cannot necessarily be -1 hence Checking for each position How many maximum ropes can be attached
for (int i = 0; i <= C_Position.Length - 1; i++)
{
int[] Copy_Durability = new int[A_Durability.Length];
for (int l = 0; l <= C_Position.Length - 1; l++)
{
Copy_Durability[l] = A_Durability[l];
}
AddNextRope(i, B_Weight[i], Copy_Durability);
Console.WriteLine("Total Number of ropes can be attached to " + C_Position[i] + " ropes are" + no_of_ropes_attached);
if (no_of_ropes_attached>=maxropeattached)
{
maxropeattached = no_of_ropes_attached;
}
no_of_ropes_attached = 0;
}
Console.WriteLine("Total Number of ropes can be attached is " + maxropeattached);
Console.ReadKey();
}
private static void AddNextRope(int currentRopePosition,int newWeight,int[] Durability)
{
if (currentRopePosition == C_Position.Length - 1) return;
// decrease same amount of weight from all ansestors from their durability and check if any of them breaks (durability <0) with new weight added
for (int k = currentRopePosition; k != 0; k--)
{
Durability[k] = Durability[k] - newWeight;
if(Durability[k]<0)
{
return;
}
}
no_of_ropes_attached = no_of_ropes_attached + 1;
for (int i = 0; i <= C_Position.Length - 1; i++)
{
if (C_Position[i] == C_Position[currentRopePosition] + 1)
{
if (A_Durability[i] > B_Weight[i])
{
AddNextRope(i, B_Weight[i], Durability);
}
else
{
return;
}
}
}
}
}
}