发表于 | | 阅读次数:

散列表的基本思想是将关键字（key）通过散列函数映射到表中的一个位置，在查找的时候只要通过关键字就可以直接获取对应位置的值。那么主要的问题就是如何设计散列函数和如何在不同的关键字映射到同一位置的时候处理冲突。注意我们现在讨论的存放的仅仅是关键字，实际情况存放的是关键字+值。

阅读全文 »

发表于 | | 阅读次数:

find命令

find命令可以用来遍历文件目录
基本形式 find pathname -option [-print -exec]
pathname:要查找的文件目录，.代表当前目录
查找完成后可以执行的action：

  • -print打印到标准输出
  • -exec：对有匹配的文件执行指定的参数命令，{}来代表查到的当前的文件名，一般格式为
  • -exec commod {} \;最后要加分号
    阅读全文 »

发表于 | | 阅读次数:

原题回顾：打印当前文件夹下所有的.txt文件的最后一行到新文件newFile.txt中
其答案最后解答如下

1
2
3
4
5
6
7
8
#!/bin/bash
for file in `ls .`
do
if [ -f $file ] && [[ $file =~ .*\.txt ]]
then
tail -1 $file >> newFile.txt
fi
done

阅读全文 »

发表于 | | 阅读次数:

什么是伸展树？

首先，伸展树(splay tree)是一颗二叉搜索树，它的定义是建立在二叉搜索树之上，并且它是基于类似程序局部性原理的假设：一个节点在一次被访问后，这个节点很可能不久再次被访问。那么伸展树的做法就是在每次一个节点被访问后，我们就把它推到树根的位置。正像程序局部性原理的实际效率被广泛证明一样，伸展树在实际的搜索效率上也是非常高效的。尽管存在最坏情况下单次操作会花费O(N)的时间，但是这种情况并不是经常发生，而实际证明伸展树能够保证M次连续操作最多花费O(MlogN)的时间。

相比于平衡二叉树，伸展树有差不多的平均性能，其他的优势在于：不需要存储平衡信息。另外如果采用自顶向下的调整方式，还能简略额外的栈开销。

阅读全文 »

发表于 | | 阅读次数:

什么是AVL树？

AVL树，又称为平衡二叉树，它是一种特殊的二叉查找树（Binary Search Tree, BST），其每一个节点的左右子树的高度差不超过1。

注意，一个节点的高度是从该节点到叶子节点的最长路径，所以，叶子节点的高度为0,而深度是指一个节点到树根的路径长度，两者是相反的概念。 一棵树的高度等于根节点的高度，而深度等于最大深度的叶子节点的深度，所以一个树的高度和深度是相同的。

阅读全文 »

发表于 | | 阅读次数:

ArrayList和LinkedList的实现方式

ArrayList的底层实现是可以增长的数组，LinkedList的底层是使用了双链表。从底层实现来看，我们可以知道，ArrayList 获取元素的时间复杂度仅为常数，而 插入和 删除的时间复杂度都为线性时间复杂度O(n)。而LinkedList则刚好相反，因为底层是链表,所以 插入和 删除的时间复杂度为常数，而 获取元素的时间复杂度却是线性时间复杂度。

另外，ArrayList和LinkedList的contains和remove方法的时间复杂度都为线性时间复杂度O(n)，对于contains方法来说，ArrayList和linkedList都需要遍历操作来实现contains方法，所以时间复杂度都是线性的；对于remove操作，ArrayList删除后需要移动元素，所以时间复杂度是线性的，而LinkedList的remove操作虽然是常数时间的，但是查找到元素的时间复杂度是线性的，所以，对已LinkedList的remove操作来说也是线性时间复杂的。

阅读全文 »

发表于 | | 阅读次数:

一些术语

  1. 参数化类的类型（parameterized type）:含有类型参数的类型，例如List<String>
  2. 原生态类型（raw type）:没有类型参数的类型，例如List
  3. 无限制通配符类型（unbounded wildcard type）:例如List<?>
阅读全文 »