列表、字符串及字典——Python基本数据结构

Python 的强大之处就在于它有丰富的库以及各种方便的特性。这篇文章将会介绍 Python 中的几个内置类型——列表、元组、字符串及字典。

我是按照 Python3 来介绍,如果和 Python2 有不同的地方会特别指出的。并且,文中的代码如果有输出的部分,都是按照 Python3 语法进行。另外,如果代码中是以 >>> 开头的,就说明这段代码是我直接在交互模式下运行的,并且包含了输出。

List——列表类型

首先,我们来介绍列表类型。什么是列表呢?你可以认为列表是多个变量的集合,并且这个集合是有序的。你在以前遇到的类型可能都只是涉及单个元素,比如说 intfloat 之类的,这都只涉及了一个数字。但是列表不同,它可以用一个变量存储多个元素,如果你了解过其它语言,列表和数组是十分类似的。

一个列表是用一个方括号包围的,列表中的元素使用逗号分隔,例如下面这几个变量都是一个列表:

值得注意的是,一个列表可以不包含任何元素,就像变量 c 存储的列表一样,这样的列表叫做空列表

另外,一个列表内的元素不一定要有相同的类型,甚至列表本身也可以作为元素存储在一个列表中:

比如说上面第一个列表,它存储着三个不同类型的元素,一个是整数,一个是浮点数,另外一个是字符串。

至于第二个列表,它包含四个元素,第一个元素是一个整数 233 ,第二个元素是先前的列表 x ,第三个元素是一个空列表 [] ,最后一个元素是另外一个仅包含一个字符串作为元素的列表。

(more…)

Read More

CodeChef上一道有趣的网络流题目

这是一道2016年二月CodeChef上的一道题目,叫做Call Center Schedule

题目大意是这样的:

一个电话公司有 P 个员工,一个星期有 D 天,每天需要工作 H 个小时。每个员工在每个小时只能做参加会议和与客户通话两件事情中的一件,或者不做。

现在要为安排一个和客户通话的时间表,要求满足

  • 每个人每天最多花费 N 个小时在参加会议和通话上
  • 第 i 个人每周最多花费 Li 个小时和客户通话
  • 每个人每天在 LTbegin 到 LTend 的时间内至少要有 1 小时没有被安排任务
  • 对于第 i 天第 j 个小时,恰好有 Ri, j 个人可以和客户通话

另外,开会的时间表已经安排完成,如果 Fk, i, j 是 0 则表示第 k 个人在第 i 天的第 j 个小时开会,如果是 1 则表示他可以被安排去和客户通话。

时限是 2s,最多 5 组数据,并且 1 \leq N \leq H \leq 70, 1 \leq D, P \leq 70, 1 \leq L_i \leq ND, 0 \leq R_{i, j} \leq 15, F_{k, i, j} \in \{0, 1\}, 1 \leq LT_{begin} \leq LT_{end} \leq N

(more…)

Read More

Tarjan算法寻找有向图的强连通分量

在图论中,一个有向图被成为是强连通的(strongly connected)当且仅当每一对不相同结点 u 和 v 间既存在从 u 到 v 的路径也存在从 v 到 u 的路径。有向图的极大强连通子图(这里指点数极大)被称为强连通分量(strongly connected component)。

tarjan-graph

比如说这个有向图中,点 1, 2, 4, 5, 6, 7, 8 和相应边组成的子图就是一个强连通分量,另外点 3, 9 单独构成强连通分量。

Tarjan 算法是由 Robert Tarjan 提出的用于寻找有向图的强连通分量的算法。它可以在\mathcal O(|V|+|E|)的时间内得出结果。

Tarjan 算法主要是利用 DFS 来寻找强连通分量的。在介绍该算法之前,我们先来介绍一下搜索树。先前那个有向图的搜索树是这样的:

search-tree

有向图的搜索树主要有 4 种边(这张图只有 3 种),其中用实线画出来的是树边(tree edge),每次搜索找到一个还没有访问过的结点的时候就形成了一条树边。用长虚线画出来的是反祖边(back edge),也被叫做回边。用短虚线画出来的是横叉边(cross edge),它主要是在搜索的时候遇到了一个已经访问过的结点,但是这个结点并不是当前节点的祖先时形成的。除此之外,像从结点1到结点6这样的边叫做前向边(forward edge),它是在搜索的时候遇到子树中的结点的时候形成的。

(more…)

Read More