longbo233-CSDN博客

原创 120. 三角形最小路径和

题目给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。（相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1的两个结点。）例如，给定三角形：[[2],[3,4],[6,5,7],[4,1,8,3]]题目分析题目要求求出自顶向下的最小路径和，这是一道典型的动态规划题型。提到动态规划首先要找出推导公式：最小的上层路径+自己代表的路径用 f[i][j] 表示从(0,0)到(i,j)的最小路径，c[i][j] 表示自己代表的路径。则有：

2020-07-14 09:51:56 133

原创编译原理——语法分析

语法分析的任务：分析一个文法的句子的结构语法分析器的功能：按照文法的产生式(语言的语法规则) , 识别输入符号串是否为一个句子(合式程序)语法分析器在编译原理中占主导地位语法分析大概分为两类：自下而上(Bottom-up)从输入串开始,逐步进行归约，直到文法的开始符号归约:根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号从树叶节点开始,构造语法树算符优先分析法、LR分析法自上而下(Top-down)从文法的开始符号出发,反复使用各种产生式,寻找"匹配"的推导推

2020-06-03 14:39:13 1869

原创 101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/symmetric-tree著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。将数组转换为二叉树，在进行判断：public class TreeNode { public int data;/

2020-05-31 21:45:41 208

原创编译原理词法分析（三）

NFA与DFA的等价性对于每一个NFA M都有一个DFA M,使得L(M)=L(M,)等价性证明思路：NFA与DFA的区别NFADFA初始状态不唯一唯一弧上标记字(单字符字、ε)字符转换关系非确定确定假定NFA M=<S, E, δ, So, F> ,我们对M的状态转换图进行以下改造:1.解决初始状态唯一性引进新的初态结点X和终态结点Y , X,Y∉S ,从X到S0中任意状态结点连一条:箭弧，从F中任意状态结点连一条:箭弧到Y。

2020-05-31 17:00:20 1849 1

原创 84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。示例:输入: [2,1,5,6,2,3]输出: 10来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。1.暴力解法public int largestRectangleArea

2020-05-31 11:10:29 123

原创 198. 打家劫舍

题目你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。示例 1:输入: [1,2,3,1]输出: 4解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。偷窃到的最高金额 = 1 + 3 = 4 。示例 2:输入:

2020-05-29 12:07:25 176

原创 394. 字符串解码

题目给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。示例:s = “3[a]2[bc]”, 返回 “aaabcbc”.s = “3[a2[c]]

2020-05-28 22:19:43 265

转载编译原理词法分析（二）

正规式与正规集正规式与正规集的关系：正规集可以用正规式表示正规式是表示正规集一种方法一个字集合是正规集当且仅当它能用正规式表示什么是正规式与正规集：对给定的字母表Σε和Ø都是Σ上的正规式,它们所表示的正规集为{ε}和Ø；任何a∈Σ , a是Σ上的正规式,它所表示的正规集为{a}；假定e1和e2都是Σ上的正规式,它们所表示的正规集为L(e1)和L(e2) ,则(e1|e2)为正规式 ,它所表示的正规集为L(e1)UL(e2)(e1.e2)为正规式 ,它所表示的正规集为L(e1)

2020-05-28 16:45:36 825

原创 974. 和可被 K 整除的子数组

题目给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。示例：输入：A = [4,5,0,-2,-3,1], K = 5输出：7解释：有 7 个子数组满足其元素之和可被 K = 5 整除：[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]力扣上的题目，看了几个小时看懂了。基本所有的坑都踩到了。来看看我的解题思路吧！解题思路我们要养成这样一个习惯一看到

2020-05-28 08:12:14 180

原创编译原理词法分析（一）

词法分析（一）词法分析器(Lexical Analyzer)1.扫描器(Scanner)2.执行词法分析的程序功能输入源程序、输出单词符号单词符号的种类基本字: 如begin,repeat,for……标识符: 用来表示各种名字,如变量名、数组名和过程名常数: 各种类型的常数运算符:+,-,*,/,……界符: 逗号、分号、括号和空白词法分析器的输出输出的单词符号的表示形式(单词种别,单词自身的值)单词种别通常用整数编码表示若一个种别只有一个单词符号,则种别编码就代表该单词符号

2020-05-26 15:09:56 3282

原创编译原理（二）

文法与语言文法: 描述语言的语法结构的形式规则例如：He gave me a book几个基本概念字母表: 一个有穷字符集,记为Σ字母表中每个元素称为字符Σ中的字符所构成的任何一个有穷序列称为字符串不包含任何字符的序列称为空字符串,记为εΣ*表示Σ上的所有字的全体,包含空字ε例如:设Z={a，b},则Σ*={ε,a,b,aa,ab,ba,bb,aaa……}如果字符串x中有m个字符，则称其长度为m，表示为|x|=m例如：|ε|=0Σ* 的子集U和V的连接(积)定义为UV={ αβ

2020-05-23 18:04:05 901

原创编译原理（一）

什么是编译程序？编译程序(Compiler)：把某一种高级语言程序等价地转换成另- -种低级语言程序(如汇编语言或机器语言程序)的程序。解释程序(Interpreter)：把源语言写的源程序作为输入,但不产生目标程序,而是边解释边执行源程序。编译过程编译过程分为6个阶段分别是：词法分析、语法分析、语义分析、中间代码产生、优化、目标代码生成。词法分析词法分析是编译过程的第一个阶段。这个阶段的任务是输入源程序,对构成源程序的字符串进行扫描和分解,识别出单词符号。再依据构词规则把单词符号分为标识符

2020-05-21 15:47:10 4411

longbo233的博客