gpt4 book ai didi

algorithm - 按字符的一半重新排序字符串

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:35:54 27 4
gpt4 key购买 nike

这是一道面试题。

Given a string such as: 123456abcdef consisting of n/2 integers followed by n/2 characters. Reorder the string to contain as 1a2b3c4d5e6f . The algortithm should be in-place.

我给出的解决方案很简单 - O(n^2)。只需将字符向左移动 n/2 个位置。

我尝试使用递归作为 -
A。将第一部分的后半部分与第二部分的前半部分交换 - 例如
123 456 abc def
123 abc 456 def
b.递归两半。

我卡住的 pbm 是交换随着元素的数量而变化 - 例如。

接下来要做什么? 第123章 12ab 3c

要做什么:12345 abcde 123abc 45ab

这是一个很老的问题,可能是重复的。请让我知道.. :)

另一个例子:输入:38726zfgsa输出:3z8f7g2s6a

最佳答案

以下是我解决问题的方法:

1) Divide the string into two partitions, number part and letter part
2) Divide each of those partitions into two more (equal sized)
3) Swap the second the third partition (inner number and inner letter)
4) Recurse on the original two partitions (with their newly swapped bits)
5) Stop when the partition has a size of 2

例如:

123456abcdef -> 123456 abcdef -> 123 456 abc def -> 123 abc 456 def

123abc -> 123 abc -> 12 3 ab c -> 12 ab 3 c

12 ab -> 1 2 a b -> 1 a 2 b

...等等

对于递归的另一半也是如此..

所有这些都可以就地完成,唯一的问题是交换大小不同的分区(但它会相差一个,所以不难处理)。

关于algorithm - 按字符的一半重新排序字符串,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7222102/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com