Google Kickstart 2017 Round F,当时做了两条就睡觉了,早上把剩下两条也过了。感觉不算是很难,可能也和这场限时24h有关吧。不过提交的时候倒是手忙脚乱,第一条交了三发,第一发是从VS迁移到DevC上是DevC由于之前配了个C++14所以崩了,第二发输出里面是Unicode BOM,WA了,蛋疼。
记忆化搜索和动态规划
记忆化搜索和动态规划常常是两种成对出现的解法。
POJ 2096 Collecting Bugs 概率DP
题意:一次找一个bug,问所有的bug能覆盖n中类型和s个子系统,需要找的次数的期望是多少。
HDU 2089 不要62 数位DP
这条题目是典型的求[L, R]区间内满足某性质的整数的数目问题,通常解法是用[0, R]区间的数目减去[0, L-1]区间的数目。数位DP是此类问题常见的解题思路。
分布式一致性详解
分布式一致性和分布式共识协议
随着请求量的增大,为了高可用和容错,常常采用维护多个冗余副本的办法来实现,因此需要维护这些副本之间的一致性。
随着数据量的增大,单个节点难以承载所有数据,分布式系统还会将数据进行分区,如何维护分区间事务是一个问题。
分布式集群搭建在网络上,而网络通信是复杂的,数据包的丢失、重复、乱序需要被妥善处理,此外节点宕机或者网络分区的情况也需要被考虑。CAP 理论认为一致性、可用性和分区容错不可能同时做到。
分布式系统中常出现以下的一些应用场景:分布式锁、负载均衡、发布订阅模型、选举、分布式队列。
本篇文章以 DDIA 以及作者的讲解视频为骨架,辅以业界的相关实现,来综述性探讨上述的一些问题。本文中的一些理论性问题被迁移到专题文章中。
数据库系统中的事务
黄山游记
黄山之行屡屡被耽搁,终于在第四次勉强成行。
Manacher算法
我们知道优化非启发性算法的方法常常包括使用定理、利用计算机的架构特点、使用恰当的数据结构以及动态规划等。而动态规划的核心理念就是减少重复计算。
对于回文串问题的Manacher算法来说,我们要重用0..(i-1)
的结果,那怎么重用呢?假设i
和j
关于p
(i > p > j
)对称,那么R[i]
便可通过R[j]
求得。
计算最长回文串的暴力算法是O(n^2)
,而马拉车算法能够在O(n)
时间内解决问题。
不动点组合子Y-Combinator
不管怎样,可以把 lambda 当做一个匿名函数来看待,那么这个匿名函数如何在递归调用的时候引用自己呢?Haskell B. Curry给出了Y不动点组合子(Y Combinator,当然不是那个著名的公司啦)可以解决这个问题。在本文中:
- 基于 Haskell 如何在匿名函数中调用自己
- 在其他语言中,如何解决 Lazy Evaluation 的问题
- 自定义的 fix 中,如何避免递归调用 fix
- 基于 Python 的 Demo
- Python 如何在匿名函数中调用自己
- Python 中的 Y Combinator
- Z Combinator
- 基于 C++ 的 Demo
- 为什么通过找不动点可以解决自我调用的问题
- 什么是不动点
- 不动点和本问题的联系
- 简单的 lambda 演算
- 证明 Y-Combinator 的性质
Y f = f (Y f)
讨论 Y-Combinator 的类型