常用的正则表达式

常用正则表达式

正则表达式用于字符串处理、表单验证等场合,实用高效。现将一些常用的表达式收集于此,以备不时之需。

用户名:/^[a-z0-9_-]{3,16}$/

密码:/^[a-z0-9_-]{6,18}$/

十六进制值:/^#?([a-f0-9]{6}|[a-f0-9]{3})$/

电子邮箱:/^([a-z0-9_\.-]+)@([\da-z\.-]+)\.([a-z\.]{2,6})$/

URL:/^(https?:\/\/)?([\da-z\.-]+)\.([a-z\.]{2,6})([\/\w \.-]*)*\/?$/

IP 地址:/^(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)$/或者^(([0-9]|[1-9][0-9]|1[0-9]{2}|2[0-4][0-9]|25[0-5])\.){3}([0-9]|[1-9][0-9]|1[0-9]{2}|2[0-4][0-9]|25[0-5])$

HTML 标签:/^<([a-z]+)([^<]+)*(?:>(.*)<\/\1>|\s+\/>)$/

Unicode编码中的汉字范围:/^[u4e00-u9fa5],{0,}$/

hostname:

^(([a-zA-Z0-9]|[a-zA-Z0-9][a-zA-Z0-9\-]*[a-zA-Z0-9])\.)*([A-Za-z0-9]|[A-Za-z0-9][A-Za-z0-9\-]*[A-Za-z0-9])$

Read more

二叉树二度节点和叶子节点的数量关系

二叉树二度节点和叶子节点的数量关系:

假设共有节点 N 个, 二度几点 x 个,一度节点y个, 则叶子节点个数(设为z)?

N个节点,那么共有树枝N – 1个

1个二度节点有2个树枝,叶子没有,一度节点有1个,那么推导出一共有 2x + y 个

2x + y = N – 1;

x   + y + z = N;

由以上两式得出,z = x + 1;

完毕。

叶子节点的个数=二度节点的个数+1

二叉树(一)——基础

数据结构可基于数组或链表实现,就其效率而言,二者各有长短。具体来说,前一实现方式允许我们通过下标或者秩,在常数的时间内找到目标对象;然而,一旦需要对这类结构进行修改,那么无论是插入还是删除,都需要耗费线性的时间。反之,后一实现方式允许我们借助引用或位置对象,在常数的时间内插入或删除元素;但是为了找到居于特定次序的元素,我们却不得不花费线性的时间,对整个结构进行便利查找。能够将这两个结构的有点结合起来,并回避其不足呢?本系列所要讨论的树结构,将正面回答这一问题。

有趣的是,作为树的特例,二叉树实际上并不失一般性。无论就逻辑结构还是算法功能而言,任何有根有序的多叉树,都可等价地转化并实现为二叉树。

从图论的角度看,树等价与连通无环图。沿每个节点v到根root的唯一路径所经过的数目,称作v的深度。依据深度排序,可对所有节点做分层归类。特别地,约定根节点的深度为0,故属于第0层。

任一节点v在通往根节点所经过的每个节点都是祖先(ancestor),v是它们的后代(descendant)。特别的,v的祖先/后代包括其本身,而v本身以外的祖先/后代称作真祖先(proper ancestor)/真后代(proper descendant)。

无孩子的节点称作叶节点(leaf),包括根在内的其余节点皆为内部节点(internal node)。

树T中所有节点深度的最大值为该树的高度。特别地,仅含单个节点的树的高度为0,空树高度为-1。

剑指Offer: 面试题3:数组中重复的数字

题目1

找出数组中重复的数字。

在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3. Read more

面向对象编程

面向对象编程的三个特性

  1. 数据抽象:实现了接口(interface)与实现(implementation)的分离;
  2. 继承:指明了相似类之间的关系;
  3. 动态绑定:在一定程度上忽略了相似类型之间的区别,而以统一的方式使用它们的对象。具体调用基类还是派生类的函数需要在运行时才能确定。在C++中,当我们使用基类的引用或指针调用一个虚函数时将发生动态绑定。(函数的参数是(const) baseClass & 或者 (const) baseClass *),e.g.
    // caculate and print the price for the given number of copies, applying any discounts
    double print_total(ostream &os, const Quote &item, size_t n)
    {
        // depending on the type of the object bound to the item parameter
        // calls either Quote::net_price or Bulk_quote::net_price
        double ret = item.net_price(n);
        os << "ISBN: " << item.isbn() // calls Quote::isbn
           << " # sold: " << n << " total due: " << ret << endl;
    }

    Read more