找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 8217|回复: 8
收起左侧

[刷题心得] Leetcode - Rotate Array

[复制链接]

30

主题

5

精华

283

积分

高级会员

Rank: 3Rank: 3

积分
283
发表于 2-24-2015 12:37 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
其实这题目是Easy不应该写题解。
不过我记得自己在《编程之美》上第一次看到这题居然第一想法还是O(n^2)的解法 ORZ
其实这题思路很简洁,说白了就是找规律。就从给的例子下手:
k = 3, 1 2 3 4 5 6 7 ----> 5 6 7 1 2 3 4
                                        |
我们来找找分割线 => 5 6 7  1 2 3 4
                                        |

好吧,分割线在7 和 1之间。啥时候这编辑器搞个一键画图功能?

左边的k个数字是原来右边的,右边的n-k个数字是原来左边的。
其实就是先把整个array reverse了。然后把左边k个reverse 再把右边n-k个reverse。

上代码:
  1.     private void rev(int [] num, int beg, int end) {
  2.         while(beg < end) {
  3.             int tmp = num[beg];
  4.             num[beg] = num[end];
  5.             num[end] = tmp;
  6.             
  7.             beg ++;
  8.             end --;
  9.         }   
  10.     }
  11.    
  12.     public void rotate(int[] nums, int k) {
  13.         k = k % nums.length;
  14.         if(k <= 0) {
  15.             return;
  16.         }
  17.         rev(nums, 0, nums.length-1);
  18.         rev(nums, 0, k-1);
  19.         rev(nums, k, nums.length-1);
  20.     }
复制代码
好吧,这个代码写的还是不那么丑的。!而且可读性还是比较高的
类似这种reverse再局部reverse的还有很多题目比如这一道:https://oj.leetcode.com/problems/reverse-words-in-a-string/
都巧妙地通过reverse技巧避免了空间浪费。



9

主题

3

精华

444

积分

高级会员

Rank: 3Rank: 3

积分
444
发表于 2-24-2015 05:25 PM | 显示全部楼层
想问下这种题是不是一定要先整体reverse一次然后在局部reverse,反过来似乎有test case过不了?但是没太想明白问什么,谢谢!
回复 支持 反对

使用道具 举报

30

主题

5

精华

283

积分

高级会员

Rank: 3Rank: 3

积分
283
 楼主| 发表于 2-24-2015 05:35 PM | 显示全部楼层
liuwun 发表于 2-24-2015 05:25 PM
想问下这种题是不是一定要先整体reverse一次然后在局部reverse,反过来似乎有test case过不了?但是没太想 ...

可以过呀~
你想想如果是 1 2 3 4 5 6 7  =》 5 6 7 1 2 3 4
相当于先局部[1, 4] 再局部[5, 7], 再整体旋转。代码如下
  1.     private void rev(int [] num, int beg, int end) {
  2.         while(beg < end) {
  3.             int tmp = num[beg];
  4.             num[beg] = num[end];
  5.             num[end] = tmp;
  6.             
  7.             beg ++;
  8.             end --;
  9.         }   
  10.     }
  11.    
  12.     public void rotate(int[] nums, int k) {
  13.         k = k % nums.length;
  14.         if(k <= 0) {
  15.             return;
  16.         }
  17.         rev(nums, 0, nums.length-k-1);
  18.         rev(nums, nums.length-k, nums.length-1);
  19.         
  20.         rev(nums, 0, nums.length-1);
  21.         
  22.     }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表