LeetCode 组队刷题活动

组队刷 LeetCode

介绍

代码仓库

 代码仓库的坐标:asdf2014 / algorithm

报名途径

 只需要在《Algorithm》文末留言,即可随时参与

留言内容的话,至少要留一下自己的 Github 名称,方便我们这边统计汇总。另外,也可以说明下自己能接受的刷题频率、希望的选题策略,亦或者,对算法知识沉淀的模式有好的建议,都可以提出

参与方式

 每位参与的小伙伴,都会获得代码仓库的 Collaborator 权限,可以自由地提交代码(不限制语种)。在 /Codes/${User} 目录下,每人都将拥有一个自己的代码库。留下 Github 名称后,将很快会收到邀请函,大家可以在 asdf2014 - algorithm - invitations 链接中认领。随后,可以在任意目录下(不需要是空目录),使用如下命令,一键完成您的第一次代码提交:

1
bash -c "$(curl -L https://raw.githubusercontent.com/asdf2014/algorithm/master/first_commit.sh)"

刷题频率

 考虑到可能大家的闲暇时间并不多,我们暂定刷题频率为“一周一题”

选题策略

 分为两个阶段:

  • 前 100 题都是经典中的经典,所以我们第一阶段先将这些题目吃透
  • 第二阶段,通过程序进行随机选定,历史题库可以点击链接看到

其他

 操作 Git 时遇到问题的话,可以参考我的一篇博客《Git 高级玩法

也可以直接在文章最后留言。目前,支持 Gitalk + Disqus 两种留言系统,以便更好地服务于国内和海外的小伙伴

 同时,为了大家更加方便地交流,也欢迎加入算法 QQ 群 或者 Gitter 聊天室

但是,请不要在评论区讨论入群问题的答案,避免打广告的进入

 另外,因为大部分算法都会有很多实现思路,我们会尽可能地展现所有可能的解题方法。但为了文章的排版更加地紧凑,我们会将同一算法的不同实现,通过选项卡的形式展现。且默认展示的选项卡将会是最优解。这样的话,如果您想要快速阅读本文,则可以不用翻看其他的选项卡。实际效果如下:

迭代解

1
2
3
4
5
6
7
8
9
10
11
def solution(n):
if n <= 1:
return n
a = 0
b = 1
while n > 1:
n = n - 1
sum_ = a + b
a = b
b = sum_
return b

递归解

1
2
3
4
5
def solution(n):
if n <= 1:
return n
else:
return solution(n - 1) + solution(n - 2)

动态规划解

1
2
3
4
5
6
7
8
def solution(n):
if n <= 1:
return n
cache = [x for x in range(0, n + 1)]
cache[1] = 1
for i in range(2, n + 1):
cache[i] = cache[i - 1] + cache[i - 2]
return cache[n]
阅读全文 »

Welcome

 Welcome to My Blog!

博客介绍

 吾生有涯而学无涯,以有涯而逐无涯(有点断章取义,不过追寻知识的热情是必要的)

大事件纪实

标题 内容 日期
混沌初开 建站第一天 2014-11-01
模糊的记忆 Hexo 框架 / next 主题 / 七牛图床 / Gulp 压缩 / 静态资源 CDN / 支持 MathJax 2014~2016
多说关闭 评论系统切换为 Disqus 2017-04-10
Order by Update 文章以最后更新时间倒排展示(避免养成隔一段时间水一篇的坏习惯) 2017-04-22
Aliyun 备案 苏 ICP 2017-05-25
全站 HTTPS TrustAsia 域名证书 2017-10-10
Coding.net 静态页面从 github.io 切换为 coding.net(香港服务器) 2017-11-15
不蒜子 502 页面统计切换为 Lean Cloud,之前的 PV / UV 统计无奈清零 2017-11-19
DDoS 攻击解除 回归不蒜子 2017-11-20
Gitment 延迟加载 Gitment 2018-05-29
回归 Github Page Github Page 开始支持 HTTPS 2019-04-20
全站 CDN 阿里云 DCDN 2019-04-21
简繁切换 支持简体与繁体切换 2019-04-27
支持 Gitalk Gitment 验证存在跨域问题,而 Gitalk 可以无缝迁移 2019-05-01
支持 DaoVoice 可以匿名留言,在线沟通 2019-05-02
暂闭 DaoVoice 出于其服务稳定性的考量,暂时关闭 2019-05-11
设计 Logo 新 Logo 寓意着浩瀚宇宙中的一处安心的港湾 2019-05-11
源站迁移 全站迁移至阿里云 OSS,代替 Github Page 作为源站 2020–01-01
镜像网站 搭建镜像网站 yuzhouwan.github.io 2020-02-09
阅读全文 »

大数据生态圈中,保证一致性的方式举不胜举

他们各有什么区别,为什么会如此选型?

Paxos 选举算法

 Paxos 是最先解决拜占庭将军问题的算法,利用过半选举的机制,保证了集群数据副本的一致性(微服务中服务注册与发现的场景,其实已经不再适用了)

Raft 选举算法

 Redis 使用 Raft 实现了自己的分布式一致性。Raft 本身和 Paxos 并没有场景上的区别。更多的是,协议上的简化、Term 概念的强化、Log 只会从 Leader 到 Follower 单向同步,使得实现起来会很方便

Zab 原子广播协议

 Hadoop 偏向于离线的海量数据处理,利用 Zookeeper 来保证数据副本的一致性,是最为合适的

Hash 路由算法

 ElasticSearch 集群接收到为文档创建索引的请求时,需要选择在哪一个 shard(完整且独立的 Lucene 索引实例)上对文档进行索引。ElasticSearch 采用的是 djb2 哈希算法(俗称 times33),对要索引文档默认或指定的 key 进行哈希 hash(key),然后再对 ElasticSearch 集群中 shard 的数量 n 进行取模,即 $hash(key) \, mod \, n$

一致性 Hash

 用于对数据存储进行负载均衡的算法。最新的进展,是在去年 Google 发表的一篇 有界负载的一致性 Hash 算法的论文。该算法保证了负载均衡一致性稳定性的同时,在均匀性方面做出了实质性地改进。同时,Consistent Hashing with Bounded Loads 算法 也在 HaProxy 开源项目中得以应用,有效减少了其 8 倍的缓存带宽

Gossip 闲话算法

 Gossip 主要被 Cassandra 用于实现其分布式一致性。因为 Cassandra 框架,更看重 去中心化容错 的特性,在不违背 CAP 定理的情况下,能够接受 最终一致性

阅读全文 »

关于本文

 虽然接触 Java 已经 8 年之久,可惜学习之初的笔记文档没能很好地保存下来。本文是近几年工作学习中遇到的一些零散的知识点,包括了 基础概念、实用的编程技巧、代码可读性、设计模式、性能优化(工具 & 编码)、测试相关、JVM 相关、常用的工具和常见问题。本着好记性不如烂笔头的初衷,在不断地踩坑和爬坑的过程中,慢慢地记录成文。期待着本文能起到抛砖引玉的作用,以看到大家的真知灼见。

基础知识

注解

GuardedBy

 @GuardedBy 注解可以作用于某一个属性或者方法,约定在访问这些被注解标记的资源时,能被同步代码块保护着。简单的使用案例如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
@GuardedBy("obj")
private ConcurrentMap<String, String> map = new ConcurrentHashMap<>();
private final Object obj = new Object();

public void put(String k, String v) {
synchronized (obj) {
map.put(k, v);
}
}

/**
* If you use `error prone` tool to check this, this annotation should be `@SuppressWarnings("GuardedBy")`
* {@see https://errorprone.info/bugpattern/GuardedBy}
* {@see https://github.com/apache/incubator-druid/pull/6868#discussion_r249639199}
*/
@SuppressWarnings("FieldAccessNotGuarded")
public void remove(String k) {
map.remove(k);
}

@Override
public String toString() {
synchronized (obj) {
return "GuardedByExample{" +
"map=" + map +
'}';
}
}

Tips: Code Example from Apache Druid;另外,error-prone 工具支持对多种版本@GuardedBy 进行检查

阅读全文 »

关于本文

 业余玩家的一些学习笔记(哈哈~ 浪起来吧~~~)

 微积分、线性代数、概率论 等知识可以参阅另一篇文章《人工智能

函数

函数正交

 正交是线性代数的概念,是垂直这一直观概念的推广。作为一个形容词,只有在一个确定的内积空间中才有意义。若内积空间中两向量的内积为 0,则称它们是正交的。如果能够定义向量间的夹角,则正交可以直观的理解为垂直。物理中:运动的独立性,也可以用正交来解释

(图片来源:wikipedia.org™,已确认版权为 CC BY 3.0 协议)

级数

级数

 在数学中,一个有穷或无穷的序列 $u_1, u_2, u_3, u_4 \ldots$ 的和 $s=u_1 + u_2 + u_3 + \ldots$ 称为级数。如果序列是有穷序列,其和称为有穷级数;反之,称为无穷级数(一般简称为级数)

格兰迪级数

 格兰迪级数(Grandi´s series),即 $1 − 1 + 1 − 1 + \cdots$,记做 $\sum_{n=0}^{+\infty}{(-1)^n}$。这是一种发散级数。在 1703 年由意大利数学家格兰迪发表,后来荷兰数学家丹尼尔·伯努利和瑞士数学家莱昂哈德·欧拉等人也都曾研究过它。格兰迪级数的欧拉和切萨罗和均为 $\frac{1}2$

 比较简单的一种证法如下(下文 $p$ 进数中也有一段印证):

$S = 1 - 1 + 1 - 1 + \cdots$
$1 - S = 1 - (1 - 1 + 1 - 1 + \cdots) = 1 - 1 + 1 - 1 + \cdots) = S$
$2S = 1$
$S = \frac{1}2$

傅里叶级数

 在数学中,傅里叶级数是把类似波的函数表示成简单正弦波的方式。更正式地说,它能将任何周期函数或周期信号分解成一个(可能由无穷个元素组成的)简单振荡函数的集合,即正弦函数和余弦函数(或者,等价地使用复指数

(图片来源:wikipedia.org™,已确认版权为 CC BY 3.0 协议)

 按照傅里叶的理论,任何周期性变化的信号量,都可以分解成对应的直流分量和许多交流分量的叠加。直流分量:幅值不随时间变化的量(也可以看作信号的时间均值);交流分量,幅值随时间做周期性变化的量

阅读全文 »