tonglin0325的个人主页

Python学习笔记——pandas

tonglin0325

官方文档：https://pandas.pydata.org/docs/reference/index.html

1.loc属性，通过标签或布尔数组访问一组行和列。pandas.DataFrame.loc

1
2
3
4
5
6
7
8
9
>>> df = pd.DataFrame([[1, 2], [4, 5], [7, 8]],
...      index=['cobra', 'viper', 'sidewinder'],
...      columns=['max_speed', 'shield'])
>>> df
            max_speed  shield
cobra               1       2
viper               4       5
sidewinder          7       8

获取单个label，返回是一个series

1
2
3
4
5
>>> df.loc['viper']
max_speed    4
shield       5
Name: viper, dtype: int64

获取List of labels。注意使用 [[]] 返回的是一个 DataFrame

1
2
3
4
5
>>> df.loc[['viper', 'sidewinder']]
            max_speed  shield
viper               4       5
sidewinder          7       8

通过行标签和列标签来获得具体值

1
2
3
>>> df.loc['cobra', 'shield']
2

对行进行切片，对列进行单标签切片（取得部分行和部分列）

全文 >>

机器学习——决策树

tonglin0325

1.决策树的构造

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据

缺点：可能会产生过度匹配问题

适用数据类型：数值型和标称型

 

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
# coding:utf-8
# !/usr/bin/env python

'''
Created on Oct 12, 2010
Decision Tree Source Code for Machine Learning in Action Ch. 3
@author: Peter Harrington
'''
from math import log
import operator

#通过是否浮出水面和是否有脚蹼，来划分鱼类和非鱼类
def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels

def calcShannonEnt(dataSet):	#计算给定数据集的香农熵
    numEntries = len(dataSet)	#数据集中的实例总数
    labelCounts = {}
    #为所有可能的分类创建字典，键是可能的特征属性，值是含有这个特征属性的总数
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    #计算香农熵
    shannonEnt = 0.0
    #为所有的分类计算香农熵
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2) 	#以2为底求对数
    #香农熵Ent的值越小，纯度越高，即通过这个特征属性来分类，属于同一类别的结点会比较多
    return shannonEnt
    
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]     #chop out axis used for splitting
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet
    
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1      #the last column is used for the labels
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):        #iterate over all the features
        featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
        uniqueVals = set(featList)       #get a set of unique values
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)     
        infoGain = baseEntropy - newEntropy     #calculate the info gain; ie reduction in entropy
        if (infoGain > bestInfoGain):       #compare this to the best gain so far
            bestInfoGain = infoGain         #if better than current best, set to best
            bestFeature = i
    return bestFeature                      #returns an integer

def majorityCnt(classList):
    classCount={}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0]) == len(classList): 
        return classList[0]#stop splitting when all of the classes are equal
    if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]       #copy all of labels, so trees don't mess up existing labels
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree                            
    
def classify(inputTree,featLabels,testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    if isinstance(valueOfFeat, dict): 
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else: classLabel = valueOfFeat
    return classLabel

def storeTree(inputTree,filename):
    import pickle
    fw = open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close()
    
def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)
    
    
if __name__ == '__main__':
    myDat,labels = createDataSet()
    print myDat
    print calcShannonEnt(myDat)

 

 

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
#通过是否浮出水面和是否有脚蹼，来划分鱼类和非鱼类
def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels

def calcShannonEnt(dataSet):	#计算给定数据集的香农熵
    numEntries = len(dataSet)	#数据集中的实例总数
    labelCounts = {}
    #为所有可能的分类创建字典，键是可能的特征属性，值是含有这个特征属性的总数
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    #计算香农熵
    shannonEnt = 0.0
    #为所有的分类计算香农熵
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2) 	#以2为底求对数
    #香农熵Ent的值越小，纯度越高，即通过这个特征属性来分类，属于同一类别的结点会比较多
    return shannonEnt

全文 >>

scyllaDB基本使用

tonglin0325

1.scylla部署

docker单机部署

可以使用docker镜像来启动scyllaDB

docker集群部署

也可以使用docker镜像来部署scyllaDB集群

1
2
3
4
5
6
7
8
docker run --name scylla -p 9042:9042 -p 9160:9160 -p 10000:10000 -p 9180:9180 -v /var/lib/scylla:/var/lib/scylla -d scylladb/scylla

docker run --name scylla-node2 -p 8042:9042 -p 8160:9160 -p 1000:10000 -p 8180:9180 -v /var/lib/scylladb2:/var/lib/scylla -d scylladb/scylla --seeds="$(docker inspect --format='{{ .NetworkSettings.IPAddress }}' scylla)"

docker run --name scylla-node3 -p 10042:9042 -p 10160:9160 -p 1100:10000 -p 10180:9180 -v /var/lib/scylladb3:/var/lib/scylla -d scylladb/scylla --seeds="$(docker inspect --format='{{ .NetworkSettings.IPAddress }}' scylla)"

docker run --name scylla-node4 -p 11042:9042 -p 11160:9160 -p 1200:10000 -p 11180:9180 -v /var/lib/scylladb4:/var/lib/scylla -d scylladb/scylla --seeds="$(docker inspect --format='{{ .NetworkSettings.IPAddress }}' scylla)"

　　

2.在cqlsh中操作scyllaDB

在cqlsh中可以使用CQL (the Cassandra Query Language) 来对scyllaDB做一些基本操作

1
2
3
4
5
6
sh-4.2# cqlsh
Connected to  at 172.17.0.3:9042.
[cqlsh 5.0.1 | Cassandra 3.0.8 | CQL spec 3.3.1 | Native protocol v4]
Use HELP for help.
cqlsh>

参考：CQLSh: the CQL shell

　　

3.scyllaDB的操作

scylla数据存储于table当中，而table由keyspace分组

创建keysapce

名字叫做test

1
2
3
4
5
cqlsh> CREATE KEYSPACE IF NOT EXISTS test WITH REPLICATION = {'class': 'SimpleStrategy','replication_factor':1};
cqlsh> describe keyspaces;

system_schema  system_auth  system  system_distributed  test  system_traces

全文 >>

机器学习——k-近邻算法

tonglin0325

k-近邻算法（kNN）采用测量不同特征值之间的距离方法进行分类。

 

优点：精度高、对异常值不敏感、无数据输入假定

缺点：计算复杂度高、空间复杂度高

使用数据范围：数值型和标称型

 

工作原理：存在一个样本数据集合，也称为训练样本集，并且样本集中每个数据都存在标签，即我们知道样本集中每一数据与所属分类的对应关系。输入没有标签的新数据后，将新数据的每个特征与样本集中数据对应的特征进行比较，然后算法提取样本集中特征最相似数据（最近邻）的分类标签。一般来说，我们只选择样本数据集中前k个最相似的数据，这就是k-近邻算法中的k的出处，通常k是不大于20的整数。然后，选择k个最相似数据中出现次数最多的分类，作为新数据的分类。

 

 

kNN.py

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
169
# coding:utf-8
# !/usr/bin/env python

'''
Created on Sep 16, 2010
kNN: k Nearest Neighbors

Input:      inX: vector to compare to existing dataset (1xN)
            dataSet: size m data set of known vectors (NxM)
            labels: data set labels (1xM vector)
            k: number of neighbors to use for comparison (should be an odd number)
            
Output:     the most popular class label

@author: pbharrin
'''

from numpy import *
import operator
from os import listdir


def classify0(inX, dataSet, labels, k):		#inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
    dataSetSize = dataSet.shape[0]	#shape函数求数组array的大小，例如dataSet一个4行2列的数组
    #距离计算
    diffMat = tile(inX, (dataSetSize,1)) - dataSet	#tile函数的功能是重复某个数组，例如把[0,0]重复4行1列，并和dataSet相减
    sqDiffMat = diffMat**2		#对数组中和横纵坐标平方
    #print(sqDiffMat)
    sqDistances = sqDiffMat.sum(axis=1)	#把数组中的每一行向量相加，即求a^2+b^2
    #print(sqDistances)
    distances = sqDistances**0.5	#开根号，√a^2+b^2
    #print(distances)
    #a = array([1.4, 1.5,1.6,1.2])
    sortedDistIndicies = distances.argsort()     #按升序排序，从小到大的下标依次是2,3,1,0	
    #print(sortedDistIndicies)
    classCount={}        #字典
    
    #选择距离最小的k个点  
    for i in range(k):
        voteIlabel = labels[sortedDistIndicies[i]]	#按下标取得标记
        #print(voteIlabel)
        classCount[voteIlabel] = classCount.get(voteIlabel,0) + 1	#在字典中计数
        #print(classCount[voteIlabel])
    #排序
    sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
    #print(sortedClassCount)
    return sortedClassCount[0][0]	#返回计数最多的标记

def createDataSet():
    group = array([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
    labels = ['A','A','B','B']
    return group, labels

def file2matrix(filename):		#处理格式问题，输入为文件名字符串，输出为训练样本矩阵和类标签向量
    fr = open(filename)
    numberOfLines = len(fr.readlines())         #取得文件的行数，1000行
    returnMat = zeros((numberOfLines,3))        #生成一个1000行3列的矩阵
    classLabelVector = []                       #创建一个列表 
    fr = open(filename)
    index = 0					#表示特征矩阵的行数
    for line in fr.readlines():
        line = line.strip()
        listFromLine = line.split('\t')		#将字符串切片并转换为列表
        returnMat[index,:] = listFromLine[0:3]	#选取前三个元素，存储在特征矩阵中
        #print listFromLine
        #print returnMat[index,:]
        classLabelVector.append(int(listFromLine[-1]))	#将列表的最后一列存储到向量classLabelVector中
        index += 1
    return returnMat,classLabelVector		#返回特征矩阵和类标签向量
    
def autoNorm(dataSet):			#归一化特征值
    minVals = dataSet.min(0)		#最小值
    maxVals = dataSet.max(0)		#最大值
    ranges = maxVals - minVals		#范围
    normDataSet = zeros(shape(dataSet))
    m = dataSet.shape[0]
    normDataSet = dataSet - tile(minVals, (m,1))    #原来的值和最小值的差
    normDataSet = normDataSet/tile(ranges, (m,1))   #特征值差除以范围
    return normDataSet, ranges, minVals
   
def datingClassTest():
    hoRatio = 0.10      		#测试数据的比例
    datingDataMat,datingLabels = file2matrix('datingTestSet2.txt')       #load data setfrom file
    normMat, ranges, minVals = autoNorm(datingDataMat)
    m = normMat.shape[0]
    numTestVecs = int(m*hoRatio)
    errorCount = 0.0
    for i in range(numTestVecs):
    	#inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
        classifierResult = classify0(normMat[i,:],normMat[numTestVecs:m,:],datingLabels[numTestVecs:m],3)
        print "分类器的结果: %d, 真正的结果: %d" % (classifierResult, datingLabels[i])
        if (classifierResult != datingLabels[i]): errorCount += 1.0
    print "整体的错误率: %f" % (errorCount/float(numTestVecs))
    print errorCount
    
def classifyPerson():
    resultList = ['不喜欢','一点点','很喜欢']
    percentTats = float(raw_input('请输入玩游戏的时间百分比：'))
    ffMiles = float(raw_input('请输入飞行里程总数：'))
    iceCream = float(raw_input('请输入冰淇淋的升数：'))
    datingDateMat,datingLabels = file2matrix("datingTestSet2.txt")	#导入数据
    normMat,ranges,minVals = autoNorm(datingDateMat)			#归一化
    inArr = array([ffMiles,percentTats,iceCream])
    classifierResult = classify0((inArr-minVals)/ranges,normMat,datingLabels,3)	#分类的结果
    print "喜欢的程度：",resultList[classifierResult-1]
    
def img2vector(filename):		#把32×32的二进制图像矩阵转换为1×1024的向量
    returnVect = zeros((1,1024))
    fr = open(filename)
    for i in range(32):
        lineStr = fr.readline()
        for j in range(32):
            returnVect[0,32*i+j] = int(lineStr[j])
    return returnVect

def handwritingClassTest():
    #准备训练数据
    hwLabels = []
    trainingFileList = listdir('digits/trainingDigits')    #导入训练数据集合
    m = len(trainingFileList)
    trainingMat = zeros((m,1024))
    #和m个训练样本进行对比
    for i in range(m):				
        fileNameStr = trainingFileList[i]
        fileStr = fileNameStr.split('.')[0]     	#取得去掉后缀名的文件名
        classNumStr = int(fileStr.split('_')[0])	#取得文件名中代表的数字
        hwLabels.append(classNumStr)			#由文件名生成标签向量
        trainingMat[i,:] = img2vector('digits/trainingDigits/%s' % fileNameStr)	#输入的训练样本集
    #准备测试数据
    testFileList = listdir('digits/testDigits')        #iterate through the test set
    errorCount = 0.0
    mTest = len(testFileList)
    #预测测试样本
    for i in range(mTest):
        fileNameStr = testFileList[i]
        fileStr = fileNameStr.split('.')[0]     	#取得去掉后缀名的文件名
        classNumStr = int(fileStr.split('_')[0])	#取得文件名中代表的数字
        vectorUnderTest = img2vector('digits/testDigits/%s' % fileNameStr)	#用于分类的输入向量
        #inX是用于分类的输入向量，dataSet是输入的训练样本集，labels是标签向量，k是选择最近邻居的数目
        classifierResult = classify0(vectorUnderTest, trainingMat, hwLabels, 3)
        print "分类器的结果: %d, 真实的结果: %d" % (classifierResult, classNumStr)
        if (classifierResult != classNumStr): errorCount += 1.0
    print "\n预测的错误数是: %d" % errorCount
    print "\n预测的错误率是: %f" % (errorCount/float(mTest))
    
if __name__ == '__main__':
#	#group,labels = createDataSet()
#	#classify0([0,0],group,labels,3)
#	datingDateMat,datingLabels = file2matrix("datingTestSet2.txt")
#	#print datingDateMat
#	#print datingLabels
#	import matplotlib
#	import matplotlib.pyplot as plt
#	fig = plt.figure()
#	ax = fig.add_subplot(111)				#控制位置
#	ax.scatter(datingDateMat[:,1],datingDateMat[:,2],15.0*array(datingLabels),15.0*array(datingLabels))	#点的横纵坐标，大小和颜色
#	#plt.show()
#	
#	normMat,ranges,minVals = autoNorm(datingDateMat)
#	print normMat
#	print ranges
#	print minVals

#	datingClassTest()
#	classifyPerson()
#	testVector = img2vector("digits/testDigits/0_0.txt")
#	print testVector[0,0:31]
	handwritingClassTest()

 

全文 >>

机器学习——分类和回归

tonglin0325

1.机器学习的主要任务：
一是将实例数据划分到合适的分类中，即分类问题。 而是是回归， 它主要用于预测数值型数据，典型的回归例子：数据拟合曲线。

 

2.监督学习和无监督学习：

分类和回归属于监督学习，之所以称之为监督学习，是因为这类算法必须直到预测什么，即目标变量的分类信息。

 

对于无监督学习，此时数据没有类别信息，也不会给定目标值。在无监督学习中，将数据集合分成由类似的对象组成的多个类的过程被成为聚类；将寻找描述数据统计值的过程称之为密度估计。此外，无监督学习还可以减少数据特征的维度，以便我们可以使用二维或者三维图形更加直观地展示数据信息。

 

3.线性回归和非线性回归

　　线性回归需要一个线性模型。一个线性的模型意味着模型的每一项要么是一个常数，要么是一个常数和一个预测变量的乘积。一个线性等式等于每一项相加的和。等式：

Response = constant + parameter * predictor + … + parameter * predictor　　<=>　　Y = b o + b1X1 + b2X2 + … + bkXk

在统计学中，如果一个回归方程是线性的，那么它的参数必须是线性的。但是可以转换预测变量加上平方，来使得模型产生曲线，比如 Y = b o + b1X1 + b2X12

这时模型仍然是线性的，虽然预测变量带有平方。当然加上log或者反函数也是可以的。

全文 >>

Hive学习笔记——beeline

tonglin0325

使用beeline连接hive

1
2
3
kinit -kt xxx.keytab xxx
beeline -u "jdbc:hive2://10.65.13.98:10000/default;principal=hive/_HOST@CLOUDERA.SITE"

参考：

1
2
https://docs.cloudera.com/runtime/7.2.7/securing-hive/topics/hive_remote_data_access.html

如果要想直接运行SQL，可以

1
2
beeline -u "jdbc:hive2://10.65.13.98:10000/default;principal=hive/_HOST@CLOUDERA.SITE" --silent=true --outputformat=tsv2 --showHeader=false -e "select * from xxx.xxx"

退出beeline

1
2
!quit

IDEA的kubernetes插件使用

tonglin0325

1.在IDEA或者pycharm中安装kubernets插件

 

2.使用kubernetes插件

在view的Tool windows中点击service

可以看到docker和kubernetes的管理界面

 

 可以切换context，从而在不同k8s集群之间切换

多个k8s集群的配置文件默认在

1
2
/Users/lintong/.kube/config

全文 >>

Java数据结构——字典树TRIE

tonglin0325

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

 

下面是字典树数据的Java实现代码，字典树中存放的是26个英文字母

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
package coding_Interview_guide.ch5;

class trie {
    // 根节点
    private TrieNode root;

    public trie() {
        super();
        this.root = new TrieNode();
    }

    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chs = word.toCharArray();
        TrieNode node = root;
        int index = 0; // root的map[TrieNode]数组的下标
        for (char ch : chs) {
            index = ch - 'a';
            if (node.map[index] == null) {
                node.map[index] = new TrieNode();
            }
            node = node.map[index]; // 转到下一个字符的节点
            node.path++; // 公用节点树加1
        }
        node.end++; // 结尾
    }

    public boolean search(String word) {
        if (word == null) {
            return false;
        }
        char[] chs = word.toCharArray();
        TrieNode node = root;
        int index = 0; // root的map[TrieNode]数组的下标
        for (char ch : chs) {
            index = ch - 'a';
            if (node.map[index] == null) {
                return false;
            } else {
                node = node.map[index];
            }
        }
        return node.end != 0;
    }

    public void delete(String word) {
        if (search(word)) {
            char[] chs = word.toCharArray();
            TrieNode node = root;
            int index = 0; // root的map[TrieNode]数组的下标
            for (char ch : chs) {
                index = ch - 'a';
                if (node.map[index].path-- == 1) { // 最后一个节点的公用节点数减一,同时如果只有一个公用节点的话,直接置为null
                    node.map[index] = null;
                    return;
                }
                // 否则继续下一个节点
                node = node.map[index]; // 转到下一个字符的节点
            }
            node.end--; // 结尾数减一
        }
    }

    public int prefixNumber(String pre) {
        if (pre == null) {
            return 0;
        }
        char[] chs = pre.toCharArray();
        TrieNode node = root;
        int index = 0; // root的map[TrieNode]数组的下标
        for (char ch : chs) {
            index = ch - 'a';
            if (node.map[index] == null) {
                return 0;
            }
            node = node.map[index];
        }
        return node.path;
    }
}

class TrieNode {
    public int path; // 表示有多少个单词公用这个节点
    public int end; // 表示有多少个单词以这个节点结尾
    public TrieNode[] map;

    public TrieNode() {
        super();
        this.path = 0;
        this.end = 0;
        this.map = new TrieNode[26];
    }
}

public class Trie {

    public static void main(String[] args) {
        // TODO 自动生成的方法存根
        trie t = new trie();
        
    }

}

 

tonglin0325

标签

标签云

AWS Airbnb Android CDH Doris ELK Flink Git Grafana HAProxy HBase Hadoop Hive Hudi InfluxDB JDBC JMeter JVM Java LaTex Linkedin Linux ML ML Infra MPP Maven MySQL Nexus OpenTSDB Paper Play Prometheus Python React Redis RocksDB Scala Solr Spark SpringBoot SpringMVC Thrift YARN antlr arthas avro cassandra clickhouse confluent docker filebeat flume golang google gradle hexo impala jenkins k8s kafka kerberos kudu ldap mac mongo mybatis nginx nlp open-falcon openwrt parquet presto ranger rocketmq scyllaDB twitter zookeeper 刷题 前端 图存储及计算 多线程 广告系统 开发工具 数据结构 杂谈 算法 系统设计 计算机基础 设计模式

文章归档

最近文章