分类目录:算法和数据结构

最长子串问题

问题描述 Given a string, find the length of the longest substring without repeating characters. Examples: Given “abcabcbb”, the answer is “abc”, which the length is 3. Given “bbbbb”, the answer is “b”, with the length of 1. Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

SkipList

概述 Skip list(也称跳表)是一种随机化数据结构,基于并联的链表,其效率可比拟二叉查找树(对于大多数操作需要O(log n)平均时间)。 基本上,Skip list是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表,因此得名。所有操作都以对数随机化的时间进行。一个基本的Skip list结构如下: