• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

逛知乎,记一个算法的题目

admin

11月 28, 2021

知乎链接是:https://zhuanlan.zhihu.com/p/38850888

题目信息:一副从1到n的牌,每次从牌堆顶取一张放桌子上,再取一张放牌堆底,直到手里没牌,最后桌子上的牌是从1到n有序,设计程序,输入n,输出牌堆的顺序数组

发现题目比较有意思,小时候还真这么玩过,当时也是一张一张的试出来,然后秀给小伙伴们看,拿到题目自己就琢磨的开始写代码

        static void Main(string[] args)
        {
            int x = 10;
            int[] temp = new int[x];
            for (int i = 0; i < x; i++)
            {
                temp[i] = i + 1;
            }
            temp = JustAgain(temp);
            Console.WriteLine(string.Join(" ", temp));
        }

        static int[] JustAgain(int[] list)
        {
            while (true)
            {
                int CurrentInt = 0;
                int WantInt = 0;
                int CurrentIndex = 0;
                int WantIndex = 0;
                if (JustTest(list, 1, out CurrentInt, out WantInt) == false)
                {
                    for (int i = 0; i < list.Length; i++)
                    {
                        if (list[i] == CurrentInt)
                        {
                            CurrentIndex = i;
                        }
                        else if (list[i] == WantInt)
                        {
                            WantIndex = i;
                        }
                    }
                    list[WantIndex] = CurrentInt;
                    list[CurrentIndex] = WantInt;
                    return JustAgain(list);
                }
                return list;
            }
        }

        static bool JustTest(int[] list, int TempCurrentInt, out int CurrentInt, out int WantInt)
        {
            if (TempCurrentInt != 1 && list.Length > 1)
            {
                //将第一位数字换到最后一位
                var tempInt = list[0];
                for (int i = 0; i < list.Length - 1; i++)
                {
                    list[i] = list[i + 1];
                }
                list[list.Length - 1] = tempInt;
            }
            if (list[0] == TempCurrentInt)
            {
                if (list.Length == 1)
                {
                    CurrentInt = 0;
                    WantInt = 0;
                    return true;
                }
                //移除第一位数字
                int[] TempNew = new int[list.Length - 1];
                for (int i = 0; i < TempNew.Length; i++)
                {
                    TempNew[i] = list[i + 1];
                }
                return JustTest(TempNew, ++TempCurrentInt, out CurrentInt, out WantInt);
            }
            else
            {
                CurrentInt = list[0];
                WantInt = TempCurrentInt;
                return false;
            }
        }

写的过程中发现了点小问题,基础知识不够扎实,本来传递的是List,后来发现List是引用类型,子方法里操作完,实际内存地址里的List数据也跟的会变,无奈改成了数组操作。写这个花了2小时,功力还是不够。。。

原文中的微软大佬说的晕头转向的,没明白啥逆向解决

“取一个1~n的数组,这里为了说明取n=5。按照题目中的规则变换,得到数组:[1 3 5 4 2],将该数组下标与值互换得到[1 5 2 4 3],即为答案。解释:[1 3 5 4 2]的意义是,经过变换,原数组中3号位置的数字现在2号槽,原数组中5号位置的数字现在3号槽... 
现在已知变换后的槽存放的是1~n,故只需将下标与值互换即可得到待求数组。 这道题还可以继续扩展: 1.变换规则更复杂使得无法逆向模拟还原原数组; 2.最终得到的序列可以扩展为任意序列。请大家以后不要黑微软是养老院了” 但是楼主貌似没理解全,问道你这些数字是数组的下标吗 后面这位微软的程序员也补充了一下,[]括起来的所有元素都是实际的数字(题目中牌上的数字)。下标从1开始

直到看到轮子哥的解释

譬如说一共有5张牌,12345那么玩一遍的结果是24531,但是桌子上的牌是12345,假设原牌数组是x,那么显然

x[2]=1

x[4]=2

x[5]=3

x[3]=4

x[1]=5

原来就是实际操作走一遍(所以是纸牌或者扑克),得到了真实的模拟数据,再根据角标互换原理,即可得出真实的序列,这方法太高了,真的是解决这道题的实践+理论完美组合,微软不是敬老院,我服。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注