算法

  • 继上一篇 #104 ,本来是在研究虚拟 DOM 算法的,看到了 livoras 的这篇文章,觉得写得很好!珠玉在前,我便不再赘述了。该文章中提到:列表更新本质上是一个最小编辑距离问题,不过并未就此详细展开。今天,我们来具体看看这个问题。

    问题

    给定两个字符串 a 和 b,只允许以下三种操作:

    1. 插入一个字符;
    2. 删除一个字符;
    3. 替换一个字符。

    求:把 a 转换成 b 的最小操作次数,也就是所谓的最小编辑距离。
    举例: "xy" => "xz",只需要把 y 替换成 z,因此,最小编辑距离为 1。
    "xyz" => "xy",只需要删除 z ,因此,最小编辑距离为 1。

    求解这个问题


  • 问题

    如何利用已知random()函数,求一个1~N的全排列?

    详细描述

    已知:一个random()函数可以生成一个(0,1)范围内的浮点数。
    要求:输入N,利用random()函数,生成一个1至N的全排列。
    例如:当输入N = 4,生成结果可以为1324或3214等等,并保证等概率。

    正文

    Step 1

    这个题最自然的想法莫过于连续产生随机数,然后如果产生的这个随机数之前没有产生过,就记录并且输出。

    这样做显然是能得到结果的,并且能保证足够的随机。

    但存在的问题就是会产生些许的浪费,每次产生随机数之后都要确认曾经是否产生过。尤其是对于这样的场景,比如 1 - 3 的全排列,如果已经产生了 3


  • 现在是凌晨三点三十八分 :)

    本来我一点钟的时候是准备睡的,然而正准备关灯的时候,我一不小心瞟到了角落的《数据结构与算法 JavaScript 描述》(下面简称《算法》)。

    这本书刚买回来时,我简单翻了一下前两章,然后就后悔买这本书了:书上讲的都是很基础的内容,第一章完全就是给 JavaScript 新手看的,第二章讲了 Array 的一些方法,而这些内容我早在《JavaScript 权威指南》里面就看过了。

    这也是这本书一直被我放在角落的原因。

    为了避免自己去睡觉(明明很困但就是不想睡),我翻了翻这本书,发现第二章有四个习题,粗略看了看也不难,正好拿来清醒一下大脑。

    前三题没什么难度,轻松完

  • Canvas 操作图像像素

    HTML5 中最吸引我的新标签就是 canvas,canvas 元素为我们操作图像带来了更多的可能。


    ## ImageData 对象

    canvas 元素给我们提供了一系列绘制 2d 图像的 API,比如绘制一个正方形或者一个椭圆等,同时我们也可以利用 getImageData() 方法返回的 ImageData 对象,获取一个图像的像素点。

    var ctx = canvas.getContext('2d')
    // 获取 ImageData 对象
    var imageData = ctx.getImageData(x, y, width, height)

    getIma


  • 认识图片隐写

    大家都知道在信息经过加密算法处理后,我们一般是无法直接从信息中读取内容,而且信息看上去并不那么合理。对于专注信息安全的人,可以从信息的奇怪的外观上判断信息是否经过加密处理,这无疑是此地无银三百两,招着人家来破解你的加密内容。

    而今天要介绍的图片隐写则更像是“大隐隐于市”的一种技巧。


    ## 隐写术

    图片隐写正是隐写术的一种。隐写术的英文是Steganography,来源于15世纪一个德国修道士特里特米乌斯(Trithemius)写的一本讲述密码学和隐写术的著作《Steganographia》。该书书名源于希腊语,意为“隐秘书写”。

    隐写术的使用可以追溯到希腊时代。当时有个人为了能