面试测试-添加使用递归算法c#

本文关键字：递归算法 添加 测试 面试 | 更新日期: 2023-09-27 18:06:45

下面是一个关于使用递归进行两个数组相加的面试问题。

我不能弄清楚，虽然因为它似乎不允许任何类型的索引来跟踪你在哪里，我已经走了几条路-试图测试null/默认值在数组中，但因为它是一个字节[]类型没有工作。

任何帮助将是伟大的，谢谢-这不是一个家庭作业问题。

public AddResult UsingARecursiveAlgorithm_ValuesAreAdded(byte[] a, byte[] b)
{
    var result = AddRecursive(a, b);
    // Assert
    return new AddResult(a, b, result);
}

。

输入:{1,1,1}，{1,1,1}

结果:{2,2,2}

输入:{1,1,255}，{0,0,1}

结果:{1,2,0}

条件:

,B不为空，且长度相同。

该算法应对输入无破坏性。

编辑:第二个结果不正确。它应该是{1,1,0}——这就是它的呈现方式

面试测试-添加使用递归算法c#

private int carry = 0;        
public byte[] AddRecursive(byte[] a, byte[] b)
{
    //Start from bottom of the byte[] array
    a = a.Reverse().ToArray();
    b = b.Reverse().ToArray();
    if (a.Length == 0) return new byte[] { };            
    int tempresult = a[0] + b[0] + carry;
    byte[] z = new byte[]
    { (byte)(tempresult) };
    carry = tempresult / (byte.MaxValue + 1);
    return z.Concat(AddRecursive(a.Skip(1).ToArray(), b.Skip(1).ToArray())).ToArray();
}
//Test//
[Test]
public void Add_UsingARecursiveAlgorithm_ValuesAreAdded()
{
    //First Test
    byte[] expectedResult = addthisaddthat.AddRecursive(new byte[] { 1, 1, 1 }, new byte[] { 1, 1, 1 }).Reverse().ToArray();
    Assert.That(expectedResult, Is.EqualTo(new byte[] { 2, 2, 2 }));
    //Sec Test
    expectedResult = addthisaddthat.AddRecursive(new byte[] { 1, 1, 255 }, new byte[] { 0, 0, 1 }).Reverse().ToArray();
    Assert.That(expectedResult, Is.EqualTo(new byte[] { 1, 2, 0 }));
    //Third Test
    expectedResult = addthisaddthat.AddRecursive(new byte[] { 255, 255, 255 }, new byte[] { 255, 255, 255 }).Reverse().ToArray();
    Assert.That(expectedResult, Is.EqualTo(new byte[] { 255, 255, 254 }));
}

好了，这里有一些相当"丑陋"的代码，可以满足您的要求。我试着把它写得清晰而不是简洁:

static byte[] AddArray(byte[] ary1, byte[] ary2) {
    System.Diagnostics.Debug.Assert(ary1.Length == ary2.Length);
    if ((ary1 == null) || (ary2 == null)) {
        throw new ArgumentException("Empty or null array");
    }
    // sum the last element
    var ix = ary1.Length - 1;
    var sum = (ary1[ix] + ary2[ix]);
    if (sum > byte.MaxValue) {
        if (ix == 0) {
            throw new ArgumentException("Overflow");
        }
        // Add carry by recursing on ary1
        var carry = (byte) (sum - byte.MaxValue);
        var carryAry = new byte[ary1.Length];
        carryAry[ix - 1] = carry;
        ary1 = AddArray(ary1, carryAry);
    }
    if ((ary1.Length == 1) || (ary2.Length == 1)) {
        return new byte[] { (byte) sum }; // end recursion
    }
    // create the remainder, elements from 0 it (len-1)
    var ary1Remainder = new byte[ary1.Length - 1];
    var ary2Remainder = new byte[ary2.Length - 1];
    Array.Copy(ary1, 0, ary1Remainder, 0, ary1.Length - 1);
    Array.Copy(ary2, 0, ary2Remainder, 0, ary2.Length - 1);
    // recurse
    var remainder = AddArray(ary1Remainder, ary2Remainder);
    // build return array (using linq Concat)
    var rv = (remainder.Concat(new byte[] { (byte) sum }));
    return rv.ToArray(); // return as an array 
}

不需要所有的强制转换和ToArray，因为值是byte[]而不是IEnumerable<int>，但是:

private byte[] AddRecursive(byte[] a, byte[] b) {
    if (a.Length == 0) return new byte[]{};
    return 
        new byte[] { (byte)(a[0] + b[0]) }.Concat(
        AddRecursive(a.Skip(1).ToArray(), b.Skip(1).ToArray())
        ).ToArray();
}

也许你的面试官有这样的想法:

using System;
using System.Linq;
public class Program
{
    public static byte[] Add(byte[] a, byte[] b, int index = -1)
    {
        if (index < 0)
        {
            return Add((byte[])a.Clone(), b, 0);
        }
        if (index < a.Length)
        {
            Add(a, b, index + 1);
            a[index] += b[index];
        }
        return a;
    }
    public static void Main(string[] args)
    {
        var r1 = Add(new byte[] { 1, 1, 1 }, new byte[] { 1, 1, 1 });
        var r2 = Add(new byte[] { 1, 1, 255 }, new byte[] { 0, 0, 1 });
        var r3 = Add(new byte[] { 0, 100, 200 }, new byte[] { 3, 2, 1 });
        // Outputs: 2, 2, 2
        Console.WriteLine(string.Join(", ", r1.Select(n => "" + n).ToArray()));
        // Outputs: 1, 1, 0
        Console.WriteLine(string.Join(", ", r2.Select(n => "" + n).ToArray()));
        // Outputs: 3, 102, 201
        Console.WriteLine(string.Join(", ", r3.Select(n => "" + n).ToArray()));
    }
}
https://dotnetfiddle.net/UqSQb3

请注意，这个(只是部分)解决方案不处理进位字节溢出。

相关文章：