找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

【算法题】韩信点兵:如何优雅移动士兵?

admin 2019-5-25 15:38 157人围观 C++相关



文章来源:算法面试题

作者:Great Eagle

麻烦

自从“韩信点兵,多多益善”事件之后,韩信的麻烦事就来了。这不,今天刘邦又找他麻烦了。

刘邦:爱将,近日朕看你早早就下班了,怎么回事呀?

韩信:陛下明鉴,臣点兵时有技巧,效率极高,陛下安排的工作任务臣均已完成。而本朝建立以来实行弹性工作制,于是臣就回家了。

刘邦:你小子是真不知道朕的苦衷啊!朕的大汉朝刚刚建立,百废待兴,你就不能为朕分忧,为大汉朝多做点贡献吗?

韩信:何事叨扰陛下?请陛下明示,臣必当竭尽全力!

(刘邦心理活动:我哪有什么事情让你去做呀?让你办事只是借口啦!只不过是担心你下班那么早,空闲下来谋划策反之事罢了。不得不防啊!为了不让你那么早下班,是得随便找个事拖拖你。)

突然,刘邦想了个法子。

刘邦:既然你点兵是个能手,朕就交你一事。从明天上班开始,你在点兵之前,要先将你的士兵循环左移,左移完毕,让我审查,再开始点兵。

说着,刘邦用木棍在地上画了起来。



刘邦:假如现在有7个士兵,循环左移3次,移动结果如上图。

韩信:陛下,这好办,在移动时,我只要先让前三个士兵出列,然后让后面的兵依次向前移动三个位置,最后把前三个兵插入到队尾即可。

刘邦:那我如果让你左移4次、5次,你是不是要分别出列4个、5个人呢?不行,限制你每次只能出列1个人。

(注:从算法角度分析,这其实是限制了空间复杂度为O(1))

(韩信心理活动:如果每次只能出列一个人的话,我就得按刘老板画得那样,第一次先将1号士兵出列,然后让其他士兵依次向前移动一个位置,最后再把1号士兵插入队尾,对于2号、3号士兵也当如此。忽然,他想到了一个问题,在点兵前为什么要进行左移这个活动呢?没什么意义呀。)

正当他想问刘邦,此时刘邦瞪了他一眼,于是他赶紧改变主意,回复遵命。毕竟,快过年了,年终奖要紧。

就这样,接下来的日子里,韩信在点兵前都要进行这样一项活动,可是,随着时间一天天流逝,韩信发现刘老板给他的兵越来越多了,兵少时没关系,进行左移活动也用不了多少时间,而兵多了就麻烦了,常常使自己加班加到很晚才能下班。

(PS:刘老板对韩信已有怀疑之心,可为什么还要给他越来越多的兵呢?没错,他在试探韩信,当韩信拥兵众多时会不会谋反。)

求助

无法忍受这样无休止的加班,韩信来拜访张良。见到张良,将自己的情况一五一十给张良道明。

张良:初创公司都这样,加班是常事,习惯就好了。

韩信:可我觉得不是加班那么简单,刘老板似乎故意在找我麻烦。

张良:你可知刘老板为何要找你麻烦呀?

韩信:实在是无所得知啊!

张良:当真不知?

韩信:不知。

张良:你可知功高盖主的道理呀?

韩信:你是指老板担心我取代他。

张良:是呀,外边都在说你“韩信点兵,多多益善”,有句话“狡兔死,走狗烹,飞鸟尽,良弓藏”,你不得不记在心上呀!

(韩信直冒冷汗)

韩信:谨记教诲,而当务之急是先把这个士兵左移问题解决了,否则,我可能因此而被杀头。

张良拿起木棍在地上画了起来,不一会儿,有了答案。

张良:还拿你刚刚说的例子为例,如下图,有7个士兵,循环左移3位,你可以将此问题分为3步:

  1. 将队列分为两部分,左移3位就从第三个士兵后面划分;

  2. 分别对左右两部分逆序,具体逆序过程:将第一个士兵与最后一个士兵交换位置,将第二个士兵与倒数第二个交换位置,以此类推。具体交换时,比如1号士兵与3号士兵,可以先让1号士兵出列,3号填补到1号位置上,再把1号入列到3号位置上,这样也满足了刘老板规定的每次只能出列一个士兵。

  3. 再对整个队列进行一次逆序,完毕。




韩信感激涕零,觉得张良的方法效率太高了,谢过张良后,告辞了。

(注:韩信原来的方法时间复杂度为O(nL),张良的方法时间复杂度为O(L),其中n为移动位数,L为数组长度)

代码实现

给定一个数组和正整数n(n小于数组长度),请将此数组循环左移n个位置。

例:

输入:[1,3,5,8,6],3

输出:[8,6,1,3,5]

下面是作者用JavaScript实现的代码,仅供参考!(建议大家自己动手实现一遍)

1//逆序函数
2function reverse(arr, left, right) {
3    let temp;
4    while(left < right) {
5        //两数交换
6        temp = arr[left];
7        arr[left] = arr[right];
8        arr[right] = temp;
9        //左下标+1,右下标-1
10        left++;
11        right--;
12    }
13}
14
15//循环左移函数
16//arr:数组
17//n:左移位数
18function loopLeft(arr, n) {
19    if(arr === null || arr.length === 0) return arr;
20    //对左半部分进行逆序
21    reverse(arr, 0, n - 1);
22    //对右半部分进行逆序
23    reverse(arr, n, arr.length - 1);
24    //对整个数组进行逆序
25    reverse(arr, 0, arr.length - 1);
26    return arr;
27}


温馨提示:可左右滑动

复制代码请前往https://blog.csdn.net/Great_Eagle/article/details/84204494

你可能会喜欢

1、为什么你学不会递归?告别递归,谈谈我的一些经验

2、【面试被虐】游戏中的敏感词过滤是如何实现的?

3、一文读懂一台计算机是如何把数据发送给另一台计算机的

4、腾讯面试:一条SQL语句执行得很慢的原因有哪些?---不看后悔系列

5、史上最全各类面试题汇总,没有之一,不接受反驳




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:苦逼的码农,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......