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

前言

有朋友推荐一个新的算法练习网站leetcode,说北美的公司招人都是400题起步,国内公司招聘也经常用到,上海的尤其多。 很有意思,可以花点时间做做leetcode,看看题目质量。 这次更新的仍然是CodeForces的Contest710

正文

A

题目链接 题目大意 一个8*8的棋盘,输入一个点表示国际象棋中的king的位置,求king能行动的格子数量;

输入两个字符,表示列和行。 列是'a'到'h',行是1到8。

Example

input

e4

output

8

题目解析 题目较简单,看如何实现比较方便。 列-'a'得到索引x; 行-'1'得到索引y; 特判当king在边界的时候和同时在两个边界的时候。

B

题目链接 题目大意 输入n个x轴上的点,输出和n个点距离最近的点,如果有多个点,输出最左边的那个点。 n (1 ≤ n ≤ 3 * 1e5) x[i] ( - 1e9 ≤ x[i] ≤ 1e9)

Example

input

4 1 2 3 4

output

2

** 题目解析** 对点排序,易知最后的点在最中间。

对于在[A, B]中的点x,易知x到A和B的距离是固定; 那么对于[A, B, C]的最优解,必然是在B; 同上,在[A,B,C,D]中,点x到A和D的距离是固定的,同时与x到[B, C]的最优解的重叠。 类推,得到答案就是排序完最中间靠左边的点。

C

题目链接 题目大意 输入一个奇数n,输出一个n*n的矩阵,矩阵内数字从1到n*n。 矩阵的要求是行、列、对角线的和都是奇数。 n (1 ≤ n ≤ 49)

Examples

input

1

output

1

input

3

output

2 1 4 3 5 7 6 9 8

题目解析 我们把1到n*n的数字抽象成0,1.(根据奇偶性) 我们来看 n=3的时候 010 111 010

问题是当n=5的时候,如何构造? 已知,n=3的矩阵,那么只要保证n=3外面的矩阵行列和都是偶数就行。 1 010 1

0 010 0 1 111 1 0 010 0

1 010 1

那么题目可以变成这样一圈圈的去构造; 并且为了方便,从中心开始构造最为简单。

E

题目链接 题目大意 构造n个'a'字符,x为insert/delete 'a'一次的代价,y为复制粘贴一次的代价。 n, x and y (1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109).

Examples

input

8 1 1

output

4

input

8 1 10

output

8

题目解析: 动态规划。 dp[i] 表示构造i个字符的最优解。 对应三种可能,三个状态转移。 dp[i] = min(dp[i], dp[i + 1] + x); 删除 dp[i + 1] = min(dp[i + 1], dp[i] + x); 增加 dp[i * 2] = min(dp[i * 2], dp[i] + y); 双倍

1 2 4 8 16 13 26 52 删除3次,double 6次 1 2 4 6 12 13 25 52 增加3次,double 6次

F

题目链接 题目大意 m个操作。 操作1,把一个字符串s放入集合D,每次插入不同; 操作2,把一个字符串s从集合D删除,保证有值; 操作3,询问一个字符串x在集合中子串的数量。 m (1 ≤ m ≤ 3·1e5)

Examples

input

5 1 abc 3 abcabc 2 abc 1 aba 3 abababc

output

2 2

题目解析: 题目有一个很重要的性质:每次插入不同。 于是可以插入建一个自动机,删除建一个自动机,相减即可。

查找函数再引入一个dp值,如果访问一次,就记录当前值。这样每个点就只访问一次 build函数,dp值=-1 比较关键 这里的字典树要引入一个flag来标志是否真的有孩子。(build之后,及时字典树没有孩子,ch指针也会指向fail指针)死循环了几次 插入和更新,在引入一个flag,有更新之后再重新build

如果题目数据更强:(队友提供的神优化) 再引入logN的优化,建logN个自动机,分别存放1、2、4、8等个自动机。

总结

A、B是简单题,C是构(脑)造(洞)题,E是动态规划,F是AC自动机。 新年快乐~

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python小屋

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

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

45450
来自专栏专知

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

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

358120
来自专栏用户2442861的专栏

动态规划算法学习

http://blog.csdn.net/nevasun/article/details/6977511

17240
来自专栏TechBox

数据结构与算法系列之时间复杂度前言时间复杂度算法的空间复杂度

13530
来自专栏aCloudDeveloper

LeetCode:152_Maximum Product Subarray | 最大乘积连续子数组 | Medium

题目:Maximum Product Subarray Find the contiguous subarray within an array (contai...

21190
来自专栏云霄雨霁

离散数学中集合上二元关系的判定及实现

52200
来自专栏落影的专栏

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

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

25130
来自专栏自然语言处理

程序员眼中的统计学5

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

9030
来自专栏zaking's

js算法初窥05(算法模式02-动态规划与贪心算法)

22530
来自专栏逸鹏说道

码农眼中的数学之~数学基础

1维直线、2维平面(长宽)、3维空间(长宽高 | xyz轴)、4维时空(xyz轴+时间轴)

13430

扫码关注云+社区

领取腾讯云代金券