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

前言

我认为的编程能力:

  • 基础知识:数据库、操作系统、网络原理等;
  • 编码能力:软件架构(MVVM、MVP)、设计模式、编程语言(C、JAVA、C++)等;
  • 思考能力:分析需求、算法设计、数学基础等;

其中非常重要的一个就是算法。 一个算法浓缩了程序员对一个问题的解读、分析、思考、推论、实现。 工作之后遇到的所有问题,难度都不如之前遇到过的算法题目。 那么,这些问题也会被我迎刃而解。

看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。 文集: 程序员进阶之算法练习(一) 程序员进阶之算法练习(二) 程序员进阶之算法练习(三) 本篇因为篇幅,不贴代码实现。

A

题目链接 题目大意:输入三个整数t, s, x。问输入的整数x等于 t, t + s, t + s + 1, t + 2s, t + 2s + 1... 中的一个。 代码实现 题目解析: 分类讨论 偏移量:ret = x - t。 如果 ret < s, 只有 ret = 0; 如果 ret >= s, 满足 ret % s = 0或者1 即可。

是否觉得题目过于简单?

B

题目链接 题目大意:输入一个科学计数法的数字,输出一个十进制计数的数字。 比如 输入8.549e2,输出854.9; 输入8.549e3,输出8549; 代码实现 题目解析: 科学计数法的e,如果不为零,那么会对小数点的位置造成影响,比如:整数部分存在前导零、小数部分全部为零、整数小数部分全部为零的情况; 对着多种情况进行分类讨论即可。

有另外一种的方式,scanf("%[^e]%ne%d",d,&l,&b);,利用scanf直接读取整数部分、小数部分的值,然后分类讨论。 可能这个才是正解。

C

题目链接 题目大意:在自然数中,数i到数2i存在一条边,数i到数2i+1存在一条边。

输入有两类型: 1、在u到v的最短路径上每条边的费用都加w; 2、求u到v的最短距离; 当输入为类型2的时候,输出u到v的最短距离。

代码实现 题目解析: 对于每个自然数i,会和比自己小的自然数构成一条边,比自己大的自然数构成两边条,那么可以把边的费用存在中较大数。 对于u到v的最短路径,必然存在的k,路径为(u, k) + (k, v),k=lca(u,v)。(lca是最近公共祖先) 在此题目中,每次对u、v中的较大值/2,即可得到lca(u, v)。

D

题目链接 题目大意:n个点形成一棵树,根节点为1。以1为起点,对树进行dfs遍历,current_time为访问到的时间。 求每个点的current_time期望值。 样例输入: 7 1 2 1 1 4 4 样例输出: 1.0 4.0 5.0 3.5 4.5 5.0 5.0

样例输入: 12 1 1 2 2 4 4 3 3 1 10 8 样例输出: 1.0 5.0 5.5 6.5 7.5 8.0 8.0 7.0 7.5 6.5 7.5 8.0 DFS算法实现

let starting_time be an array of length n
current_time = 0
dfs(v):
   current_time = current_time + 1
   starting_time[v] = current_time
   shuffle children[v] randomly (each permutation with equal possibility)
   // children[v] is vector of children cities of city v
   for u in children[v]:
dfs(u)

代码实现 题目解析: 对于点u有的若干个子节点,有: 如果v是u的子节点,那么starting_time[v] = 所有其他子树的和/2 + starting_time[u] + 1。 推论: 如果u只有一个子树,那么starting_time[v] = starting_time[u] + 1; 如果u有多个子树,如果先遍历其他子树,再遍历v所在子树,starting_time会加上其他子树的节点和; 由题目可知,遍历是随机的,那么相对子树v,先遍历某个子树的概率为1/2;

(如果难以理解,可以枚举abc、abcd的全排列,b在a前面的概率为1/2。

E

题目链接 题目大意:有三个一模一样盒子从左到右排列。中间的盒子有一个特殊物品,每次操作随机选择左右两边的盒子和中间交换。 问n次操作后,中间盒子有特殊物品的概率。答案按照最简分数化简后,分子分母再mod值10E9+7。

代码实现 题目解析: 给盒子编号1、2、3,那么盒子的排列有: 123、132、213、231、312、321;其中123、321是中间有特殊物品。 假设d[i][j]是第i次操作后,盒子排列为j的次数。 d[i][123] = d[i-1][213] + d[i-1][132]; d[i][321] = d[i-1][231] + d[i-1][312]; d[i][123] + d[i][132] + d[i][213] + d[i][231] + d[i][312] + d[i][321] = 2 ^ i。(每次操作产生2种可能)

令f[i] = d[i][123] + d[i][321]。 f[i] = d[i-1][213] + d[i-1][132] + d[i-1][231] + d[i-1][312] = 2 ^ (i - 1) - d[i-1][123] - d[i-1][321] = 2 ^ (i - 1) -f[i-1]. 其中f[0] = 1;

当i=2k的时候,f[2k] = 2^(2k-1) - 2^(2k-2) + 2^(2k-3) ... + 2^1 - 2^0 + 1; f[2k+1] = 2^(2k) - 2^(2k-1) + 2^(2k-2) ... - 2^1 + 2^0 - 1; 等比数列求和,化简后有: f[2k] = (2^(2k)+2)/3; f[2k+1] = (2^(2k+1)-2)/3;

最终的答案为: ans = f[n] / 2^n. 当n=2k的时候,ans = f[2k] / 2^(2k) = (2(2k-1)+1)/(2(2k-1)*3); 当n=2k+1的时候,ans = f[2k+1] / 2^(2k+1) = (2(2k)-1)/(2(2k)*3);

ans = x / y; 统一下,当n为奇数,x = (2^(n-1)+1) / 3, y = 2^(n-1); 当n为偶数, y = (2^(n-1)-1) / 3, y = 2^(n-1);

性质:如p是质数,且gcd(a,m)=1,那么 a^(m-1)≡1(mod m)。 (费马小定理) 推论:(a/b) % m = (a/b * 1) % m = (a/b * b^(m-1)) % m = (a * b^(m-2)) % m = a%m * b^(m-2)%m

2^(n-1) % m = (2^n / 2) % m = 2^n % m * 2^(m-2)%m

备注:感谢胡浩大神提供最后推论的思路。

总结

有思考,才会有收获。多次的苦思冥想,最后解决问题的那一刻,很刺激。 E题推论出公式很快,最后在化简卡住了很久,演算了多张草稿纸都没有思路,最后猜测应该是数论的知识,询问了数学系的一个朋友,最后得到了费马小定理可以用来化简分数的mod。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

34570
来自专栏java一日一条

编程面试过程中常见的10大算法

以下是在编程面试中排名前10的算法相关的概念,我会通过一些简单的例子来阐述这些概念。由于完全掌握这些概念需要更多的努力,因此这份列表只是作为一个介绍。本文将从J...

12220
来自专栏数据派THU

一文解读Tensor到底是个啥玩意儿?(附代码)

本文介绍了各种数值型数据的容器(标量、向量、矩阵、张量)之间的关系,在实践中,张量特指3维及更高维度的数据容器。

15830
来自专栏一个爱吃西瓜的程序员

每天学习一点儿算法--二分查找

算法是什么? 算法就是完成一组特定任务的方法。 比如将大象放进冰箱需要三步: 打开冰箱 将大象放进冰箱 关闭冰箱 这就是一种算法。 如果用计算机语言来叙述...

34260
来自专栏IT可乐

Java数据结构和算法(一)——简介

  本系列博客我们将学习数据结构和算法,为什么要学习数据结构和算法,这里我举个简单的例子。   编程好比是一辆汽车,而数据结构和算法是汽车内部的变速箱。一个开车...

34090
来自专栏zaking's

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

24230
来自专栏程序员叨叨叨

6.3 数学操作符(Math Operators)

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

9510
来自专栏我是攻城师

理解算法的复杂度

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

24020
来自专栏后端技术探索

两道腾讯技术面试题(二面经历)

编程语言不限,主要考查两方面能力:1.算法逻辑能力。2.编码能力。笔者上次换工作,面试了十余家公司,其实很多关于算法逻辑的面试题都大同小异,每遇到一道题目就吃透...

11920
来自专栏Python小屋

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

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

49550

扫码关注云+社区

领取腾讯云代金券