l****f
发帖数: 88 | 1 写了几次都没写出来, 太笨了。有没有大牛贴个简单明了的版本
150上的算法感觉也不对 |
A*****i
发帖数: 3587 | |
t*******i
发帖数: 4960 | 3 Re
【在 A*****i 的大作中提到】
: 分割开两部分一个一个拼不就完了？
|
h*****a
发帖数: 1718 | 4 No additional space other than a few variables.
【在 A*****i 的大作中提到】
: 分割开两部分一个一个拼不就完了？
|
h*******e
发帖数: 1377 | |
l****f
发帖数: 88 | 6 这个不用extra space吗？
【在 A*****i 的大作中提到】
: 分割开两部分一个一个拼不就完了？
|
A*****i
发帖数: 3587 | 7 不用啊，如果是数组的话，用A[i+1] = A[i]一步一步把前面的往后挪就完了啊
就是复杂度有些高不能线性了。
如果一个字符一个node放在连表里就可以线性了。
【在 l****f 的大作中提到】
: 这个不用extra space吗？
|
h*******t
发帖数: 2679 | 8 原题是什么？
是不是这个思路：
char x='b';
char y='1';
x=x^y;
y=x^y;
x=x^y;
result ==> x = '1'; y='b';
这样可以不用extra space实现字符对调。
【在 l****f 的大作中提到】
: 写了几次都没写出来, 太笨了。有没有大牛贴个简单明了的版本
: 150上的算法感觉也不对
|
d*k
发帖数: 207 | 9 好久没来贡献了，刚好有时间来，和大家交流一下。
这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
，不可能想出来。
设原来的结构为
a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
T(n) = O(n/2) + 2 * T(n / 2)
因此T(n) = O(nlogn)。
关于inplace地交换A2和B1的算法，相信大家都知道了。首先将A2B1这部分反序，设A2
长度为p，B1长度为q。反序后的部分，先将前q个元素反序，再将后面的p个元素反序。
这时原序列已经变成B1A2了。
试一下online coding。
# inplace swap A2B1 to B1A2
def rev(seq, begin, p, q):
i = begin
j = begin + p + q - 1
while i < j:
seq[i], seq[j] = seq[j], seq[i]
i += 1
j -= 1
# recursive routine to solve the main problem
# idx is the first index of the sequence
# calling solve(seq, 0, len(seq)) will solve the original problem
def solve(seq, idx, size):
n = (size - idx) / 2
if n <= 1:
return
p = int(math.floor(n / 2))
q = int(math.ceil(n / 2))
begin = idx + q
rev(seq, begin, p, q)
solve(seq, idx, q * 2)
solve(seq, idx + q * 2, p * 2) |
w*****5
发帖数: 75 | |
|
|
y**********a
发帖数: 824 | |
y**********a
发帖数: 824 | 12 void swap(char[]A, int i, int j) {char c=A[i];A[i]=A[j];A[j]=c;}
void shuffleString(char[]A) {
for (int n=A.length,l=1,r=n/2;l
for (int l=2,n=A.length;l
while (A[l]!='A'+l/2)swap(A, l, (A[l]-'A')*2);
} |
j********g
发帖数: 427 | 13 这种题，当你想据掉candidate的时候还是挺合适的
solely
A2
【在 d*k 的大作中提到】
: 好久没来贡献了，刚好有时间来，和大家交流一下。
: 这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
: on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
: ，不可能想出来。
: 设原来的结构为
: a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
: 做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
: A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
: 1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
: A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
|
l****f
发帖数: 88 | 14 写了几次都没写出来, 太笨了。有没有大牛贴个简单明了的版本
150上的算法感觉也不对 |
A*****i
发帖数: 3587 | |
t*******i
发帖数: 4960 | 16 Re
【在 A*****i 的大作中提到】
: 分割开两部分一个一个拼不就完了？
|
h*****a
发帖数: 1718 | 17 No additional space other than a few variables.
【在 A*****i 的大作中提到】
: 分割开两部分一个一个拼不就完了？
|
h*******e
发帖数: 1377 | |
l****f
发帖数: 88 | 19 这个不用extra space吗？
【在 A*****i 的大作中提到】
: 分割开两部分一个一个拼不就完了？
|
A*****i
发帖数: 3587 | 20 不用啊，如果是数组的话，用A[i+1] = A[i]一步一步把前面的往后挪就完了啊
就是复杂度有些高不能线性了。
如果一个字符一个node放在连表里就可以线性了。
【在 l****f 的大作中提到】
: 这个不用extra space吗？
|
|
|
h*******t
发帖数: 2679 | 21 原题是什么？
是不是这个思路：
char x='b';
char y='1';
x=x^y;
y=x^y;
x=x^y;
result ==> x = '1'; y='b';
这样可以不用extra space实现字符对调。
【在 l****f 的大作中提到】
: 写了几次都没写出来, 太笨了。有没有大牛贴个简单明了的版本
: 150上的算法感觉也不对
|
d*k
发帖数: 207 | 22 好久没来贡献了，刚好有时间来，和大家交流一下。
这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
，不可能想出来。
设原来的结构为
a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
T(n) = O(n/2) + 2 * T(n / 2)
因此T(n) = O(nlogn)。
关于inplace地交换A2和B1的算法，相信大家都知道了。首先将A2B1这部分反序，设A2
长度为p，B1长度为q。反序后的部分，先将前q个元素反序，再将后面的p个元素反序。
这时原序列已经变成B1A2了。
试一下online coding。
# inplace swap A2B1 to B1A2
def rev(seq, begin, p, q):
i = begin
j = begin + p + q - 1
while i < j:
seq[i], seq[j] = seq[j], seq[i]
i += 1
j -= 1
# recursive routine to solve the main problem
# idx is the first index of the sequence
# calling solve(seq, 0, len(seq)) will solve the original problem
def solve(seq, idx, size):
n = (size - idx) / 2
if n <= 1:
return
p = int(math.floor(n / 2))
q = int(math.ceil(n / 2))
begin = idx + q
rev(seq, begin, p, q)
solve(seq, idx, q * 2)
solve(seq, idx + q * 2, p * 2) |
w*****5
发帖数: 75 | |
y**********a
发帖数: 824 | |
y**********a
发帖数: 824 | 25 void swap(char[]A, int i, int j) {char c=A[i];A[i]=A[j];A[j]=c;}
void shuffleString(char[]A) {
for (int n=A.length,l=1,r=n/2;l
for (int l=2,n=A.length;l
while (A[l]!='A'+l/2)swap(A, l, (A[l]-'A')*2);
} |
j********g
发帖数: 427 | 26 这种题，当你想据掉candidate的时候还是挺合适的
solely
A2
【在 d*k 的大作中提到】
: 好久没来贡献了，刚好有时间来，和大家交流一下。
: 这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
: on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
: ，不可能想出来。
: 设原来的结构为
: a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
: 做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
: A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
: 1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
: A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
|
f**********t
发帖数: 1001 | 27 void abc123_(string &s, unsigned left, unsigned right) {
int num = right - left;
if (num < 3) {
return;
}
int mid = (left + right + 1) / 2;
int ll = left + (mid - left) / 2;
int rr = mid + (ll - left);
int i = ll;
for (int k = mid; k < rr; ++i, ++k) {
swap(s[i], s[k]);
}
if (i < mid) {
char temp = s[i];
for (int z = mid; z < rr; ++z) {
s[z - 1] = s[z];
}
s[rr - 1] = temp;
--mid;
}
abc123_(s, left, mid);
abc123_(s, mid, right);
}
void abc123(string &s) {
abc123_(s, 0, s.size());
} |
s*********3
发帖数: 25 | 28 这个题就是一个2* 3 的矩阵转置成一个3*2的矩阵。
a b c
1 2 3
===>
a 1
b 2
c 3
如何实现矩阵的就地转置，网上搜一下就有了。 |
l*******a
发帖数: 36 | |
r****7
发帖数: 2282 | 30 你都recursive了还谈啥constant space。。。
这个就是操作index，可以算出来的，和矩阵转置差不多。
solely
【在 d*k 的大作中提到】
: 好久没来贡献了，刚好有时间来，和大家交流一下。
: 这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
: on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
: ，不可能想出来。
: 设原来的结构为
: a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
: 做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
: A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
: 1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
: A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
|
|
|
w****k
发帖数: 755 | 31 You cannot recurse because space should be O(1). It has to be iterative.
Also, you can only solve a1b1a2b2.. . You cannot solve a1b1c1..
Here is my iterative solution:
Say original array is M. Then ai appears in M[i] and it should finally
appear in M[3i]; also bi from M[n+i] to M[3i+1], and ci from M[2n+i] to M[3i
+2].
With these in mind, we can start from a1, find its final position and put it
there after saving the value there. Then we can figure out for that value
where its final position, and put it there after saving ..repeat these steps
until you go back to your start point.
Then you should repeat the above steps starting from a2, and then you are
done.
Note, if the question has a,b,c then you need to work on first 3 elements.
If it's a,b,c,d, then work on first 4 elements, etc.
solely
【在 d*k 的大作中提到】
: 好久没来贡献了，刚好有时间来，和大家交流一下。
: 这个题需要一个巧妙的思路，如果想不到是无法解答的。个人认为这种depend solely
: on one key observation的题目不适合当面试题，而且以我的能力，除非有很好的提示
: ，不可能想出来。
: 设原来的结构为
: a1a2a3...anb1b2b3...bn，需要变换为a1b1a2b2a3b3...anbn。可以把左右两个数组看
: 做A和B，长度分别为n。现在把A和B都划分成两个长度为n/2的数组，则输入可表示为
: A1A2B1B2。这里的四个数组长度都是n/2（n是奇数也则A2和B2的长度比A1和B1的长度少
: 1）。有算法可以在O(n)时间内inplace地交换A2和B1得到A1B1A2B2。之后递归地处理
: A1B1和A2B2。时间复杂度分析，上面的递归时间代价可以表示为
|
p****a
发帖数: 447 | |
k******e
发帖数: 145 | 33 Very good comment
Thanks
3i
it
steps
【在 w****k 的大作中提到】
: You cannot recurse because space should be O(1). It has to be iterative.
: Also, you can only solve a1b1a2b2.. . You cannot solve a1b1c1..
: Here is my iterative solution:
: Say original array is M. Then ai appears in M[i] and it should finally
: appear in M[3i]; also bi from M[n+i] to M[3i+1], and ci from M[2n+i] to M[3i
: +2].
: With these in mind, we can start from a1, find its final position and put it
: there after saving the value there. Then we can figure out for that value
: where its final position, and put it there after saving ..repeat these steps
: until you go back to your start point.
|
w**a
发帖数: 487 | 34 用StringBuilder算extra space么？
public static String googleABC(String test){
int len = test.length()/2;
StringBuilder res = new StringBuilder();
for(int i=0;i
res.append(test.charAt(i)).append(test.charAt(i+len));
}
return res.toString();
}
【在 h*****a 的大作中提到】
: No additional space other than a few variables.
|
S*******C
发帖数: 822 | 35 StringBuilder肯定不能算extra space，不然这道题用JAVA无解，因为答案的长度就是
O(N)
【在 w**a 的大作中提到】
: 用StringBuilder算extra space么？
: public static String googleABC(String test){
: int len = test.length()/2;
: StringBuilder res = new StringBuilder();
: for(int i=0;i: res.append(test.charAt(i)).append(test.charAt(i+len));
: }
:
: return res.toString();
: }
|
h******o
发帖数: 30 | 36 这个方法很好。可以按照新的坐标来逐次更换原来数组中的每个元素。当然不用新数组
储存坐标，可以计算出来。
【在 s*********3 的大作中提到】
: 这个题就是一个2* 3 的矩阵转置成一个3*2的矩阵。
: a b c
: 1 2 3
: ===>
: a 1
: b 2
: c 3
: 如何实现矩阵的就地转置，网上搜一下就有了。
|
