关于go:Go-数据结构与算法持续更新中

参考

数据结构

• 实质上，数据结构底层存储形式就两种: 数组 和 链表
• 基本操作就四种: 增删改查
• 遍历形式就两种: 迭代 和 递归

算法

• 计算机算法 (非数学算法) 的实质就是穷举
• 如何穷举？即无脱漏的列举所有可能解，此类问题个别是递归类问题，最典型的是 DP 系列问题
• 如何聪慧的穷举？即防止所有冗余计算，耗费尽可能少的资源求出答案，一些耳熟能详的非递归算法技巧，都能够归在这一类

• 如何刷算法题:

  先刷数组、链表相干的根本算法
  把握根本算法之后，刷二叉树相干的罕用算法
  最初刷动静布局、回溯、DPS 等算法

数组

双指针技巧

• 快、慢指针

  定义 
  对数组而言，两个指针对应两个下标，两个下标往同一个方向前进，一个快，一个慢
  
  经典例题
  求一个有序数组的不反复元素最多有多少个？如 [1,2,3,3,5,6,8,9,9] 应输入 [1,2,3,5,6,8,9] 7 个
  解析：快指针一直往后移，如果碰到的元素与慢指针指向的元素不同，则慢指针右移一步，且将快指针指向的值 赋给 以后 慢指针指向 的 数组元素

  package doublePointer
  
  func SlowFast(sorted_nums []int) []int{sorted_nums_len := len(sorted_nums)
  
      if sorted_nums_len <= 1 {return sorted_nums}
  
      slow, fast := 0, 0
      for ;fast < sorted_nums_len; fast++{if sorted_nums[slow] != sorted_nums[fast]{
              slow++
              sorted_nums[slow] = sorted_nums[fast]
          }    
      }
  
      return sorted_nums[:slow+1]
  }

• 左右指针

  定义 
  对数组而言，两个指针对应两个下标，两个下标由中间往两头聚拢 或者 由两头向中间挪动

前缀和数组

• 定义

  前缀和数组由老数组结构而得，前缀和数组中每个下标 i 的值 为 老数组前 i 个小标所指向的元素之和
  那么在计算老数组 [i:j] 时，只需计算 前缀和数组[j+1] - 前缀和数组[i] 即可

• 一维数组的前缀和数组

  package preSumList
  
  func NewList(oldList []int) []int {newList_len := len(oldList) + 1
      newList := make([]int, newList_len)
      // 老数组前 0 项之和为 0
      newList[0] = 0
      for i, v := range oldList{newList[i+1] = newList[i] + v
      }
  
      return newList
  }