算法分享-01

ljs666 / 2023-09-06 / 原文

一. 初识数据结构与算法

“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”——Sartaj Sahni，《数据结构、算法与应用》

“数据结构是ADT（抽象数据类型 Abstract DataType）的物理实现。”—— Clifford A.Shaffer，《数据结构与算法分析》

“数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。” ——中文维基百科

1. 常见的数据结构

数组（Aarray）
栈（Stack）
链表（Linked List）
图（Graph）
散列表（Hash）
队列（Queue）
堆（Heap）
树（Tree）

2. 算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

二. 数组结构

什么是数组？
字面理解就是 数字的组合
其实不太准确，准确的来说数组是一个 数据的集合
也就是我们把一些数据放在一个盒子里面，按照顺序排好
```
[1, 2, 3, 'hello', true, false]
```
这个东西就是一个数组，存储着一些数据的集合

数据类型分类

number / string / boolean / undefined / null / object / function / array / ...
数组也是数据类型中的一种
我们简单的把所有数据类型分为两个大类 基本数据类型 和 复杂数据类型
基本数据类型： number / string / boolean / undefined / null
复杂数据类型： object / function / array / ...

1 创建一个数组

数组就是一个 []
在 [] 里面存储着各种各样的数据，按照顺序依次排好

字面量创建一个数组

直接使用 [] 的方式创建一个数组

// 创建一个空数组
var arr1 = []

// 创建一个有内容的数组
var arr2 = [1, 2, 3]

内置构造函数创建数组

使用 js 的内置构造函数 Array 创建一个数组

// 创建一个空数组
var arr1 = new Array()

// 创建一个长度为 10 的数组
var arr2 = new Array(10)

// 创建一个有内容的数组
var arr3 = new Array(1, 2, 3)

2 数组的 length

length: 长度的意思
length 就是表示数组的长度，数组里面有多少个成员，length 就是多少
```
// 创建一个数组
var arr = [1, 2, 3]

console.log(arr.length) // 3
```

3 数组的索引

索引，也叫做下标，是指一个数据在数组里面排在第几个的位置
注意： 在所有的语言里面，索引都是从 0 开始的

在 js 里面也一样，数组的索引从 0 开始

// 创建一个数组
var arr = ['hello', 'world']

上面这个数组中，第 0 个 数据就是字符串 hello，第 1 个 数据就是字符串 world

想获取数组中的第几个就使用 数组[索引] 来获取

var arr = ['hello', 'world']

console.log(arr[0]) // hello
console.log(arr[1]) // world

4 数组的常用方法

数组是一个复杂数据类型，我们在操作它的时候就不能再想基本数据类型一样操作了
比如我们想改变一个数组
```
// 创建一个数组
var arr = [1, 2, 3]

// 我们想把数组变成只有 1 和 2
arr = [1, 2]
```
- 这样肯定是不合理，因为这样不是在改变之前的数组
- 相当于心弄了一个数组给到 arr 这个变量了
- 相当于把 arr 里面存储的地址给换了，也就是把存储空间换掉了，而不是在之前的空间里面修改
- 所以我们就需要借助一些方法，在不改变存储空间的情况下，把存储空间里面的数据改变了

数组常用方法之 push

push 是用来在数组的末尾追加一个元素

var arr = [1, 2, 3]

// 使用 push 方法追加一个元素在末尾
arr.push(4)

console.log(arr) // [1, 2, 3, 4]

数组常用方法之 pop

pop 是用来删除数组末尾的一个元素

var arr = [1, 2, 3]

// 使用 pop 方法删除末尾的一个元素
arr.pop()

console.log(arr) // [1, 2]

数组常用方法之 unshift

unshift 是在数组的最前面添加一个元素

var arr = [1, 2, 3]

// 使用 unshift 方法想数组的最前面添加一个元素
arr.unshift(4)

console.log(arr) // [4, 1, 2, 3]

数组常用方法之 shift

shift 是删除数组最前面的一个元素

var arr = [1, 2, 3]

// 使用 shift 方法删除数组最前面的一个元素
arr.shift()

console.log(arr) // [2, 3]

数组常用方法之 splice

splice 是截取数组中的某些内容，按照数组的索引来截取
语法： splice(从哪一个索引位置开始，截取多少个，替换的新元素) （第三个参数可以不写）
```
var arr = [1, 2, 3, 4, 5]

// 使用 splice 方法截取数组
arr.splice(1, 2)

console.log(arr) // [1, 4, 5]
```
- arr.splice(1, 2) 表示从索引 1 开始截取 2 个内容
- 第三个参数没有写，就是没有新内容替换掉截取位置
```
var arr = [1, 2, 3, 4, 5]

// 使用 splice 方法截取数组
arr.splice(1, 2, '我是新内容')

console.log(arr) // [1, '我是新内容', 4, 5]
```
- arr.splice(1, 2, '我是新内容') 表示从索引 1 开始截取 2 个内容
- 然后用第三个参数把截取完空出来的位置填充

数组常用方法之 reverse

reverse 是用来反转数组使用的

var arr = [1, 2, 3]

// 使用 reverse 方法来反转数组
arr.reverse()

console.log(arr) // [3, 2, 1]

数组常用方法之 sort

sort 是用来给数组排序的

var arr = [2, 3, 1]

// 使用 sort 方法给数组排序
arr.sort()

console.log(arr) // [1, 2, 3]

这个只是一个基本的简单用法

数组常用方法之 concat

concat 是把多个数组进行拼接

和之前的方法有一些不一样的地方，就是 concat 不会改变原始数组，而是返回一个新的数组

var arr = [1, 2, 3]

// 使用 concat 方法拼接数组
var newArr = arr.concat([4, 5, 6])

console.log(arr) // [1, 2, 3]
console.log(newArr) // [1, 2, 3, 4, 5, 6]

注意： concat 方法不会改变原始数组

数组常用方法之 join

join 是把数组里面的每一项内容链接起来，变成一个字符串
可以自己定义每一项之间链接的内容 join(要以什么内容链接)
不会改变原始数组，而是把链接好的字符串返回
```
var arr = [1, 2, 3]

// 使用 join 链接数组
var str = arr.join('-')

console.log(arr) // [1, 2, 3]
console.log(str) // 1-2-3
```
- 注意： join 方法不会改变原始数组，而是返回链接好的字符串

数组常用方法之 indexOf

indexOf 用来找到数组中某一项的索引
语法： indexOf(你要找的数组中的项)
```
var arr = [1, 2, 3, 4, 5]

// 使用 indexOf 超找数组中的某一项
var index = arr.indexOf(3)

console.log(index) // 2
```
- 我们要找的是数组中值为 3 的那一项
- 返回的就是值为 3 的那一项在该数组中的索引

如果你要找的内容在数组中没有，那么就会返回 -1

var arr = [1, 2, 3, 4, 5]

// 使用 indexOf 超找数组中的某一项
var index = arr.indexOf(10)

console.log(index) // -1

你要找的值在数组中不存在，那么就会返回 -1

数组常用方法之 forEach

和 for 循环一个作用，就是用来遍历数组的

语法：arr.forEach(function (item, index, arr) {})

var arr = [1, 2, 3]

// 使用 forEach 遍历数组
arr.forEach(function (item, index, arr) {
  // item 就是数组中的每一项
  // index 就是数组的索引
  // arr 就是原始数组
  console.log('数组的第 ' + index + ' 项的值是 ' + item + '，原始数组是', arr)
})

forEach() 的时候传递的那个函数，会根据数组的长度执行
数组的长度是多少，这个函数就会执行多少回

数组常用方法之 map

和 forEach 类似，只不过可以对数组中的每一项进行操作，返回一个新的数组

var arr = [1, 2, 3]

// 使用 map 遍历数组
var newArr = arr.map(function (item, index, arr) {
  // item 就是数组中的每一项
  // index 就是数组的索引
  // arr 就是原始数组
  return item + 10
})

console.log(newArr) // [11, 12, 13]

数组常用方法之 filter

和 map 的使用方式类似，按照我们的条件来筛选数组

把原始数组中满足条件的筛选出来，组成一个新的数组返回

var arr = [1, 2, 3]

// 使用 filter 过滤数组
var newArr = arr.filter(function (item, index, arr) {
  // item 就是数组中的每一项
  // index 就是数组的索引
  // arr 就是原始数组
  return item > 1
})

console.log(newArr) // [2, 3]