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

前言

这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集

这次A、B、C都是很合适的面试题。

正文

A. Memory and Crow 题目链接 题目大意: 给出n个数字。(a[1], a[2], ..., a[n]) a[i]和b[i]的关系如下。 a[i] = b[i] - b[i+1] + b[i+2] - b[i+3].... 给出数组a[i],求数组b[i]。 n (2 ≤ n ≤ 100 000) a[i] ( - 1e9 ≤ a[i] ≤ 1e9)

** Examples** ** input** 5 6 -4 8 -2 3 ** output** 2 4 6 1 3 ** input** 5 3 -2 -1 5 6 output 1 -3 4 11 6

题目解析: 根据通项公式,知道b[n] = a[n];(因为不能存在b[n+1]) 然后倒着求b[i], b[i] = a[i] + a[i+1];

B. Memory and Trident 题目链接 ** 题目大意:** 输入一个字符串s,由 'L', 'R', 'U', or 'D'组成,分别表示点P在原点的向左、右、上、下前进一步。 修改字符串的序列,每次操作能修改一个字符为其他字符(L/R/U/D),问点P按照字符串s移动后能回到原点的最小操作次数; 如果可以,输出做小操作次数; 如果不能,则输出-1;

** Examples** ** input** RRU ** output** -1 ** input** UDUR ** output** 1

** 题目解析:** 先考虑不能情况。 如果字符串的长度为奇数,那么必然不能回到原点。 如果字符串的长度为偶数,那么必然有解。(最多把所有的字符串变成UDUD) 然后分开考虑,L 和 R 相对, U 和 D 相对。 求出在x方向和y方向的需要修改的字符数量。 容易知道我们可以把需要修改的数量加起来,然后除以2可以得到修改的次数。(两个方向的需要修改数量,必然为偶数)

C. Memory and De-Evolution 题目链接 题目大意: 有两个正三角形,边长分别为x,y。 现在可以对三角形进行操作,每次操作可以改变三角形的一条边长度(为整数),变成另外一个三角形。 问让正三角形x 变成 正三角形y 的最小操作次数。 x and y (3 ≤ y < x ≤ 100 000)

** Examples** ** input** 6 3 ** output** 4 样例解释:666 -> 663 -> 643 -> 343 -> 333 总共需要操作4次

** 题目解析:** 三角形的性质:两边之和大于第三边。 反过来考虑,把三角形y变成三角形x。(操作步数是一致的) 那么自然可以想到一种贪心:每次把最小的边变得最大。 每次操作完排序,再对最小的进行变大。 直到最小的边也等于x。

D. Memory and Scores 题目链接 ** 题目大意:** A 和 B玩一个游戏,游戏分成t轮。 初始时,A和B的分数为a和b; 每轮游戏,A和B都可以从[-k, k]的区间里面选择一个整数加到自己的分数; 问最后有多少种可能,A的分数大于B的分数。 (只要某一轮A或者B的分数不同,即视为不同的可能)

a, b, k, and t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100) 结果mod 1 000 000 007 (1e9 + 7)。

Example ** input** 1 2 2 1 ** output** 6 ** 样例解释:** In the first sample test, A starts with 1 and B starts with 2. If B picks  - 2, A can pick 0, 1, or 2 to win. If B picks  - 1, A can pick 1 or 2 to win. If B picks 0, A can pick 2 to win. If B picks 1 or 2, A cannot win. Thus, there are 3 + 2 + 1 = 6 possible games in which A wins.

** 题目解析:** 容易知道,每次的选择都是[-k, k],那么总共就有(2k + 1)个选择; t轮之后就是(2k+1)^t个选择。 接下来考虑去重,存在一轮分数不同,即是在第i轮的时候,选择不同的数字。 那么,我们用dp[i][j]来表示 前i轮,分数等于j的选择个数。 这样就可以统计出t轮之后,分数为j的不同选择个数。 先是对A dp出t次后的结果,再对B dp出t次后的结果。这两个都是O(NK^2)。 最后再对dpB[n][j] 统计下所有∑dpA[n][c],c > j,然后相乘,得到B为j的时候,A赢的选择数。 最后累加j = [-k * k / 2, k * k / 2]的和即可。

** 小技巧:** 1、为了方便计算,把所有的状态都加上一个offset,这样-k*k/2 就变成正数,避免dp过程中访问到下标是负的情况; 2、为了状态转移更快,dpA[i][j] 可以存分数为1到j的和,这样分数为j的值可以通过dpA[i][j] - dpA[i][j - 1]求出。

总结

趁着写文章,回顾下这四个题目,发现A/B/C对于我来说都是很简单题目,D需要一些思考和细节的考虑,算中等题。 但是对某些牛,可能他做D的难度就和我做前三个的难度差不多。 差距是哪里?? 1、角度,大牛思考更全面,能用最适当的思路去解决问题; 2、熟练度,像offset、mod、累加这些trick大牛一眼就看穿并且熟练地实现; 3、复杂度,大牛经常面对很多更复杂的情况,再回过来处理这些题目就更为容易; 或许还有其他原因,但是就这三点就值得深思。 如果是要做题目,应该先看到出题人的思路,顺着这个方向查看设置的trick,在有具体的解法后要完善好细节再实现; 如果是工作开发,则是要理解产品的需求,从用户的角度观察未来可能的变化,在设计好具体的解决方案后,再进行开发; 三思而后行,这是非常难以坚持的要求。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

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

前言 我认为的编程能力: 基础知识:数据库、操作系统、网络原理等; 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)等;...

45410
来自专栏aCloudDeveloper

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

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

3317
来自专栏落影的专栏

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

前言 最近在接触新知识,也是选择2017年的方向。 其他文集更新会放缓,没有学习就没有心得,肚中无墨就无从下笔。 但是算法练习还是挺好玩的,欢迎关注algo...

3515
来自专栏程序员叨叨叨

6.3 数学操作符(Math Operators)

Cg语言对向量的数学操作提供了内置的支持,Cg中的数学操作符有:*乘法、/除法、-取反、+加法、—减法、%求余、++、——、*=、/=、+=、-=。后面四种运算...

851
来自专栏杨建荣的学习笔记

使用贪心算法解决集合覆盖问题

有的同学可能对这些州没概念,这个简称就跟京代表北京,鲁代表山东,甘代表甘肃一样,细细一看,都是西部的一些州。

1352
来自专栏Python小屋

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

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

4335
来自专栏深度学习计算机视觉

算法基础+分治策略(算法复习第1弹)

马上就要算法考试了,好紧张,先复习第一波.... 参考文献(算法导论)+(张莉老师ppt) ---- 函数的增长,对算法效率的描述 渐进记号:Θ、Ω、O、o、...

3287
来自专栏小樱的经验随笔

单表代替密码原理及算法实现

    要了解单表替代密码就得先了解替代密码,在这里我就做一下简单的介绍:       替代是古典密码中用到的最基本的处理技巧之一 。       替代密码是指...

5456
来自专栏我是攻城师

理解算法的复杂度

在计算机科学中,算法的时间复杂度是一个函数,它定性描述该算法的运行时间,时间复杂度常用大O符号表示,不包括这个函数的低阶和首项系数,使用这种方式时,时间的复杂度...

1912
来自专栏灯塔大数据

每周学点大数据 | No.13 Misra Gries算法

No.13期 Misra Gries算法 Mr. 王:嗯,所以我们提出如下的方法: (1)处理一个新到来的元素x时 (2)If已经为其分配计数器,增加之 (3...

4116

扫码关注云+社区

领取腾讯云代金券