欢迎来 https://github.com/JenniferZh/PrincetonAlgorithmsPart1 围观源码
Contents
- Notes
- HomeWork Reports
- Percolation
- 8puzzle
- kdtree
Notes
Java对象内存大小估计
一个有n个元素的stack, 其中每个元素:
- class overhead：16bytes
- inner class(inner class Node): 8bytes
- inner class(inner class Iterator): 8bytes
- data member: 8bytes value + 8bytes next pointer
共计：48bytes
Java Iterator
1.如果一个类Implements Iterable
那么这个类需要有iterator()函数，返回这个类的Itertor
2.如果一个类Implements Iterator
那么这个类需要有
- boolean hasNext():当前是不是最后一个
- Item next()：返回当前的，并把指针向后移动一个
3.为什么需要有Iterator
代表这个类表示拥有一系列元素的集合，可以被便历的。使用Iterator，就可以使用Java中的foreach loop
for(Item item: stack)
{
}
4.自己实现一个Iterator的关键点
- 把这个Iterator设置为你要Iterate的类的Inner Class
- 由于内部类可以访问外部类的内部变量，在iterator中设置一个current，一般指向外部类需要iterate的的集合的头指针。
为什么Java的数组不支持Generic泛型
主要是因为数组是covariant的，但是泛型是Invariant的。也就是String[]是Object[]的子类，但是Stack不是Stack的子类。
Java在编译时的类型检查很严格，所以不支持。具体例子见 http://www.tothenew.com/blog/why-is-generic-array-creation-not-allowed-in-java/
堆排序的优缺点
- 优点：一个In-place不需要额外空间，且最差时间复杂度也是nlgn的算法；相比快速排序，虽然inplacee，但是最差时n方的复杂度；相比归并，虽然最差是nlgn，但是需要额外空间
- 缺点：不稳定排序；且对与cache利用不好，因为交换比较的元素经常距离很远，利用不上cache。。相比快排，对于cache的利用就很棒。
2-3 tree
- 2-3tree的两种node
- 2-Node 这种节点里面只有一个Key
- 3-node 这种节点里面有两个key
- 2-3tree的重要性质
从根节点到每一个叶子结点都是一样高的
- 2-3tree的查找
和想象的一样
- 2-3tree的插入
先插入到最底下一层，如果出现了4-node，把中间的key上浮，一直浮到根节点，如果根节点还是4-node,就分裂根节点
-
时间复杂度
查找，插入，删除时间复杂度均为logn
Left-leaning Red-Black Tree
- 核心思想
2-3的二叉树表示！转化流程是把3-node拆分为left-leaning red-black tree，
- 主要性质
- 没有一个节点有两个红色边连在上面
- 每一个从根部到叶子节点的路径上-黑色边的数量相同，这条性质显而易见，因为它就是从2-3树演化而来的，我们可以把红色的边当做是internal的，不计算在内，所以红黑树的黑色边满足2-3树的定理
- 红色边在左边
- 数据结构设计
对于如何表达一个红色边，我们规定如果一个节点和它的父亲之间是红色边，那这个节点的红色属性为true, 这样设计的原因是一个节点和自己的父节点可以唯一确定一条边。
private class Node {
Key key;
Value value;
Node left, right;
boolean color;
}
- 基本操作
- 左旋
- 右旋
- Color flip
当一个节点左右都是红色边时，这两条红色边上浮到这个节点的父亲边上。
-
查找的worst case
红黑树的高度小于等于2logN，原因很简单
- 黑链是等高的，全黑链的高度是logN
- 红链不能相连，因此在一条path上最多和黑链一样多，因此最多2lgN
- 插入节点
插入的节点默认带一条红色链，再通过三种基本操作来转化成合法红黑树
kd tree
- 从1d key到2d key
键值从一维变成了二维，可以联想我们在一个平面上插入，寻找点的信息；具体规定的操作如下：
- insert 2d key
- search 2d key
- range search: 给定方形中的点
-
range count: 给定方形中的点个数
<<<<<<< HEAD
Reports
percolation
序
渗透问题，如下图，可以装水的空心格子是open的（白色+蓝色），想象从上向下倒水，水可以流通的格子是full的(蓝色)，如果水可以直接流下去（如图）那么这个容器是可渗透的。
设计算法：时刻知道现在的容器是不是可渗透的
方案
当然是并查集啦
几个关键点
并查集的哈希方法
并查集应用的关键点是如何把现实问题映射到0-(n-1)上，比如这个问题的二维坐标点的映射方法，可以是row*n+col
虚拟点的设计
开始判断是否可渗透时，我的想法是两个for循环判断最上面一行的点和最下面一行的点是否存在两个相通的点。然而这种方法的时间复杂度很高，根据题目提示，采用上下各一个虚拟点，在点的添加时，如果是第一行，就和上虚拟点相连；如果是最后一行，就和下虚拟点相连。
backwash倒流问题
当采取上述的上下虚拟点方案后，可能出现倒流的问题。出现原因如下：当系统可渗透时，上虚拟点和下虚拟点已经处于一个集合内，而和下虚拟点相连的点不一定是full的，却会因为上下虚拟点的合二为一而被误认为是full的（标成蓝色点），因此产生了错误的蓝色标注。
解决方案是，采用两个并查集，一个绑定上虚拟点，一个绑定下虚拟点。
结果
本次实验得分99，通过了所有正确性测试。
8puzzle
序
8 puzzle是一个大家都玩过的游戏，3*3个格子里面有8个方块，上面的图画拼起来是一个大图片，有一个空位置可以供这些方块移动，便产生了一些问题：给定一个初始状态，可以通过移动恢复成有序的样子吗？如果可以，最少几次移动呢？
方案选择
我们可以使用bfs进行搜索，每个节点是一个棋盘状态。但其实我们可以使用更高级的bfs来让搜索变的更快——A star search.
这个搜索方法的关键是：把bfs中的队列换成优先队列，先弹出最接近结果的。最接近结果的考评方法，我们需要设置合适的考评函数，例如在8 puzzle问题中，有几个方块已经在他们应该在的位置上就是考评这个状态是否接近最终结果的方案之一。
一个介绍本算法的视频：https://www.youtube.com/watch?v=ySN5Wnu88nE
在写作业是遇到的问题
Board类中equals()的实现
记住以下套路：
- 判断x是不是同一个指针x == this
- 判断x是不是null
- 判断x的class是不是本类型，如果是才可以强制转化
- 强制转化类型，写你想写的比较逻辑
public boolean equals(Object x) {
if (x == this) return true;
if (x == null) return false;
if (x.getClass() != this.getClass()) return false;
Board other = (Board) x;
// start comparison...
}
如何发现当前状态有解呢？
当我们设置一个优先队列来储存状态，如果初始状态本来就没有解，那将为陷入一个死循环，因此我们首先应该判断是否有解。
判断有解的方案：作业提示中讲了一个定理，对于任何一个初始状态，我们可以找到另一个状态（方法是交换原有状态的任意两个方格[不包含空方格]的位置）这两个状态中，如果一个可以达到终点，那另一个肯定不行。
基于以上原理，我们可以理解为什么Board类中让我们实现一个twin函数，这个函数就是生成上述的另一个状态的。
因此，我们在初始化时，可以把初始状态，和初始状态的一个twin状态都放入优先队列，这样，一定有一个可以到达目标状态，所以循环一定可以结束；在达到目标状态时，只需要判断是twin状态的子节点还是初始状态的子节点就可以确定，是否可解，以及最短路径长度。
重复状态的避免
我们希望避免的情况是，一个格子推过去后，在下一个状态又被推回来了。因此，进入队列时，我们可以预先检查即将入队列的状态是否和当前状态的父状态重复（就是不要让爷爷和孙子重复）
注意immutable
课堂上说，放在priority queue里面的类中与大小比较有关的变量推荐设置为immutable的——即final类型。顺便，在practice中，如果你没有一个一定要修改这个变量的理由，那么记得一定声明这个变量为final的，这是一个好习惯。
结果
本次作业获得93分，correctness用例全部通过，扣分在时间效率上。
kdtree
序
编写二维空间中使用暴力方法和kdtree方法解决
- 给定长方形，确定其包围的点集合问题
- 给定其中一点，找此点最近点问题
kdtree实现要点
- kdtree的节点插入模板
开始写节点插入时，使用while循环寻找插入位置，最后通过更新路径上的最后一个节点实现插入，这种插入的方法需要写很多判断条件，代码不简洁。关于BST的插入，kdtree的插入，可以使用递归调用的插入模板编写插入函数。
public void insert(Point2D p) {
if (p == null) throw new IllegalArgumentException();
RectHV rect = new RectHV(0, 0, 1, 1);
root = put(root, p, true, rect);
}
//递归插入，代表以node为根节点插入点p，并返回插入之后的根节点返回
private TreeNode put(TreeNode node, Point2D p, boolean vertical, RectHV rect) {
if (node == null) {
size++;
return new TreeNode(p, rect, vertical);
}
if (node.key.compareTo(p) == 0) return node;
if (node.isVertical) {
if (p.x() < node.key.x()) {
//左下不变，右上左移
RectHV rectleft = new RectHV(rect.xmin(), rect.ymin(), node.key.x(), rect.ymax());
node.leftdown = put(node.leftdown, p, false, rectleft);
} else {
//右上不变，左下右移
RectHV rectright = new RectHV(node.key.x(), rect.ymin(), rect.xmax(), rect.ymax());
node.rightup = put(node.rightup, p, false, rectright);
}
} else {
if (p.y() < node.key.y()) {
//左下不变，右上下移
RectHV rectdown = new RectHV(rect.xmin(), rect.ymin(), rect.xmax(), node.key.y());
node.leftdown = put(node.leftdown, p, true, rectdown);
} else {
//右上不变，左下上移
RectHV rectup = new RectHV(rect.xmin(), node.key.y(), rect.xmax(), rect.ymax());
node.rightup = put(node.rightup, p, true, rectup);
}
}
return node;
}
- kdtree的数据结构设计
注意：需要添加两个变量
- isVertical表示当前的点是横向分割还是纵向分割
- rect是当前点插入在了哪一个长方形里，并不是以这个点划分后的某半边。例如如果点确定在1x1大小的方格中，插入的第一个点对应的长方形就是最大的1x1这个长方形。rect的设置会使判断长方形中的包围点问题更加容易。
private class TreeNode {
private final Point2D key;
private final RectHV rect;
private TreeNode leftdown;
private TreeNode rightup;
private final boolean isVertical;
TreeNode(Point2D point, RectHV rec, boolean vertical) {
key = point;
rect = rec;
isVertical = vertical;
}
}
- rect长方形包围的点集问题的剪枝策略
如果某个子树的根节点对应的长方形和当前要查找的长方形没有交集，那么这个子树就会被剪枝。
- 查找最近点问题的剪枝策略
如果某个子树的根节点对应的长方形到给定点的距离大于当前找到的最小距离，那么这个子树就会被剪枝。
- 查找最近点的评分遍历问题
你可能会遇到自动评分系统在最近点问题出现错误，这是因为你需要做一个小优化：如果两边都没有被剪枝，应该先遍历靠近查找点的那一边。
结果
本次作业得分87，正确性全部通过，时间效率得分较低。