如何将字符串反转到堆的2/3位置？

Question

最近我参加了一次面试，被问到一个奇怪的问题(至少对我来说是这样)：

我应该写一个方法来反转一个字符串。

public static String myReverse(String str){
    ...
}

问题是str是一个非常非常大的对象(内存的2/3)。

我想只有一个解决方案：

创建一个新的字符串，我将在其中存储结果，然后反转1/2的源字符串。使用反射后，清除源字符串底层数组的后半部分(已经反转)，然后继续反转。

我说的对吗？

还有其他的解决方案吗？

Answer 1

如果您正在使用反射，您可以访问字符串的底层字符数组，并通过从两端遍历并交换两端的字符来在适当的位置反转它。

public static String myReverse(String str){
    char[] content;
    //Fill content with reflection

    for (int a = 0, b = content.length - 1; a < b; a++, b--) {
        char temp = content[b];
        content[b] = content[a];
        content[a] = temp;
    }

    return str;
}

不幸的是，我想不出一种不使用反射的方法。

Answer 2

String在内部是一个16位char数组。如果我们知道字符集是ASCII码，这意味着每个char映射到一个byte，我们可以将字符串编码到一个8位的byte数组中，而只需要50%的内存开销。这将在转换期间充分利用可用内存。然后，我们释放输入字符串以回收2/3的内存，反转字节数组并重新构造字符串。

public static String myReverse(String str) {
    byte[] bytes = str.getBytes("ASCII");
    // memory at full capacity
    str = null;
    // memory at 1/3 capacity
    for (int i = 0; i < bytes.length / 2; i++) {
        byte tmp = bytes[i];
        bytes[i] = bytes[bytes.length - i - 1];
        bytes[bytes.length - i - 1] = tmp;
    }
    return new String(bytes, "ASCII");
}

当然，这假设您有一些额外的内存可用于编码过程创建的临时对象、数组标头等。

Answer 3

如果不使用反射之类的技巧，或者假设String是以一种有效的方式存储的(例如，知道它只是ASCII字符)，就不太可能做到这一点。您遇到的问题是，在java String中，s是不可变的。另一种可能是垃圾收集的实现。

垃圾收集的可能实现的问题是，在对象之后，内存被回收，不能再被访问。这意味着有一段时间，转换的输入和输出都需要占用内存。

例如，可以尝试通过连续构建结果并剪切原始字符串来反转字符串：

rev = rev + orig.substring(0,1);
orig = orig.substring(1);

但这依赖于分别在创建rev或orig的新化身时收集以前的rev或orig化身，以便它们不会同时占用多达2/3的内存。

更一般地说，人们应该研究这样的过程。在这个过程中，会有一组在整个过程中演变的对象，既有set本身，也有(一些)对象。在开始时，原始字符串将在集合中，而在结束时，反转的字符串将在那里。显然，由于信息内容的原因，集合中对象的总大小永远不会低于原始大小。这里的关键点是，必须在某个时刻删除原始字符串。在此之前，至多50%的信息可能存在于其他对象中。因此，我们需要一个同时删除String对象的构造，因为它保留了其中一半以上的信息。

这样的构造基本上需要你调用一个对象的方法，返回另一个对象，在这个过程中，在构造结果时删除该对象。实现不太可能以这种方式工作。

您的方法似乎依赖于String确实在某种程度上是可变的，然后在不使用大量内存的情况下在适当的位置反转字符串将不会有任何问题。你不需要复制任何东西，你可以在适当的地方做整个事情:交换[j]，然后[len-1-j] (对于所有的j<(len-1)/2)