在使用map的过程中，有两个问题是经常会遇到的：读写冲突和遍历无序性。为什么会这样呢，底层是怎么实现的呢？带着这两个问题，我简单的了解了一下map的增删改查及遍历的实现。 结构 hmap type hmap struct { // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go. // Make sure this stays in sync with the compiler's definition. count int // 有效数据的长度# live cells == size of map. Must be first (used by len() builtin)...阅读全文
Golang: 思路：两个map分别存储应该被清空的行和列，遍历二维数组得到map，然后遍历map，清空相应的行列，就这样。 代码如下： func setZeroes(matrix [][]int) { if len(matrix)==0 { return } col:=make(map[int]int) row:=make(map[int]int) for i:=0; i
面试中有遇到几个golang的问题，记录一下 recover能处理所有的异常吗 根据目前查到的资料和实践， recover能处理程序主动触发的panic和除0以及空指针访问、异常地址访问等错误，因此可以认为是能处理所有异常了。 golang中常量是怎么实现的 这个问法还是很奇怪的， 从汇编中看是对字符串常量加了一个标号，同时设置为SRODATA，也就是只读，对数字常量直接在代码中作为立即数使用了 简单描述下golang的gc算法 golang现行的gc算法是三色标记法，三色指的是在gc过程中会把对象标记给黑，灰，白三色。 三色标记法是对标记-清除算法的优化，目的是减少stop the world的时间。 标记-清除算法： 对象只有黑白两色 stop the world,即停止所有gorout...阅读全文
题目一：Max Chunks To Make Sorted II 1、题目链接 leetcode No768:https://leetcode.com/problems/max-chunks-to-make-sorted-ii/ This question is the same as "Max Chunks to Make Sorted" except the integers of the given array are not necessarily distinct, the input array could be up to length 2000, and the elements could be up to 10**8. Given an array arr of inte...阅读全文
给你两个数组，arr1 和 arr2， arr2 中的元素各不相同arr2 中的每个元素都出现在 arr1 中对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。https://leetcode-cn.com/problems/relative-sort-array 输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6] 输出：[2,2,2,1,4,3,3,9,6,7,19] 题意：arr2给你自定义了一个数字大小顺序，将arr1里的数按照2中定义的规则拍一拍。 思路：统计1中的数字出现的次数，遍历2，依次取出1中的数，按照统计的...阅读全文
package main import "fmt" type Node struct { data int next *Node } func Shownode(p *Node){ //遍历 for p != nil{ fmt.Println(*p) p=p.next //移动指针 } } func main() { var head = new(Node) head.data = 0 var tail *Node tail = head //tail用于记录最末尾的结点的地址，刚开始tail的的指针指向头结点 for i :=1 ;i<10;i++{ var node = Node{data:i} (*tail).next = &node tail = &node } Shownode(h...阅读全文
思路： 通过当前label计算父节点 题目限制 1 <= label <= 10^6 完全二叉树每一层的节点和节点开始数字为： 1 2 4 8 16 32 ... 所以每一层的数为 []int{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576} 提前计算每一层的数量。 遍历找到当前lablel所在的层。当前层最后一个节点为 last - 1。因为这个二叉树是蛇形走位。所以 上层节点所在对应层的偏移是 (last - 1 - label)/2 计算上一层的起始位置为last/4。 上一层label即为 (last ...阅读全文
Learn Golang in Days - Day 11 要点 Range Go语言中range关键字用于for循环中迭代数组array,slice,channel or map 的元素。在数组和切片中它返回元素的索引和索引对应的值，在集合中返回key-value的key值。 range 可以遍历数组，切片 range 可以遍历字符串 range 可以遍历map 实例 package main import "fmt" func main() { // ---------------- 定义切片 ---------------- //定义slice nums := []int {1,2,3} sum := 0 for _,num := range nums { fmt.Printf("%d...阅读全文
Golang: 思路：这题稍微抓住一个点，在一个有序数组里，最小元素差总是出现在两个相邻的元素间，于是这题就变成了，排序，然后一次遍历。 代码如下： func minimumAbsDifference(arr []int) [][]int { sort.Ints(arr) min:=arr[1]-arr[0] var res [][]int for i:=1;i
给定一个整数数组 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...阅读全文
题目 将一个给定的字符串根据给定的行数，以从上到下、从左到右进行 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...阅读全文
map 声明的几种方式var a map [sting] int // string 代表key 值的类型 int 代表 value 值的类型var b map [int] string // int key 值的类型 ,string 代表value 值的类型var c map [string] string // string 代表 值的类型 string 代表value 值的类型map 类型的变量需要先声明才能使用,需要使用make 分配map内存 示列package main import "fmt" func map1() { var a map [string] int fmt.Println(a) // a["s1"] = 123 // fmt.Println(a) //pani...阅读全文
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...阅读全文
Learn Golang in Days - Day 12 要点 Map是一种无序的键值对的集合。Map最重要的一点是通过Key可以检索到Valu. Map是使用hash表来实现的 定义map 使用map关键字定义 使用make函数定义 // 声明变量，默认map是nil var map_variable map[key_data_type]value_data_type var countryMap map[string]string // 使用make函数来定义 map_variable := make(map[key_data_type]value_data_type) countryMap := make(map[string]string) //定义并初始化 var country...阅读全文
快速排序 快速排序思路 快速排序通过分支法的思想，从一个数组中选取一个基准元素pivot，把这个数组中小于pivot的移动到左边，把大于pivot的移动到右边。然后再分别对左右两边数组进行快速排序。 双边循环法 思路 设置两个指针left和right，最初分别指向数组的左右两端。比较right指针指向元素和pivot元素，如果right元素大于pivot元素，right指针左移一位，再和pivot进行比较，如果right元素小于pivot元素的话停止移动，换到left指针。left指针的操作是，left指针指向的元素和pivot元素比较，如果left指向元素小于或等于pivot，left指针右移，如果left元素大于pivot元素，停止移动。左右都停止移动后，交换left和right指向的元...阅读全文
题目描述 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）. 思路 先将字符串遍历一次，使用map存储每个字符出现的次数。 再将字符串遍历一次，若当前字符在map中对应的次数是1，即为正确答案。 若出了两次循环，说明没有正确答案，返回-1即可。 Java代码实现 public class Solution { public int FirstNotRepeatingChar(String str) { Map
好久没写了，打算今年做个Dig101系列，挖一挖技术背后的故事。 也可以移步微信版阅读 Dig101: dig more, simplified more and know more golang常用的遍历方式，有两种： for 和 for-range。 而for-range使用中有些坑常会遇到，今天我们一起来捋一捋。 0x01 遍历取不到所有元素指针? 如下代码想从数组遍历获取一个指针元素切片集合 arr := [2]int{1, 2} res := []*int{} for _, v := range arr { res = append(res, &v) } //expect: 1 2 fmt.Println(*res[0],*res[1]) //but output: 2 2 复制代...阅读全文
Map是无序的、基于key-value的数据结构，内部使用散列表hash实现。 Map是引用类型，声明时是nil，必须初始化才能使用。 map[keytype]valuetype map类型变量默认初始值是nil，需要使用make()函数进行初始化 make(map[keytype]valuetype, [cap]) map声明和初始化 func main() { //声明 var a map[string]int fmt.Println(a == nil) //true //初始化，容量可以写，建议编程时候加上 a = make(map[string]int, 10) fmt.Println(a == nil) //false // 声明map并初始化 b := map[int]strin...阅读全文
/** * 简化版桶算法 * 通过一维数组保存对应数字在一维数组中出现的个数，然后遍历一维数组达到排序的效果 * 这里一位数组是排序列表的范围，必须10以内的数字列表排序， 则一维数组大小为11 （N+1） * * 涉及知识点： * @随机数功能 * @时间处理和格式化 */ package main import ( "fmt" "math/rand" "time" ) func main() { var scoreList [11]int score := [5]int{5, 3, 5, 2, 8} for _, v := range score { scoreList[v]++ } fmt.Println(scoreList) var result []int // fmt.Print...阅读全文
什么是map map 是在go 中将值(value) 与 键(key) 关联的内置类型，通过相应的键可以获取到值定义类型为 map[key]value 一、 创建map ``` package mainimport "fmt"func maptest() {// 1、声明方式1 mapmap2 :=map[int] string{1:"hello",2:"world"}fmt.Println(map2) // 输出map2 :=map[int] string{1:"hello",2:"world"}fmt.Println(map2) //2、声明方式2 声明一个空map map2 :=map[int] string{} fmt.Println(map2) // 输出 map[] // 3、 ...阅读全文
Golang: 思路：使用多指针，一次遍历即可实现 代码如下： func deleteDuplicates(head *ListNode) *ListNode { if head==nil||head.Next==nil{ return head } p1,flag:=head,0 var p2,node *ListNode for p1!=nil{ if p1.Next!=nil&&p1.Next.Val==p1.Val{ temp,p3:=p1.Val,p1.Next.Next for p3!=nil{ if p3.Val!=temp{ break } p3=p3.Next } if p2!=nil{ p2.Next=p3 }else{ node,flag=p3,1 } p1=p3 co...阅读全文
Go的数组只能有固定的长度，传入变量作为数组长度时，只能创建为定义了size的切片 length := 5 array := [length]int // error: non-constant array bound length array := make([]int, length) Go没有内置的比较整数大笑的方法，需要自己实现 func max(a int, b int) int { if a >= b { return a } else { return b } } Go没有内置的判断array或map是否存在某一个元素的方法，需要通过判断普通的get的error实现 // implement array/list contains func contains(array []i...阅读全文
在 Go 中，for range 用来遍历 slice, map, chan 等，使用频率很高，但遍历虽好用，却很容易踩坑，且看 demo 如下： 1. 只有一个返回值时，则第一个参数是 index package main import "fmt" func main() { s := []string{"a", "b", "c"} // 只有一个返回值：则第一个参数是index for v := range s { fmt.Println(v) } // 两个返回值 for i, v := range s { fmt.Println(i, v) } } 输出结果如下： 0 1 2 ============= 0 a 1 b 2 c 2. 遍历 map 为随机序输出，slice 为索引序输...阅读全文
package main import ( "fmt" "reflect" ) // reflect 反射 type Student struct { Name string `json:"name" jike:"名字"` Score int `json:"score" jike:"成绩"` } func main() { s1 := Student{ Name:"xiaomaike", Score:666, } t_obj := reflect.TypeOf(s1) // TypeOf() 查看对象类型 //fmt.Printf("%#v\n", t_obj) //fmt.Println(t_obj) //fmt.Print(t_obj.Name(), t_obj.Kind()) // 类...阅读全文
好久没写了，打算今年做个Dig101系列，挖一挖技术背后的故事。 Dig101: dig more, simplified more and know more golang常用的遍历方式，有两种： for 和 for-range。而for-range使用中有些坑常会遇到，今天我们一起来捋一捋。 0x01 遍历取不到所有元素指针? 如下代码想从数组遍历获取一个指针元素切片集合 arr := [2]int{1, 2} res := []*int{} for _, v := range arr { res = append(res, &v) } //expect: 1 2 fmt.Println(*res[0],*res[1]) //but output: 2 2 答案是【取不到】同样代码对切片...阅读全文
跑次树的遍历，可添加到 hashmap 中维护，就变成两数之和I 了。我添加到了 list 中，应该换一下......列表中的话，应该也可以用双指针！！！ Definition for a binary tree node. class TreeNode(object): def init(self, x): self.val = x self.left = None self.right = None class Solution(object): def findTarget(self, root, k): """ :type root: TreeNode :type k: int :rtype: bool """ if not root or (not root.left and no...阅读全文
Golang: 思路：找到插入区间与原区间的交集，一次遍历，然后统一处理。 代码如下： func insert(intervals [][]int, newInterval []int) [][]int { i:=0 flag:=0 for i
package main import "fmt" func SelectSort(arr *[5]int) { //1.先将最大值和arr[j]交换 for j := 0; j < len(arr)-1; j++ { max := arr[j] //假设最大值为 arr[j] maxIndex := j //2.遍历比较 for i := j + 1; i < len(arr); i++ { if max < arr[i] { //找到真正的最大值 max = arr[i] maxIndex = i } } //交换 if maxIndex != j { arr[j], arr[maxIndex] = arr[maxIndex], arr[j] } fmt.Printf("%d time,...阅读全文
Golang: 思路：广度优先实现层序遍历 代码如下： func levelOrder(root *Node) [][]int { var res [][]int var arr[]*Node if root!=nil{ arr=append(arr,root) for len(arr)!=0{ temp:=len(arr) var level []int for i:=0;i
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} } } } ...阅读全文
Golang: 思路：这个，建立个数组，对应'a'，'b'，'l'，'o'，'n'，每当出现'a'，'b'，'n'时，对应数组位置加二，出现'l'，'o'时，对应数组位置加一，然后遍历数组，找到最小值，除以2即可 代码如下： func maxNumberOfBalloons(text string) int { res:=make([]int,5) for i:=0;i
Golang: 思路：这题不是要求输出最右边的路径，而是你从最右侧看去，每一层的最右端的点。方法就是BFS进行层序遍历，每次将最右边的那个放进结果里了。 代码如下： func rightSideView(root *TreeNode) []int { var res []int var nodes []*TreeNode if root!=nil { nodes=append(nodes, root) for len(nodes)!=0{ length:=len(nodes) res=append(res, nodes[length-1].Val) i:=0 for ;i
Golang: 思路：依旧是中序遍历，如果数组是递增的，那么二叉搜索树是正确的 代码如下： func isValidBST(root *TreeNode) bool { arr := inOrderValDFS(root) for i := 1; i < len(arr); i++ { if arr[i] <= arr[i-1] { return false } } return true } func inOrderValDFS(root *TreeNode) []int { var stack []*TreeNode var res []int for len(stack) != 0 || root != nil { for root != nil { stack = append(st...阅读全文
Golang: 思路：先求和判断能否除以3，能的话开始遍历元素并相加，每当和等于总和的1/3时，将和清零并继续向下遍历，再出现一次和的1/3即可返回true，否则返回false 代码如下： func canThreePartsEqualSum(A []int) bool { sum:=0 for i:=0;i
系列文章:总目录索引：九析带你轻松完爆 go 系列教程目录1 前言2 一维数组 2.1 一维数组声明 2.2 一维数组初始化 2.2.1 全量初始化 2.2.2 长度推测初始化 2.2.3 指定索引初始化 2.3 一维数组遍历 2.3.1 索引遍历数组 2.3.2 range 遍历数组3 二维数组 3.1 二维数组声明 3.2 二维数组初始化 3.3 二维数组遍历 3.3.1 索引遍历 3.3.2 range 遍历1 前言 如果你对博客有任何疑问或者想更深入学习 go，请加微信群，我们一起进步：2 一维数组2.1 一维数组声明 一维数组声明是三段式：var arr_name [arr_length] arr_type 样例代码如下：var arr [2]int2.2 一维数组初始化2.2.1...阅读全文
Golang: 思路：用一个数组arr，arr[i]表示以nums中以i为下标的元素所构成的最长上升子序列的长度，举个例子：[1,3,6,7,9,4,10,5,6]，i=4时，即nums[i]=9，则arr[4]表示的是9作为最长上升子序列的最后一位时，这个序列的最大长度。最后，遍历这个数组arr，看下最大值，那么就是最长上升子序列的长度。 代码如下： func lengthOfLIS(nums []int) int { if len(nums)<=1 { return len(nums) } arr:=make([]int,len(nums)) arr[0]=1 res:=1 for i:=1;i
Golang: 思路：二叉树，层序遍历即可 代码如下： func averageOfLevels(root *TreeNode) []float64 { var res []float64 if root!=nil{ stack:=[]*TreeNode{root} for len(stack)!=0{ level:=len(stack) num:=0 for i:=0;i
Golang: 思路：还是通过层序遍历的方式来实现 代码如下： func addOneRow(root *TreeNode, v int, d int) *TreeNode { if d==1{ return &TreeNode{Left:root,Val:v} } if root!=nil{ stack:=[]*TreeNode{root} depth:=1 for depth
