月度归档：2013年06月

博客搭建笔记

发表于由
37

这里记录下我的博客搭建过程。

购买VPS

VPS提供商有很多，我用的美国 BudgetVM 提供的linux vps，最便宜的那种，128M RAM、10G硬盘、一个固定的IPv4的IP地址，3个IPv6的IP地址，500G流量/月，14.99$/年，非常便宜，一年不到100元。这样的配置搭个个人网站完全够了。

购买之后可以通过信用卡或paypal付款，付款后需要大约十分钟进行系统安装等工作，然后你就拥有一台新电脑了，只是看不见而已。
可以通过 ssh root@ip-address 进行访问了。

我选的是Ubuntu 12.04 32位的，默认安装了Apache。

域名

买了VPS后虽然有固定的IP地址了，但没有人会去记一串数字的地址，而且以后如果迁移到其他的VPS提供商时，IP会变的，所以最好有个自己的域名。

我的域名是在万网买的，150元3年。是.net的域名，用.cn的话还得备案什么的超级麻烦。

有了域名和IP地址后，还要把两者关联起来，就需要配置DNS解析了。我用的DNSPod(<www.dnspod.cn>)，可以免费使用，如果要用人家的增值服务，那肯定是要付费的。

配置DNS后需要一定的时间来使DNS服务器的记录更新，很快就可以通过 http://you-domain 来访问了。如果你看到Apache的默认页面： it works，说明到目前为止的配置都是成功的，否则就google吧。

继续阅读 →

向量旋转

发表于由
回复

向量旋转

题目均来自《编程珠玑》。

题

将一个n元一维向量向左旋转（循环移位）i个位置。例如，当n=8时且i=3时，向量abcdefgh旋转为defghabc。简单的代码使用一个n元的中间向量在n步内完成该工作。能否仅用数十个额外直接的存储空间，在正比于n的时间内完成向量的旋转？

旋转操作对应于交换相邻的不同大小的内存块：每当拖动文件中的一块文件到其他地方时，就要求程序交换两块内存中的内容。

两个简单直接的方法

方法一：首先将 x 的前 i 个元素复制到一个临时数组中，然后将余下的 n-i 个元素向左移动 i 个位置，最好将最初的 i 个元素从临时数组中复制到 x 中余下的位置。这种办法使用 i 个额外的位置产生了过大的存储空间的消耗。

方法二：定义一个函数将 i 向左旋转一个位置（其时间正比于 n），然后调用该函数 i 次。该方法产生了过多的运行时间消耗。

下面介绍三种更好的方法。

继续阅读 →

非递归、固定量额外存储空间 遍历二叉树

发表于由
3

非递归、固定量额外存储空间 遍历二叉树

题

写出一个O(n)时间的非递归过程，输出给定的含n个节点的二叉树中每个结点的关键字，要求只能使用除树本身以外固定量的额外存储空间，而且在过程中不能修改该树，哪怕只是暂时的。

树的遍历方式分类

从树的深度分类

树的遍历可以分为广度优先和深度优先两种形式。

  • 广度优先，就是先输出父结点，再输出子结点。一般借助于（FIFO）队列。
  • 深度优先，就是先输出子结点，再输出父结点。一般需要借助（LIFO）栈结构，如果不使用栈数据结构，一般就需要借用运行时的方法调用栈。

从树的节点的先后顺序分类

树的遍历可以分为先根遍历、中序遍历、后序遍历。前中后是以父节点在遍历中的顺序为根据的。

  • 先根遍历：先遍历根，再遍历左子树，最后遍历右子树。
  • 中序遍历：先遍历左子树，再遍历根，最后遍历右子树。
  • 后序遍历：先遍历左子树，再遍历右子树，最后遍历根。

分析

由于只能使用固定量的额外存储空间，所以，没法构建队列或栈来进行遍历 或 用变量标记哪些结点是已输出的。由于不能修改树，也没法在树上做标记。所以，结点是否已输出只能在遍历过程中判断，也就需要遍历的算法能够区分出已输出和未输出的。

如果采用广度优先的方式，先输出父结点后，由于没有足够的空间来存储对子树的引用，树可以说是变为两棵独立的树，这个方式应该是不可行的。

如果采用深度优先的方式，以中序遍历为例，总是按左子树、父结点、右子树的顺序遍历，那么当右子树遍历完后，说明父结点及其所有子树都遍历完成了，可以这样往上处理父结点的父结点。而判断右子树是否遍历完成可以通过：当前遍历完成的结点是否是父结点的右结点来完成。这种方法是可行的。

当结点p及其子树都遍历完成后，需要向上查找第一个未遍历的右子树（parent = p.parent）：

  • p == parent.rChild，当前遍历是子树是右子树，需要继续往上查找；
  • 否则，p是parent的左孩子，先输出parent；如果parent有右孩子，需要进行遍历；如果parent没有右孩子，需要继续往上查找。

继续阅读 →

计算整数的二进制表示里1的位数

发表于由
回复

题

编程计算给定的整数在用二进制来表示时含有多少个 1。

分析

假定以高位在前、低位在后的形式，一个整数的二进制表示为：000110100；当该整数减1时，由于低位是0，所以会一直往高位借位，直至碰到最低位的1（竖线后面的那个1）：000110|100；减1之后整数那个最低位1变为0，之后的位都变为1：000110|011；此时进行 i & (i-1) 就会让竖线后面的都变为0：


000110|100　　i
000110|011　　i-1
000110|000　　i&(i-1)

1110　　-2
1101　　-2 - 1
1100　　-2 & (-2 - 1)

所以 i = i & (i-1) 都会让 i 里的位为 1 的个数减一。对于负数，同样具有这样的性质。
继续阅读 →

堆排序

发表于由
回复

堆排序

这里的堆不是编程语言里的堆，是一种数据结构。

堆像一棵倒立的满二叉树，每个节点最多有两个直接子节点。最上面的节点称为根节点，没有子节点的节点称为叶子节点，有子节点的节点称为分支节点。

堆有大顶堆和小顶堆之分。大顶堆是指分支节点大于它的所有子节点，堆里最大元素是根节点；小顶堆是指分支节点小于它的所有子节点，堆里最小元素是根节点。

堆排序是借助堆数据结构进行排序的一种高效算法，它的平均时间复杂度是O(n*lg(n))。

实现

堆排序的核心是构建和维持堆。

实现时要注意的是：

  • 以数组第一个节点（序号为0）为根，方便计算叶子节点。

  • 大多数算法介绍都是以1为数组的起始下标的，左右叶子节点的计算分别为：lchild=2*parent; rchild =2*parent+1；而实际编程语言大多数都是以0为起始下标的，所以子节点计算需要调整为：lchild=2*parent+1; rchild=2*parent+2；因为根节点是0，导致根节点的左子树与根节点相同而出错。

  • 构建是从底向上逐层构建堆，从最后一层的分支节点（ len(arr)/2 ）开始构建堆。

  • 从堆顶取出最大元素与最后一个堆元素交互后，堆的大小减1。所以堆在排序过程中是逐渐缩小的，但根总是第一个元素，所以可以利用之前也构建好的堆，只需要调整一棵子树。
    继续阅读 →

快速排序

发表于由
回复

快速排序也是基于分治模式的，对于规模为n的数组，最坏情况运行时间是O(n^2)，平均运行时间是O(lg(n))。

对数组A[p…r]排序的分治过程的三个步骤：

  • 分解：数组A[p…r]被划分成两个（可能空）子数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]中的每个元素都小于等于A[q]，而且小于等于A[q+1…r]中的元素。下标q也在这个划分过程中计算。
  • 解决：通过递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]排序。
  • 合并：因为两个子数组是就地排序，将他们合并不需要操作：整个数组A[p…r]已经排序。

从上面的步骤可以看到，快速排序的关键在划分子数组，且每次划分都产生一个元素，它所在的位置就是它最终的位置。
继续阅读 →

求元素累加和最大的子数组

发表于由
1

问题描述

对于一个给定的整数数组arr[0...n)，求这样一个子数组，它的元素的累加和在所有子数组中是最大的。

这个题在《编程珠玑》一书中有介绍，以前也是在这本书上看到解决方法后就再也没有忘记了。现在重新实现并记录一下，记录了从最低效的3重循环解决方法到最高效的线性时间解决方法及其中的优化考量。
继续阅读 →

合并排序

发表于由
回复

合并排序

合并排序是基于分治思想的：
1. 如果数组足够小，直接对数组进行排序。
2. 否则，把数组划分为两个子数组，分别进行合并排序，然后合并两个有序的子数组为有序数组。

进行合并操作的复杂度为O(n)，由于每次把数组分为2个子数组，需要进行lg(n)次合并，所以时间复杂度为O(n*lg(n))，。

每次合并都需要与两个子数组长度和 大小的数组，所以空间复杂度为O(n)。

继续阅读 →

ssh 命令说明与使用

发表于由
回复

ssh

简介

SSH（secure shell）是一种网络协议，用于计算机之间的加密登录。SSH有多种实现，Linux系统下使用的一般是OpenSSH。

来自维基百科：


传统的网络服务程序，如rsh、FTP、POP和Telnet其本质上都是不安全的；因为它们在网络上用明文传送数据、用户帐号和用户口令，很容易受到中间人（man-in-the-middle）攻击方式的攻击。就是存在另一个人或者一台机器冒充真正的服务器接收用户传给服务器的数据，然后再冒充用户把数据传给真正的服务器。

而SSH是目前较可靠，专为远程登录会话和其他网络服务提供安全性的协议。利用SSH协议可以有效防止远程管理过程中的信息泄露问题。通过SSH可以对所有传输的数据进行加密，也能够防止DNS欺骗和IP欺骗。

SSH之另一项优点为其传输的数据可以是经过压缩的，所以可以加快传输的速度。SSH有很多功能，它既可以代替Telnet，又可以为FTP、POP、甚至为PPP提供一个安全的“通道”。

使用形式


     ssh [-1246AaCfgKkMNnqsTtVvXxYy] [-b bind_address] [-c cipher_spec]
         [-D [bind_address:]port] [-e escape_char] [-F configfile] [-I pkcs11]
         [-i identity_file] [-L [bind_address:]port:host:hostport]
         [-l login_name] [-m mac_spec] [-O ctl_cmd] [-o option] [-p port]
         [-R [bind_address:]port:host:hostport] [-S ctl_path] [-W host:port]
         [-w local_tun[:remote_tun]] [user@]hostname [command]

继续阅读 →