专栏首页落影的专栏程序员进阶之算法练习(十八)

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

前言

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

正文

A. Bus to Udayland 题目链接 题目大意: 输入n行字符,每行5个字符; 表示公交车上n排位置,X表示有人,O表示空位,|是过道。 问是否能找到两个连续的空位; 如果可以,输出"YES",并且空位改为++后输出; 如果没有输出"NO"; n (1 ≤ n ≤ 1000)

Example

input

5 XX|XX XX|XX XO|OX XO|OO OX|XO

output

YES XX|XX XX|XX XO|OX XO|++ OX|XO

** 题目解析:** 只有两种情况,前两个或者最后两个。 分情况讨论即可。

B. Chris and Magic Square 题目链接:http://codeforces.com/contest/711/problem/B 题目大意: 输入一个n*n的数组矩阵,在数字为0的位置填入一个正数(只有一个位置为0),让矩阵的行列对角线和相同。 如果没有答案输出-1; 如果答案,输出完整的矩形。 n (1 ≤ n ≤ 500)

Example

input

3 4 0 2 3 5 7 8 1 6

output

9

input

4 1 1 1 1 1 1 0 1 1 1 2 1 1 1 1 1

output

-1

** 题目解析:** 看似很难,但是因为只有一个位置为0,题目简化许多。 我们假设存在答案,那么可以: 根据上一行和当前行的差值,可以计算出0应该填的数字。 再判断一下结果是否符合即可。

C. Coloring Trees 题目链接 题目大意: 有n棵树排成一行,m种颜料(数字1~m); 输入n个数字,表示n棵树当前的颜色(0为uncolor,其他为当前的颜色); 树的排列顺序有一个魅力值, 连续的相同颜色值算1点魅力值,例如: 树的颜色排列为 [2, 1, 1, 1, 3, 2, 2, 3, 1, 3],其魅力值为7,分别如下: {2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}

如果树的颜色是uncolor,代表可以染色; 输入n*m个数字,表示第i颗树染色成第j种颜色的代价cost[i][j];

问,如果要把树的魅力值变为k,需要的最小代价是多少?(如果无解,输出-1)

n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100)

Example

input

3 2 2 0 0 0 1 2 3 4 5 6

output

10

input

3 2 2 2 1 2 1 3 2 4 3 5

output

-1

** 题目解析:** 从给出的数据范围来看,容许时间复杂度比较大的做法。 从给出的选择来看,每次的抉择只有uncolor的树,假设要染色的树是i,大概的类别有: 1、color[i-1] != color[i+1],这时color[i]可以等于color[i-1]或者color[i+1],或者都不相同; 2、color[i-1] == color[i+1],这时color[i]可以等于color[i-1]和color[i+1],或者都不相同; 因为题目要求的是特定的魅力值,故而不能用贪心的做法。 考虑用动态规划来做, dp[i][j[k] 表示前i个,color为j,最后一个为颜色k的最小代价; 对于第i颗树,color为j的状态,考虑以下的状态: 1、color[i] != 0,不能染色,那么j=color[i]的状态,可以通过dp[i-1]的状态中获得最小代价; 1、color[i] != 0,不能染色,那么j!=color[i]的状态,不合法,忽略; 1、color[i] == 0,能染色,那么枚举j的状态,从dp[i-1]转移即可。 具体的转移方程较多,可以见代码。

** 思考?: 如果把k去掉,改成最大值,是一道不错的面试题。**

** D. Directed Roads** 题目链接 ** 题目大意:** 给出n个点,每个点有一条从其出发的有向边; 现在选择一个边的集合,对集合的每条边进行一个翻转的操作; 要求:让n个点没有形成环。 问有多少种集合可能,结果对MOD取余。 n (2 ≤ n ≤ 2·1e5) MOD = 1e9 + 7.

Example

input

3 2 3 1

output

6

input

4 2 1 1 1

output

8

题目解析: 注意重点:每个点初始状态只有一条有向边,那么每个环都是简单的环(没有重叠的环)。 那么把所有的点分成两种,环上的点,环外的点。 不在环上的点有k个,那么有2^k个选择。 第i个环的数量为num[i],有2^num[i] - 2个选择。(全选和全不选是不行的) 结果之乘积就是答案。

总结

不知道你们有没有这样一种感觉,当你换到一个新的环境,接触到很多新的知识之后,本能地开始排斥这些新的内容。 表现出来的行为就是焦虑,觉得很多事情未完成,但是仍然注意力不集中。 明知道这些知识很重要,但是就不愿意去学,觉得这个东西很难且以后也很少用到。 这种焦虑就是人与人的价值观区别,甚至有的人会抱着好奇心的态度去接受这种新知识。 不去评判价值观的好坏,但如果能怀着好奇的心态迎接新的生活,总归会过的轻松点。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    前言 坚持做算法练习对开发的好处是抽象能力变强,拿到一个需求能很快对其进行抽象,然后再用学过的设计模式相关知识进行整理,最后用代码实现。 最大的好处在于:对...

    落影
  • 程序员进阶之算法练习(十六)

    前言 正文6道题目来自leetcode––为求职为生的编程网站,目的是工作闲暇之时锤炼代码功底。 没有捷径,但手熟尔; 一步领先,步步领先。 正文 5. L...

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

    前言 这周很忙,但是越忙的时候反而越喜欢抽空做算法题。 欢迎关注algorithm文集。 这次A、B、C都是很合适的面试题。 正文 A. Memory ...

    落影
  • 环形布局CircleLayout效果图用法链接

    1.可以直接在布局文件中进行布局,类似LinearLayout,但是这里不需要关心布局方式,会自动将布局中的所有子view均匀分布到中心点四周,这里你可以设置自...

    坑吭吭
  • new 原理及模拟实现

    注意点 ES6新增 symbol 类型,不可以使用 new Symbol(),因为 symbol 是基本数据类型,每个从Symbol()返回的 symbol ...

    grain先森
  • 开源 | CVPR2020 端到端的ZSL训练模型,用于视频分类任务

    经过大型数据集的训练,深度学习(DL)可以准确地将视频分类为数百个不同的类。但是,对视频数据进行标注的代价非常高。为此Zero-shot learning (Z...

    CNNer
  • 微信小程序向左滑动删除操作(类仿微信、QQ)

    上一个小程序的项目里面做过这个功能,当时没有记录下来,今天特意做了一个小的demo放在了github上面,下次在开发中遇到的话就可以直接拿下来代码复用了。效果很...

    王小婷
  • Android-布局优化merge, viewStub, include总结

    多层布局的嵌套会导致页面加载慢,影响用户的体验,今天我们就来学学如何使用 include,merge及viewStub。

    android_薛之涛
  • Android编程实现图片的颜色处理功能示例

    本文实例讲述了Android编程实现图片的颜色处理功能。分享给大家供大家参考,具体如下:

    砸漏
  • 直接可用的Android studio学生信息管理系统

    网上流传最广的版本有所欠缺,并不能直接使用,同时有很多不必要的功能,这是我进行删减、修改、核查后的版本,根据下面的步骤一步步来直接能够运行程序。

    砸漏

扫码关注云+社区

领取腾讯云代金券