# algorithm-go

**Repository Path**: cn_wlei/algorithm-go

## Basic Information

- **Project Name**: algorithm-go
- **Description**: 记录golang数据结构及leetCode刷题算法
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 1
- **Created**: 2021-01-11
- **Last Updated**: 2021-09-27

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 记录数据结构和leetCode算法题

## 数据结构

### `sparsearray 稀疏数组`

### `singlequeue 数组模拟队列`

### `circelqueue 数组模拟环形队列`

### `singlequeue 单向链表`

### `doublelink 双向链表`

### `circlesinglelink 环形链表`

### `josephu 约瑟夫环`

### `bubblesort 冒泡排序`

### `selectsort 选择排序`

### `insertsort 插入排序`

### `quicksort 快速排序`

### `mergeSort 归并排序`

### `stack 栈`

### [`quickPower 快速幂模板`](./dataStructure/quickPower/quickPower.go)

### [`quickMul 快速乘模板`](./dataStructure/quickMul/quickMul.go)


## leetCode

### `maximumProduct 628. 三个数的最大乘积`

### `numEquivDominoPairs 1128. 等价多米诺骨牌对的数量`

### `pivotIndex 724. 寻找数组的中心索引`

### `minimumEffortPath 1631. 最小体力消耗路径(并查集)`

### `fairCandySwap 888. 公平的糖果棒交换`

### `fairCandySwap 665. 非递减数列`

### `checkInclusion 567. 字符串的排列`

### `matrixReshape 566. 重塑矩阵`

### `getRow 119. 杨辉三角 II`

### `longestOnes 1004. 最大连续1的个数 III`

### `findShortestSubArray 697. 数组的度`

### `longestSubarray 1438. 绝对差不超过限制的最长连续子数组`

### `isToeplitzMatrix 766. 托普利茨矩阵`

### `maxSatisfied 1052. 爱生气的书店老板`

### `oddEvenList 328. 奇偶链表`

### `decodeString 394. 字符串解码`

### `flipAndInvertImage 832. 翻转图像`

### `climbStairs 70. 爬楼梯`

### `transpose 867. 转置矩阵`

### `longestSubstring 395. 至少有 K 个重复字符的最长子串`

### `isMonotonic 896. 单调数列`

### `longestPalindrome 409. 最长回文串`

### `longestPalindromeSubstring 5. 最长回文子串`

### [`maxSumSubmatrix 363. 矩形区域不超过 K 的最大数值和(朴素解法)`](./leetcode/maxSumSubmatrix/maxSumSubmatrix.go)

### `NumMatrix 338. 比特位计数`

### `MyQueue 232. 用栈实现队列`

### `nextGreaterElements 503. 下一个更大元素 II(单调栈)`

### `partition 131. 分割回文串`

### `minCut 131. 分割回文串`

### `wordBreak 139. 单词拆分(动态规划)`

### `removeDuplicates 1047. 删除字符串中的所有相邻重复项(用切片模拟栈)`

### `calculate 224. 基本计算器 (栈应用)`

### `calculate2 227. 基本计算器 II (栈应用)`

### [`clumsy 1006. 笨阶乘 (栈应用)`](./leetcode/clumsy/clumsy.go)

### `isValidSerialization 331. 验证二叉树的前序序列化 (栈应用)`

### `MyHashSet 705. 设计哈希集合`

### `MyHashMap 706. 设计哈希映射`

### `spiralOrder 54. 螺旋矩阵`

### `generateMatrix 59. 螺旋矩阵 II`

### `reverseBetween 92. 反转链表 II(头插法)`

### `evalRPN 150. 逆波兰表达式求值（栈）`

### `setZeroes 73. 矩阵置零（原地算法 o(1)空间）`

### `hammingWeight 191. 位1的个数（&运算）`

### [`NestedIterator 341. 扁平化嵌套列表迭代器（栈、队列）`](./leetcode/NestedIterator/NestedIterator.go)

### [`find132pattern 456. 132 模式（栈）`](./leetcode/find132pattern/find132pattern.go)

### [`deleteDuplicates 83. 删除排序链表中的重复元素`](./leetcode/deleteDuplicates/deleteDuplicates.go)

### [`deleteDuplicates1 82. 删除排序链表中的重复元素 II`](./leetcode/deleteDuplicates1/deleteDuplicates1.go)

### [`hasCycle 141. 环形链表(快慢指针,自删,字典,反转链表再比较)`](./leetcode/hasCycle/hasCycle.go)

### [`splitListToParts 725. 分隔链表(均分)`](./leetcode/splitListToParts/splitListToParts.go)

### [`Trie 208. 实现 Trie (前缀树)`](./leetcode/Trie/Trie.go)

### [`rotateRight 61. 旋转链表（闭合成环）`](./leetcode/rotateRight/rotateRight.go)

### [`BSTIterator 173. 二叉搜索树迭代器（中序遍历,栈）`](./leetcode/BSTIterator/BSTIterator.go)

### [`inorderTraversal 94. 二叉树的中序遍历（递归、栈迭代、莫里斯）`](./leetcode/inorderTraversal/inorderTraversal.go)

### [`increasingBST 897. 递增顺序搜索树（中序遍历）`](./leetcode/increasingBST/increasingBST.go)

### [`rangeSumBST 938. 二叉搜索树的范围和（中序遍历）`](./leetcode/rangeSumBST/rangeSumBST.go)

### [`minDiffInBST 783. 二叉搜索树节点最小距离（递归、栈迭代、莫里斯）`](./leetcode/minDiffInBST/minDiffInBST.go)

### [`isCousins 993. 二叉树的堂兄弟节点（递归、栈迭代）`](./leetcode/isCousins/isCousins.go)

### [`leafSimilar 872. 叶子相似的树（递归、栈迭代）`](./leetcode/leafSimilar/leafSimilar.go)

### [`reverseBits 190. 颠倒二进制位（分治算法、逐位分离）`](./leetcode/reverseBits/reverseBits.go)

### [`searchMatrix 74. 搜索二维矩阵`](./leetcode/searchMatrix/searchMatrix.go)

### [`subsets 78. 子集(回溯)`](./leetcode/subsets/subsets.go)

### [`subsetsWithDup 90. 子集 II（回溯+剪枝）`](./leetcode/subsetsWithDup/subsetsWithDup.go)

### [`combinationSum 39. 组合总和（回溯+剪枝）`](./leetcode/combinationSum/combinationSum.go)

### [`combinationSum2 40. 组合总和 II（回溯+剪枝）`](./leetcode/combinationSum2/combinationSum2.go)

### [`permute 46. 全排列（回溯+剪枝）`](./leetcode/permute/permute.go)

### [`permuteUnique 47. 全排列 II（回溯+剪枝）`](./leetcode/permuteUnique/permuteUnique.go)

### [`minimumTimeRequired 1723. 完成所有工作的最短时间（回溯、递归）`](./leetcode/minimumTimeRequired/minimumTimeRequired.go)

### [`longestCommonSubsequence 1143. 最长公共子序列（动态规划）`](./leetcode/longestCommonSubsequence/longestCommonSubsequence.go)

### [`minDistance 583. 两个字符串的删除操作（动态规划）`](./leetcode/minDistance/minDistance.go)

### [`rob 198. 打家劫舍（动态规划）`](./leetcode/rob/rob.go)

### [`rob 213. 打家劫舍 II（动态规划）`](./leetcode/rob1/rob1.go)

### [`isScramble 87. 扰乱字符串（动态规划 3维）`](./leetcode/isScramble/isScramble.go)

### [`numDecodings 91. 解码方法（动态规划）`](./leetcode/numDecodings/numDecodings.go)

### [`largestDivisibleSubset 368. 最大整除子集（动态规划）`](./leetcode/largestDivisibleSubset/largestDivisibleSubset.go)

### [`combinationSum4 377. 组合总和 Ⅳ（动态规划）`](./leetcode/combinationSum4/combinationSum4.go)

### [`canCross 403. 青蛙过河（动态规划）`](./leetcode/canCross/canCross.go)

### [`lengthOfLIS 300. 最长递增子序列（动态规划+二分）`](./leetcode/lengthOfLIS/lengthOfLIS.go)

### [`numWays 1269. 停在原地的方案数（动态规划）`](./leetcode/numWays/numWays.go)

### [`numRabbits 781. 森林中的兔子（贪心算法）`](./leetcode/numRabbits/numRabbits.go)

### [`merge 88. 合并两个有序数组（双指针）`](./leetcode/merge/merge.go)

### [`removeDuplicates1 26. 删除有序数组中的重复项（双指针）`](./leetcode/removeDuplicates1/removeDuplicates1.go)

### [`removeElement 27. 移除元素（双指针、交换移除、通用解法）`](./leetcode/removeElement/removeElement.go)

### [`removeDuplicates2 80. 删除有序数组中的重复项 II（双指针）`](./leetcode/removeDuplicates2/removeDuplicates2.go)

### [`purchasePlans LCP 28. 采购方案（双指针）`](./leetcode/purchasePlans/purchasePlans.go)

### [`compareVersion 165. 比较版本号（双指针、字符串模拟）`](./leetcode/compareVersion/compareVersion.go)

### [`maxFrequency 5739. 最高频元素的频数（双指针、滑动窗口）`](./leetcode/maxFrequency/maxFrequency.go)

### [`findLongestWord 524. 通过删除字母匹配到字典里最长单词（双指针+排序+贪心）`](./leetcode/findLongestWord/findLongestWord.go)

### [`longestBeautifulSubstring 5740. 所有元音按顺序排布的最长子字符串（滑动窗口）`](./leetcode/longestBeautifulSubstring/longestBeautifulSubstring.go)

### [`search1 33. 搜索旋转排序数组（二分法）`](./leetcode/search1/search1.go)

### [`search2 81. 搜索旋转排序数组 II（二分法）`](./leetcode/search2/search2.go)

### [`findMin 153. 寻找旋转排序数组中的最小值（二分法）`](./leetcode/findMin/findMin.go)

### [`findMin2 154. 寻找旋转排序数组中的最小值 II（二分法）`](./leetcode/findMin2/findMin2.go)

### [`searchRange 34. 在排序数组中查找元素的第一个和最后一个位置（二分法）`](./leetcode/searchRange/searchRange.go)

### [`divide 29. 两数相除（二分法）`](./leetcode/divide/divide.go)

### [`shipWithinDays 1011. 在 D 天内送达包裹的能力（二分法）`](./leetcode/shipWithinDays/shipWithinDays.go)

### [`search 704. 二分查找（二分法）`](./leetcode/search/search.go)

### [`peakIndexInMountainArray 852. 山脉数组的峰顶索引（二分法）`](./leetcode/peakIndexInMountainArray/peakIndexInMountainArray.go)

### [`findPeakElement 162. 寻找峰值（二分法）`](./leetcode/findPeakElement/findPeakElement.go)

### [`isUgly 263. 丑数（朴素解法）`](./leetcode/isUgly/isUgly.go)

### [`nthUglyNumber 264. 丑数 II（三指针）`](./leetcode/nthUglyNumber/nthUglyNumber.go)

### [`storeWater LCP 33. 蓄水（模拟法）`](./leetcode/storeWater/storeWater.go)

### [`findTheWinner 5727. 找出游戏的获胜者（约瑟夫环、模拟、公式）`](./leetcode/findTheWinner/findTheWinner.go)

### [`minSideJumps 5728. 最少侧跳次数（动态规划）`](./leetcode/minSideJumps/minSideJumps.go)

### [`largestNumber 179. 最大数（排序）`](./leetcode/largestNumber/largestNumber.go)

### [`containsDuplicate 217. 存在重复元素（排序）`](./leetcode/containsDuplicate/containsDuplicate.go)

### [`containsNearbyDuplicate 219. 存在重复元素 II（滑动窗口、维护一个大小为k的set）`](./leetcode/containsNearbyDuplicate/containsNearbyDuplicate.go)

### [`containsNearbyAlmostDuplicate 220. 存在重复元素 III（滑动窗口 & 二分,桶排序）`](./leetcode/containsNearbyAlmostDuplicate/containsNearbyAlmostDuplicate.go)

### [`getMaximumXor 5719. 每个查询的最大异或值(异或)`](./leetcode/getMaximumXor/getMaximumXor.go)

### [`getXORSum 5737. 所有数对按位与结果的异或和(异或)`](./leetcode/getXORSum/getXORSum.go)

### [`decode 1720. 解码异或后的数组(异或)`](./leetcode/decode/decode.go)

### [`xorOperation 1486. 数组异或操作(异或、数学)`](./leetcode/xorOperation/xorOperation.go)

### [`decode1 1734. 解码异或后的排列(异或)`](./leetcode/decode1/decode1.go)

### [`xorQueries 1310. 子数组异或查询(异或、前缀和、树状数组)`](./leetcode/xorQueries/xorQueries.go)

### [`corpFlightBookings 1109. 航班预订统计(前缀和)`](./leetcode/corpFlightBookings/corpFlightBookings.go)

### [`NumArray 303. 区域和检索 - 数组不可变(前缀和)`](./leetcode/NumArray/NumArray.go)

### [`NumMatrix 304. 二维区域和检索 - 矩阵不可变(前缀和)`](./leetcode/NumMatrix/NumMatrix.go)

### [`countTriplets 1442. 形成两个异或相等数组的三元组数目(异或)`](./leetcode/countTriplets/countTriplets.go)

### [`getOrder 5736. 单线程 CPU（优先队列）`](./leetcode/getOrder/getOrder.go)

### [`strStr 28. 实现 strStr()（朴素解法、KMP）`](./leetcode/strStr/strStr.go)

### [`judgeSquareSum 633. 平方数之和（数学）`](./leetcode/judgeSquareSum/judgeSquareSum.go)

### [`rand10 470. 用 Rand7() 实现 Rand10()（拒绝采样）`](./leetcode/rand10/rand10.go)

### [`balancedStringSplit 1221. 分割平衡字符串（贪心）`](./leetcode/balancedStringSplit/balancedStringSplit.go)

### [`maxArea 11. 盛最多水的容器（贪心）`](./leetcode/maxArea/maxArea.go)

### [`jump 45. 跳跃游戏 II（贪心）`](./leetcode/jump/jump.go)

### [`numberOfBoomerangs 447. 回旋镖的数量（哈希表）`](./leetcode/numberOfBoomerangs/numberOfBoomerangs.go)

### [`checkValidString 678. 有效的括号字符串（动态规划+模拟）`](./leetcode/checkValidString/checkValidString.go)

### [`chalkReplacer 1894. 找到需要补充粉笔的学生编号（前缀和、模拟）`](./leetcode/chalkReplacer/chalkReplacer.go)

### [`isValidSudoku 36. 有效的数独（数组）`](./leetcode/isValidSudoku/isValidSudoku.go)

### [`lengthOfLastWord 58. 最后一个单词的长度（字符串）`](./leetcode/lengthOfLastWord/lengthOfLastWord.go)

### [`isPowerOfThree 326. 3的幂（数学）`](./leetcode/isPowerOfThree/isPowerOfThree.go)

### [`getSum 371. 两整数之和（位运算）`](./leetcode/getSum/getSum.go)


##  程序员面试金典（第 6 版）

### `isUnique 面试题 01.01 判定字符是否唯一`

### `CheckPermutation 面试题 01.02. 判定是否互为字符重排`

### `replaceSpaces 面试题 01.03. URL化`

### [`search 面试题 10.03. 搜索旋转数组（二分法）`](lcci/search/search.go)

### [`smallestK 面试题 17.14. 最小K个数（大小根堆、快速选择、排序）`](lcci/smallestK/smallestK.go)

### `massage 面试题 17.16. 按摩师`

### [`trap 面试题 17.21. 直方图的水量（单调栈、面积差值、双指针）`](lcci/trap/trap.go)


## 剑指 Offer（第 2 版）

### `findNumberIn2DArray 剑指 Offer 04. 二维数组中的查找`

### `reversePrint 剑指 Offer 06. 从尾到头打印链表`

### `buildTree 剑指 Offer 07. 重建二叉树`

### `CQueue 剑指 Offer 09. 用两个栈实现队列`

### `minArray 剑指 Offer 11. 旋转数组的最小数字`

### `exist 剑指 Offer 12. 矩阵中的路径`

### `movingCount 剑指 Offer 13. 机器人的运动范围(dfs,bfs)`

### `cuttingRope 剑指 Offer 14- I. 剪绳子`

### `cuttingRope 剑指 Offer 14- II. 剪绳子 II（快速幂算法）`

### `hammingWeight 剑指 Offer 15. 二进制中1的个数（与运算技巧）`

### `myPow 剑指 Offer 16. 数值的整数次方（快速幂算法）`

### `printNumbers 剑指 Offer 17. 打印从1到最大的n位数（大数全排列解法）`

### `deleteNode 剑指 Offer 18. 删除链表的节点（双指针）`

### `isMatch 剑指 Offer 19. 正则表达式匹配(动态规划)`

### `exchange 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面（双指针、快慢指针）`

### [`getKthFromEnd 剑指 Offer 22. 链表中倒数第k个节点（快慢指针）`](./lcof/getKthFromEnd/getKthFromEnd.go)

### `reverseList 剑指 Offer 24. 反转链表（快慢指针、递归）`

### `mergeTwoLists 剑指 Offer 25. 合并两个排序的链表(假头、递归)`

### `isSubStructure 剑指 Offer 26. 树的子结构(递归)`

### `mirrorTree 剑指 Offer 27. 二叉树的镜像(栈、递归)`

### `isSymmetric 剑指 Offer 28. 对称的二叉树（递归、bfs）`

### `spiralOrder 剑指 Offer 29. 顺时针打印矩阵`

### [`MinStack 剑指 Offer 30. 包含min函数的栈(栈)`](./lcof/MinStack/MinStack.go)

### `validateStackSequences 剑指 Offer 31. 栈的压入、弹出序列(栈)`

### `levelOrder 剑指 Offer 32 - I. 从上到下打印二叉树（BFS、队列）`

### `levelOrder2 剑指 Offer 32 - II. 从上到下打印二叉树 II（BFS、DFS）`

### `levelOrder3 剑指 Offer 32 - III. 从上到下打印二叉树 III（BFS、DFS）`

### `verifyPostorder 剑指 Offer 33. 二叉搜索树的后序遍历序列(递归、单调栈)`

### [`pathSum 剑指 Offer 34. 二叉树中和为某一值的路径（回溯法）`](./lcof/pathSum/pathSum.go)

### `copyRandomList 剑指 Offer 35. 复杂链表的复制（map,原地复制）`

### [`treeToDoublyList 剑指 Offer 36. 二叉搜索树与双向链表（dfs）`](./lcof/treeToDoublyList/treeToDoublyList.go)

### [`serialize 剑指 Offer 37. 序列化二叉树（层序遍历、找规律）`](./lcof/serialize/serialize.go)

### [`permutation 剑指 Offer 38. 字符串的排列（回溯算法）`](./lcof/permutation/permutation.go)

### [`majorityElement 剑指 Offer 39. 数组中出现次数超过一半的数字（摩尔投票,字典,排序）`](./lcof/majorityElement/majorityElement.go)

### [`getLeastNumbers 剑指 Offer 40. 最小的k个数(最大堆,快速选择)`](./lcof/getLeastNumbers/getLeastNumbers.go)

### [`MedianFinder 剑指 Offer 41. 数据流中的中位数（最大堆、最小堆）`](./lcof/MedianFinder/MedianFinder.go)

### [`maxSubArray 剑指 Offer 42. 连续子数组的最大和（动态规划）`](./lcof/maxSubArray/maxSubArray.go)

### [`countDigitOne 剑指 Offer 43. 1～n 整数中 1 出现的次数(数学)`](./lcof/countDigitOne/countDigitOne.go)

### [`findNthDigit 剑指 Offer 44. 数字序列中某一位的数字(数学)`](./lcof/findNthDigit/findNthDigit.go)

### [`minNumber 剑指 Offer 45. 把数组排成最小的数(自定义排序)`](./lcof/minNumber/minNumber.go)

### [`translateNum 剑指 Offer 46. 把数字翻译成字符串(动态规划)`](./lcof/translateNum/translateNum.go)

### [`maxValue 剑指 Offer 47. 礼物的最大价值(动态规划)`](./lcof/maxValue/maxValue.go)

### [`lengthOfLongestSubstring 剑指 Offer 48. 最长不含重复字符的子字符串(滑动窗口)`](./lcof/lengthOfLongestSubstring/lengthOfLongestSubstring.go)

### [`nthUglyNumber 剑指 Offer 49. 丑数(三指针)`](./lcof/nthUglyNumber/nthUglyNumber.go)

### [`firstUniqChar 剑指 Offer 50. 第一个只出现一次的字符(hash表、有序hash表)`](./lcof/firstUniqChar/firstUniqChar.go)

### [`reversePairs 剑指 Offer 51. 数组中的逆序对(分治算法、归并排序)`](./lcof/reversePairs/reversePairs.go)

### [`getIntersectionNode 剑指 Offer 52. 两个链表的第一个公共节点(链表)`](./lcof/getIntersectionNode/getIntersectionNode.go)

### [`search 剑指 Offer 53 - I. 在排序数组中查找数字 I(俩次二分)`](./lcof/search/search.go)

### [`missingNumber 剑指 Offer 53 - II. 0～n-1中缺失的数字(二分法)`](./lcof/missingNumber/missingNumber.go)

### [`kthLargest 剑指 Offer 54. 二叉搜索树的第k大节点(中序遍历+提前返回)`](./lcof/kthLargest/kthLargest.go)

### [`maxDepth 剑指 Offer 55 - I. 二叉树的深度(层序遍历、后序遍历)`](./lcof/maxDepth/maxDepth.go)

### [`isBalanced 剑指 Offer 55 - II. 平衡二叉树(深度优先搜索)`](./lcof/isBalanced/isBalanced.go)

### [`singleNumbers 剑指 Offer 56 - I. 数组中数字出现的次数(异或)`](./lcof/singleNumbers/singleNumbers.go)

### [`singleNumber 剑指 Offer 56 - II. 数组中数字出现的次数 II(位运算)`](./lcof/singleNumber/singleNumber.go)

### [`twoSum 剑指 Offer 57. 和为s的两个数字(双指针)`](./lcof/twoSum/twoSum.go)

### [`findContinuousSequence 剑指 Offer 57 - II. 和为s的连续正数序列(双指针)`](./lcof/findContinuousSequence/findContinuousSequence.go)

### [`reverseWords 剑指 Offer 58 - I. 翻转单词顺序(双指针)`](./lcof/reverseWords/reverseWords.go)

### [`reverseLeftWords 剑指 Offer 58 - II. 左旋转字符串(api)`](./lcof/reverseLeftWords/reverseLeftWords.go)

### [`maxSlidingWindow 剑指 Offer 59 - I. 滑动窗口的最大值(单调队列)`](./lcof/maxSlidingWindow/maxSlidingWindow.go)

### [`MaxQueue 剑指 Offer 59 - II. 队列的最大值(单调双向队列)`](./lcof/MaxQueue/MaxQueue.go)

### [`dicesProbability 剑指 Offer 60. n个骰子的点数(动态规划)`](./lcof/dicesProbability/dicesProbability.go)

### [`isStraight 剑指 Offer 61. 扑克牌中的顺子(集合 Set / 排序)`](./lcof/isStraight/isStraight.go)

### [`lastRemaining 剑指 Offer 62. 圆圈中最后剩下的数字(数学 / 动态规划)`](./lcof/lastRemaining/lastRemaining.go)

### [`maxProfit 剑指 Offer 63. 股票的最大利润(动态规划)`](./lcof/maxProfit/maxProfit.go)

### [`sumNums 剑指 Offer 64. 求1+2+…+n(递归、数学公式)`](./lcof/sumNums/sumNums.go)

### [`add 剑指 Offer 65. 不用加减乘除做加法(位运算)`](./lcof/add/add.go)

### [`constructArr 剑指 Offer 66. 构建乘积数组(两次dp)`](./lcof/constructArr/constructArr.go)

### [`strToInt 剑指 Offer 67. 把字符串转换成整数(数字越界处理)`](./lcof/strToInt/strToInt.go)

### [`lowestCommonAncestor 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先(迭代、递归)`](./lcof/lowestCommonAncestor/lowestCommonAncestor.go)

### [`lowestCommonAncestor2 剑指 Offer 68 - II. 二叉树的最近公共祖先(DFS)`](./lcof/lowestCommonAncestor2/lowestCommonAncestor2.go)