首页 > 编程语言 > 详细

一道算法面试题目——变种的零钱问题

时间:2019-09-11 00:40:57      阅读:158      评论:0      收藏:0      [点我收藏+]

标签:公开   发现   list()   开课   过程   event   

 

最近面试一家外企,给了我一道算法题目,让我回家做。

原题如下:

技术分享图片

 

 

 

是说 在EXCEL有两列数字,左边列大概有5000个,是小于1500的包含两位小数的金额,右边是大于1500的包含两位小数的金额。

写一个程序,当你选择了右边的金额,快速的输出左边金额相加等于右边的金额的数字。

就是一个快速从数组中找出几项相加等于一个数字的题目

比如数组a=[1,3,2,5,4],    输入8,则会显示  (1,2,5)  ( 3,5) (1,3,4)

 

看到题目心理一松。

他奶奶的不算麻烦,循环几次就出来了,最多是个平方时间复杂度。

又理了一下,大概思路如下:

从1开始,向后累加,小于8则继续加

大于8,就跳过其中已经累加的数字,重新累加

比如1+3+2+5>8,就跳过3,得到1+2+5=8,接着循环,1+2+5+4>8,就跳过2,1+5+4还是大于8,跳过5,直到跳到1+4<8,没有数字了

向上从2开始。

写的过程中就发现不对劲了,他奶奶的这是个指数时间复杂度。

还是太单纯啊。

我用了栈,是希望自己能理的清楚点。代码如下:

        /// <summary>
        /// 栈解决  多项式量级,考虑优化
        /// </summary>
        /// <param name="bankValue">当前循环的数字</param>
        /// <param name="duePayment">整个数字列表</param>
        void calcByStack(int bankValue, List<int> duePayment)
        {
           DateTime dtbegin = DateTime.Now;
            //倒叙排列可以快速得到值 但是数字越小越难计算 
            duePayment = duePayment.OrderByDescending(o => o).ToList();
            //duePayment = duePayment.OrderBy(o => o).ToList();
            int count = duePayment.Count();
            Stack<int> result = new Stack<int>();
            int temp = 0;
            for (int i = 0; i < count; i++)
            {
               temp++;
                //排除单数字大于结果的数字
                if (duePayment[i] > bankValue)
                {
                    continue;
                }
                //栈加入
                result.Push(duePayment[i]);
                //获取当前栈
               int nowSum = result.Sum();
                if (nowSum > bankValue)
                {
                    result.Pop();
                }
                else if (nowSum == bankValue)
                {
                    int times = (DateTime.Now - dtbegin).Milliseconds;
                    dtbegin = DateTime.Now;
                    drawLbItems(times, 1, result,null);
                    result.Pop();
                }

                if (i == count - 1)
                {
                    if (nowSum < bankValue)
                    {
                        result.Pop();
                    }
                    if (result.Count() > 0)
                    {
                        i = duePayment.IndexOf(result.Peek());
                        result.Pop();
                    }

                }
            }
        }    

 

写完感觉还不赖,虽然有复杂度让人有点担心,但是最差也是有结果的。

先用简化版的数字跑了一下,能得出正确结果。

然后上了正式的5000个数字。

很快就出了个几个结果,心里美滋滋,看来虽然已经不敲代码带团队了,基本功还是没落下。

 

但是

但是电脑就一直跑啊跑。

跑啊跑。

跑啊跑。

跑啊跑。

我寻思数字多得多跑一会,我歇一下,几十行代码也是耗费脑细胞的。

于是我定了外卖,拿出啤酒,顺手打开了LOL。

大乱斗打完了,还在跑。

外卖来了。

啤酒喝完了。

饭吃光了。

还在跑。

我……%¥&……%*

 

特么的一直跑不完是怎么回事?

内存一直占用100M左右。

看来我写的有问题。

断点调试,还在循环,还是在循环。

我搭环境写程序用了俩钟头,结果跑了三个钟头还没跑完。

我焦虑了。

我抑郁了。

我丢掉啤酒拿起咖啡准备上多线程。

但是特么的多线程再多也搞不定复杂度的问题啊。

这是算法题啊。。

 

我打开了百度,参考也是一门学问

背包问题,背包问题不是相等啊,pass。

零钱问题,零钱是无限用的啊,找到一个答案就终止了啊。我这个要找到全部的啊,pass。

动态规划,pas嗯?

动态规划?每次的最优解?

最优?路径优化?

我的路径能优化吗?有什么问题?

 

我重新打开了excel。

滚动着鼠标看竖屏上的数字。

我幻想自己是段誉,风度翩翩又色心大起的看着神仙姑姑就领悟了神功。

技术分享图片

 

 

我该怎么优化?减少数字就是优化嘛。。

嗯,先把大于结果的数字拿掉,我已经写了。

然后排个序,排过序的数字才好操作。

嗯?有思路了,最优路径嘛,肯定是找到到最接近的数字。

排好序的数组如下 a=[5,4,3,2,1]   结果是8

先输入5,我用8-5得出差3。那么我去判断4是不是大于3,大于就不算了,跳过。

得到5+3=8

2<3,在往上加。

上1,得到了5+2+1.

满足小于等于差值的再去加,这就是变种的动态规划啊,这是变种的插值查找啊。

感谢CCTV欧不,是网易公开课和算法导论,总算没白看。

虽然在例子里只跳了一个4,但是在5000个数字里跳的还是很可观的,这么一跳减了至少五分之一呢。

嗯,老骥伏枥,尚能饭桶。一个一年都写代码的项目经理能把题目做到这个份上,也是真的把脑细胞当糖原给挥发了。

 

我感觉自己是乔峰,站在城门口打出了一套降龙十八掌。看我的“亢龙有悔”,我一边念叨一边按下了F5。

嗯~!~

这次更快的出结果了。

嗯~!

看这个效率优化的很客观啊。

 

五分钟。。

十分钟。。

又开始了。

。。。

。。。

我呼吸急促。

我脸色变红,就像杨过丢掉了姑姑。

还是不行~!@¥#@!……*&……*&……

我的难过跟委屈排山倒海。

 

我拿出了红牛。凌晨3点了,我告诉自己冷静。

丢了姑姑不可怕,丢了左手才可怕。

我打好断点,使劲看那些数字。

我看到一堆小于10的数字在嘲笑我。

好多好多,有一千个,小于1的也有好几百。

他奶奶的我再怎么往下跳都是上百的数字,优化有效果,但是还是没结果。

数组如下  a=[5,4,3,2,1,0.1,0.1,0.001,0.02,0.03]

我跳过了4还是顶不住小数轰炸啊。

有了,把这些个数字拿出来累加一下。

一个5,我用8-5得到了3,

先用3去判断4要不要跳过,顺带判断 4+3+2+一堆小于1的数 是不是小于3

如果小于3则不用再往下计算了,循环到结束也没有正确结果。

 


凌晨4点,我敲出了如下代码:

 1 void bw_DoWork(object sender, DoWorkEventArgs e)
 2         {
 3             //筛掉比总值大的数据,去除重复数据,倒叙排列
 4             duePayments = duePayments.Where(o=>o< bankValue).Distinct().OrderByDescending(o => o).ToList();
 5             int count = duePayments.Count();
 6             result = new List<int>();
 7             for (int j = 0; j < count; j++)
 8             {
 9                 //以每个数字为主计算
10                 result.Add(duePayments[j]);
11                 calcPruning(bankValue, duePayments, j);
12                 //计算完毕初始化结果
13                 result = new List<int>();
14             }
15         }

 

 1 /// <summary>
 2         /// 剪枝操作跳转,减少大量无需计算的数字
 3         /// </summary>
 4         /// <param name="bankValue">总值</param>
 5         /// <param name="duePayment">全部数据</param>
 6         /// <param name="j">当前数字</param>
 7         void calcPruning(int bankValue, List<int> duePayment, int j)
 8         {
 9             //全部数据的最大长度
10             int count = duePayment.Count;
11             for (int i = j + 1; i < count; i++)
12             {
13                 //汇总 获取当前计算值中的数据总值
14                 int nowReuslt = result.Sum();
15                 //差值=总值-当前数据总值
16                 int temp = bankValue - nowReuslt;
17                 //如果差值比当前需要计算的数字大,则直接加入计算
18                 if (temp > duePayment[i])
19                 {
20                     //获取所有小于当前数值的数进行汇总,如果总值小于差值,则向上回溯
21                     var max = duePayment.Where(o => o < duePayment[i]);
22                     if (max.Sum() < temp)
23                     {
24                         result.Add(duePayment[i]);
25                         //直接回溯
26                         i = count - 1;
27                     }
28                     //否则继续计算
29                     else
30                     {
31                         result.Add(duePayment[i]);
32                     }
33 
34 
35                 }
36                 //如果差值等于当前的数字,找到一个正确解
37                 else if (temp == duePayment[i])
38                 {
39                     result.Add(duePayment[i]);
40                     drawLbItemsBack drawItem = drawLbItems;
41                     lbResult.Invoke(drawItem, (DateTime.Now - beginTime).Milliseconds, 3, null,result);
42                     break;
43                 }
44                 //如果差值小于了当前数字,则做剪枝操作,向下跳转
45                 else
46                 {
47                     //获取当前数组中小于temp的所有数字
48                     var last = duePayment.Where(o => o <= temp);
49                     if (last.Count() > 0)
50                     {
51                         //获取最接近temp的数组下标
52                         i = duePayment.IndexOf(duePayment.Where(o => o <= temp).OrderByDescending(o => o).First()) - 1;
53                     }
54                     else
55                     {
56                         i = count - 1;
57                     }
58                 }
59                 //如果一个循环周期未找到正确数字,待计算数组向上回溯
60                 if (i == count - 1)
61                 {
62                     if (result.Count > 0) {
63                         i = duePayment.IndexOf(result[result.Count - 1]);
64                         //移除最小值向上
65                         result.RemoveAt(result.Count - 1);
66                     }
67                     //获取当前大数组中当前计算的最小的值,为i指定下标跳过
68                     
69                     if (i == count - 1&&result.Count>0) {
70                         i = duePayment.IndexOf(result[result.Count - 1]);
71                         //移除最小值再次向上回溯
72                         result.RemoveAt(result.Count - 1);
73                         if (result.Count == 0) {
74                             break;
75                         }
76                     }
77                    
78                 }
79 
80 
81             }
82 
83         }

 

 

 

我怀着无限惆怅又欣喜的心情按下了F5。

就像杨过丢了胳膊找到姑姑一样。

3分钟出了结果。

验证正确。

 

这个题目我已经优化不动了。

我对自己的水平一度怀疑。

我就这样发送题目给了面试公司。

我从开始的忐忑到现在的更忐忑。

还好 拿到了OFFER

后续待写。

一道算法面试题目——变种的零钱问题

标签:公开   发现   list()   开课   过程   event   

原文:https://www.cnblogs.com/fyanx/p/calcAmount.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号