算法 韩信点兵 循环左移数组元素

2023-12-28 08:30

本文主要是介绍算法 韩信点兵 循环左移数组元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

static void Main(string[] args){ForeachLeft();//韩信点兵
        }public static void ForeachLeft(){int[] arr = new int[5] { 1, 3, 5, 8, 6 };int[] result = loopleft(3, arr);foreach (var item in result){Console.WriteLine(item);}Console.ReadKey();}public static int[] loopleft(int n,  int[] arr){if (arr==null||arr.Length==0){return arr;}reverse(0, n - 1, ref arr);reverse(n , arr.Length - 1, ref arr);reverse(0, arr.Length - 1, ref arr);return arr;}public static void reverse(int left, int right, ref int[] arr){int temp = 0;while (left < right){temp = arr[left];arr[left] = arr[right];arr[right] = temp;left++;right--;}}

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

 

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

 

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

 

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

 

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

 

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

 

突然,刘邦想了个法子。

 

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

 

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

 

 

 

刘邦:假如现在有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为数组长度)

 

转载于:https://www.cnblogs.com/zhaokunbokeyuan256/p/10215770.html

这篇关于算法 韩信点兵 循环左移数组元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/545424

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4