MENU

Manacher算法

一:背景

  给定一个字符串,求出其最长回文子串。例如:
  (1)s="abcd",最长回文长度为 1;
  (2)s="ababa",最长回文长度为 5;
  (3)s="abccb",最长回文长度为 4,即 bccb。
  以上问题的传统思路大概是,遍历每一个字符,以该字符为中点向两边查找。其时间复杂度为$O(n^2)$,很不高效。而在1975年,一个叫Manacher的人发明了一个算法,Manacher算法,也称马拉车算法,该算法可以把时间复杂度提升到$O(n)$。下面来看看马拉车算法是如何工作的。





Read More

表达式求值

一:前言

  所谓表达式求值,就是写一个微型计算器。例如输入:(1+9)* 2 / 2 - 1,输出9。对于这样的问题,我们一般利用栈,模拟数学运算来完成。为了简化问题,在继续下面的分析之前,先在此作个约定:本文只讨论+-*/()基本的四则运算,另外不对意外出现的符号(例如^)和不符合规范的数学表达式(例如2*-1)做异常处理。

Read More

单链表操作(面试必看)

一:前言

  本篇不会涉及基础知识,我默认来到这里的读者已经掌握何谓链表,何谓链表的头结点等基础概念。
  单链表经常为公司面试所提及,先不贬其过于简单,因为单链表确实是数据结构中最简单的一部分,但往往最简单的,人们越无法把握其细节。
  本文一共总结了单链表常被提及的八种操作,如下:
  (1)逆序构造单链表;
  (2)链表反转;
  (3)链表排序;
  (4)合并两个有序链表;
  (5)求出链表倒数第k个值;
  (6)判断链表是否有环;
  (7)删除当前节点;
  (8)找出链表的中间节点。
  在此先约定下链表的节点结构和链表类的结构:












Read More

Brackets(续)

  Brackets是一个开源的前端编辑器,个人比较喜爱,下面列举下自己所用的插件。因为其插件扩展访问太慢,所以下载插件建议去Brackets Extension Registry

一: Beautify-格式化代码

  安装好后,在代码区,鼠标右击即可进行Beautify操作。

二:Emmet-前端必备

  下载地址为:https://github.com/emmetio/brackets-emmet#readme。但是安装好后发现无法使用,百度了下找到了解决方案。另外Emmet使用教程可以参考https://www.zhihu.com/question/26890730

Read More

位运算总结

一:i+(~i)=-1

  证明 对于一个有符号位类型为int的i为例,假设其为正数,则~i为其取反,则i+(~i)后其32位二进制都是1,即为-1。

二:计算n+1与n-1

2.1 -~n==n+1

  证明 对于一个有符号位类型为int的n为例,假设其为正数,则~n为其取反,符号-再对其取反并加1。

2.2 ~-n==n-1

  证明 首先思考如何把32位二进制转化为其值-1,思路就是找到其低位的第一个1,对其取反并把该位后的所有位也取反,即1000变为0111

三:取相反数

  思路就是取反并+1,也即~n + 1或者(n ^ -1) + 1

Read More

算法复杂度分析概要

一:渐近符号

1.1 符号的辨析

1.1.1 符号$O$

  $O$,读作“大O”,非正式来说,$O(g(n))$是增长次数小于等于$g(n)$及其常数倍($n$趋向于无穷大)的函数集合。
  定义 如果函数$f(n)$包含在$O(g(n))$中,记作$f(n)∈O(g(n))$(平时使用为了方便书写,我们通常使用$f(n)=O(g(n))$代替)。它的成立条件是:对于所有足够大的$n$,$f(n)$的上界由$g(n)$的常数倍所确定,也就是说,存在大于0的常数$c$和非负整数$n_0$,使得:

<p style="text-align:center">对于所有的$n≥n_0$来说,$f(n)≤c(g(n)$</p>

  下图说明了这个定义:



Read More

BFPRT算法(TOP-K问题)

一:背景介绍

  在一大堆数中求其前$k$大或前$k$小的问题,简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是BFPRT算法,又称为中位数的中位数算法,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,其最坏时间复杂度为$O(n)$。
  在首次接触TOP-K问题时,我们的第一反应就是可以先对所有数据进行一次排序,然后取其前$k$即可,但是这么做有两个问题:
  (1)快速排序的平均复杂度为$O(nlogn)$,但最坏时间复杂度为$O(n^2)$,不能始终保证较好的复杂度。
  (2)我们只需要前$k$大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。
  除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为$k$的堆,时间复杂度为$O(nlogk)$。
  那是否还存在更有效的方法呢?我们发现,通过修改快速排序中主元的选取方法可以降低快速排序在最坏情况下的时间复杂度(即BFPRT算法),并且我们的目的只是求出前$k$,故递归的规模变小,速度也随之提高。下面来简单回顾下快速排序的过程,以升序为例:
  (1)选取主元(首元素,尾元素或一个随机元素);
  (2)以选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;
  (3)分别对左边和右边进行递归,重复上述过程。
  而BFPRT算法主要是修改上述过程的第(1)步而已,接下来再看下BFPRT算法的过程。










Read More

Title - Artist
0:00