原创 ©著作权归作者所有:来自51CTO博客作者wx634e39bb59725的原创作品,请联系作者获取转载授权,否则将追究法律责任 最近发现了一个刷题网站://app.codility.com/programmers/lessons 这个网站做题目时候的界面让我惊艳到了 首先这是题目界面:Codility MinMaxDivision
然后点击start, 出来的是这样一个界面
有计时功能,还有自己编写测试样例功能,还有很多其他功能。给人营造一种完全融入到刷题状态的感觉。
点击提交之后的结果如下:
还可以分析你程序的时间效率。满分是100%
从体验来说,比LeetCode 强很多了。但是他的题目好像很少。
接下来说这道题目。从一个数组中划分k个块,要求k个块中最大数组和最小,我一开始想用动态规划,结果发现,数据范围太大,不是动态规划的范畴。
一看题目的类别是二分。根据之前刷题的经验,求最大中的最小,或者最小中的最大,要么是二分,要么是动态规划。
二分的话,得找到用来二分的对象。这道题目应该对结果进行二分。就是k个块中最大数组和的最小值。
从0 到 sum 进行二分,那么二分中的判断条件就是该数组是否可以划分小于等于k个块,并且每个块的和都小于等于mid
如果符合条件,说明mid的值是过大的,还可以再小一点,end=mid-1;
如果不符合条件,说明mid的值是过小的,start=mid+1;
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
int n,m,k;
using namespace std;
bool isTrue(vector<int> &A,int sum,int k)
{
int s=0;
int p=0;
for(int i=0;i<A.size();i++)
{
if(s>sum)
{
p++;
i--;
s=0;
}
s+=A[i];
}
if(s<=sum)
p++;
else
p+=2;
if(p<=k)
return true;
return false;
}
int solution(int K, int M, vector<int> &A) {
int end=0;
int start = 0;
for(int i=0;i<A.size();i++)
{
end += A[i];
start = max(start,A[i]);
}
while(start<end)
{
int mid = (start+end)/2;
if(isTrue(A,mid,K))
{
end=mid;
}
else
{
start=mid+1;
}
}
return start;
// write your code in C++14 (g++ 6.2.0)
}
- 赞
- 收藏
- 评论
- 举报
相关文章
codility上的问题(18) Rho 2012
从正整数1开始,产生一个数列,数列中的每个数是之前出现过的任意两个数的和(可以相等),问产生正整数A,需要的数列长度至少是多少?返回这样一个最短的序列。例如A=42 可以这样[1, 2, 3, 6, 12, 24, 30, 42],也可以[1, 2, 4, 5, 8, 16, 21, 42],后者是最短的。A不大于600。 分析: 本题没规定时间、空间复杂度。因为本题只能暴力搜索,但是一般的实现会超时,需要一些剪枝。首先保证数列严格单增。另外,我们用迭代加深dfs做的时候,注意看一下剩余的长度能不能达到所要找的数,判断的方法很简单,达到一个数最快的方法是,每次把最大的翻倍……另外可以估算下序列
#include 进制 暴力搜索 空间复杂度 迭代加深
公司介绍 查看更多> TomTom 上海 · 计算机软件 · 20-99人 在线Codility三个task 面试职位: TomTom-图像算法-上海
在Codility上面170min三个task要做,要求C++。都是字符串和排序的问题。但是需要注意的是,因为Codility本身的IDE功能比较差,所以要谨慎修改代码。 不爽的是,很多在Visual Studio中可以使用语句和库,在Codility当中不能使用,会耽误很多事情。 ...查看全文
面试结果: 感觉靠谱
面试难度: 有难度
面试感受: 一般
工资水平同同业其他公司
共有3位员工分享个人工资,来自300个职位
猜你可能喜欢
TomTom相关的公司
字节跳动
北京-互联网-10000人以上
公司全称:北京字节跳动网络技术有限公司
联想
北京-计算机硬件/网络设备-10000人以上
公司全称:联想(北京)有限公司
中国人寿保险
北京-保险-10000人以上
公司全称:中国人寿保险(集团)公司
TomTom相关的问答
有什么特别优于其他公司的福利吗?年终奖有多少,你满意吗?
有午餐,餐标10.5。交通补贴120。年终奖分部门。化学一般1.5个月
业务代理是什么
向保险公司采购保险产品、产品销售定价(包含优惠促销及业务人员佣金提比)、通过各种渠道进行销售
...查看全文
查看更多
微信扫码
下载看准App