-
scala99解题小结(List)
一个月之前，我把之前知道的scala99除了最后两题都做了下。总体来说自己用Scala来解决一些算法问题上有了一些感觉。 scala99的问题分为List，Arithmetic，Logic，Binary Tree，Multiway Tree，Graph和Misc。树和图和之后的问题和算法关系大一些。以下列一些影像比较深的题目。 本次先是List相关。
-
用DLX解sudoku(数独)
最近在做scala99，其中有一道题目P97是sudoku（数独）。一开始我想到的是列举每个空格的可选数字，选择可选数字最少的的格子开始填写。每次填写，修改关联格子的可选数字。再次尝试填写。这里无解条件是存在没有可选数字的格子。还有就是easy或者normal级别的数独一般可选数字都是1个，分批填写很快就能完成。hard或以上就没有那么幸运了，必须猜测然后验证，存在回溯。 这里描述的算法其实就是搜索+启发。启发是选择性地从最少可选数的格子开始。猜测+验证，感觉这个问题属于NP问题。事实上也确实是，而且可以转化为NP完全的精确覆盖问题（Exact Cover），所以这个问题也是NP完全问题。 P97给的答案有两个，第一个就是搜索+启发，第二个是DLX。DLX是Exact Cover的高效解法。本文就是讲如何用DLX来解数独问题的。考虑到scala99上第二个实现大部分都是可变数据，所以我用Java实现了相应算法。
-
NxN矩阵顺时针旋转90度
是一个面试题，我想了好久，果然好久不做类似算法题的话会思维迟钝。题目还有一个条件是每个点用4 bytes存储，实际上是每个点是int类型的暗示，这个矩阵就是int[][]的结构。 我是先考虑点的旋转规律的，用了一点三角函数和计算机图形学的坐标变换，实际上归纳法也是可以的，只是我没找出规律。之后是实际编码，比想象中要麻烦一些，和参考答案也是有点不同的。 首先说下变化规律，计算机坐标系下(x, y)点顺时针旋转90度后结果是(y, n – x），通过多次数据归纳也可以做，以下是图形学上的证明： ——————–> | (x, y) | | | (y, n – x) | v
-
无聊之作：简单模拟电梯程序[Java]
记得刚开始学Java时用的是《Java大学教程》，这本书每章都在介绍一点电梯程序的样子，加上上班天天都要坐电梯，突发奇想想要做一个模拟电梯程序。 一开始没想清楚电梯程序的运行方式，但是知道几个关键表现。 电梯有静止的时候 电梯往往停在最后请求的楼层，也有最后静止在底层（1楼）的，这相当于电梯在没有请求时自己按了一下1 电梯存在插队现象，即电梯在1楼，A在8楼先按，B在4楼后按，如果电梯没到4楼的话，后按的人先进 其实还有一个关键点，一般电梯都是有向上向下提示的，电梯上行时，A在8楼按下，B在4楼按下的话，B是不会插队的。不过如果把这个也考虑在内的话问题会复杂很多，因为操作电梯会有两步：指示方向和指出具体楼层。为了简化问题，我实际考虑每个楼层只有一个按钮，不指示方向，电梯内仍旧有具体到达楼层的按钮。这样的电梯可能有点怪，但也可以用。
-
看似简单的一个问题：请求速率限制问题
最近遇到一个场景，在每分钟错误计数达到250时发送消息。这里的每分钟并不是说整点的几分，有可能是现在16：16：16到16：17：16。 我了解到周围有人是用分钟的定时器来近似实现的，首先这样就限制了是整点的分秒，其次只限于对时间不敏感的场景，第三不能精确到秒，比如要求1次每秒的限制，因为定时器中任务执行很可能超过1s，而且还有并发的副作用。 那么直接在每次错误后向前扫描数量的笨方法呢？明显效率太低。 个人对于这个问题进一步分析，认为这个属于请求速率限制问题，并且找到的合适的关键字rate limit之后去google。发现stackoverflow有关于这类问题的讨论。在阅读了诸多资料之后，自己了解到两种专门针对请求速率限制的算法：Leaky Bucket和Token Bucket。下面简单介绍一下两种算法。
-
[Java]排列和组合算法
下午花了点时间，把排列和组合算法搞出来了。网上一堆资料看了不靠谱，要么是不明所以的变量名，要么直接帖代码。 排列 实现要点：交换和顺序处理。考虑对[1, 2, 3, 4]排列。实际是排列 [1], [2, 3, 4] [2], [1, 3, 4] [3], [2, 1, 4] [4], [2, 3, 1] 排列[1], [2, 3, 4]时，实际是排列 [1, 2], [3, 4] [1, 3], [2, 4] [1, 4], [3, 2] 从上面的分解可以看出，代码中实际要做的是交换当前的数字和右边数字中的某一个，具体来说，第一步是分别交换第一个和第一个，第一个和第二个，第一个和第三个，第一个和第四个。第二步是交换第二个和第二个，第二个和第三个，第二个和第四个。依次类推。递归的停止条件是右边的数组仅有一个元素，比如[1, 2, 3], [4]。具体代码如下，注意参数比较多的permutation方法。 start和end分别是第二个数组的起始位置和结束位置，当两者相等时，右边的数组只有一个元素，这时就可以直接输出排列的数组。 一般情况下，交换当前元素和右边数字中的一个，递归排列，在结束时交换回来（这步是必须的）。
-
哈希表二次探测
最近重新看哈希表的东西，发现自己大致能看懂了。以下是自己从书中了解的几个重点。 二次探测是一个根据哈希函数散列到同一个位置即碰撞时重新查找的方式，具体来说，假如i是哈希函数得到的位置，如果i有值了，那么尝试查找i + 1×1，i + 2×2，i + 3×3…i + NxN。 其次和二次探测相关的是在哈希表的大小为一个质数，并且使用量在一半以下时出现碰撞或者聚类的机率很小。 下面写一下实现哈希表二次探测个人认为主要的两个点，剩下的就是一些具体实现的细节问题了。 查找下一个质数 在容量超过一半时重新散列。需要找到比当前表大小大一些的质数。个人实现如下（Java）： public static int findNextPrime(int current) { int nextPrime = current; if(nextPrime % 2 == 0) nextPrime++; while(!isPrime(nextPrime)) { nextPrime += 2; } return nextPrime; } private static boolean isPrime(int number) { for (int i = 3; i <= Math.sqrt(number); i +=…
-
递归的进一步学习-动态规划之最少硬币问题
阶乘和斐波那契数列相信各位都很熟悉，典型的教材式递归例子，因为简单退化为循环也没啥难度。不过依赖于递归的问题并不都是那么简单的，比如最少硬币问题，需要称为动态规划（DP）的方式来实现。 所谓动态规划个人理解就是缓存一下递归的结果。比如斐波那契数列，简单的实现方式是： public int fib(int n) { if(n == 0 || n == 1) return 1; return fib(n – 2) + fib(n – 1); } 假如计算fib(5)，事实上计算了一次fib(4)，两次fib(3)，三次fib(2)，四次fib(1)，两次fib(0)，换句话说，重复计算了(1 – 1) + (2 – 1) + (3 – 1) + (4 – 1) + (2 – 1)有7次之多。理想情况下每个fib(n)只要计算一次。改进方法很简单，增加cache，其实就是简单的映射数组： public int fib(int n) { if(fib_cache[n] > 0) return fib_cache[n]; //…
-
Dijkstra非负加权有向图最短路径算法
成果在这里，前天完成的，花了大约半天的时间。参考资料主要是维基百科和一篇博客。 在分析自己代码前，先写一点自己对于Dijkstra算法的理解。 u s v
-
二叉查找树学习笔记
二叉查找树如其名是一种主要用于查找的每个非叶子节点最多有两个子节点（左右子节点）的树，其特点是： a b c 任何a, b, c三个节点（父节点和两个子节点，左右子节点可能只有一个或者都没有）满足a < b < c。对于相等的值使用节点计数+1或者节点中的链表等不同的方式来处理。 a < b < c这个条件乍一看和二分搜索binary_search很像，实际查找元素时也是类似的，时间复杂度在O(logn)。 一般的二叉查找树（不考虑链表退化和平衡的处理）包含查找，创建树/增加节点，删除节点，前/中/后序遍历等操作，下面分别介绍。