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

前言

四道题,分别锻炼哈希、贪心、贪心+排序、二分四个能力。 第一题较为简单,后续的题目都需要一定的基础。 贪心是最基础的能力,codeforce有专门的 Tag用以描述,叫做greedy; 二分是常用的一种降低时间复杂度方法,前提的要求是单调性; 哈希和排序是工程中常见的处理,前者用于映射,后者用于数据有序化。 这四个能力也多用于面试的算法题,因为其属于基础能力。

正文

1.Santa Claus and Keyboard Check

题目链接 题目大意: 小明把键盘的键都卸下来清洗,在装回去后,发现有些键装错了。 他看着键盘,打出一个字符串str,在屏幕显示出来一个字符串str'; 现在他可以选择任意两个键,交换它们的位置,但是每个键只能交换一次;

问,小明是否能复原正确的键盘? 如果可以,先输出交换次数,接下来每行输出每次交换的字母;(顺序无关) 如果不可以,直接输出-1。

输入数据: str长度不超过1000;

Examples input helloworld ehoolwlroz output 3 h e l o d z input merrychristmas christmasmerry output -1

题目解析: 题目有个很重要的条件,每个键只能使用一次。 那么每次当遇到字符不同的时候,这两个字符就必须交换;如果这个字符已经交换过,那么无解。

实现逻辑,可以用一个简单字符hash来实现,对str的字符,每次先判断是有hash字符,如果有则转成hash后的符; 如果没有,添加hash[c]=c; 保证下次再遇到不会出错; 然后进行判断,如果hash后的字符和str'上的不对应,则无解;

2.Santa Claus and Robot

题目链接 题目大意: 有一个机器人,在一个网格的网格线上行走,每次有L/R/U/D四个方向; 当机器人从点p1走到点p2时,它会走最短的路径。 如果有3个点p1、p2、p3,机器人会按照最短的路径走向p1点,到达后再走向p2点,再到p3点; 现在假设机器人在原点,已知机器人走的序列(长度为n),求最少有几个点,可以满足机器人走的序列。

输入数据: n (1 ≤ n ≤ 2·105)

Examples input 6 RRULDD

output 2 input 26 RRRULURURUULULLLDLDDRDRDLD output 7

题目解析: 看似很难,仔细分析一下,只要找到两点之间路径的规律即可。 当出现过R之后,本次路径,就不允许再出现L,同理L、U、D; 这样,R、L之间算一条路径,U、D之间算一条路径,加起来就是需要的最小点数。

3.Santa Claus and a Palindrome

题目链接 题目大意: k个字符串,长度均为n; 每个字符串有一个权值a[i]; 现在可以从k个字符串中,选择若干个字符串拼成一个新的回文串str,要求每个字符串只能用一次,并且不能改变原有字符串的字符排列顺序; str的权值为所有拼成的串的权值和,求str的最大权值。 (注意,空串也是回文串,所有str的最大权值不小于0)

输入数据: 1 ≤ k, n ≤ 100 000; n·k  ≤ 100 000 - 10 000 ≤ a[i] ≤ 10 000

Examples input 7 3 abb 2 aaa -3 bba -1 zyz -4 abb 5 aaa 7 xyx 4 output 12 样例解释:最后的结果是abbaaaxyxaaabba,组合第5, 2, 7, 6 和 3字符串。

题目解析: 每个字符串分两种,第一种是自身为回文,第二种是自身不为回文。 自身为回文串有两种选择,放在中心点(单独一个)和不放在中心点(两两配对分在左右); 自身不为回文串的字符串str,可以和str的reverse组合回文串;(比如abc和cba) 我们把字符串相同的放到同一个桶,把桶按照字符串是否为回文分成两类。 对于非回文串str,每次从str的桶里找一个最大的key值x,再从reverse(str)的桶里找一个最大的key值y,只要x+y>0,那么就组成一个匹配; 对于回文串paliStr,每次从paliStr的桶里找key值最大的两个x和y,如果x+y>0,那么就组成一个匹配; 这里有个trick:因为paliStr还可以单独放在中间,如果paliStr的两个权值是-3和5,那么选中-3其实是不划算的。 但是如果只选择x>0&&y>0的话,假设有多个-3和5的组合,就会失去-3+5=2的额外收益。 抉择是根源是在于paliStr可以选择放在中间!但是中间其实只能有一个字符串。 于是可以采取额外补偿的方式,我们还是采用x+y>0的选择,但是保留一个addition的收益,类似-3和5的组合,addition的收益是3; 同理,如果只剩下一个回文串,那么addition的收益是该回文串。 最后计算所有的收益和+addition收益得到答案。

思考?: 更好理解addition的方式,是把组合看成单体的,比如说pair(-3, 5), pair(2, 3);把剩下的单个,也视为单体; 然后从所有的单体中选择一个,放入中间的收益。

4.Santa Claus and Tangerines

题目链接 题目大意: 给出n个数字a[i],要分给k个人; 数字a[i]可以平分,如果是奇数,那么会分成a[i]/2 和 a[i]/2 + 1; 每个人只能分得一个数字,问所有人中最小的数字的最大值是多少? 如果不够分,那么输出-1;

输入数据: n and k (1 ≤ n ≤ 1e6, 1 ≤ k ≤ 2·1e9) 1 ≤ a[i] ≤ 1e7

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

题目解析: 分出k个数,保证最小值尽可能大; 第一想法是二分答案,假设最后的结果是ans,对于数字x,while(x/2>=ans),对数字x进行平分; 假设num[x]表示数字x的数量,如果x/2>=ans,那么有num[x/2] += num[x], num[x - x/2] += num[x]; 最后再统计所有数字比ans大的数字数量,判断是否大于k; 复杂度为二分复杂度log(1e7) * 枚举平分复杂度(1e7) =24*1e7=2.4e8的复杂度; 因为题目给的时限为2s,勉强可以完成;

思考?: 另一种更优雅的方案。 以数字21为例,如果ans∈[11, 21]这一区间,>ans的数字只有一个; 如果ans=10时,就能算两个数字;(因为21可以拆分为10+11) 数字x,可以切分为数字较小的部分x/2和数字较大的部分(x-x/2),我们用a[x]来表示数字x的个数,b[x]表示当x拆分时(x-x/2)的数量; 当ans>(x-x/2)时,x的拆分没有额外收益; 当ans<=x/2时,x的拆分相当于多出来一个数字a[x/2]; 于是有: a[x/2] += a[x]+b[x]; b[x-x/2] += a[x]+b[x]; 核心代码很短,如下:

    for (lld i = maxAns; i > 0; --i) {
        total += a[i];
        if (total >= k) {
            cout << i << endl;
            return 0;
        }
        else {
            a[i / 2] += a[i] + b[i]; 
            b[i - i / 2] += a[i] + b[i];  
        }
    }

总结

基础能力在做一线开发的时候极为重要,往往决定了综合能力的天花板。 实际开发中的各种性能优化,功能系统的时间空间复杂度分析,都是基于基本的算法能力。 算法是编程能力提升的必要条件,做题只是学算法的一种实践手段。 而在业余时间越来越少的现在,做题占用的是我的娱乐时间和学习时间。如果一直停留在重复做类似题的境界,对我的能力提升微乎其微。 所以我现在在做的事情是尝试用规范的方式去解决、思考问题,然后把这个过程用文字描述出来。在保持思考习惯的同时,提升描述能力和锻炼耐力。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ACM算法日常

LIS的简单应用:UVA-437

上一次紫芝详细地介绍了动态规划中的经典问题LIS,今天我们抽出一个类似思想的简单题目进行实践练习。

10630
来自专栏数据库

用SQL高性能解决字符串的连续匹配

高性能解决有序集合的连续匹配问题 场景: A集合有8个元素:ali、boy、c、dog、e、f、g、h, B集合有5个元素:boy、c、dog、e、h 问B中...

20190
来自专栏Albert陈凯

MapReduce编程思想通俗理解

综述 Map(映射)与Reduce(化简)来源于LISP和其他函数式编程语言中的古老的映射和化简操作,MapReduce操作数据的最小单位是一个键值对。用户在使...

31880
来自专栏take time, save time

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

三、对于效率提高的初次尝试     对于最自然的几种排序算法,数学家们开始思考如何提高排序算法的效率,可以通过数学证明出来如果想达到这个目的,必须想办法将相距...

29270
来自专栏落影的专栏

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

前言 趁着8月还没结束,更新一篇算法练习。 正文 1. Alyona and mex 题目链接 题目大意: mex()定义:mex(arr)是 数组arr的...

42470
来自专栏一个会写诗的程序员的博客

用 Kotlin 的函数式编程 替代 GOF 设计模式用 Kotlin 的函数式编程 替代 GOF 设计模式函数式编程(FP)《Kotlin极简教程》正式上架:

"函数式编程", 又称泛函编程, 是一种"编程范式"(programming paradigm),也就是如何编写程序的方法论。它的基础是 λ 演算(lambda...

17140
来自专栏喔家ArchiSelf

IOT语义互操作性之本体论

这个系列文章描述了一个单一的语义数据模型来支持物联网和建筑、企业和消费者的数据转换。 这种模型必须简单可扩展, 以便能够在各行业领域之间实现插件化和互操作性。 ...

13450
来自专栏懒人开发

(6.4)James Stewart Calculus 5th Edition:Work

牛顿第二定律: F = ma (这里 dv = ds/dt, da=dv/dt) 于是有

11020
来自专栏chenjx85的技术专栏

leetcode-202-Happy Number

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

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

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

30970

扫码关注云+社区

领取腾讯云代金券