"就地"是什么意思？

Question

字符串中的反转单词(单词由一个或多个空格分隔).现在就地进行.

就地是什么意思？

Answer 1

就地意味着您应该更新原始字符串而不是创建新字符串.

根据您使用的语言/框架,这可能是不可能的.(例如,字符串在.NET和Java中是不可变的,因此如果不诉诸某些邪恶的黑客,就不可能执行字符串的就地更新.)

Answer 2

就地算法O(1)本质上只能使用额外的空间.数组逆转(基本上是面试问题归结为)是一个典型的例子.以下内容摘自维基百科:

假设我们想要反转n个项目的数组.一种简单的方法是:

function reverse(a[0..n])
    allocate b[0..n]
    for i from 0 to n
       b[n - i] = a[i]
    return b

不幸的是,这需要O(n)额外的空间来创建阵列b,并且分配通常是一个缓慢的操作.如果我们不再需要a,我们可以使用这种就地算法用它自己的反转来覆盖它:

function reverse-in-place(a[0..n])
    for i from 0 to floor(n/2)
       swap(a[i], a[n-i])

有时候就地做某事很难.一个典型的例子是一般的非方阵矩阵换位.

也可以看看

• 就地算法
• 就地矩阵转置

Answer 3

您应该将原始字符串的内容更改为反向,而不使用临时存储变量来保存字符串.