0%

字典树, 又称单词查找树, Trie树, 是一种树形结构, 是一种哈希树的变种. 典型应用是用于统计, 排序和保存大量的字符串(但不仅限于字符串), 所以经常被搜索引擎系统用于文本词频统计.
它的优点是: 利用字符串的公共前缀来节约存储空间, 最大限度地减少无谓的字符串比较, 查询效率比哈希表高.
字典树与字典很相似, 当你要查一个单词是不是在字典树中, 首先看单词的第一个字母是不是在字典的第一层, 如果不在, 说明字典树里没有该单词, 如果在就在该字母的孩子节点里找是不是有单词的第二个字母, 没有说明没有该单词, 有的话用同样的方法继续查找.
字典树不仅可以用来储存字母, 也可以储存数字等其它数据.

Read more »

动态规划的核心思想

其核心思想同分治法相似, 即将一个问题分解成若干个子问题; 通过递归地求解子问题的值并合并子问题得到该问题的最终解.但是动态规划和分治法最大的差别在于, 分治法得到的子问题是相互独立的, 而动态规划的子问题之间是相互联系的.

适用情况

能采用动态规划求解的问题的一般要具有3个性质:

  • 最优化原理: 如果问题的最优解所包含的子问题的解也是最优的, 就称该问题具有最优子结构, 即满足最优化原理.
  • 无后效性: 即某阶段状态一旦确定, 就不受这个状态以后决策的影响. 即状态以后的的过程不会影响该状态.
  • 有重叠子问题: 即子问题之间不是相互独立的, 一个子问题的下一个阶段的决策中可能被多次用到.
Read more »

Stock Problems

在刷题过程中遇到股票买卖一类的问题,把该类问题归类为线性查找的subarray问题,一般方法有two pointer, greedy, dynamic programming等。下面对该类题型进行总结和拓展。

Stock Problem I

给定一列整数数组,表示每天股票的价格,求多次交易使得获利最大,有两个条件

  • 卖出在买入之后
  • 买入之后只有卖出之后才可再买入

For Example, given an array [1, 4, 3, 8, 4, 3, 1, 3, 6, 9]
The max profit can made is 16.

1
2
3
4
5
6
7
8
9
10
11
// 典型的贪心算法,增长买入不增长卖出。
public static int calMax (int nums) {
int sum = 0;
for (int i = 1; i < nums.length; i++) {
int diff = nums[i] - nums[i-1];
if (diff > 0) {
sum += diff;
}
}
return sum;
}

时间复杂度O(N),空间复杂度O(1)

Read more »

二分法

二分法的两个前提条件

  • 数组有序
  • 以数组的形式储存

满足二分法的条件并使用二分法会使搜索变得很快(O(log(N)), 但是同时也有不少的问题

  • 无序数组无法使用
  • 由于是数组, 插入删除变得很低效

二分法刷题的时候注意点

  1. while (lo ? hi)这里?号的使用, 根据不同的情况进行调整
  2. mid = lo + (hi - lo) / 2 or mid = hi - (hi - lo) / 2. 一方面这种形式可以防止溢出, 另一方面不同的写法决定了corner case的时候lo和hi的指向.
  3. 更新lo和hi的值, 要知道更新的意义是什么.
  4. 判断循环什么什么时候停止, 已经停止后lo和hi指针指向的数字.

下面是对二分法出现的场景的总结.

Read more »

The best way to learn is trying it. HERE is a interactive website link.

Git is a distributed revision control and source code management system with an emphasis on speed. Git was initially designed and developed by Linus Torvalds for Linux kernel development.

Installation

1
$ sudo apt-get install git-core

Configure

1
2
$ git config --global user.name [name]
$ git config --global user.email [email]

Create and Initialize Repository

1
2
3
$ mkdir git_folder
$ cd git_folder
$ git init
Read more »

Tree traversals

常见的三种树的遍历:pre-order traversal, in-order traversal, post-order traversal.

1
2
3
4
5
    1
/ \
2 3
/ \
4 5

Pre-order

for any node, root - left - right
上述的树遍历的结果是:1 2 4 5 3

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static List<Integer> preOrderTraversal (TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}

private static void helper(TreeNode root, List<Integer> res) {
if (root == null) {
return;
}

res.add(root.val);
helper(root.left, res);
helper(root.right, res);
}
Read more »

今天刚考完CSCI 571的Final,把这几天整理的资料传上来。

Map Reduce

  1. MapReduce was developed at Google
  2. Hadoop is an open source implementation of MapReduce
  3. Assumptions
    • Files are distributed
    • Files are rarely updated, often read and sometimes appended to
    • Files are divided into chunks and chunks are replicated
  4. What Map reduce provide
    • Automatic parallelization of code & distribution across - multiple processors
    • Fault tolerance in the event of failure of one or more nodes
    • I/O scheduling
    • Monitoring & Status updates
  5. The Map/Reduce Paradigm
    • Records are broken into segments
    • Map: extract something of interest from each segment
    • Group and sort intermediate results from each segment
    • Reduce: aggregate intermediate results
    • Generate final output
  6. Map
    • The master controller process knows how many Reduce tasks there will be, say r.
    • Map tasks turn the chunk into a sequence of k-v pairs by applying Map function.
    • Each k-v pair will be put into r files. (depends on hash of their keys)
  7. Reduce
    • keys are divided among all the Reduce tasks, so all key-value pairs with the same key wind up at the same Reduce task
    • output from all reduce tasks are merged into a single file.
    • *The Reduce function is generally associative and commutative implying values can be combined in any order yielding the same result
  8. Coping with Node Failure
    • Master is executing fail
      • Restart map-reduce job
    • Map worker fails
      • The Master detect and sets the status of each Map task to idle and re-schedules them when a worker becomes available
    • Reduce worker fails
      • The Master detect and sets the status of its currently executing Reduce tasks to idle and they will be re-scheduled on another reduce worker later
Read more »

刚好复习考试的时候出现了Edit Distance这个概念而这个概念又比较重要,在面试和应用中都有一席之地。因此抽出了一点时间总结一些这个算法。

编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数,如果它们的距离越大,说明它们越不同。这些操作包括

  • 插入一个字符,例如:fj -> fxj
  • 删除一个字符,例如:fxj -> fj
  • 替换一个字符,例如:jxj -> fyj

算法的应用很广泛,例如用于DNA序列检查,字符的拼写和纠正,抄袭的侦测等等。

Read more »

Permutation 类题目的解法

在面试和刷题中,有遇到很多permutation,其大致的就是数列的全排列。下面针对全排列对LeetCode上面此类题型进行一下总结。

解题基本思路

Read more »

Sort总结

在计算机科学与数学中, 一个排序算法是一种能将一串数据依照特定排序方式进行排列的一种算法. 下面针对常见的排序进行一个总结.

Bubble Sort 冒泡排序

冒泡排序是最基础的排序方法, 其过程可分为以下步骤

  • 比较相邻的元素. 如果第一个比第二个大, 就交换他们两个.
  • 对每一对相邻元素作同样的工作, 从开始第一对到结尾的最后一对. 这步做完后, 最后的元素会是最大的数.
  • 针对所有的元素重复以上的步骤, 除了最后一个.
  • 持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对数字需要比较.
Read more »