linear

Documentation

Index

• func BubbleSort(arr []int)
• func FastSort(arr []int, left, right int)
• func FindMaxWater(arr []int) int
• func FindMedianSortedArrays(nums1 []int, nums2 []int) float64
• func GenerateParenthesis(n int) []string
• func HeapSort(arr []int)
• func InsertionSort(arr []int)
• func MaxArea(height []int) int
• func MergeSort(arr []int) []int
• func MergeTwoSortedArr(num1 []int, num2 []int) []int
• func RemoveDuplicates(nums []int) int
• func RemoveElement(nums []int, val int) int
• func SearchInsert(nums []int, target int) int
• func SelectSort(nums []int)
• func ShellSort(nums []int)
• func TwoSum(nums []int, target int) []int
• type ListNode
  • func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode
  • func AddTwoNumbersV2(l1 *ListNode, l2 *ListNode) *ListNode
  • func MergeKLists(lists []*ListNode) *ListNode
  • func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode
  • func RemoveNthFromEnd(head *ListNode, n int) *ListNode
  • func RemoveNthFromEndV2(head *ListNode, n int) *ListNode
  • func ReverseK(head *ListNode, k int) *ListNode
  • func ReverseKGroup(head *ListNode, k int) *ListNode
  • func SwapPairs(head *ListNode) *ListNode
  • func SwapPairsV2(head *ListNode) *ListNode
  • func (head *ListNode) PrintLinkedList()

Functions

func BubbleSort

func BubbleSort(arr []int)

BubbleSort 冒泡排序 每一趟扫描交换 都可以把最大的扫描出来 两两比较, 一轮循环之后 最大的就是到尾部位置, 然后一直重复即可; 稳定排序; O(NN)

func FastSort

func FastSort(arr []int, left, right int)

FastSort arr[left, right]

func FindMaxWater

func FindMaxWater(arr []int) int

FindMaxWater 在一个数组中出现次数大于等于一半

func FindMedianSortedArrays

func FindMedianSortedArrays(nums1 []int, nums2 []int) float64

FindMedianSortedArrays 寻找两个有序数组的中位数 使用分割线; leetcode4 寻找两个有序数组的中位数 中位数定义： 有序数组 如果长度是奇数 n/2 就是中位数 如果是偶数 (n/2 + n/2-1) >> 1 就是中位数

func GenerateParenthesis

func GenerateParenthesis(n int) []string

GenerateParenthesis 生成有效括号 leetcode22 括号的生成 算法导论 深度优先遍历 DFS depth first search; 回溯+剪枝 所有的叶子节点就是解

func HeapSort

func HeapSort(arr []int)

HeapSort 使用的堆排序 堆得概念, 堆就是 完全二叉树 从上到下 从左到右 排序, 和满二叉树一样的序号 i 子节点 2i + 1; 2i + 2 这是一颗子树 4 6 8 5 9 升序是大顶堆

func InsertionSort

func InsertionSort(arr []int)

InsertionSort 插入排序 算法的入门 O(n^2); 反向冒泡 - 稳定排序, 比 冒泡的效率快很多; 前面的数组有序效率很高; n 在[0, n) 总是有序的 把第n个数 和前面有序的比较 严格小于 前面的就交换, 然后选择有序的位置; 可以不交换

func MaxArea

func MaxArea(height []int) int

MaxArea 最大的面积 leetcode11 盛最多水的容器 area = (r-l)Min(p[r], p[l]) 这个就是面积的计算公式 每次查找必然 r-l 就是 -- 过程, min(x, y) 这个尽可能的大

func MergeSort

func MergeSort(arr []int) []int

MergeSort conquer and merge; 调用这个方法保证 [left, right] 这个区间的切片有序

func MergeTwoSortedArr

func MergeTwoSortedArr(num1 []int, num2 []int) []int

MergeTwoSortedArr 合并两个有序的数组 面临的问题就是不等长数组 但是有序, 可以填入指定的切片, 注意尽可能把 代码的逻辑 布局写的相对美观一些, 有一些面试官 就是看代码风格的; 不要写的乱糟糟的, 尽管我们可以通过 接口 抽象行为; 下面这个实现确实有点乱 重新写一下

func RemoveDuplicates

func RemoveDuplicates(nums []int) int

RemoveDuplicates 要求：空间复杂度 O(1) 时间复杂度 O(N) leetcode26 删除有序数组的重复项 要求原地删除 返回删除之后的数组的长度 Level: easy

func RemoveElement

func RemoveElement(nums []int, val int) int

RemoveElement 移除所有等于val元素 leetcode27: 移除元素 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组 Level: easy 这个不是有序的

func SearchInsert

func SearchInsert(nums []int, target int) int

SearchInsert 搜索插入的位置 如果有就返回索引 如果没有 就返回应该插入的位置 leetcode35 搜索插入的位置

func SelectSort

func SelectSort(nums []int)

SelectSort 选择排序 最简单 最没用; 依次查找最小的数 这个是严格小于; T=O(NN) 不稳定的; 2 5 5 2 8 存在一个就是不稳定;

func ShellSort

func ShellSort(nums []int)

ShellSort 希尔排序; 基于插入排序 优化了间隔; 先写出插入排序 然后使用 一个 3h + 1 序列 改进的插入排序, 间隔大 比较的次数小; 间隔小, 比较的距离小; O(n^1.3)

func TwoSum

func TwoSum(nums []int, target int) []int

TwoSum 两数之和 本题是在一个没有重复的数组中查找两个数索引返回 不重复查找 使用一个等长的hash table效率高 leetcode1

Types

type ListNode

type ListNode struct {
	Val  int
	Next *ListNode
}

ListNode leetcode定义链表的一个节点的通用结构体

func AddTwoNumbers

func AddTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode

AddTwoNumbers 两个非空的链表 1->2->3 2->3->4 ==> 3->5->7 第一想法就是这不是就是 两个有序数组合并那种写法 处理长度不等 非空; 保证开始的节点不是0 [9,9,9,9,9,9,9] [9,9,9,9] [不要忘记 处理最后一个进位] leetcode2

func AddTwoNumbersV2

func AddTwoNumbersV2(l1 *ListNode, l2 *ListNode) *ListNode

AddTwoNumbersV2 第二种写法 上面那是一种处理不等长的一般操作 这个通过补0 使短的等长 leetcode2 两数相加

func MergeKLists

func MergeKLists(lists []*ListNode) *ListNode

MergeKLists 合并k个有序链表 leetcode23 合并k个有序链表 Level diff; 妈的我做这个题目真的就是喜欢玩这种 conquer and merge

func MergeTwoLists

func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode

MergeTwoLists 合并两个有序列表 leetcode21 合并两个有序列表 又可以使用递归 我透了

func RemoveNthFromEnd

func RemoveNthFromEnd(head *ListNode, n int) *ListNode

RemoveNthFromEnd 删除链表的倒数第n个节点 leetcode19 删除链表的倒数第n个节点

func RemoveNthFromEndV2

func RemoveNthFromEndV2(head *ListNode, n int) *ListNode

RemoveNthFromEndV2 删除倒数第n个节点 使用递归来解 第一次 leetcode19 删除链表的倒数第n个节点 利用递归 利用方法栈出栈的次数 需要定义全局变量 leetcode 全局变量有问题 操

func ReverseK

func ReverseK(head *ListNode, k int) *ListNode

func ReverseKGroup

func ReverseKGroup(head *ListNode, k int) *ListNode

ReverseKGroup K 个一组翻转链表 leetcode25 Level: diff

func SwapPairs

func SwapPairs(head *ListNode) *ListNode

SwapPairs 交换相邻的节点 leetcode24 交换相邻的节点 一般做法 感觉下面写法很怪 明天再写 并且把递归的也写了了

func SwapPairsV2

func SwapPairsV2(head *ListNode) *ListNode

SwapPairsV2 使用递归

func (*ListNode) PrintLinkedList

func (head *ListNode) PrintLinkedList()