头条的算法面试题:简洁版的最优分单法

JAVA herman 544浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:xttblog,发送下载链接帮助你免费下载!
本博客日IP超过1800,PV 2600 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:xttblog,之前的微信号好友位已满,备注:返现
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

今天中午,发了一个微博,13 分钟,1.4 万的阅读。

宏颜获水

昨天,有网友给我抛出了一道算法题,说是一道头条的面试题。

听说,头条的算法是很牛的。我不一定会,所以,发到了群里。没想到大家的热情超出我的预期,很多人给出了思路,还有一些人给出了代码,有 js 实现的,有 Java 实现的,还有 C++ 实现的。

面试题如下:

给定一个数,算出平均值是整数的算法。例如:5 平均 2 份,则结果为,2 和 3;8 平均为 3 份,则为 2,3,3;11 平均 4 份,则为 2,3,3,3;15 平均 3 份,则为:5,5,5。求算法

有人说,这和微信发红包一样,其实完全不一样的。

抢红包的额度是从 0.01 到剩余平均值 * N (N 是一个系数,决定最大的红包值)之间。所以,差别还是挺大的。

网友 A 的 Java 版算法如下:

public class Divide {
  public static int sum(int[] res) {
    int sum=0;
    for(int i:res) {
      sum += i;
    }
    return sum;
  }
  public static void aveDivide(int m,int n) {
    if(n <= 0) {
      return;
    }
    int res [] = new int[n];
    int i = 0;
    while(true) {
      if(sum(res) == m) {
        break;
      } else {
        res[i%n] += 1;
        i++;
      }
    }
  }
  public static void main(String[] args) {
    aveDivide(15,10);
  }
}

试了一下,运行结果完全正确!

网友 B 的算法思路:

找除数n大约被除数m的最小公倍数p,得最小商x=p/n ,然后计算除数m有最多a个x,则组合伟x0、x1…xa-1、m-a*x

并且进一步补充道:

比如11 分4份,4大于11的最小公倍数为12,12/4=3 这有最小 3个3,剩下的就是2
(8+1)/3=3 最多有2个3 这组合为 2、3、3

吃瓜群众!

吃瓜群众

网友 C 的 JavaScript 版算法:

JavaScript 版算法

整齐的队列,一排 666 !

网友 D 的 C++ 算法:

#include <iostream>
using namespace std;

void xxx(int m, int n) // m 平均分为n份, 复杂度O(n)
{
  for (int i = 0; i< n-m%n; i++) printf("%d ", m/n);
  for (int i = 0; i<m%n; i++) printf("%d ", m/n+1);
  puts("");
}

int main()
{
  int m,n;
  while(~scanf("%d%d", &m, &n)) xxx(m,n);
  return 0;
}

还有网友考虑了算法复杂度!

算法复杂度

对于算法我很平庸,一窍不通。最能体现我的,还是马云那句“算了吧”。

核心思想很简单,逻辑如下:

算法面试题

对于懂算法的,这又是一道送分题!

以上,希望能对每个读者有所帮助,如果你想交流技术,请加我微信:xttblog,坑位不多了!

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:codedq(5000人已满),微信号3:xttblog(超2800)。备注:“xttblog”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » 头条的算法面试题:简洁版的最优分单法