程序员进阶之算法练习(三十一)

前言

BAT常见的算法面试题解析: 程序员算法基础——动态规划 程序员算法基础——贪心算法 工作闲暇也会有在线分享,算法基础教程----腾讯课堂地址

正文

1.Mahmoud and a Triangle

题目链接 题目大意: 给出n个线段,每个线段长度为a[i]; 从中选出3个线段,组成一个三角形; 如果可以,输出YES; 如果不可以,输出NO;

输入数据: 第一行,整数n (3 ≤ n ≤ 1e5) 第二行,n个整数 a1, a2, ..., an (1 ≤ ai ≤ 1e9)

Examples input 5 1 5 3 2 4 output YES input 3 4 1 2 output NO

题目解析: 这个题的题意很清晰, 我们知道三角形的性质是:两边之和大于第三边; 暴力的做法是:枚举两条边,再遍历每一条边,通过上面的性质,判断是否为三角形; 但是因为n较大,暴力枚举不可行;

假设三条边分别是a,b,c,并且a<=b<=c,那么只需满足 a+b>c的条件即可; 那么先对数组a排序,然后枚举两条边,假设是a[i]和a[j],且(i < j) 容易知道,对于第三条边,必然是a[j+1];(证:如果存在k>j+1,且a[i]+a[j]>a[k],那么必然有a[i]+a[j]>a[j+1]); 同理,我们知道j必然等于i+1; 这样我们可以知道,只需枚举i,就能知道另外两条边; 复杂度降到O(N);

思考🤔:

2. The Queue

题目链接 题目大意: 小明要去一个地方办业务,业务员上班时间是Ts到Td; 办业务的人很多,排成一列,业务员为每个人办业务都需要时间Tf; 已知n个人的到达时间a[i];(a[i]为正整数,a[i] < a[i+1] ) 小明可以在任何非负整数的时间到达,如果和其他人同时到达,小明会让其他人先,自己排队; 现在小明希望排队时间最短,问:他应该在哪个时间点到达;如果有多个答案,输出任何一个;

输入数据: 第一行 三个整数,Ts、Td和Tf(Ts和Td最大不超过1e12) 第二行,数字n (0 ≤ n ≤ 100 000) 第三行,n个数字,表示n个人的到店时间;

Examples input 10 15 2 2 10 13 output 12 input 8 17 3 4 3 4 5 8 output 2

题目解析: 从题意知道,小明如果0点就到达,一定可以得到服务,故答案必然有解; 用贪心的思想,所有的情况可以分为两种: 1、小明可以在某个人到达的时间的前一秒钟到达; 2、小明在所有人办理业务完成后再到达;

于是枚举a[i]-1到达的时间的最小等待时间,并且再统一考虑最后一种情况即可。 时间复杂度O(N);

思考🤔:

3.Garland

题目链接 题目大意: 小明有一群羊,羊之间用绳子连接起来,最前面的羊由小明牵着,每只羊有一个价值a[i]; 小明还有两个朋友,他希望和他们平分这群羊,并且三个人至少有一只羊,三个人分到的羊的总价值相同;

小明只能剪断两条绳子,问是否存在合适解? 如果不存在输出-1; 如果存在,则输出两只羊的序号,表示应该剪断牵着这两只羊的绳子;

输入数据: 第一行 数字n (3 ≤ n ≤ 1e6) 接下来n行,每行两个数字x和t;第i行的x表示第i只被第x只羊用绳子牵着(x=0表示被小明牵着),第i行的y表示第i只羊的价值;(-100<=t<=100)

Examples input 6 2 4 0 5 4 2 2 1 1 1 4 2 output 1 4

样例解释:如图,应该剪断牵着1、4号羊的绳子,这样可以得到价值5的三个羊群。

题目解析: 抽象一下,就是把一棵树分成3部分,并且每部分的节点之和相等。

注意到题目一个很重要的条件,三个人的价值相同。 而且注意到只能减两次,那么必然有一个是子树; 于是遍历整个树,当遇到一个子树的节点和满足条件时,把这个子树从树中剔除; 再遍历整棵树,找到另外一颗子树,节点和满足条件即可。

思考🤔: 优化: 两次dfs合并成一次,当找到被剔除的节点时,return的sum=0即可。

4.Cartons of milk

题目链接 题目大意: 小红很喜欢喝牛奶,每天最多能喝k瓶牛奶; 小红有n瓶牛奶,每瓶牛奶都有一个有效时间f[i],表示需要在f[i]天内喝完; 同时商店里有m瓶牛奶,每瓶牛奶的有效时间是g[i]; 小红很讨厌浪费,所以她希望能全部喝完自己的牛奶; 同时小红很喜欢牛奶,她希望尽可能喝更多的牛奶; 问小红最多能买多少瓶牛奶,保证牛奶都在保质期内喝完。

如果小红无法保证所拥有牛奶都在保质期内喝完,则输出-1; 如果小红可以保证所拥有牛奶都在保质期内喝完,则输出小红可以买的牛奶数量x; 接下来一行输出x个数字,表示小红应该买的商店牛奶序号。

输入数据: 第一行 n, m, k (1 ≤ n, m ≤ 1e6, 1 ≤ k ≤ n + m) 第二行 n个数字f[i],表示小红n瓶牛奶的保质期; (0 ≤ f[i] ≤ 1e7) 第三行 m个数字g[i],表示商店m瓶牛奶的保质期;(0 ≤ g[i] ≤ 1e7)

Examples input 3 6 2 1 0 1 2 0 2 0 0 2 output 3 1 2 3

题目解析: 可以知道,小红必须是先满足喝完自己的牛奶,再尽可能去喝商店里的牛奶;

小红的策略应该是每天尽可能喝有效时间最短的牛奶,并且每天都喝k瓶; 考虑一个简单的做法: 把小红所有的牛奶排序,按照有效时间从小到大遍历每瓶牛奶,可以容易判断小红自己的牛奶是否能全部喝完;

再来考虑商店里的牛奶:假如小红能喝完数量为i+1瓶的牛奶,那么必然能喝完i瓶牛奶,具有单调性; 二分mid,表示小红能喝完mid瓶商店里的牛奶; 再使用贪心策略,从商店里选择mid瓶有效时间最长的牛奶,混入小红必须喝完的列表,然后排序;

总得复杂度O(logMNLogN); 但没想到tle了,因为N=106,加上logM和logN,复杂度要加220 * 2 = 400,大概有4 * 10^8的复杂度;

于是采用优化的方案,在二分完mid之后,不与小红已有的牛奶混合排序; 用two pointers 的方法进行判断。

5. From Y to Y

题目链接 题目大意: 有一个字符数组,长度为n;(全部是小写字母) 现在有一个操作:从数组中取出两个元素s和t,把字符s和t进行合并,得到新的字符串str,然后把str放入数组; 每次操作的代价是,对于所有字母x∈{a,b,c...z},字母x在两边s出现的次数的乘积的和; 比如说:aab+aab, 代价就是(22) + (11) = 5;

现在给出数字k,要求构造一个字符集合s,将s合并为一个字符串的最小代价刚好是k;

输入数据: 第一行,整数k (0 ≤ k ≤ 100 000)

Examples input 12 output abababab 样例解释: 对于字符集合 {'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'},其中一个最小代价的方案是: {"ab", "a", "b", "a", "b", "a", "b"},代价是0; {"aba", "b", "a", "b", "a", "b"}, 代价是1; {"abab", "a", "b", "a", "b"}, 代价是1; {"abab", "ab", "a", "b"}, 代价是0; {"abab", "aba", "b"}, 代价是1; {"abab", "abab"}, 代价是1; {"abababab"}, 代价是8; 总得的最小代价是12;

题目解析: 对于代价的计算,我们看简单的例子: aaaa的两种合并方式, 1、先(a,a)=aa, (a,a)=aa, 再(aa,aa)=aaaa; 2、先(a,a)=aa, 在(aa,a)=aaa, 再(aaa,a)=aaaa;

这两种的代价分别是1+1+4=6; 1+2+3=6; 容易知道,对于(aa,aa)的操作方式,我们可以看成是(aa,a) + (aa,a),然后根据定义,我们可以知道(aa,a)+(a,a)=(aaa,a); 其实合并方式1 和 合并方式2 是等价的;

再由定义,我们知道不同字母的代价计算是独立的;

对于一个字符集合s,其合并的最小代价∑x∈{a,b,c...z}, sum+=1+2+3+...+count(x-1);

这样可以得到一个快速的构造方案: 先尽可能填a,从1、2、3.... 直到不能再填,接着重复b的数量。

总结

这段时间忙完后,应该能有多余的时间,继续准备新的算法基础课程。 目前也在平衡一些职业上的选择,业余时间有限,是继续投在音视频方向,还是专注于当前的业务?

分享一些关于算法对学习和工作的帮助:在进行算法练习的时候,相当于把自己掌握的知识不断锤炼和组合出新的思路。 当我再学习新的一门技术的时候,我更倾向于先去掌握基础的知识,摸索基本的规律和原则,最后再尝试自己的一些组合与应用。期间不断优化自己对技术的积累与认知,最终通过较短的时间,可以深刻地理解技术。

而且在“爬过”华山之后,再去攀登小山峰的时候,会更加游刃有余。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏绿巨人专栏

函数式编程 : 一个程序猿进化的故事

3609
来自专栏数据之美

浮点数加法引发的问题:浮点数的二进制表示

1、问题: 之前有同学问过这样一个问题: echo|awk '{print 3.99 -1.19 -2.80}' 4.44089e-16 类似的问题还...

2239
来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

3177
来自专栏数说工作室

循环、分支...都可以在Python中用函数实现! | 函数式编程,打开另一个世界的大门

编程界有一位传奇人物——王垠,介绍一下他的退学经历,对,你没听错,退!学!经!历!: 2006年,从清华大学计算机系退学,在水木社区BLOG上发表了《清华梦的...

2886
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

第一篇:集合与推理方法 1:我们为什么要学习形式语言与自动机 任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们...

1.1K13
来自专栏数据结构与算法

P1538 迎春舞会之数字舞蹈

题目背景 HNSDFZ的同学们为了庆祝春节,准备排练一场舞会。 题目描述 在越来越讲究合作的时代,人们注意的更多的不是个人物的舞姿,而是集体的排列。 为了配合每...

2907
来自专栏落影的专栏

程序员进阶之算法练习(二十八)

前言 四道题,分别锻炼哈希、贪心、贪心+排序、二分四个能力。 第一题较为简单,后续的题目都需要一定的基础。 贪心是最基础的能力,codeforce有专门的 ...

4599
来自专栏ACM算法日常

leetcode 题解 | 121. 买卖股票的最佳时机

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

1263
来自专栏python3

python 面向对象之继承实例讲解

        --- info of Student:ChenRonghua ---

952
来自专栏desperate633

LeetCode 121. Best Time to Buy and Sell Stock题目Solution

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。 样例 给出一...

743

扫码关注云+社区

领取腾讯云代金券