归并排序

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

def merge_sort(a):
def merge_array(a, i, j):
if i >= j:
return a

def merge(a, left_i, left_j, right_i, right_j):
new_a = []
i, j = left_i, right_i
while i <= left_j and j <= right_j:
if a[i] <= a[j]:
pos = i
i += 1
else:
pos = j
j += 1
new_a.append(a[pos])

if i <= left_j:
new_a.extend(a[i:left_j+1])

if right_i <= right_j:
new_a.extend(a[j:right_j+1])

a[left_i:right_j+1] = new_a

mid = i + (j - i) // 2
merge_array(a, i, mid)
merge_array(a, mid+1, j)
merge(a, i, mid, mid+1, j)
return a

return merge_array(a, 0, len(a)-1)

if __name__ == "__main__":
print(merge_sort([1, 3, 2, 4, 6, 8, 7]))
print(merge_sort([8]))
print(merge_sort([9, 8, 7, 4, 3, 2, 0]))
print(merge_sort([9, 10, 12, 14, 13, 22, 100]))

查找第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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p215 file
Author: zhangxiaoan 00565442
Create: 2021/4/30 16:19
"""

def top_k(nums, k):
def partition(nums, left, right):
if left >= right:
return 1

sel = nums[right]
pos = left-1
start = left
while start < right:
if nums[start] > sel:
pos += 1
if start != pos:
tmp = nums[pos]
nums[pos] = nums[start]
nums[start] = tmp
start += 1
pos += 1
nums[pos], nums[right] = sel, nums[pos]
return pos - left + 1

def quick_find(nums, left, right, k):
m = partition(nums, left, right)
if m == k:
return nums[left + m - 1]

if m > k:
return quick_find(nums, left, left + m - 2, k)
else:
return quick_find(nums, left + m, right, k - m)
return quick_find(nums, 0, len(nums)-1, k)

if __name__ == "__main__":
print(top_k([1], 1))
print(top_k([3, 1, 2, 4], 2))
print(top_k([3, 2, 1, 5, 6, 4], 2))
print(top_k([5, 2, 4, 1, 3, 6, 0], 4))

给表达式添加运算符

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
"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p282 file
Author: zhangxiaoan 00565442
Create: 2021/4/29 9:25
"""


def add_operators(num, target):
n = len(num)
ans = []

def gen_expr(num, index, expr, prev_op, prev_value, value):
nonlocal n, target, ans

start = num[index]
end = index
while end < n:
val = int(num[index:end + 1])
expr.append(prev_op)
expr.append(num[index:end + 1])


if prev_op == '+':
next_val = value + val
if prev_op == '-':
next_val = value - val
if prev_op == '*':
next_val = value + prev_value * val

if end == n - 1:
if next_val == target:
ans.append("".join(expr[1:]))

expr.pop()
expr.pop()
return

if prev_op == '+':
gen_expr(num, end + 1, expr, "*", val, value)
elif prev_op == '-':
gen_expr(num, end + 1, expr, "*", -val, value)
else:
gen_expr(num, end + 1, expr, "*", prev_value * val, value)


gen_expr(num, end + 1, expr, "+", 0, next_val)
gen_expr(num, end + 1, expr, "-", 0, next_val)
expr.pop()
expr.pop()

if start == '0':
break

end += 1

gen_expr(num, 0, [], "+", 0, 0)
return ans


if __name__ == "__main__":
print(add_operators("123", 6))
print(add_operators("232", 8))
print(add_operators("105", 5))
print(add_operators("00", 0))
print(add_operators("3456237490", 9191))
print(add_operators("134562379", 134562379))
print(add_operators("123456789", 45))

查找两个有序数组的中位数


def find_media_sorted_arrays(nums1, nums2):
    m, n = len(nums1), len(nums2)

    def find_kth(nums1, nums2, k):
        m, n = len(nums1), len(nums2)
        if m < n:
            return find_kth(nums2, nums1, k)

        if n == 0:
            return nums1[k-1] 

        if k == 1:
            return min(nums1[0], nums2[0])

        m2 = min(n, (k+1)//2)
        m1 = k - m2
        if nums1[m1-1] < nums2[m2-1]:
            return find_kth(nums1[m1:], nums2, k - m1)
        else:
            return find_kth(nums1, nums2[m2:], k - m2)
        

    total = m + n
    if total % 2 != 0:
        return find_kth(nums1, nums2, total//2 + 1)
    else:
        return (find_kth(nums1, nums2, total//2) + find_kth(nums1, nums2, total//2 + 1))/2

    
if __name__ == "__main__":
    print(find_media_sorted_arrays([1, 3], [2]))
    print(find_media_sorted_arrays([1, 2], [3, 4]))

求数组的逆序度

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

"""
Copyright (c) Huawei Technologies Co., Ltd. 2021-2021. All rights reserved.
Description: easy_ut p_offer_51 file
Author: zhangxiaoan 00565442
Create: 2021/4/28 17:38
"""
def merge_reverse(nums, i, j):
if j < i:
return [], 0

if i == j:
return nums[i:i+1], 0

mid = i + (j-i)//2
left, left_num = merge_reverse(nums, i, mid)
right, right_num = merge_reverse(nums, mid+1, j)

new_nums, reverse = [], 0
n_left, n_right = len(left), len(right)
n_i, n_j = 0, 0
while n_i < n_left and n_j < n_right:
if left[n_i] <= right[n_j]:
new_nums.append(left[n_i])
n_i += 1
else:
new_nums.append(right[n_j])
reverse += n_left - n_i
n_j += 1

new_nums.extend(left[n_i:])
new_nums.extend(right[n_j:])

return new_nums, reverse + left_num + right_num


def reversePairs(nums):
return merge_reverse(nums, 0, len(nums)-1)[1]

if __name__ == "__main__":
print(reversePairs([7, 5, 6, 4]))
print(reversePairs([1, 3, 2, 3, 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

def quick_sort(a):
def quick_sort_array(a, i, j):
if i >= j:
return a

def partition(a, i, j):
pos = i
while i < j:
if a[i] < a[j]:
if i != pos:
a[pos], a[i] = a[i], a[pos]
pos += 1
i += 1
a[pos], a[j] = a[j], a[pos]
return pos


k = partition(a, i, j)
quick_sort_array(a, i, k-1)
quick_sort_array(a, k+1, j)
return a

return quick_sort_array(a, 0, len(a)-1)

if __name__ == "__main__":
print(quick_sort([1, 3, 2, 4, 5, 8, 7, 0]))
print(quick_sort([1]))
print(quick_sort([]))
print(quick_sort([9, 8, 7, 3, 2, 0]))
print(quick_sort([9, 18, 27, 33, 42, 50]))

动态规划

dp动态规划

解决问题

通常用于解决最优化问题,通常做出一组选择来达到最优解.

特点

  • 做出每个选择时,通常会生成与原问题形式相同的子问题
  • 多于一个选择子集都会生成相同的子问题(子问题重叠)

关键技术

  • 对每个相同的子问题保存其解,当其重复出现时避免重复求解
  • 通常可将指数时间的算法转换为多项式级别的算法

步骤

  1. 刻画一个最优解的结构特征
  2. 递归地定义最优解的值
  3. 计算最优解的值,通常采用自底向上的方法
  4. 利用计算出的信息构造一个最优解

典型问题

算法导论

钢条切割
求两个序列的最长公共子序列
构造最优二叉搜索树

antlr4实现一个计算器--python语言

使用antlr4实现一个计算器

antlr4简介

antlr4是一款强大的语法分析器生成工具,我们可以使用antlr4分析处理各种可以用语法描述的文本(代码,配置文件,报表,json文本),还可以用来实现DSL.

antlr4能够为我们定义的语法生成AST(一种描述语法与输入文本匹配关系的数据结构),还能够自动生成遍历AST的代码,使我们可以专注于业务逻辑实现.antlr4支持生成各种语言的代码,因此我们可以根据熟悉的语言实现业务功能.

本文章通过实现一个计算器来直观的感受一下antlr4如何使用.

定义语法规则

antlr4语法文件以g4为后缀,可以在一个文件中同时定义词法和语法.

  • 词法以全大写表示
  • 语法以全小写表示.
  • 首行使用grammar声明语法名称,需要和文件名完全一致.
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
grammar LabeledExpr;

prog: stat+;

stat: expr NEWLINE # printExpr
| ID '=' expr NEWLINE # assign
| NEWLINE #blank
;

expr: expr op=('*' | '/') expr # MulDiv
| expr op=('+' | '-') expr # AddSub
| INT #int
| ID #id
| '(' expr ')' #parens
;

MUL : '*';
DIV : '/';
ADD : '+';
SUB : '-';

ID : [a-zA-Z]+ ;
INT : [0-9]+ ;
NEWLINE : '\r'? '\n';
WS : [ \t]+ -> skip;

解释一下:

  • prog: stat+; 定义了一个prog语法,程序是由1个或多个语句构建,antlr4支持类似正则的语法,(+表示一个或多个). ‘|’表示或的关系.
  • stat: 定义语句的语法,语句可以是表达式,赋值或者换行.
  • expr: 定义表达式的语法,表达式可以是两个表达式的乘除,加减,或者是一个整数,一个变量,或者带括号的表达式. antlr4支持上下文无关方法,可以处理左递归,因此我们可以递归定义语法.
  • “#”: #号开关的属于antlr4标签,通过定义标签可以让antlr4为每个备选分支都生成一个遍历方法,否则antlr4只为expr这种语法生成一个遍历方法.
  • MUL,DIV,ADD,SUB: 定义词法的名字,通过定义名字使我们可以在代码中通过这些名字来引用具体的单词.
  • ID,INT,NEWLINE: 定义变量和整型的词法.
  • WS: 定义空白符词法, ->skip为antlr4的指令,表示丢弃当前的单词(每个输入的字符都至少被一条词法规则匹配)

生成代码

本文以Python代码举例,antlr4本身使用java语言编写,可以生成不同的目标语言

1
antlr4 -no-listener -visitor -Dlanguage=Python3 -o python3 LabeledExpr.g4
  • -Dlanguage: 定义输出的目标语言,这里是Python3
  • -o:指定代码输出路径
  • -no-listener -visitor: antlr4默认为处理AST生成监听器代码,这里我们不使用监听器方式而是使用visitor(访问者模式)方式来遍历AST.

通过上述命令antlr4为我们生成以下代码:

  1. LabeledExprParser.py: 语法分析器代码,每条语法规则都有对应的处理方法.
  2. LabeledExprLexer.py: 词法分析器代码
  3. LabeledExpr.tokens: 词法符号对应的数字类型
  4. LabeledExprVisitor.py: 语法分析树的访问器,每条语法和标签都有对应的访问方法,通过实现里面的方法实现业务功能.

编写处理逻辑

1.首先编写visitor实现处理逻辑

代码比较容易理解,就不再详细展开.定义了一个vars字典用来存储定义的变量,然后在对应的语法里获取相应的数据并计算.

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
class LabeledExprVisitor(ParseTreeVisitor):
def __init__(self):
self.vars = {}

# Visit a parse tree produced by LabeledExprParser#prog.
def visitProg(self, ctx:LabeledExprParser.ProgContext):
return self.visitChildren(ctx)


# Visit a parse tree produced by LabeledExprParser#printExpr.
def visitPrintExpr(self, ctx:LabeledExprParser.PrintExprContext):
value = self.visit(ctx.expr())
print(value)
return 0


# Visit a parse tree produced by LabeledExprParser#assign.
def visitAssign(self, ctx:LabeledExprParser.AssignContext):
var = ctx.ID().getText()
value = self.visit(ctx.expr())
self.vars[var] = value
return value


# Visit a parse tree produced by LabeledExprParser#blank.
def visitBlank(self, ctx:LabeledExprParser.BlankContext):
return self.visitChildren(ctx)


# Visit a parse tree produced by LabeledExprParser#parens.
def visitParens(self, ctx:LabeledExprParser.ParensContext):
return self.visit(ctx.expr())


# Visit a parse tree produced by LabeledExprParser#MulDiv.
def visitMulDiv(self, ctx:LabeledExprParser.MulDivContext):
left = self.visit(ctx.expr(0))
right = self.visit(ctx.expr(0))
if ctx.op.getType() == LabeledExprParser.MUL:
return left * right
return left / right


# Visit a parse tree produced by LabeledExprParser#AddSub.
def visitAddSub(self, ctx:LabeledExprParser.AddSubContext):
left = self.visit(ctx.expr(0))
right = self.visit(ctx.expr(1))
if ctx.op.type == LabeledExprParser.ADD:
return left + right
return left - right


# Visit a parse tree produced by LabeledExprParser#id.
def visitId(self, ctx:LabeledExprParser.IdContext):
var = ctx.ID().getText()
if var in self.vars: # use before assignment?
return self.vars[var]
return 0


# Visit a parse tree produced by LabeledExprParser#int.
def visitInt(self, ctx:LabeledExprParser.IntContext):
return int(ctx.INT().getText())

2.编写主程序,将输入与语法分析结合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
caculator.py:

import sys
from antlr4 import *
from LabeledExprLexer import LabeledExprLexer
from LabeledExprParser import LabeledExprParser
from LabeledExprVisitor import LabeledExprVisitor

def main(argv):
input_stream = FileStream(argv[1])
lexer = LabeledExprLexer(input_stream) # 将输入文件交给记法分析器
tokens = CommonTokenStream(lexer) # 将记法分析器传递给token生成一个个单词
parser = LabeledExprParser(tokens) # 将单词传递给语法分析器
tree = parser.prog() # 调用prog语法生成AST

eval = LabeledExprVisitor() # 调用visitor遍历生成的AST
eval.visit(tree)

if __name__ == '__main__':
main(sys.argv)

3.验证程序

输入文本:

1
2
3
4
5
1.text

a=5
b=4
a+b
1
2
3
python3 caculator.py 1.text

输出:9