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

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

相关文章

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n

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.