程序员进阶之算法练习(三十)附基础教程

前言

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

正文

1.k-th divisor

题目链接 题目大意: 给出一个数字n,求数字n所有因子中,第k大的数字; 如果没有输出-1;

输入数据: 两个数字 n and k (1 ≤ n ≤ 1e15, 1 ≤ k ≤ 1e9)

Examples input 4 2 output 2 input 5 3 output -1

题目解析: 假如n=x*y(x<y),那么x和y是n的因子,且有x <= sqrt(n); 那么只要枚举x=1~sqrt(n),y=n/x,这样可以得到n所有的因子; 再从因子中选择第k大的数字即可。

思考🤔: 小trick,n=9,x=3时,有y=3,但是x=y,所以只算一个因子;

2.USB vs. PS/2

题目链接 题目大意: 机房有三种电脑,一种只有USB接口,一种只有PS/2接口,一种是两种接口均有,数量分别为a、b、c; 现在机房希望给电脑配上鼠标,鼠标有两种,一种只支持USB,一种只支持PS/2; 鼠标有m个,每个仅能用于一台电脑,价格为val[i]; 现在希望能支持尽可能多的电脑,如果有多个选择,选择总价格最低的。

输入数据: 第一行 s a, b and c (0 ≤ a, b, c ≤ 1e5) 第二行 m (0 ≤ m ≤ 3·1e5) 接下来m行 每行 val[i] 和 鼠标支持类型 (1 ≤ val[i] ≤ 1e9) 输出: 最多能支持的电脑数量还有总价格;

Examples input 2 1 1 4 5 USB 6 PS/2 3 PS/2 7 PS/2 output 3 14

题目解析: 要求首先是支持的电脑数量最多,其次再是价格最低。 电脑与电脑之间的差别:电脑类型A(USB接口)和电脑类型B(PS/2接口)兼容性比电脑类型C(两种接口都支持)差,那么应该优先支持类型A、B; 鼠标与鼠标之间的差别:同类型的鼠标,价格低者应该优先使用,这样总价格会更低; 综合这两者的差异,可以得到一个贪心的策略: 对鼠标按价格排序,从价格小的开始选;在配电脑的时候,优先选择类型A/B,如果没有再选择类型C。

3. Two strings

题目链接 题目大意: 给出两个字符串a和b,现在从b中删去一个连续的子串,得到字符串b', 要求b'是a的子序列; 现在希望删除尽可能短的字符串,并 输出b'; (如果b'为空,输出'-')

输入数据: 两行字符串,分别是a和b; a和b的长度均小于1e5;

Examples input hi bob output - 样例解释:删除所有的字符,得到空串,输出-;

input abca accepted output ac 样例解释:删除子串cepted,得到b'=ac,是a的子序列;

题目解析: 删除必然是某个区间[l, r],先看最暴力的做法: 枚举[l, r]的可能性,得到新的字符串bNew,对a和bNew做一次匹配; 匹配的规则是对于bNew的每一个字符,都在原来基础上找最近的匹配,最后看bNew是否能在a中找到所有的字符匹配位置; 枚举区间是O(N^2),匹配是O(N),总的复杂度是O(N^3); 接下来看优化思路, 性质1:区间[l, r]如果满足题意,那么[l-1, r]或者[l, r+1]也会满足题意; 如果用动态规划,状态数有N^2,已经超过限制;(虽然动态规划的转移是整体O(N))

由性质1,这里可以引入一个二分:二分区间长度。 然后再枚举区间的起点,得到bNew,再进行一次匹配; 整体的复杂度是O(logN)的二分,O(N)的枚举区间起点,O(N)的单次匹配复杂度;

这里单次匹配可以优化: dp[i]表示字符串b,前i个字符匹配字符串a,的最短长度; dpR[i]表示reverse_b(字符串b的转置),前i个字符串匹配字符串reverse_a,的最短长度; 那么bNew=b减去区间[l, r]=[1,l-1] + [r+1, len] 只要dp[i]+dpR[j]<=lenA,那么就有解; 这样单次匹配的复杂度降到了O(1);

总体的复杂度是O(logN * N), 题目能接受的复杂度。

4.Timofey and a tree

题目链接 题目大意: 一棵树有n个点,序号是1~n,每个点有一个颜色值color[i]; 现在要求选择一个点,以这个点作为新的root根节点,要求其root根节点下,每颗子树内的颜色相同(子树与子树之间颜色可以不同); 如果可以则输出YES,然后再输出点序号; 如果不可以则单独输出NO。

输入数据: 第一行 n (2 ≤ n ≤ 1e5) 接下来n-1行,每行有两个数字(x,y),表示点x和y之间有一条边; 最后一行是颜色值 c1, c2, ..., cn (1 ≤ ci ≤ 1e5)

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

题目解析: 题目要求子树内颜色相同,那么对于边(u, v),如果u和v的颜色不同,那么有三种可能: 1、以u为根; 2、以v为根; 3、无解;

接下来的问题是,如何判断以u为根的情况是否满足题意? 以u为根,对每个子树进行一次dfs,判断是否子树的颜色相同,即可。

5.Ilya And The Tree

题目链接 题目大意: 有一颗根为1的树,共有n个点,每个点有一个权值a[i]; 我们定义一个点的魅力值为:点到根的路径上,所有点的最大公约数(gcd); 同时,我们可以选择修改一个点的权值为0;(gcd(0, m) = m) 问,每一个点的可能最大魅力值;

输入数据: 第一行,n (1 ≤ n ≤ 2e5) 第二行,a[i] (1 ≤ a[i] ≤ 2e5) 接下来n-1行,每行有两个数字(x,y),表示点x和y之间有一条边;

Examples input 3 6 2 3 1 2 1 3 output 6 6 6 样例解释: 输入:首先n; 接下来是n个数字a[i]; 然后n-1行,表示树的边; 输出:n个点可能的最大魅力值; 点1的最大魅力值是6(不做修改),点2的最大魅力值是6(修改点2的权值为0),点3的最大魅力值是6(修改点3的权值为0) 题目解析: 先重复下题目的定义:对于树上某个点u,其最大魅力值是点u到根上的所有数字的gcd; 对于点u,如果可以修改某个某个数字为0,那么相当于从点u到根上的所有数字中去掉一个数字,再求gcd; 问题简化成,在数组x[1]、x[2]、....x[k]中,去掉一个数字使得gcd最大。

如果不考虑复杂度,我们可以枚举去掉任意一个数字,再计算剩下的gcd,从中选择最大的数字; 对其思路进行优化,我们用d[i][0]表示前i个数字的gcd值,d[i][1]表示前i个数字去掉一个数字的最大gcd值; 于是有,d[1][0]=x[1], d[1][1]=0; d[i][0] = gcd(d[i-1][0], x[i]); d[i][1] = max(gcd(d[i-1][1], x[i]), d[i-1][0]); //如果前i个数字去掉的是x[i],那么gcd为d[i-1][0];如果去掉的数字不为x[i],那么结果为d[i-1][1]和x[i]的gcd值。

再回到树上的实现方案: 对每个点i维护一个数组d[i][2],在dfs过程不断更新数组即可。

总结

算法文集里有上百道各式各样的算法题,欢迎品尝。 本文题目源于Codeforces。 授人以鱼不如授人以渔,但是大多数人只需要鱼,并不要渔。 这里是鱼: 程序员算法基础——动态规划 程序员算法基础——贪心算法

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

讨厌算法的程序员 2 | 证明算法的正确性

第1篇介绍了插入排序算法,这里要提出一个问题:学习算法仅仅是积累一个又一个的算法实现吗? 当然不是。比算法本身更重要也更基础的,是对算法的分析:能够证明其正确性...

3475

与机器学习算法有关的数据结构

可能你对经常使用的统计分类包中的功能不满足你的需求而感到不爽,或者你已经有了一个新的数据处理方法。所以,你决定改动现有封装好的算法,开始编写你自己的机器学习方法...

2577
来自专栏Python小屋

Python版组合数计算方法优化思路和源码

总体说明:本文的优化思路并不局限于Python,但C、C++、C#、Java等语言无法使用内置类型直接表示大整数,需要通过数组等特定形式并自己实现大整数乘除法才...

3515
来自专栏专知

【专知-关关的刷题日记17】Leetcode 268. Missing Number

题目 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find...

34512
来自专栏游戏杂谈

IEEE 754二进制浮点数算术标准

纳尼,不应该是0.1么,怎么变成0.09999999999999998呢?这就要从ECMAScript标准讲起了。

602
来自专栏落影的专栏

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

前言 有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做le...

3665
来自专栏aCloudDeveloper

算法导论第九章中位数和顺序统计量(选择问题)

  本章如果要归结成一个问题的话,可以归结为选择问题,比如要从一堆数中选择最大的数,或最小的数,或第几小/大的数等, 这样的问题看似很简单,似乎没有什么可研究的...

2727
来自专栏LinkedBear的个人空间

【挑战剑指offer】系列01:二维数组的查找

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

944
来自专栏CDA数据分析师

开工大吉:几个让你月薪3万+的excel神技能

来源:运营圈信息流广告 职场中经常会用到哪些函数? IF函数、SUMIF函数、VLOOKUP函数、SUMPRODUCT函数...... 小编总结了8个在工作中常...

3766
来自专栏自然语言处理

程序员眼中的统计学5

定义:若具有性质A的事件有m个,具有性质B的事件有n个,则具有性质A或性质B的事件有m+n个。

753

扫码关注云+社区