ARTS(30)

1 Algorithm

上图为一手机键盘,手指尖可以在键与键之间移动,但是每次只能按照日字对角线移动,类似中国象棋马移动方式。现在输入指尖开始的键( key )和可以移动的步数 k,请输出移动最终移动到 1 键方法数。

按照移动规则,将键盘转换为网络连接图,按照日字关系绘制跳转关系。为了方便,我们将全部键按照一维数组形式表示出来。

// 连接表形式表示图

func buildGraph(m map[byte]int) [][]int {

neighbour := make([][]int, len(m))

neighbour[m['1']] = []int{......

ARTS(29)

1 Algorithm

二叉树遍历是通过某种特定的顺序对二叉树的节点有且仅访问一次,遍历能够将二叉树非线性结构转换为某种线性顺序。二叉树的遍历主要分为先序遍历,中序遍历和后序遍历三种,每一种都有递归和迭代两种方式实现。

二叉树节点定义如下

type TreeNode struct {

Val int

Left *TreeNode

Right *TreeNode

}

1.1 递归遍历

二叉树是递归定义的,所以递归遍历二叉树就非常简单

// 先序遍历

func PreOrder(root *TreeNode, visite func(*TreeNode) ) {

if r......

ARTS(28)

1 Algorithm

设计一个实时数据流接收器,要求在任意时刻输出所有数据的中位数。

初步设计在内部维护一个有序队列,每接受一个数据,插入到这个有序队列中,时间复杂度为 $O(n^2)$。既然需要输出数据流的中位数,那么只需要维护好这个中位数即可,至于其他数据可以降低排序的顺序要求,所以我们可以借助堆 (heap) 这个数据结构。

将整个数据流划分到这个两个堆中,数据流的前半部分将构建最大堆,而后半分布构建最小堆。为了保证快速获取数据的中位数,保证这个两个堆的数据量相差不超过 1, 那么中位数必定最大堆的顶元素和最小堆顶元素中产生(或者取平均数),所以在接受数据流的时候,往......

ARTS(27)

1 Algorithm

不使用 + 和 - 运算符完成两个整数之和计算。

如果不使用 + 和 - 运算符,那么就需要考虑一下两点:

CPU 运算单元是完成加法和减法运算;

整数的二进制是怎样表达的;

CPU 运算都是基于二进制的,也就是通过布尔代数完成各种计算。每一个 bit 进行布尔代数计算,除了两数相加各个比特位之间的计算,还包括进位符(carrier) 的特殊处理。布尔代数计算非常简单,只需要绘制出真值表即可。

A

B

carrier

result

newCarrier

0

0

0

0

0

0

1

0

1

0

0

1

1

0

1......

ARTS(26)

1 Algorithm

在一个数组中,只包含 0, 1, 2 三个数据,在 O(n) 时间复杂度和 O(1) 空间复杂度的情况下,将数组排序。

我们知道基于比较的数组排序算法中,时间复杂度的下限是 $nlog(n)$,而 O(1) 空间复杂度要求不能借助字典数据结构。 由于数组中只包含 0, 1, 2 三种数值,那么排序后的数组,必定形如 [0, 0 ... 1, 1 ..., 2, 2 ... ],那么我们只需要遍历整个数组,将 0 与数组前面的元素交换,将 2 与数组后面的元素交换。因此我们需要三个指针:

pivot: 指向正在比较的数组元素;

header: 数组前......