A家onsite, 求bless - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

A家onsite, 求bless

A家onsite, 求bless# JobHunting - 待字闺中

s*d2014-02-26 08:02

1 楼

题目很简单，脑子发蒙。郁闷啊
http://www.geeksforgeeks.org/array-rotation/

h*22014-02-26 08:02

2 楼

上周末做的oniline test。同 bless！
话说大概多久给答复啊。

l*52014-02-26 08:02

3 楼

上周去的onsite，至今无音讯。。。求 bless吧。。。

h*22014-02-26 08:02

4 楼

Online test 之后多就给的回复呢？
谢谢啊，bless all！

【在 l********5 的大作中提到】

: 上周去的onsite，至今无音讯。。。求 bless吧。。。

R*d2014-02-26 08:02

5 楼

bless

【在 s******d 的大作中提到】

: 题目很简单，脑子发蒙。郁闷啊
: http://www.geeksforgeeks.org/array-rotation/

R*d2014-02-26 08:02

6 楼

【在 s******d 的大作中提到】

: 题目很简单，脑子发蒙。郁闷啊
: http://www.geeksforgeeks.org/array-rotation/

c*02014-02-26 08:02

7 楼

bless~~

s*x2014-02-26 08:02

8 楼

我觉得geekforgeeks 给的答案并不好，太复杂了，应该用reverse words in a string
的解法。
1234567
7654321
3456712
You can write code easily.

m*l2014-02-26 08:02

9 楼

赞

string

【在 s**x 的大作中提到】

: 我觉得geekforgeeks 给的答案并不好，太复杂了，应该用reverse words in a string
: 的解法。
: 1234567
: 7654321
: 3456712
: You can write code easily.

s*d2014-02-26 08:02

10 楼

题目很简单，脑子发蒙。郁闷啊
http://www.geeksforgeeks.org/array-rotation/

h*22014-02-26 08:02

11 楼

上周末做的oniline test。同 bless！
话说大概多久给答复啊。

l*52014-02-26 08:02

12 楼

上周去的onsite，至今无音讯。。。求 bless吧。。。

h*22014-02-26 08:02

13 楼

Online test 之后多就给的回复呢？
谢谢啊，bless all！

【在 l********5 的大作中提到】

: 上周去的onsite，至今无音讯。。。求 bless吧。。。

R*d2014-02-26 08:02

14 楼

bless

【在 s******d 的大作中提到】

: 题目很简单，脑子发蒙。郁闷啊
: http://www.geeksforgeeks.org/array-rotation/

R*d2014-02-26 08:02

15 楼

【在 s******d 的大作中提到】

: 题目很简单，脑子发蒙。郁闷啊
: http://www.geeksforgeeks.org/array-rotation/

c*02014-02-26 08:02

16 楼

bless~~

s*x2014-02-26 08:02

17 楼

我觉得geekforgeeks 给的答案并不好，太复杂了，应该用reverse words in a string
的解法。
1234567
7654321
3456712
You can write code easily.

m*l2014-02-26 08:02

18 楼

赞

string

【在 s**x 的大作中提到】

: 我觉得geekforgeeks 给的答案并不好，太复杂了，应该用reverse words in a string
: 的解法。
: 1234567
: 7654321
: 3456712
: You can write code easily.

k*g2014-02-26 08:02

19 楼

在网上找到个更快的：
void rotate(int a[], int k, int n) {
int i=0;
for (; i+kif (n%k == 0) return;
k--;
for (; i}
谁能解释下思路？

m*s2014-02-26 08:02

20 楼

Bless

【在 s******d 的大作中提到】

: 题目很简单，脑子发蒙。郁闷啊
: http://www.geeksforgeeks.org/array-rotation/

c*h2014-02-26 08:02

21 楼

如果n是k整倍数，一个for就是把第一组k个元素逐个平移到最后的过程。done！
如果n是k整数倍＋零头，先昨晚这个过程，必然有k－零头个数stuck在最后一个k的整
数倍区间，对他们再平移一次。

【在 k***g 的大作中提到】

: 在网上找到个更快的：
: void rotate(int a[], int k, int n) {
: int i=0;
: for (; i+k: if (n%k == 0) return;
: k--;
: for (; i: }
: 谁能解释下思路？

c*c2014-02-26 08:02

22 楼

bless

b*k2014-02-26 08:02

23 楼

thanks for sharing， bless！

p*r2014-02-26 08:02

24 楼

上面的回复中已经有好的方法了
没必要用额外空间，
1 2 3 4 5 6 7
翻转左半部分变成 2 1 3 4 5 6 7
翻转右半部分变成 2 1 7 6 5 4 3
翻转整个数组 3 4 5 6 7 1 2
Bingo

【在 s******d 的大作中提到】

: 题目很简单，脑子发蒙。郁闷啊
: http://www.geeksforgeeks.org/array-rotation/

w*p2014-02-26 08:02

25 楼

bless

m*t2014-02-26 08:02

26 楼

programming pearl 上的例题啊。前几年国内研究生计算机统考也考了这道题。
这是经典题目啊，做不出来只能说明准备不充分

y*a2014-02-26 08:02

27 楼

w*12014-02-26 08:02

28 楼

for (int i=0; iif(i-d<0)
swap(arr, i-d+n, i);
else if(i-d>=0)
swap(arr, i-d, i);
}

M*i2014-02-26 08:02

29 楼

这个解好像有问题。
for example, array {1,2,3,4,5}, k = 3, n = 5
I = 0 swap(a[0],a[3]) ==> 4,2,3,1,5
I = 1 swap(a[1],a[4]) ==> 4,5,3,1,2
then second loop
I == 2, k -- ==> k = 2
swap(a[2], a[4]) ==> 4, 5, 2, 1, 3
I == 3, k = 1
swap(a[3], a[4]) ==> 4, 5, 2, 3, 1
I == 4, k == 0 stop.
final arr 4, 5, 2, 3, 1
expected arr 4, 5, 1, 2, 3

【在 k***g 的大作中提到】

: 在网上找到个更快的：
: void rotate(int a[], int k, int n) {
: int i=0;
: for (; i+k: if (n%k == 0) return;
: k--;
: for (; i: }
: 谁能解释下思路？

t*l2014-02-26 08:02

30 楼

use pointer jumping, the number of iteration is GCD(n, k), O(1) space.

【在 s******d 的大作中提到】

: 题目很简单，脑子发蒙。郁闷啊
: http://www.geeksforgeeks.org/array-rotation/

s*r2014-02-26 08:02

31 楼

版上说的A家到底是哪家啊？？觉得除了Alibaba，无聊Apple还是Amazon都没法和FLG比
。

d*n2014-02-26 08:02

32 楼

How about this:
void rotate(int a[], int k, int n) {
int i=0;
while(k > 0)
{
for(; i+kint lastK = k;
k = n % k;
n = lastK;
}
}

【在 M******i 的大作中提到】

: 这个解好像有问题。
: for example, array {1,2,3,4,5}, k = 3, n = 5
: I = 0 swap(a[0],a[3]) ==> 4,2,3,1,5
: I = 1 swap(a[1],a[4]) ==> 4,5,3,1,2
: then second loop
: I == 2, k -- ==> k = 2
: swap(a[2], a[4]) ==> 4, 5, 2, 1, 3
: I == 3, k = 1
: swap(a[3], a[4]) ==> 4, 5, 2, 3, 1
: I == 4, k == 0 stop.

m*g2014-02-26 08:02

33 楼

这个验证通过：
#include
#include
#include
using namespace std;
void rotate(int a[], int k, int n) {
int i=0;
k = k%n;
for (; i+kif (n%k == 0) return;
rotate(&a[i], k - n%k, k);
}
int main()
{
int i;
int a[]= {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
rotate(a, 5, 12);
for(i=0; iprintf( "%d ", a[i]);
}
printf("n");
return 0;
}

【在 d****n 的大作中提到】

: How about this:
: void rotate(int a[], int k, int n) {
: int i=0;
: while(k > 0)
: {
: for(; i+k: int lastK = k;
: k = n % k;
: n = lastK;
: }

M*i2014-02-26 08:02

34 楼

这个差不多了。不过这么recursive一下，好像没有经典做法三次倒转optimal。

【在 m**********g 的大作中提到】

: 这个验证通过：
: #include
: #include
: #include
: using namespace std;
: void rotate(int a[], int k, int n) {
: int i=0;
: k = k%n;
: for (; i+k: if (n%k == 0) return;

d*n2014-02-26 08:02

35 楼

Fixed a bug below.

【在 d****n 的大作中提到】

: How about this:
: void rotate(int a[], int k, int n) {
: int i=0;
: while(k > 0)
: {
: for(; i+k: int lastK = k;
: k = n % k;
: n = lastK;
: }