所谓全排列就是将一个数据组合拆开重新排列,比如 abc,可重新排序为 acb、bac、bca、cab、cba,通过算法上实现一般就是递归或一个while循环来实现。最近复习算法方面的内容接触到的新的算法,记录一下思路。

Continue reading

JavaScipt 数组的一些常用操作,高级语言这些优点就是好,给数组排序一个 sort 就搞定了,在 C 下要自己写算法。真的是大大节省了时间。

var arr = new Array("html", "body", "head", "title", "style", "script", "span", "title");
// 在尾部插入元素
arr.push("ul");
console.log("push", arr);
// 弹出尾部最后一个元素
arr.pop();
console.log("pop", arr);
// 在首部插入一个元素
arr.unshift("dt");
console.log("unshift", arr);
// 弹出首部第一个元素
arr.shift();
console.log("shift", arr);
// 按字典序(ASCII)排序
arr.sort();
console.log("sort", arr);
// 翻转数组
arr.reverse(arr)
console.log("reverse", arr);
// 返回数组指定位置的几个元素
console.log("slice", arr.slice(2, 4));
// 在数组中首次出现的位置
console.log("indexOf", arr.indexOf("title"));
// 在数组中最后一次出现的位置
console.log("lastindexOf", arr.lastIndexOf("title"));

一个数组,如果有个20个元素,但有效元素只有不到5个,剩下的全部是 undefined,此时使用 for 遍历的话,所有元素都会被遍历出来,包括 undefined,但如果使用 for in 则不会出现这种情况,for in 只会遍历出有效的元素,并且与 for 不同的时,for in 可以遍历出数组的成员属性。我们看如下代码和打印的结果。Continue reading

开始恶补 JavaScript 的基础知识,数组篇。

// 第一种
var color = ["red", "black", "gold", "pink"];
console.log(color);
// 第二种
var animal = new Array("dog", "pic", "cat");
console.log(animal);
// 第三种
var city = Array();
city[0] = "北京";
city[1] = "上海";
city[2] = "杭州";
city["henan"] = "郑州"; // 给 city 对象声明一个成员属性 henan,并非数组元素
console.log(city);
console.log(city[1]);
console.log(city.henan);
console.log(city["河南"]);

注意最后的 city[“henan”] = “郑州”,并不是给数组添加一个元素,而是给 city 这个数组对象添加了一个成员属性。在计算数组长度的时候,它不被算在内。

屏幕快照 2015-11-04 下午19.32.42 下午

 

二叉树细分了两种类型的二叉树,一种叫做“满二叉树”,就是每一层都挂满了节点,没有空位。另一种叫做“完全二叉树”,完全二叉树假设有n层,那么n-1层和满二叉树是一样的,但是第n层最后一个节点前边都挂满了节点。这是它们两个概念的唯一具体区别。表示图如下:

【满二叉树】

2015-06-01_223256

【完全二叉树】

2015-06-01_223801

上面的树符合最后一个节点(F节点)前都挂满了节点的规则,所以它属于一个完全二叉树。下面重点来了,二叉树具有5大性质,如下介绍。

【二叉树的五大性质】

  • 性质1: 在二叉树的第i层上至多有2i-1个结点(i>0)。
    比如第3层,那么就是 23-1 = 4,第3层最多有4个节点

 

  • 性质2: 深度为k的二叉树至多有2k-1个结点(k>0)。
    比如第3层,最多有 23 -1 = 7 个节点

 

  • 性质3: 对于任何一棵二叉树,若2度的结点数有n2个,则叶子数(n0)必定为n2+1 (即n0=n2+1)
    度为2的节点有3个(A B C),那么 n2 = 3
    叶子数 = n2 + 1,那么就是 3 + 1 = 4 个

 

  • 性质4: 具有n个结点的完全二叉树的深度必为log2n(向下取整)+1
    log2n + 1 转换为公式是
    2x = n,此时 n 为 7 ,所以 x 约等于 2.几次方,向下取整后得 2
    深度 = x + 1,2 + 1 = 3,所以深度结果就是3

 

  • 性质5: 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,其左孩子编号必为2i,其右孩子编号必为2i+1;其双亲的编号必为i/2(i=1 时为根,除外)。
    如下图:编号为3的节点是C,其左子节点的编号是2*3=6就是F,右子节点的编号是2*3+1=7就是G,双亲的编号是 3/2=1就是A

2015-06-01_224246

最后我们做一下总结,讲了这么多,无非我们就是希望引出二叉树是有规则的,我们将二叉树存入一个数组后,是可以恢复回来的,不像多叉树那样无法恢复。根据第五条的性质,我们很轻松就可以在一个存放在数组中的二叉树数据恢复为一个二叉树模型。

而如果是一个非满二叉树怎么办呢?我们如何把非满二叉树存放到一个数组里面呢?其实思路非常简单,我们只需把哪些缺少一个子节点的节点给他填充一个空就可以了。如下图:

2015-06-03_232545

在搞清楚多叉树转换为二叉树之前,我们有必要想清楚,为什么要这样转换?多叉树哪里有缺点需要我们转换为二叉树使用?我们来考虑一个问题:“如果我们将一个多叉树存放在一个数组中,然后删除了整个多叉树。我们能否通过这个仅有的数组恢复原来的多叉树呢?”Continue reading

我本想将 STL 中各种容器的实现方法和作用全部写一遍,然后每种容器都发一篇文章,但后来发现这样做的意义不大,在 MSDN 或其他一些帮助文档中,他们比我写的要详细,其实我只需要记住每种容器的常用方法,和在什么场合选择合适的容器。下面这张表是我这里的一些常用方法集合。备用参考。Continue reading