a******h
发帖数: 19 | 1 given a string, how to do a string rotation without using extra memory? |
m*****f
发帖数: 1243 | |
a****n
发帖数: 1887 | 3 reverse whole string
reverse first part
reverse second part |
r****o
发帖数: 1950 | 4 问问，没有额外存储空间怎么reverse string?
【在 a****n 的大作中提到】
: reverse whole string
: reverse first part
: reverse second part
|
m*****f
发帖数: 1243 | 5 swap就可以拉
【在 r****o 的大作中提到】
: 问问，没有额外存储空间怎么reverse string?
|
g*******y
发帖数: 1930 | 6 两种方法
一种是swap(circularly)，利用到最小公约数
一种是flip 3次
【在 a******h 的大作中提到】
: given a string, how to do a string rotation without using extra memory?
|
a******h
发帖数: 19 | 7 Could you explain swap circularly?
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
|
n******r
发帖数: 1247 | 8 swap不需要额外空间？
【在 m*****f 的大作中提到】
: swap就可以拉
|
g*******y
发帖数: 1930 | 9 这个是无比经典的问题了。。。
假设前4个数和后6个数rotate，
最小公约数2
4/2=2
6/2=3
得到的2，3必然互质
再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
集合｛0...p+q-1}的一个循环遍历
【在 a******h 的大作中提到】
: Could you explain swap circularly?
|
r****o
发帖数: 1950 | 10 还是不明白，swap不用临时变量吗?
【在 m*****f 的大作中提到】
: swap就可以拉
|
|
|
g*******y
发帖数: 1930 | 11 两种方法空间差不多，都只要2，3个指针，后者最多再多用一个char temp。flip时间
慢个常数因子。
【在 n******r 的大作中提到】
: swap不需要额外空间？
|
a******h
发帖数: 19 | 12 What is 前4个数和后6个数rotate ?
Suppose you have a string "abcdef" and right rotate 4.
How to apply your GCD in this case?
【在 g*******y 的大作中提到】
: 这个是无比经典的问题了。。。
: 假设前4个数和后6个数rotate，
: 最小公约数2
: 4/2=2
: 6/2=3
: 得到的2，3必然互质
: 再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
: 集合｛0...p+q-1}的一个循环遍历
|
a****n
发帖数: 1887 | 13 不要临时变量的
swap(T& a, T& b)
{
a = a^b
b = a^b
a = a^b
}
【在 r****o 的大作中提到】
: 还是不明白，swap不用临时变量吗?
|
g*******y
发帖数: 1930 | 14 012345678 -> 4567890123
【在 a******h 的大作中提到】
: What is 前4个数和后6个数rotate ?
: Suppose you have a string "abcdef" and right rotate 4.
: How to apply your GCD in this case?
|
a******h
发帖数: 19 | 15 This is string length of 9. So could you explain your gcd in this case?
【在 g*******y 的大作中提到】
: 012345678 -> 4567890123
|
r****o
发帖数: 1950 | 16 flip是什么意思？bit operation吗？
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
|
H*M
发帖数: 1268 | 17 we need AB ->BA
can use:
(A'B')' = BA
【在 r****o 的大作中提到】
: flip是什么意思？bit operation吗？
|
r****o
发帖数: 1950 | 18 能不能再详细说说阿，
遍历集合{0...p+q-1}之后再咋弄呢？
【在 g*******y 的大作中提到】
: 这个是无比经典的问题了。。。
: 假设前4个数和后6个数rotate，
: 最小公约数2
: 4/2=2
: 6/2=3
: 得到的2，3必然互质
: 再用一点点基本的数论，两个数p,q互质的话，{i*p%(p+q) | i=0...(p+q)-1} 刚好是
: 集合｛0...p+q-1}的一个循环遍历
|
g*******y
发帖数: 1930 | 19 按这个次序挨个挪动数
比如 12345 -> 34512
1开始，
1挪到4的位置
4挪到2的位置
2挪到5的位置
5挪到3的位置
3挪到1的位置
然后你发现走了一圈走回1了，就结束了。
【在 r****o 的大作中提到】
: 能不能再详细说说阿，
: 遍历集合{0...p+q-1}之后再咋弄呢？
|
a******h
发帖数: 19 | 20 // only needs gcd(strLen, k) times circular swap
// this function supports right rotation only
public static String rotateStr(String str, int k) {
if (str == null)
return null;
if (k == 0 || str.length() == k)
return str;
if (k < 0)
throw new InvalidParameterException();
char [] arr = str.toCharArray();
int gcd = findGCD(str.length(), k);
for (int i = 0; i < gcd; i++) {
|
k***e
发帖数: 556 | 21 唉 你怎么老是有保留呢
有三种方法
programming pearl chap 2 （如果没记错的话）
【在 g*******y 的大作中提到】
: 两种方法
: 一种是swap(circularly)，利用到最小公约数
: 一种是flip 3次
|
g*******y
发帖数: 1930 | 22 我真的只知道有两种。。。你说说第三种是什么？pearl我看得很水。。。
【在 k***e 的大作中提到】
: 唉 你怎么老是有保留呢
: 有三种方法
: programming pearl chap 2 （如果没记错的话）
|
