# golang实现常用集合原理介绍 ## [ArraySort排序数组](https://github.com/chentaihan/container/blob/master/array/arraySort.go) ArraySort使用数组保存数据，新增的时候通过类似二分查找找到插入位置，插入位置后面的数据往后移动一位，插入新元素，查找就是二分查找，删除就是通过二分查找找到对应的元素，之后的元素都向前移动一位。时间复杂度如下： | 功能 | 时间复杂度 | | :--- | :--- | | 新增 | **O**\(n\) | | 删除 | **O**\(n\) | | 查找 | **O**\(logn\) | ## [LinkList单链表](https://github.com/c...阅读全文
理简单选择排序应该是最直观最容易理解的排序方法了。直接从头开始一个一个去比，找出最小的放到最左边。再依次完成其他位的排序。 时间复杂度比较次数固定为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...阅读全文
前言 前一段时间在 reddit 上看到有人推广一篇名为 GopherCon 2018 - Demystifying Binary Search Tree Algorithms 的博客，博客中列举了传统大学里学习算法的种种弊端，并强调了用 Go 实现算法是多么简单有趣，然后拿二叉树举了个例子。读完这篇博客以后，我不得不说，真心没看出来 Go 写算法的优势在哪里。但是，配图确实萌翻了，下面盗图一副。 虽然不会画画，但是并不妨碍用 Go 做一些算法实现的尝试。这里我从 "Pears of Functional Algorithms Design" 里拿了一道题：给定一个无序自然数数组 A，求出不在 A 中的最小自然数，约束条件如下： A 中的元素个数是有限的，每个元素都是自然数，并且互不相同（自...阅读全文
基于golang web项目实际开发中在controller层对客户端请求参数进行验证，这样导致controller层代码冗余度非常高，影响开发效率。代码示例： feedback := &mysql_model.OfbankFeedback{} err := json.Unmarshal(body, feedback) feedback.FStatus=1 feedback.CreateTime=time.Now() if err != nil { resp := apiservice.GenerateResponse(0, "请求参数有误", "") rw.Write([]byte(resp)) return } if feedback.Phone=="" { resp := apiser...阅读全文
好多人都在刷leetcode，今天我也注册了一个玩玩，发现里面好多都是算法题，好吧，毕业十来年，学的那点可怜的数学知识，全都还给学校了。好了闲话少说，言归正传，让我们看看今天在里面我尝试的第一道题，有点意思， 不只是单纯的算法，还有数据和是否适合的问题。 承题 点开题库，看了第一题，我们看看这道题： 给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。 你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 用了这么多文字描述，其实总结起来就是：数组里那两个数想加等于目标值，找出来这两个数的索引。 题是不难...阅读全文
创翻译文章，转载请注明出处：服务器非业余研究-sunface 对于代码风格的争议由来已久：程序员在一段代码中到底该使用多少嵌套或者缩进结构。请先看看下面两个例子： 在第一个例子中，如果我们想在高亮代码附近进行debug，那么我们需要记住哪些呢？ func (g *Gopher) WriteTo(w io.Writer) (size int64, err error) { err = binary.Write(w, binary.LittleEndian, int32(len(g.Name))) if err == nil { size += 4 var n int n, err = w.Write([]byte(g.Name)) size += int64(n) if err == nil ...阅读全文
7.1-1 参照图7-1的方法，说明PARTITION在数组A=<13,19,9,5,12,8,7,4,21,2,6,11>上的操作过程。 答:golang实现： // Partition 分解重排步骤 func Partition(a QuickSortInterface, p int, r int) int { x := a.Get(r) i := p - 1 for j := p; j < r; j++ { if a.Get(j) < x { i++ a.Swap(i, j) } } a.Swap(i+1, r) return i + 1 } 结果为: [9 5 8 7 4 2 6 11 21 13 19 12] 7.1-2 当数组A[p..r]中所有元素的值都相同时，PARTITIO...阅读全文
rlp序列化文档 RLP（Recursive Length Prefix，递归的长度前缀）是一种编码规则，可用于编码任意嵌套的二进制数据，特定的数据类型（例如：string,int等类型）则交给更高阶的协议处理。需要注意的是：int类型必须去掉首部0，且必须用大端模式表示。 编解码规则 编码规则 如果数据的长度是1个字节，并且它的值在[0x00, 0x7f] 范围之间，那么其RLP编码就是数据本身。即前缀为空，用前缀代表数据本身； 如果数据的长度是0-55字节，其RLP编码是前缀跟上(拼接)数据本身，前缀的值是0x80加上数据的长度。由于在该规则下，数据的最大长度是55,因此前缀的最大值是0x80+55=0xb7，所以在本规则下前缀(第一个字节)的取值范围是[0x80, 0xb7]； 如果数...阅读全文
基于比较的排序算法：冒泡，插入，选择，快排，归并 不基于比较的排序算法：桶，计数，基数 稳定性 待排序的序列中存在值相同的元素，经过排序后相同元素之间原有的先后顺序不变。 冒泡排序 image.png 优化：在每次冒泡操作时可以加入有序标志位，如果一次冒泡操作后没有进行过数据交换，则认为数据集为有序，可以提前退出冒泡排序 冒泡排序是原地排序，只需要常量级别的临时空间作为交换数据使用； 冒泡排序是稳定的排序算法，只要在两个相邻元素比较时，相同大小不进行交换就可以保证； 冒泡排序的时间复杂度：最好情况为有序数据集，仅需要一次冒泡操作，所以最好的时间复杂度为O(n)，最坏情况为倒序数据集，时间复杂度为O(n2)，平均时间复杂度为O(n2); 插入排序 插入排序是原地排序算法，不需要额外空间； 插入...阅读全文
文链接 github 简介 Rabin-Karp字符串快速查找算法和FNV hash算法是golang中strings包中字符串查所用到的具体算法，算法的核心就在于循环hash，而 FNV则是散列方法的具体算法实现。 算法思想 Rabin-Karp算法思想： 假设待匹配字符串长度M，目标字符串长度N（N>M） 首先计算待匹配字符串hash，计算目标字符串前M个字符hash 比较前两个hash值，比较次数N-M+1 若hash不相等，继续计算目标字符串下一个长度为M的hash并继续循环比较 若hash相等则再次判断字符串是否相等已确保正确性 FNV hash： 将字符串看作是字符串长度的整数，这个数的进制是一个质数。计算出来结果之后，按照哈希的范围求余数得到结果。 其中不同机制对应质数分别是：...阅读全文
题目 https://github.com/betterfor/leetcode-go/tree/master/algorithms/0003_Longest_String 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 题解 暴力法 简单来说就是列出...阅读全文
求一个字符串中最长的回文子串。 a11.png package main import "fmt" /* 马拉松算法，求最长回文子串，时间复杂度：线性 */ func main() { // 回文数 str := "abcddcbadcbadcabdadacd" // 填充#变成奇数个元素 strArray := make([]byte, 0, 2*len(str)+1) // 每个字符是一个byte for i := 0; i < len(str); i++ { strArray = append(strArray, str[i]) strArray = append(strArray, '#') } fmt.Print("原始字符串：") for i := 0; i < len(strA...阅读全文
理 我们都知道怎么使用goLang中的map来存储键值对类型的数据，但是它的内部实现是怎么样的？ 其实map是一种HashMap，表面上看它只有键值对结构，实际上在存储键值对的过程中涉及到了数组和链表。HashMap之所以高效，是因为其结合了顺序存储(数组)和链式存储(链表)两种存储结构。数组是HashMap的主干，在数组下有有一个类型为链表的元素。 这是一个简单的HashMap的结构图： image 当我们存储一个键值对时，HashMap会首先通过一个哈希函数将key转换为数组下标，真正的key-value是存储在该数组对应的链表里。 HashMap的数组往往是有限的，那当要存储的键值对很多数组不够或者两个键值对哈希运算后的值相同时，不就会有不同的键值对存储在同一个数组下吗？是的，这个就叫...阅读全文
问题地址，难度：Easy 若有错误之处请予以指正:) 问题描述 Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A. Example 1: Input: [3,1,2,4] Output: [2,4,3,1] The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. Note: 1 <= A.length <= 5000 0 <= A[i] <= 5000 题意分析 把偶数奇数分成前后...阅读全文
文链接 github 简介 Rabin-Karp字符串快速查找算法和FNV hash算法是golang中strings包中字符串查所用到的具体算法，算法的核心就在于循环hash，而 FNV hash则是散列方法的具体算法实现。 算法思想 Rabin-Karp算法思想： 假设待匹配字符串长度M，目标字符串长度N（N>M） 首先计算待匹配字符串hash，计算目标字符串前M个字符hash 比较前两个hash值，比较次数N-M+1 若hash不相等，继续计算目标字符串下一个长度为M的hash并继续循环比较 若hash相等则再次判断字符串是否相等已确保正确性 FNV hash： 将字符串看作是字符串长度的整数，这个数的进制是一个质数。计算出来结果之后，按照哈希的范围求余数得到结果。 其中不同机制对应质...阅读全文
选择排序 package main import "fmt" func main() { arr := []int{7, 13, 4, 5, 8, 1, 11, 9} fmt.Println("排序前：", arr) length := len(arr) for i := 0; i < length; i++ { for j := i+1; j < length; j++ { if arr[i] > arr[j] { arr[i], arr[j] = arr[j], arr[i] } } } fmt.Println("排序前：",arr) } 选择排序的时间复杂度 首先，为了在第 1 轮找到最小的数字，需要从左往右确认数列中的数字，只要查询 n 个数 字即可。在接下来的第 2 轮中，需要从 ...阅读全文
问题地址，难度：Easy 若有错误之处请予以指正:) 问题描述 Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A. Example 1: Input: [3,1,2,4] Output: [2,4,3,1] The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. Note: 1 <= A.length <= 5000 0 <= A[i] <= 5000 题意分析 把偶数奇数分成前后...阅读全文
题目描述 给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]解法一 暴力解法 解题思路 最容易想到的就是暴力法，使用两个遍历，查找两数之和是否为target。流程如下： 使用i来遍历数组每个元素 在i的每一个循环中，使用j从i + 1开始遍历 判断i和j对应的值的和是否为target 代码实现 func twoSum(nums []int, target ...阅读全文
外观模式 1. 定义： 外部与一个子系统通信必须通过一个统一的对象进行，为子系统中的一组接口提供一致界面。 2. 代码示例： // 定义对外API type API interface { Test() } func NewAPI() API { return apiImpl{newMod()} } type apiImpl struct { m mod } func (a apiImpl) Test() { a.m.mod() } // 需要交互的内部模块 type mod interface { mod() } func newMod() mod { return modImpl{} } type modImpl struct { } func (m modImpl) mod() { }...阅读全文
Go package(1) time 用法 golang使用的版本： go version go1.10.3 一：功能介绍 time的一些功能，比如时区，像linux中的定时器，时间计算等 格式化时间 时区(Location) 时间计算 Ticker Timer(定时器) Time一般分为时间Time 和 时段Duration 二：Time 结构体 time结构体定义： type Time struct { wall unit64 //表示距离公元1年1月1日00:00:00UTC的秒数 ext int64 //表示纳秒 loc *Location //代表时区，主要处理偏移量。因为不同的时区，对应的时间不一样 } 上面的loc表示时区， 那什么是时区呢？因为地球是圆的，所以同一个时刻，在地...阅读全文
题目 https://github.com/betterfor/leetcode-go/tree/master/algorithms/0004_Median_Of_Two_Sorted_Arrays 假定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m+n)) 。 你可以假定 nums1 和 nums2 不会同时为空。 示例1： nums1 = [1,3] nums2 = [2] 则中位数是 2.0 示例2： nums1 = [1,2] nums2 = [3,4] 则中位数 （2+3）/2=2.5 题解 1、暴力法 将两个数组合并，两个有序数组合并也是归并数组，然后根据奇偶数返回中位数。 func ...阅读全文
写在前面 反射机制是一个很重要的内容，当我们写框架的时候，要想要松耦合，高复用，那么就有很多地方都需要用到反射，可谓是中高级程序员必须掌握的知识点 很多后台语言都有反射机制，但它们的使用原理大多都是一样的 各语言不同的地方，大致就是代码实现方式不一致罢了 其根本，都是从变量得到反射对象，再由反射对象去操作原变量 好了，步入正题 什么是反射 我就用一句话来概括吧 使用反射，可以让我们在程序运行时对任意类型的对象进行操作 注意操作这两个字，操作是指：可以获取对象的信息、改变对象的值、调用对象的方法、甚至是创建一个对象 说到这你可能有点困惑，我们在编写代码的时候不就已经把该实例化的象进行了实例化，该调用的方法都调用了嘛？为什么写程序的时候不调用方法，偏要在运行时去进行这些操作？ 其实问题就在这里，...阅读全文
面试题25. 合并两个排序的链表 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例1： 输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 限制： 0 <= 链表长度 <= 1000 注意：本题与主站 21 题相同：https://leetcode-cn.com/problems/merge-two-sorted-lists/ 148. 排序链表 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输入: -1->5->3->4->0 输出: -1->0->3->4->...阅读全文
.-. .- .-,.--..-,.--. \ \ / / __ | .-. | .-. | __ \ \ / / .:--.'. | | | | | | |.:--.'. \ \ / / / | \ || | | | | | / | \ | \ \ / / `" __ | || | '-| | '-`" __ | | \ ` / .'.''| || | | | .'.''| | \ / / / | || | | | / / | |_ / / \ \._,\ '|_| |_| \ \._,\ '|`-' / `--' `" `--' `" '..' GolangOnline Go tutorial 1.1 原理 数组（Array）是一种线性表数据结构，通过在内存中申请一组连续的存储空间，用于...阅读全文
Self Dividing Numbers A self-dividing number is a number that is divisible by every digit itcontains.For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0. Also, a self-dividing number is not allowed to contain the digit zero. Given a lower and upper number bound, output a list of every possible self dividi...阅读全文
给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？ 示例： 输入: [4,3,2,7,8,2,3,1] 输出: [2,3] 题意：关键就是把数组中的元素当成是索引来看就行。如果索引处的数字出现过一次，就给-1，因为只会出现两次，如果第二次再出现，那么对应位置的值就会是小于0的，直接加到结果集中就行。一开始我还想着出现过一次-1，再出现一次再*-1，这样最后再遍历一次找到小于0的即可，但是发现有些问题，有些数字没出现过会被误杀。 O（N）时间，O（1）空间 func findDuplicates(nums []int) []int { resul...阅读全文
Golang: 思路：看了下大佬的回答，用map实现，O(n)，但是无论是时间复杂度的效率还是空间复杂度的效率都很低，不知道为什么 代码如下： func longestConsecutive(nums []int) int { mp:=make(map[int]int) res:=0 for _,v:=range nums{ if mp[v]==0{ mp[v]=mp[v-1]+mp[v+1]+1 if mp[v]>res { res=mp[v] } mp[v-mp[v-1]]=mp[v] mp[v+mp[v+1]]=mp[v] } } return res ...阅读全文
题目 将一个给定的字符串根据给定的行数，以从上到下、从左到右进行 Z 字形排序。 比如输入字符串为 “LEETCODEISHIRING” 行数为3，排列如下： L C I R E T O E S I I G E D H N 之后，需要从左到右逐行读取，结果为 “LCIRETOESIIGEDHN” 示例1： 输入：s = "LEETCODEISHIRING", numRows = 3 输出: "LCIRETOESIIGEDHN" 示例2： 输入: s = "LEETCODEISHIRING", numRows = 4 输出: "LDREOEIIECIHNTSG" 解释: L D R E O E I I E C I H N T S G 题解 1、找规律 Z 字形很容易找到规律，假如 numRow...阅读全文
Golang: 思路：其实这题用栈的话很好解决，但Go里好像没有栈，我就用切片去实现了一个类似的栈，思路是，每当遇见{ [ (时，这些符号会进入切片（入栈），每当遇到} ] )时，我们去查看切片尾端的符号是否是相对应的符号，不是则直接return false，是的话，切片会删除尾端的符号（出栈），在全部字符串处理完了以后，我们查看切片的长度，如果不为0，那么说明有符号没有配对成功，为0则说明成功了 注意：这里需要小心切片的长度问题，例：当我们去处理"}()[]"这个字符串时，遇见的第一个就是}符号，这时候查看切片尾端res[len(res)-1]=='{'可能会导致越界错误，因为此时res的长度为0。在这里我的处理方法是在每次判断时首先判断len(res)!=0，如果为0，则直接可以retu...阅读全文
试设计算法得到原数组循环右移 k 次的 结果并分析算法的时间复杂度。 1.问题描述 已知一个长度为 n 的数组和一个正整数 k，并且最多只能使用一个用于 交换数组元素的附加空间单元，试设计算法得到原数组循环右移 k 次的 结果并分析算法的时间复杂度。 2.解决思路 根据三步反转法，实现时间复杂度为O（n）,空间复杂度为O（1） 过程： 1、将整体数组进行反转，原顺序1，2，3，4，5，6，7，8，9变为9，8，7，6，5，4，3，2，1 2、将前K-1个数进行反转，比如K=2,则结果为：8，9，7，6，5，4，3，2，1 3、将后K个数进行反转，结果：8,9,1,2,3,4,5,6,7 3.代码实现 golang code: package main import "fmt" func Do...阅读全文
Golang: 思路：这大概是我提交错误最多的一次。思路很简单，先二分找到变化的点，知道变化的点后，查找可以去到数组的不同区域去二分。时间复杂度是logn没有问题。思路很正确没有问题。至于为什么错这么多，状态不好，没啥耐心，强行写题，炸了。顺便一提，这道题我的代码极烂，烂到我都不想承认这是我写的！！！后面会不会改要看心情。 代码如下： func search(nums []int, target int) int { if len(nums)==0 { return -1 } if len(nums)==1{ if target==nums[0]{ return 0 }else { return -1 } } temp:=pointChanged(nums) if temp==0 { tem...阅读全文
栈的性质 只允许一段插入和删除数据 先进后出 栈可以用链表实现也可以用数组实现 操作时间复杂度 入栈和出栈时间复杂度都为Ｏ(1) (因为只涉及操作栈顶部的第一个元素） 涉及到可扩容的栈的时候，因为栈满了要扩容，数据迁移时间复杂度为Ｏ(n) 但是前ｎ次插入的时间复杂度都是Ｏ(1) 进行均摊后， 时间复杂度为O(2) = O(1) 所以不管是否扩容 时间复杂度都是O(1) 曾经（去年） 面试的时候有个面试官曾过我， 你知道栈吗？ 两个栈怎么组成一个先进先出的队列， 可是我太年轻那，bb半天也没有让人家满意。 栈的golang代码实现 type ArrayStack struct { data []interface{} top int } func NewArrayStack() *ArrayS...阅读全文
字典 我们翻阅书籍时，很多时候都要查找目录，然后定位到我们要的页数，比如我们查找某个英文单词时，会从英语字典里查看单词表目录，然后定位到词的那一页。 计算机中，也有这种需求。 一、字典 字典是存储键值对的数据结构，把一个键和一个值映射起来，一一映射，键不能重复。在某些教程中，这种结构可能称为符号表，关联数组或映射。我们暂且称它为字典，较好理解。 如： 键=>值 "cat"=>2 "dog"=>1 "hen"=>3 我们拿出键cat的值，就是2了。 Golang提供了这一数据结构：map，并且要求键的数据类型必须是可比较的，因为如果不可比较，就无法知道键是存在还是不存在。 Golang字典的一般的操作如下： package main import "fmt" func main() { // ...阅读全文
Golang: 思路：这题虽然是M*N的时间复杂度，但使用并查集，好像会极大的减少时间复杂度。推测起来，要么我执行了太多的修改操作，要么计算机在处理二维数组上难度大于一维数组。 代码如下： func numIslands(grid [][]byte) int { arr:=make([]int,len(grid)*len(grid[0])) for i,_:=range arr{ arr[i]=i } res:=0 r:=len(grid) c:=len(grid[0]) for i:=0;i
如果说什么是区块链的灵魂，那一定是共识机制。 它是区块链的根基。无论公链或是联盟链，共识机制都从基础上限制了区块链的交易处理能力和扩展性。 2019年6月18日，Facebook 发布了自己 Libra 项目的白皮书，引发广泛关注。作为 Facebook 试图创造国际流通数字货币的重要项目，Libra 区块链采用的是 LibraBFT 共识机制，是一个为 Libra 设计的鲁棒的高效的状态复制系统。它基于一种新型的 BFT 共识算法，HotStuff。 就在 Facebook Libra 项目白皮书发布之前不久，5月17日，比原链发布了 BaaS 平台 Bystack。这是一个一主多侧链架构的商用区块链系统，主链采用 PoW 共识保证多样资产安全和去中心化，侧链提供可插拔的共识以满足不同业务...阅读全文
冒泡排序(Bubble Sort) 冒泡排序也叫做起泡排序 执行流程 1 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置 ✓ 执行完一轮后，最末尾那个元素就是最大的元素 2 忽略 1 中曾经找到的最大元素，重复执行步骤 1，直到全部元素有序 //最坏、平均时间复杂度:O(n2) 最好时间复杂度:O(n) //空间复杂度:O(1) for end := len(this.Array) - 1; end > 0; end-- { for begin := 1; begin <= end; begin++ { if this.ComWithIndex(begin, begin-1) < 0 { this.Swap(begin, begin-1) } } } 冒泡排序 – 优化1...阅读全文
Golang: 思路：用了两个map，时间复杂度还行，但空间复杂度可太高了，第一个map存放长度更长的列表，第二个map去存储索引最小的字符串集合。代码还是有些复杂的，而且空间复杂度太低了，不推荐。 代码如下： func findRestaurant(list1 []string, list2 []string) []string { if len(list1)==0||len(list2)==0{ return nil } minsum:=-1 dic:=make(map[string]int) minress:=make(map[int][]string) var longl,shortl []string if len(list1)>len(list2) { longl,shortl=...阅读全文
Golang: 思路：简单DP，这里可以注意到，当n>10，即这个数字的长度>10后，所有这个长度的数字都会有重复的现象发生，所以也可以直接穷举。 代码如下： DP的放在这里，双百时空间复杂度 func countNumbersWithUniqueDigits(n int) int { if n<0{ return 10 } arr1:=make([]int,11) arr1[0],arr1[1]=1,10 temp:=9 flag:=9 for i:=2;i
归并排序 归并排序使用分治思想，分支算法一般都是用递归来实现的。 归并排序是一个稳定的排序算法，在merge过程中可以保证值相同的元素在合并前后顺序不变； 归并排序的时间复杂度是O(nlogn)，他的执行效率和排序的原始数组的有序成都是无关的，任何情况的时间复杂度都是O(nlogn) 但是归并排序在合并的时候需要借助额外的存储空间，空间复杂度为O(n)，所以不是原地排序算法； 快速排序 如果快排的partition函数不使用额外内存空间来进行，则可以做到原地排序； 快排是不稳定的； 虽然快速排序最坏情况的时间复杂度是O(n2)，但是平均时间复杂度为O(nlogn)，而且最坏情况的概率很小，可以通过合理地选择pivot来避免这种情况； 代码实现（Golang） type Sort struct...阅读全文
Golang: 思路：这题贪心解法其实很好想，不过我最终实现了O(n)的时间复杂度解法，执行效果上在时间复杂度上超过100%。 代码如下： func partitionLabels(S string) []int { var res []int arr:=make([][]int,26) used:=make([]int,26) for i:=0;i
Given a non-empty, singly linked list with head node head, return a middle node of linked list. If there are two middle nodes, return the second middle node. Example 1: Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a...阅读全文
优先队列及堆排序 堆排序(Heap Sort)由威尔士-加拿大计算机科学家J. W. J. Williams在1964年发明，它利用了二叉堆(A binary heap)的性质实现了排序，并证明了二叉堆数据结构的可用性。同年，美国籍计算机科学家R. W. Floyd在其树排序研究的基础上，发布了一个改进的更好的原地排序的堆排序版本。 堆排序属于选择类排序算法。 一、优先队列 优先队列是一种能完成以下任务的队列：插入一个数值，取出最小或最大的数值（获取数值，并且删除）。 优先队列可以用二叉树来实现，我们称这种结构为二叉堆。 最小堆和最大堆是二叉堆的一种，是一颗完全二叉树（一种平衡树）。 最小堆的性质： 父节点的值都小于左右儿子节点。 这是一个递归的性质。 最大堆的性质： 父节点的值都大于左右儿...阅读全文
1/100-两数之和 问题描述 link-to-leetcode 解法一：暴力搜索 暴力搜索是最简单的方法（笔者觉得从暴力搜索不断优化的过程是一个有趣的过程）时间复杂度：O(N^2)空间复杂度：O(1) func twoSum(nums []int, target int) []int { // loop： // 选择第一个数字 // 遍历后面的数字： // if 两个数字的和==target，then 输出结果 // 继续选择下一个数字 for i := 0; i < len(nums); i++ { for j := i + 1; j < len(nums); j++ { if nums[i] + nums[j] == target { return []int{i, j} } } } ...阅读全文
前言 工作一段时间之后，最大的感觉就是算法好像没什么用，确实不会算法也能胜任平常的工作，但是总觉得缺了点什么，所以最近抽空复习了以前刷的 Leetcode，希望在这里找到一群志同道合的人。 两数之和（Two Sum） 这是 LeetCode 的第一题，总体来说是比较简单的，题干如下： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。示例: 给定 nums = [2, 7, 11, 15]，target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]来源：力扣 简单来说就是给定一个数组，让你找到和为 target 的两个元素的索引。 解题思路 主要有 两种解题思路 ： 暴力...阅读全文
冒泡排序的特点是调整相邻两个对象的位置，每进行一次内循环就可以将最大值调整到最后。时间复杂度是O(n^2) package main import "fmt" func popsort(a []int) []int{ for i:=0;i
Golang: 思路：这题我个人感觉要复杂一些，难度在于首尾相连，并且，你需要考虑的更全面一些。当然，这题做完的时间复杂度100%，空间47%，但我不太想优化了。简单来说，有房子[1...n]，通过打家劫舍1得出的最大值，我们需要做出判断：如果我们没抢n，那么这个最大值没有问题，如果我们抢了n，那么就需要去看下我们抢没抢1，如果也没抢1，那么没问题，但如果抢1了，那么这个最大值就需要修改了，为max([2....n],[1...n-1])。 代码如下： func rob(nums []int) int { if len(nums) == 0 { return 0 } if len(nums) == 1 { return nums[0] } if len(nums) == 2 { if num...阅读全文
Golang: 思路：这题O(1)空间复杂度，其实只需要拆分成两个链表，然后连接下就好了 代码如下： func oddEvenList(head *ListNode) *ListNode { nd1,nd2:=&ListNode{Val:0},&ListNode{Val:0} node1,node2,temp,flag:=nd1,nd2,head,0 for temp!=nil{ if flag%2==0{ node1.Next=temp node1=node1.Next }else{ node2.Next=temp node2=node2.Next } temp=temp.Next flag++ } node2.Next=nil node1.Next=nd2.Next return nd1...阅读全文
冒泡排序 冒泡排序是大多数人学的第一种排序算法，在面试中，也是问的最多的一种，有时候还要求手写排序代码，因为比较简单。 冒泡排序属于交换类的排序算法。 一、算法介绍 现在有一堆乱序的数，比如：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: 思路：这里补充个并查集实现，时间复杂度也是O(n)，但空间复杂度会差很多，因为使用了哈希表。这题我陷入了个误区，忘记了使用题目给的数组空间是可以算作O(1)的，做的时候还在想，不用额外的空间，怎么可能呢？ 代码如下： func firstMissingPositive(nums []int) int { mp:=make(map[int]int) for i:=0;i
Golang: 思路：这题是字符串处理吧，没啥好说的，但是这里我的代码需要精简一下，Count函数那里，有多余的时间复杂度。 代码如下： func subdomainVisits(cpdomains []string) []string { mp:=make(map[string]int) for _,v:=range cpdomains{ flds:=strings.Fields(v) count,_:=strconv.Atoi(flds[0]) mp[flds[1]]+=count temp:=flds[1] for strings.Count(temp,".")>0 { temp=temp[strings.Index(temp,".")+1:] mp[temp]+=count } } ...阅读全文
