leeyupeng

leeyupeng@126.com

0%

发表于 更新于 分类于 ， 阅读次数： Valine：

计算器

题目

- leetcode 224. 基本计算器

语法树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
class Solution {
  public:

  	//词素
  	struct morpheme
  	{
  		long digital;
  		char operatorcharacter;
  		int type;
  		int priority = -1;

  		morpheme(int t, int d, char o,int p)
  		{
  			type = t;
  			digital = d;
  			operatorcharacter = o;
  			priority = p;
  		}

  		morpheme()
  		{
  		}
  	};

  	struct SyntaxTreeNode
  	{
  		int index;
  		//long value;
  		SyntaxTreeNode * parent;
  		SyntaxTreeNode * left;
  		SyntaxTreeNode * right;

  		SyntaxTreeNode(int idx)
  		{
  			index = idx;
  		}
  	};
      void scanning(const string str, vector<morpheme>& v)
  	{
          char morphemetype[6] = { ')','+','-','*','/','(' };
  	    int morphemetypelength = 6;

  		long digit = 0;
  		int len = str.length();
  		for (int i = 0; i < len; i++)
  		{
  			char c = str[i];
              if (c == ' ')
  			{
  				continue;
  			}
  			bool flag = false;
  			for (int j = 0; j < morphemetypelength; j++)
  			{
  				if (c == morphemetype[j])
  				{
  					v.push_back(morpheme(j, 0, c,j));
  					flag = true;
  				}
  			}

  			if (flag == false)
  			{
  				digit = digit * 10 + (int)c - 0x30;

  				if (i == len - 1 || (str[i + 1] < '0' || str[i + 1] > '9'))
  				{
  					v.push_back(morpheme(-1, digit, '\0',-1));
  					digit = 0;
  				}
  			}
  		}
  	}
      SyntaxTreeNode* syntaxtree(vector<morpheme>& v)
  	{
  		SyntaxTreeNode* root = new SyntaxTreeNode(-1);
  		SyntaxTreeNode* pre = NULL;
  		pre = root;

  		for (int i = 0; i < v.size(); i++)
  		{
  			SyntaxTreeNode* node = new SyntaxTreeNode(i);

  			int priority = v[i].priority;
  			if (priority == -1)
  			{
  				pre->right = node;
  				node->parent = pre;
  				continue;
  			}
  			SyntaxTreeNode* smallnode = pre;
  			while (smallnode->index != -1)
  			{
  				if (v[smallnode->index].priority == 5)
  				{
  					break;
  				}
  				if (v[smallnode->index].priority >= priority)
  				{
  					smallnode = smallnode->parent;
  				}
  				else
  				{
  					break;
  				}
  			}

  			node->left = smallnode->right;
  			smallnode->right = node;
  			node->parent = smallnode;


  			if (v[node->index].priority == 0 && smallnode->index != -1 && v[smallnode->index].priority == 5)
  			{
  				pre = smallnode->parent;
  			}
  			else
  			{
  				pre = node;
  			}
  		}

  		return root;
  	}
      int order(SyntaxTreeNode* node, vector<morpheme>& v)
  	{
  		int value;
  		int priority = v[node->index].priority;
  		if (priority == -1)
  		{
  			value = v[node->index].digital;
  		}
  		else if (priority == 0)
  		{
  			value = order(node->left, v);
  		}
  		else if (priority == 1)
  		{
  			value = order(node->left, v) + order(node->right, v);
  		}
  		else if (priority == 2)
  		{
  			value = order(node->left, v) - order(node->right, v);
  		}
  		else if (priority == 3)
  		{
  			value = order(node->left, v) * order(node->right, v);
  		}
  		else if (priority == 4)
  		{
  			value = order(node->left, v) / order(node->right, v);
  		}
  		else if (priority == 5)
  		{
  			value = order(node->right, v);
  		}

  		//node->value = value;
  		return value;
  	}
      int calculate(string s) {
          vector<morpheme> v;
          scanning(s,v);
          SyntaxTreeNode* tree = syntaxtree(v);
          int result = order(tree->right,v);
          return result;
      }
};
阅读全文 »

发表于 更新于 分类于 ， ， 阅读次数： Valine：

线段树(Segment Tree)

描述

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。
而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。

线段树是建立在线段的基础上，每个结点都代表了一条线段[a,b]。长度为1的线段称为元线段。非元线段都有两个子结点，左结点代表的线段为[a,(a + b) / 2]，右结点代表的线段为[((a + b) / 2）+1,b]。
下图就是两棵长度范围为[1,5][1,10]的线段树。
长度范围为[1,L] 的一棵线段树的深度为log (L) + 1。这个显然，而且存储一棵线段树的空间复杂度为O(L）。
线段树支持最基本的操作为插入和删除一条线段。下面以插入为例，详细叙述，删除类似。
将一条线段[a,b] 插入到代表线段[l,r]的结点p中，如果p不是元线段，那么令mid=（l+r）/2。如果bmid，那么将线段[a,b] 也插入到p的右儿子结点中。
插入（删除）操作的时间复杂度为O（logn）。

空间压缩

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

KMP算法

next函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//优化过后的next 数组求法  
void GetNextval(char* p, int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀    
        if (k == -1 || p[j] == p[k])  
        {  
            ++j;  
            ++k;  
            //较之前next数组求法，改动在下面4行  
            if (p[j] != p[k])  
                next[j] = k;   //之前只有这一行  
            else  
                //因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，k = next[k] = next[next[k]]  
                next[j] = next[k];  
        }  
        else  
        {  
            k = next[k];  
        }  
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int KmpSearch(char* s, char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
}

正则表达式 模式匹配 静态KMP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
vector<int> GetNextval(string p)
{
  int pLen = p.length();
  vector<int> next(pLen, 0);
  next[0] = -1;
  int k = -1;
  int j = 0;

  while (j < pLen - 1)
  {
    if (p[j] == '*')
    {
      k = j;
      ++j;
      next[j] = k;
    }
    else if (k == -1 || (p[j] == p[k] || p[j] == '?' || p[k] == '?' || p[j] == '*' || p[k] == '*'))
    {
      ++j;
      ++k;
      if (p[j] != p[k] || p[j] == '?' || p[k] == '?' || p[j] == '*' || p[k] == '*')
      {
        next[j] = k;
      }
      else
      {
        if (k != 0 && p[k - 1] == '*')
        {
          next[j] = k - 1;
        }
        else
        {
          next[j] = next[k];
        }
      }
    }
    else
    {
      k = next[k];
    }
  }
  return next;
}
阅读全文 »

发表于 更新于 阅读次数： Valine：

string

string metric

string searching algorithm

multiple string searching

regular expression

sequence alignment

data structure

题目

正则表达式

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

正则表达式

  • 1.字符串s是否可以匹配字符串p
  • 2.字符串s匹配到的字符串p的子字符串信息

模式匹配

字符串s是否可以匹配字符串p
isMatch(s,p)

动态规划

阅读全文 »