algorithm

[xiyoulaoyuanjia]

字符串匹配算法

kmp 算法

sunday 算法

后缀树 算法

[xiyoulaoyuanjia]

后缀树几点应用

• 一个字符串在另一个字符串中出现了几个次?
• 一个字符串中的最长重复序列
• 字符串匹配问题
• 两个字符串的最长公共部分 方案:将S1#S2$作为字符串压入后缀树,找到最深的非叶节点,且该节点的叶节点既有#也有$

[xiyoulaoyuanjia]

T(N) = N + T(N/2)+T(2N), 问T(N)的时间复杂度是多少?

O(N*logN) or O(N)? 这是一道 主定理的题目.可以参考这里

[xiyoulaoyuanjia]

平均要取多少个(0,1)中的随机数才能让和超过1?

[xiyoulaoyuanjia]

非递归遍历一颗树

先序遍历树

void preOrder(TNode* root) { if (root != NULL) { Visit(root); preOrder(root->left); preOrder(root->right); } }

非递归遍历树

// 先序遍历伪代码：非递归版本，用栈实现，版本1 void preOrder1(TNode* root) { Stack S; while ((root != NULL) || !S.empty()) { if (root != NULL) { Visit(root); S.push(root); // 先序就体现在这里了，先访问，再入栈 root = root->left; // 依次访问左子树 } else { root = S.pop(); // 回溯至父亲节点 root = root->right; } } }

[xiyoulaoyuanjia]

动态规划求不相邻的最大子数组和

有N个节点，每两个节点相邻，每个节点只与2个节点相邻，因此，N个顶点有N-1条边。每一条边上都有权值wi，定义节点i到节点i+1的边为wi。
求：不相邻的权值和最大的边的集合。

#include   
#include   
#include   
using namespace std;  

#define NMax 1000  

int data[NMax];  
int table[NMax][2];  

int GetMaxSubsetSum(int len)  
{  
    memset(table, 0 , sizeof(table));  
    //第0行表示NS，表示该元素未被选中  
    //第一行表示DS，表示该元素被选中  
    table[0][0] = 0;  
    table[0][1] = data[0];  

    //动态规划 过程  
    for (int i = 1; i < len; ++i)  
    {  
        table[i][0] = max(table[i-1][1], table[i-1][0]);  
        table[i][1] = table[i-1][0] + data[i];  
    }  

    //打印原始数组  
    for (int i = 0; i < len; ++i)  
        cout << data[i] <<"\t";  
    cout <> len;  
    if (len <= 0)return 1;  
    for (int i = 0; i < len ; ++i)  
    {  
        data[i] = rand()% 10;  
    }  

    cout << GetMaxSubsetSum(len)<