MENU

线索二叉树

一:背景

  线索二叉树的定义为:一个二叉树通过如下的方法“穿起来”:所有应该为空的右孩子指针指向该节点在中序序列中的后继,所有应该为空的左孩子指针指向该节点的中序序列的前驱。
  那么在有N个节点的二叉树中共有N+1个空指针,这些空指针就叫做“线索”。(补充:在N个节点的二叉树中,每个节点有2个指针,所以一共有2N个指针,将这N个节点连接起来需要N-1条线,即使用了N-1个指针。所以剩下2N-(N-1)=N+1个空指针。)
  那线索二叉树有何妙用呢?由于巧妙地利用了空指针,所以它可以快速地查找到二叉树中某节点的前驱和后继。接下来具体介绍这个数据结构。
  在进行下文之前,约定如下:




Read More

二叉树基础

一:前言

  本文主要讲解以下二叉树的4个部分:
  (1)构造二叉树;
  (2)前,中,后序遍历(递归与非递归)和层次遍历;
  (3)求节点数;
  (4)求叶子数。
  在此先约定下二叉树的节点结构和类的结构:






Read More

01背包问题

一:问题

  有$N$件物品和一个容量为$V$的背包。第$i$件物品的体积是$C_i$,其价值是$W_i$。求解,在不超过背包容量情况下,将哪些物品装入背包可使价值总和最大。

二:基本思路

  这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。
  状态 $F[i,v]$表示前$i$件物品恰放入一个容量为$v$的背包可以获得的最大价值。
  转移方程 $F[i,v]=\max \{F[i−1,v],F[i−1,v−C_i]+W_i\}$
对于第$i$件物品,有放与不放两种选择。若选择不放,$F[i,v]=F[i−1,v]$;若选择放,$v−C_i$确保有足够的空间,随之$F[i,v]=F[i−1,v−C_i]+W_i$。




Read More

二分查找(面试必备)

  在计算机科学中,二分搜索(binary search),也称折半搜索(half-interval search)、对数搜索(logarithmic search),是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

Read More

扩展KMP算法

  前文已经介绍了经典的KMP算法,本文继续介绍KMP算法的扩展,即扩展KMP算法。
  问题定义:给定两个字符串S和T(长度分别为n和m),下标从0开始,定义extend[i]等于S[i]...S[n-1]与T的最长公共前缀的长度,求出所有的extend[i]。举个例子,看下表:

i01234567
Saaaaabbb
extend[i]54321000
Taaaaac

  为什么说这是KMP算法的扩展呢?显然,如果在S的某个位置i有extend[i]等于m,则可知在S中找到了匹配串T,并且匹配的首位置是i。而且,扩展KMP算法可以找到S中所有T的匹配。接下来具体介绍下这个算法。


Read More

size_t,微尘下的bug

  这个问题是我在写KMP时遇到的,考虑到并不是每位读者都了解这个算法,这里我简化下问题,请看下面的代码,并猜测其输出什么:

string str = "123456";

if (-1 < str.size())
    cout << "win\n";
else
    cout << "lose\n";

  你的答案是win,是么?那么很遗憾的告诉你,NO,答案是;lose!!!
  为何?其实很简单的问题,类型不一致。
  -1默认为intsize()返回类型为size_tunsigned int



Read More

KMP算法

一:背景

  给定一个主字符串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,即串的模式匹配问题。今天来介绍解决这一问题的常用算法之一,Knuth-Morris-Pratt 算法(简称 KMP),这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终由三人于1977年联合发表。
  在继续下面的内容之前,有必要在这里介绍下两个概念:前缀后缀


由上图所得, "前缀"指除了最后一个字符以外,一个字符串的全部头部组合;"后缀"指除了第一个字符以外,一个字符串的全部尾部组合。




Read More

C++函数指针

  函数指针可以像一般函数一样,用于调用函数、传递参数。在如C++这样的语言中,通过提供一个简单的选取、执行函数的方法,函数指针可以简化代码。函数指针只能指向具有特定特征的函数。因而所有被同一指针运用的函数必须具有相同的参数和返回类型。下面具体分析。

Read More

Title - Artist
0:00