最长子串问题

问题描述

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.

Continue reading 最长子串问题

SkipList

概述

Skip list(也称跳表)是一种随机化数据结构,基于并联的链表,其效率可比拟二叉查找树(对于大多数操作需要O(log n)平均时间)。

基本上,Skip list是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表,因此得名。所有操作都以对数随机化的时间进行。一个基本的Skip list结构如下:

Continue reading SkipList