快速排序 快速排序是一种分治策略的排序算法，是由英国计算机科学家Tony Hoare发明的， 该算法被发布在1961年的Communications of the ACM 国际计算机学会月刊。 注：ACM = Association for Computing Machinery，国际计算机学会，世界性的计算机从业员专业组织，创立于1947年，是世界上第一个科学性及教育性计算机学会。 快速排序是对冒泡排序的一种改进，也属于交换类的排序算法。 一、算法介绍 快速排序通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 步骤如下： 先从数列中取出一个...阅读全文
现在还有一个问题，在最后一个进程运行完之后，还会再打印一次输出 package main import "fmt" type Process struct { //定义进程的数据结构 PRIORITY int CPUTIME int ALLTIME int STATE string } func main() { PR := map[int]*Process{ //初始进程 0: &Process{ PRIORITY: 9, CPUTIME: 0, ALLTIME: 3, STATE: "ready", }, 1: &Process{ PRIORITY: 38, CPUTIME: 0, ALLTIME: 2, STATE: "ready", }, 2: &Process{ PRIORITY:...阅读全文
理简单选择排序应该是最直观最容易理解的排序方法了。直接从头开始一个一个去比，找出最小的放到最左边。再依次完成其他位的排序。 时间复杂度比较次数固定为O(n^2)，数据交换次数是0~n-1次因为会交换不同位置相同数值的数据，所以选择排序并不稳定 代码实现 package main import ( "fmt" ) func main() { var length = 10 var mm = make(map[int]int, length) var o []int // 先准备一个顺序随机的数(qie)组(pian) for i := 0; i < length; i++ { mm[i] = i } for k, _ := range mm { o = append(o, k) } fmt.P...阅读全文
今日去被大佬问到如何实现一个敏感词的匹配,所以写了一个简版的敏感词匹配结构,还待后期优化! **注:暂时不可以投放到生产环境使用** **有喜欢的可以提交代码给我,或者拿走自己维护** 希望各位大佬指点 谢谢~, 关键词为网上找到的所以不是很全,望大家海涵~谢谢! 源码地址:https://github.com/tianye/sensitive_words 源码实现方式: ``` package decision import ( "fmt" "strings" ) type Node struct { Word string Node [] *Node Location int IsSensitive bool } type Tree struct { TreeNode [] *Node ...阅读全文
Home Menu 解析器眼中的 Go 语言 02 Feb 2019 Golang Go实现原理 编译原理 词法分析 语法分析 抽象语法树 词法分析 lex Go 语法分析 文法 分析方法 自顶向下 自底向上 Lookahead Go 辅助方法 节点 总结 相关文章 Reference 代码其实就是按照约定格式编写的一堆字符串，工程师可以在脑内对语言的源代码进行编译并运行目标程序，这是因为经过训练的软件工程师能够对本来无意义的字符串进行分组和分析，按照约定的语法来理解源代码。既然工程师能够按照一定的方式理解和编译 Go 语言的源代码，那么我们如何模拟人理解源代码的方式构建一个能够分析编程语言代码的程序呢。 我们在这一节中将介绍词法分析和语法分析这两个非常重要的编译过程，这两个过程的主要作用就...阅读全文
示例代码（含测试）在这里 需求 在甘特图的场景下，我们经常会遇到这种情况，五位员工A, B, C, D, E，可能他们的工作都是并行的，我们需要计算某段时间内他们总的工作时长。 我们不能简单得把五个人的工作时间都加起来，因为当中会有重叠的部分。所以这时候我们就需要一个计算时间交并集的工具。 思路 将一组离散的时间段按照开始时间，从小到大排序。像这样 [{2 7} {4 11} {10 19} {10 30} {16 18} {19 29} {23 35} {24 42} {25 30} {27 49}] 我这里将时间用十分小的秒来代替，方便理解。 循环排序后的数组，如果下一个时间段开始时间介于上个时间段的开始时间和结束时间之间，那么就进行合并，否则就分离。可以看到我们这里有两个关键动作，合并...阅读全文
Go语言关键字range可以作用在array，string，slice，map和channel五种数据结构上...阅读全文
本文讨论复合数据类型。C++中复合数据类型只有数组和结构体，Go中增加了两种复合数据类型slice和map。Go中的数组和结构体与C++的没有差别，都是聚合结构。数组是由同构的元素组成，结构体是由异构的元素组成，二者都有固定大小的内存。slice与map则是动态的数据结构，它们将根据需要动态增长。本文主要讨论slice和map...阅读全文
package main import "github.com/sanity-io/litter" // slice增删改查,很实用 func main() { var sliceInt []int // init sliceInt = append(sliceInt, []int{1, 2, 3, 4}...) litter.Dump(sliceInt) // remove index 0 sliceInt = append(sliceInt[:0], sliceInt[1:]...) litter.Dump(sliceInt) sliceInt = append(sliceInt, []int{5,6,7,8,9,10}...) litter.Dump(sliceInt) // remo...阅读全文
range 迭代各种各样的数据结构。 range遍历数组示例： package main import "fmt" func main() { rangeTest() } // range func rangeTest() { var arr = []int{12, 3, 2, 12, 3, 2, 31} for k, v := range arr { fmt.Println("数组输出的key,value为：",k, v) } } 结果是： 输出的key,value为： 0 12 输出的key,value为： 1 3 输出的key,value为： 2 2 输出的key,value为： 3 12 输出的key,value为： 4 3 输出的key,value为： 5 2 输出的key,val...阅读全文
Go 语言的项目结构 一般,一个 Go 项目在 GOPATH 下，会有如下三个目录 . ├── bin // 存放编译后的可执行文件 ├── pkg // 存放编译后的包文件 └── src // 存放项目源文件 一般情况下，bin 和 pkg 目录可以不创建，go 命令会自动构建（如 go install），只需要创建 src 目录即可。 Go 程序的一般结构 // 当前程序的包名 package main // 导入其他包 import "fmt" // 常量的声明 const _PI float64 = 3.14 // 全局变量声明 var title string = "Go 语言学习笔记" // 一般类型声明 type newType int // 结构声明 type Stu...阅读全文
课程目录:01、课程内容综述02、第一章内容概述03、TensorFlow产生的历史必然性04、TensorFlow与JeffDean的那些事05、TensorFlow的应用场景06、TensorFlow的落地应用07、TensorFlow的发展现状08、第二章内容概述09、搭建你的TensorFlow开发环境10、HelloTensorFlow11、在交互环境中使用TensorFlow12、在容器中使用TensorFlow13、第三章内容概述14、TensorFlow模块与架构介绍15、TensorFlow数据流图介绍16、讲张量（Tensor）是什么（上）17、讲张量（Tensor）是什么（下）18、讲变量（Variable）是什么（上）19、讲变量（Variable）是什么（下）20、...阅读全文
学习的golang的练习，推荐学习golang。https://www.liwenzhou.com mian.go 文件 package main import ( "fmt" "os" ) func showAction() { fmt.Println("学生管理系统！") fmt.Println("1. 添加学生信息") fmt.Println("2. 编辑学生信息") fmt.Println("3. 显示学生信息") fmt.Println("4. 退出学生管理系统") } //getInput 获取输入信息 func getInput() *Student { var ( name string id int ages int ) fmt.Println("输入信息") fmt.Pr...阅读全文
https://research.swtch.com/godataWhen explaining Go to new programmers, I've found that it often helps to explain what Go values look like in memory, to build the right intuition about which operations are expensive and which are not. This post is about basic types, structs, arrays, and slices.Basic typesLet's start with some simple examples: The v...阅读全文
_ _ _ _ _ _ _ | (_) | | | | | (_) | | | |_ _ __ | | _____ __| | | |_ ___| |_ | | | '_ \| |/ / _ \/ _` | | | / __| __| | | | | | | < __/ (_| | | | \__ \ |_ |_|_|_| |_|_|\_\___|\__,_| |_|_|___/\__| 1.1 原理 链表与数组都非常基础也非常常用，从底层数据结构上看，数组需要一块连续的内存空间来存储数据，而链表则不需要，链表通过指针将一组零散的内存块串联起来使用。 日常中有三种常见的链表结构： 单向链表 双向链表 循环链表 1.2 分析 对于单链表来说，插入和删除操作的时间复杂度为 $O(1)$。双向链表...阅读全文
哈希表：散列查找 一、线性查找 我们要通过一个键key来查找相应的值value。有一种最简单的方式，就是将键值对存放在链表里，然后遍历链表来查找是否存在key，存在则更新键对应的值，不存在则将键值对链接到链表上。 这种链表查找，最坏的时间复杂度为：O(n)，因为可能遍历到链表最后也没找到。 二、散列查找 有一种算法叫散列查找，也称哈希查找，是一种空间换时间的查找算法，依赖的数据结构称为哈希表或散列表：HashTable。 Hash: 翻译为散列，哈希，主要指压缩映射，它将一个比较大的域空间映射到一个比较小的域空间。 简单的说就是把任意长度的消息压缩到某一固定长度的消息摘要的函数。Hash 算法虽然是一种算法，但更像一种思想，没有一个固定的公式，只要符合这种思想的算法都称 Hash 算法。 散...阅读全文
链接: https://leetcode-cn.com/problems/get-watched-videos-by-your-friends/ 难度：medium 解题思路：广搜找到对应level的所有朋友，然后累加相应的video，最后排序。go语言没有啥priority queue，图简单这里排序用的直接插入排序，有点挫 Golang的数据结构支持太少了，各种都要自己写，真是麻烦。。 func watchedVideosByFriends(watchedVideos [][]string, friends [][]int, id int, level int) []string { visited := map[int]int{} queue := []Person {Person{i...阅读全文
1.3 基本类型 更明确的数字类型命名，支持 Unicode，支持常用数据结构。 常用数据结构 支持八进制、十六进制，以及科学记数法。标准库 math 定义了各数字类型取值范围。 a, b, c, d := 071, 0x1F, 1e9, math.MinInt16 空指针值 nil，而非 C/C++ NULL。 1.4 引用类型 引用类型包括 slice、map 和 channel。它们有复杂的内部结构，除了申请内存外，还需要初始化相关属性。 内置函数 new 计算类型大小，为其分配 零值内存 ，返回指针。而 make 会被编译器翻译成具体的创建函数，由其分配内存和初始化成员结构，返回 对象 而 非指针。 a := []int{0, 0, 0} // 提供初始化表达式。 a[1] = 10...阅读全文
1. if结构 概念：if是用于测试某个条件的语句，如果该条件成立，则会执行if后面由大括号包裹的代码块，否则就会忽略该代码块继续执行后面的语句 其格式如下 if condition { // statement } 2. if-else结构 如果有两个分支就可以在if条件语句的基础上添加else语句 其格式如下 if condition { // statement } else { // statement } 3. 多重if-else结构 多重if-else的格式如下 if condition { // statement } else if condition { // statement } else { // statement } 4. switch结构 switch分支结构如...阅读全文
排序算法 人类的发展中，我们学会了计数，比如知道小明今天打猎的兔子的数量是多少。另外一方面，我们也需要判断，今天哪个人打猎打得多，我们需要比较。 所以，排序这个很自然的需求就出来了。比如小明打了5只兔子，小王打了8只，还有部落其他一百多个人也打了。我们要论功行赏，谁打得多，谁就奖赏大一点。 如何排序呢，怎么在最快的时间内，找到打兔子最多的人呢，这是一个很朴素的问题。 经过很多年的研究，出现了很多的排序算法，有快的有慢的。比如： 插入类排序有：直接插入排序和希尔排序 选择类排序有：直接选择排序和堆排序 交换类排序有：冒泡排序和快速排序 它们的复杂度如下： 稳定性概念 定义：能保证两个相等的数，经过排序之后，其在序列的前后位置顺序不变。（A1=A2，排序前A1在A2前面，排序后A1还在A2前面）...阅读全文
问题地址，难度：Easy 若有错误之处请予以指正:) 问题描述 Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, ...阅读全文
AVL树 二叉查找树的树高度影响了查找的效率，需要尽量减小树的高度，AVL树正是这样的树。 一、AVL树介绍 AVL树是一颗严格自平衡的二叉查找树，1962年，发明者Adelson-Velsky和Landis发表了论文，以两个作者的名字命名了该数据结构，这是较早发明的平衡二叉树。 定义如下： 首先它是一颗二叉查找树。 任意一个节点的左右子树最大高度差为1。 由于树特征定义，我们可以计算出其高度h的上界h<=1.44log(n)，也就是最坏情况下，树的高度约等于1.44log(n)。 假设高度h的AVL树最少有f(h)个节点，因为左右子树的高度差不能大于1，所以左子树和右子树最少节点为：f(h-1)，f(h-2)。 因此，树根节点加上左右子树的节点，满足公式f(h) = 1 + f(h-1) ...阅读全文
type Traversal interface { Traverse() } func main() { traversal := getTraversal() traversal.Traverse() } duck typing 描述事物的外部行为而非内部结构 golang类似duck typing golang中接口是由使用者定义的 实现者只需要实现接口的方法就可以 接口的内部实现 接口中包含实现者的类型和实现者的值/实现者的指针 将实现者赋值给接口变量时有两种方式：值赋值和指针赋值 值赋值是将实现者的值赋给接口的内部变量 指针赋值是将实现者的指针赋值给接口的内部变量 接口的指针赋值只能将实现者的指针赋值给接口变量 接口的值赋值既可以将实现者的指针赋值给接口变量又可以将值赋值给接口变量...阅读全文
什么是 GO 程序 go 程序是一段简单的 UTF-8 编码的以 .go 结尾的文件。 GO 程序结构 package main // 创建一个 main 包，使用关键字 package import "fmt" // 从 Go 标准库中引入 fmt 包，使用关键字 import func main() { // 入口函数 fmt.Println("hello go") // fmt包中 Println 函数 } Go 程序都必须以一个包开头，必须包含一个 main 函数。main 函数是程序的入口函数。 $ go run ./hello.go // 执行 hello.go 文...阅读全文
一、背景 在引入Go Module管理之前，即在Go 版本在1.11之前，项目的框架结构主要是bin、pkg、src，如下的结构应该都比较熟悉 ~/projectname/ bin/ pkg/ src/ mypack/ --项目内容 foo.go bar.go mypack_test.go commpack --三方公共库 comunit.go 正常情况下，如果引入第三方库，有三种引入方式： 一般三方库代码都是需要放在GOPATH的Src路径下面,然后直接引入 import ( "commpack" ) 通过本地相对路径引用的方式，如： import ( "../commpack" ) 引用git源码库的http路径 import ( "github.com/projectname/comm...阅读全文
像鸭子走路，像鸭子叫，那么就是鸭子 描述事物外部行为而非内部结构 严格说go属于结构化类型系统，类似duck typing python c++ 中duck typing （只要retriever 具有get方法即可）但是编译运行才知道错误 def download(retriever r): r.get("www.baidu.com") java 中传入参数必须要实现某个接口，不是duck typing 接口定义 download (使用者) retriever(使用者) golang中接口由使用者定义 typpe assertion n, p := reader.Shape() point := p.(*shp.Point) x := point.X y := point.Y 接口变量里...阅读全文
字典 我们翻阅书籍时，很多时候都要查找目录，然后定位到我们要的页数，比如我们查找某个英文单词时，会从英语字典里查看单词表目录，然后定位到词的那一页。 计算机中，也有这种需求。 一、字典 字典是存储键值对的数据结构，把一个键和一个值映射起来，一一映射，键不能重复。在某些教程中，这种结构可能称为符号表，关联数组或映射。我们暂且称它为字典，较好理解。 如： 键=>值 "cat"=>2 "dog"=>1 "hen"=>3 我们拿出键cat的值，就是2了。 Golang提供了这一数据结构：map，并且要求键的数据类型必须是可比较的，因为如果不可比较，就无法知道键是存在还是不存在。 Golang字典的一般的操作如下： package main import "fmt" func main() { // ...阅读全文
Golang: 思路：最开始的思路接近于枚举法，后来逆向思考了一下，觉得是字典树结构，但是这个实现的效率很低 代码如下： type Words []string func (s Words) Len() int { return len(s) } func (s Words) Less(i, j int) bool { return len(s[i]) > len(s[j]) } func (s Words) Swap(i, j int) { s[i], s[j] = s[j], s[i] } func minimumLengthEncoding(words []string) int { res:=0 sort.Sort(Words(words)) tree:=Trie{} for _,v...阅读全文
题目描述 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构） 思路 1.递归比较两个数的结构。 2.比较A树和B树当前的结点，若A树和B树的值相等，则继续比较它们的左右子树；若不相等，则拿A树的左子树和右子树进行同样的过程。 3.当B树遍历到了空结点，说明B是A的子结构；否则不是A的子结构。 Java代码实现 public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1 == null || root2 == null){ return false; } boolean flag = judge(root1,root2); if(!flag){ flag = HasSubtree...阅读全文
题目描述 给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。 示例 给定的树 s: 3 / \ 4 5 / \ 1 2 给定的树 t： 4 / \ 1 2 返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。 思路 1.递归比较两个数的结构。 2.比较A树和B树当前的结点，若A树和B树的值相等，则继续比较它们的左右子树；若不相等，则拿A树的左子树和右子树进行同样的过程。 3.当A树和B树同时遍历到了空结点，说明B是A的子结构；否则不是A的子结构。 Java代码实现 class Solution { public boolean isSubtree(Tr...阅读全文
go中只有一种循环控制结构， for。 没有do或while循环。 Go的循环有三种形式，只有其中的一种使用分号 for init; condition;post { } //普通的循环 sum := 0 for i := 0; i < 10; i++ { sum += i } for condition {} //和while一样 for {} //死循环 break和continue break可提前退出循环，终止当前的循环, 也可在break后指定标签， 用标签决定哪个循环被终止 //break可提前退出循环，终止当前的循环 for i := 0 ; i < 10 ; i++ { i f i > 5 { break 终止这个循环，只打印 0 到 5 } println(i) } //当...阅读全文
go 的程序控制大致分成三种 if for case 语句 1、 if 循环 if-else 语句之间可以有任意数量的 else if。条件判断顺序是从上到下。如果 if 或 else if 条件判断的结果为真，则执行相应的代码块。 如果没有条件为真，则 else 代码块被执行。 语法结构 if condition{}else if condition{ }else{ } 定义示列 package main import "fmt" func iftest() { score :=61 if score > 60{ fmt.Println("成绩合格") } else if score >90{ fmt.Println("成绩优秀") }else if score<0 { fmt.Print...阅读全文
优先队列及堆排序 堆排序(Heap Sort)由威尔士-加拿大计算机科学家J. W. J. Williams在1964年发明，它利用了二叉堆(A binary heap)的性质实现了排序，并证明了二叉堆数据结构的可用性。同年，美国籍计算机科学家R. W. Floyd在其树排序研究的基础上，发布了一个改进的更好的原地排序的堆排序版本。 堆排序属于选择类排序算法。 一、优先队列 优先队列是一种能完成以下任务的队列：插入一个数值，取出最小或最大的数值（获取数值，并且删除）。 优先队列可以用二叉树来实现，我们称这种结构为二叉堆。 最小堆和最大堆是二叉堆的一种，是一颗完全二叉树（一种平衡树）。 最小堆的性质： 父节点的值都小于左右儿子节点。 这是一个递归的性质。 最大堆的性质： 父节点的值都大于左右儿...阅读全文
Golang: 思路：这题没有好的思路，双重递归吧，第一次拿到所有节点，第二次对所有节点进行递归，看看有没有路径符合题目要求。这里讲下我最初的思路：我最开始想的是，把每一条从根节点到叶子节点的路径都提取出来（以数组的形式），然后去对数组做处理，这样会不会效率高一些。后面思考不难发现，这样如果可以实现，会有很多重复的路径被算进总和。所以，这题可能就只剩下暴力的求解思路了。 再插一句，递归这东西，在树结构里真的是无往不利。 代码如下： func pathSum(root *TreeNode, sum int) int { if root==nil { return 0 } var nodes []TreeNode traverse(root,&nodes) res:=0 for _,v:=ran...阅读全文
冒泡排序 冒泡排序是大多数人学的第一种排序算法，在面试中，也是问的最多的一种，有时候还要求手写排序代码，因为比较简单。 冒泡排序属于交换类的排序算法。 一、算法介绍 现在有一堆乱序的数，比如：5 9 1 6 8 14 6 49 25 4 6 3。 第一轮迭代：从第一个数开始，依次比较相邻的两个数，如果前面一个数比后面一个数大，那么交换位置，直到处理到最后一个数，最后的这个数是最大的。 第二轮迭代：因为最后一个数已经是最大了，现在重复第一轮迭代的操作，但是只处理到倒数第二个数。 第三轮迭代：因为最后一个数已经是最大了，最后第二个数是次大的，现在重复第一轮迭代的操作，但是只处理到倒数第三个数。 第N轮迭代：.... 经过交换，最后的结果为：1 3 4 5 6 6 6 8 9 14 25 49，我...阅读全文
数据结构和算法在计算机科学里，有非常重要的地位。此系列文章尝试使用 Golang 编程语言来实现各种数据结构和算法，并且适当进行算法分析。 我们会先简单学习一下Golang，然后进入计算机程序世界的第一个大门。 系列文章首发于：https://goa.lenggirl.com。 简单入门Golang 我们只学Golang语言的一个子集，足以开展接下来数据结构和算法的实现即可。 一、前言 Golang语言是谷歌Google公司在2007年启动，并在2009年正式发布并开源的高级编程语言。开源地址：https://github.com/golang/go，官网地址：https://golang.org。 Golang语言语法简单，支持多平台交叉编译（Linux/Mac/Windows），支持内存...阅读全文
选择排序 选择排序，一般我们指的是简单选择排序，也可以叫直接选择排序，它不像冒泡排序一样相邻地交换元素，而是通过选择最小的元素，每轮迭代只需交换一次。虽然交换次数比冒泡少很多，但效率和冒泡排序一样的糟糕。 选择排序属于选择类排序算法。 我打扑克牌的时候，会习惯性地从左到右扫描，然后将最小的牌放在最左边，然后从第二张牌开始继续从左到右扫描第二小的牌，放在最小的牌右边，以此反复。选择排序和我玩扑克时的排序特别相似。 一、算法介绍 现在有一堆乱序的数，比如：5 9 1 6 8 14 6 49 25 4 6 3。 第一轮迭代，从第一个数开始，左边到右边进行扫描，找到最小的数 1，与数列里的第一个数交换位置。 第二轮迭代，从第二个数开始，左边到右边进行扫描，找到第二小的数 3，与数列里的第二个数交换位...阅读全文
