一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等(感谢博友提供的关于该问题的相关资料 划分问题)。由于时间仓促,加之面试时头昏脑涨,这道题没做出来甚至没有给出思路,这让我多少有些遗憾和不甘。因为最近接触算法的东西较多而且本身对算法感兴趣,所以回家之后绞尽脑汁想把这题做出来。其实刚看到这题时感觉不难,但是因为数字个数及数值的不确定,我感觉这题越想越难。昨天一晚上没有睡好,甚至做梦都在想这题!

今天上午在多个群里问了这题,都没有给出思路,真是绝望至极。很多人都说 n/3 的思路,其实这种思路一开始就是死胡同。本人属于那种不会轻言放弃之人,哈哈。本人多年经验得出一结论:只要认真思考,有耐心,很多问题都能迎刃而解。每次遇到难缠的问题,我都会抓耳挠腮,而一旦解决,又会手舞足蹈。跑远了,言归正传,中午正准备趴在工位上休息,眼睛扫了扫笔记本,瞬间茅塞顿开。真是踏破铁鞋无觅处,得来全不费工夫!果不其然,算法就是窗户纸!

我先说一下我的思路,首先一定要先排序,这也是解决问题的关键。然后降序排序后的前三个数各分一组(根据博友的评论,此处是问题所在,前三个数也有可能属于同一组,暂时没有想到好方法),把剩余数往三个数上叠加。我最开始的思路也是如此,问题在于分组个数不确定,出现极端大的数怎么办,怎么叠加?那层窗户纸就是将剩余数中的最大值加到前三个数的最小值上,然后重排序,继续叠加,直到数组个数剩三个为止!不知道这样说好不好理解,比如以下数组:

    [3, 8, 20, 15, 60, 1, 32];

    // 分组流程分解,根据博友评论,此方法属于贪心算法,只是局部求解:

    // 1.从大到小排序 
    [60, 32, 20, 15, 8, 3, 1]

    // 2.剩余数叠加 
    [60, 32, 35(20+15), 8, 3, 1]

    // 3.重排序 
    [60, 35, 32, 8, 3, 1]

    // 4.再叠加 
    [60, 35, 40(32+8), 3, 1]

    // 5.重排序 
    [60, 40, 35, 3, 1]

    // 6.再叠加 
    [60, 40, 38(35+3), 1]

    // 7.结果 
    [60, 40, 39]

 我想看完上述流程演示,这个题基本就没问题了吧。上述流程最终输出的是每组的和,并没有反映出每组的分组情况。我们应该定义一个函数,输出带有分组情况的数组。比如:

    var arr = [3, 8, 20, 15, 60, 1, 32];

    function equal(arr) {
        
        ......

        return array;

    }

    > input equal(arr)

    < output [[60],[32,8],[20,15,8,3,1]]

 算法这东西,只有自己亲自思考出来才能深刻理解它。各位博友看到这里,可以自己试着写一下上面的函数,然后再对比我写的函数,如果你觉得你写的函数更优雅,欢迎给我留言!

以下是我写的算法,其实从有思路到写出程序也废了很大劲:

    // 任意数分三组,每组和尽量相等(也就是最大值与最小值差值最小)
    function equal(arr) {

        var array = [];

        arr = sortMArray(arr);

        for (var i = 0; i < arr.length; i++) {
            // 转换成多维数组
            array.push([arr[i]]);
        }

        while (array.length > 3) {
            array[2].push(array[3][0]);
            array.splice(3, 1);
            array = sortMArray(array);
        }

        return array;

    }

为了按要求输出数组,我还使用了多维数组排序及数组内元素求和的算法,我在此没有深究,只是普通的冒泡排序,如下:

    // 计算数组元素和
    function sum(o) {

        var sum = 0;

        if (Array.isArray(o)) {
            o.map(function(item, index, array) {
                sum += item;
            });
        } else {
            sum += o;
        }

        return sum;

    }

    // 多维数组排序
    function sortMArray(arr) {

        for (var i = 0, len = arr.length; i < len - 1; i++) {
            for (var j = i + 1; j < len; j++) {
                if (sum(arr[i]) < sum(arr[j])) {
                    var temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        return arr;

    }

看着输出的结果,确实有点小激动~

最后,我们可以将此题再延伸一下,比如任意数分任意组,有了上面的算法,这个就很简单了,直接贴代码

    // 计算数组元素和
    function sum(o) {

        var sum = 0;

        if (Array.isArray(o)) {
            o.map(function(item, index, array) {
                sum += item;
            });
        } else {
            sum += o;
        }

        return sum;
    }

    // 多维数组排序
    function sortMArray(arr) {

        for (var i = 0, len = arr.length; i < len - 1; i++) {
            for (var j = i + 1; j < len; j++) {
                if (sum(arr[i]) < sum(arr[j])) {
                    var temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        return arr;

    }

    // 任意数分 n 组,每组和尽量相等(也就是最大值与最小值差值最小)
    function equal(arr,n) {

        var array = [];

        arr = sortMArray(arr);

        for (var i = 0; i < arr.length; i++) {
            // 转换成多维数组
            array.push([arr[i]]);
        }

        while (array.length > n) {
            array[n-1].push(array[n][0]);
            array.splice(n, 1);
            array = sortMArray(array);
        }

        return array;

    }

    // 测试数组
    var arr = [3, 8, 20, 15, 60, 1, 32];

最后的最后还要说一句,也算是自我检讨以及对代码的孜孜以求,虽然功能完成了,但从程序员的角度来看,我还没有对输入参数进行校验,所以这样的代码还是有瑕疵的!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏web前端教室

重学javascript 红皮高程(5)

JS这项技术,细节到位了,就会一通百通。经常在网上看到说学一个框架,最有效的办法是去看它的源码。但我经常看不懂,为什么呢?因为我基础不好,不明白源码中的一些写法...

2055
来自专栏数据结构与算法

Day2上午解题报告

预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

4374
来自专栏专知

【专知-关关的刷题日记18】Leetcode 35. Search Insert Position

题目 Given a sorted array and a target value, return the index if the target is fo...

3739
来自专栏take time, save time

你所能用到的数据结构(二)

      周末开始更新了,首先感谢各位对我写的东西还能保持兴趣,先回答几个留言中的一个问题和我对无损编码那一节的一个留言的一个看法,第一个是推荐算法书,首先,...

3156
来自专栏数据结构与算法

1026 逃跑的拉尔夫

1026 逃跑的拉尔夫 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 年轻的...

3728
来自专栏程序员互动联盟

【答疑解惑】失之毫厘谬以千里

1、scanf使用陷阱 ? ? 如果scanf中%d是连着写的如“%d%d”,在输入数据时,数据之间不可以加逗号,只能是空格或tab键或者回车键“1 2” 或 ...

3017
来自专栏JavaEdge

设计模式实战 - 抽象工厂模式导读定义适用场景优点缺点产品等级结构与产品族实践 coding

工厂方法模式人是造出来了,可都是清一色的类型,缺少关爱、仇恨、喜怒哀乐等情绪,人类的生命太平淡了,忘记给人类定义性别了,那怎么办? 从头开始建立所有的事物也是...

1401
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列02:替换空格 原

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1223
来自专栏云时之间

算法导论系列:分治算法

说起分治法,大家一定也都听过秦始皇采用郡县制将国家分为三十六郡的故事,我们常说”山高皇帝远”,意思就是山高路远,皇帝都管不了,实际上无论皇帝多远,山有多高,整个...

1272
来自专栏数据结构与算法

P1796 汤姆斯的天堂梦_NOI导刊2010提高(05)

题目描述 汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣,每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。 有一些航班将...

2788

扫码关注云+社区

领取腾讯云代金券