算法和数据结构

伪代码与流程图

逻辑

结构化编程理论

只需要三种语句，就可以表示逻辑。

顺序执行语句

语句1
语句2
复制代码

条件执行语句

if ... then ... else ...
if ... else if ... else
复制代码

循环语句

while ... do ...
for i from 1 to n ...
复制代码

流程图、伪代码的好处

锻炼大脑

必须自己画出来，不能运行在计算机里。

整理思路

思路乱，则图乱。伪代码写不好，代码更写不好。

用流程图找到N个数中的最大数

数据结构

数据结构就是数据与数据之间的关系和结构。

数据结构 = 数据形式 + 操作

不同形式的数据暴露不同的操作

如何表示两个数据

如果顺序有意义

[x,y]表示第一个是x，第二个是y

[y,x]表示第一个是y，第二个是x

比如坐标就是这样的数据

要提供first和last操作

如果顺序无意义

(x,y)和(y,x)一样

比如血压值(120,80)和(80,120)没区别

不需要提供first和last操作

如何表示N个数据

如果顺序有意义

数组表示[a1,a2,…,aN]

要提供索引操作get(i)

要提供 add / indexOf / delete 操作

如果顺序没意义

集合表示{a1,a2,…,aN}

要提供 add / delete / has 操作

如何表示N对N数据

比如学号

用哈希表表示

hash = {1001 => ‘小方’,1002 => ‘小红’}

注意了，和JS不同的是，JS的参数只能是字符串，而这里可以是数字、字符串、对象等等。

面试题：

有一段英文对白，里面只会出现a-z、A-Z、标点符号和空格，请告诉我每个字符出现的次数。

例如 Hi,I'm River，输出v出现1次，R出现1次，r出现1次…

str = `Hi,I'm River`
hash = {}

for i from 0 to str.length-1
  key = str.get(i)
  value = hash.get(key,0) + 1
  hash.set(key,value)

for key,value from hash
  print `${key} 出现了 ${value} 次`
复制代码

数据结构的作用

提前记住一些结构

这些结构很常见，能让你快速理清思路，面试经常问

锻炼抽象能力

一种数据结构往往能解决很多类似的问题，如果你选错了数据结构，根本想不出思路

排序算法

选择排序

selection sort

求最小值

找出两个数中最小的那个

代码

let minOf2 = (numbers) => {
	if(numbers[0] < numbers[1]){
		return numbers[0]
	}else{
		return numbers[1]
	}
}
复制代码

优化代码

let minOf2 = numbers =>
	numbers[0] < numbers[1]
		? numbers[0] : numbers[1]
复制代码

再优化代码

let minOf2 = ([a,b]) => a < b ? a : b
复制代码

这种写法叫做析构赋值

调用

minOf2([1,2])	//小白调用法
minOf2.call(null,[1,2])	//高手调用法
复制代码

现成API

JS内置了 Math.min

Math.min(1,2)	//1
Math.min.call(null,1,2)
Math.min.apply(null,[1,2])
复制代码

关于Math

看起来Math像Object一样是构造函数，实际上Math只是一个普通对象。

首字母大写是构造函数，这是唯一特例。

找出三个数中最小的那个

代码

let minOf3 = ([a,b,c]) => {
	return minOf2([minOf2([a,b]),c])
}
复制代码

或者

let minOf3 = ([a,b,c]) => {
	return minOf2([a,minOf2([b,c])])
}
复制代码

找出四个数中最小的那个

代码

let minOf4 = ([a,b,c,d]) => {
	return minOf2([a,minOf3([b,c,d])])
}
复制代码

任意长度数组求最小值，都可以通过 minOf2 实现

求任意长度数组最小值

代码

let min = (numbers) => {
	return min(
		[numbers[0],min(numbers.slice(1))]
	)
}	//代码会死循环，需添加中止条件
复制代码

let min = (numbers) => {
	if(numbers.length > 2){
		return min(
			[numbers[0],min(numbers.slice(1))]
		)
	}else{
		return Math.min.apply(null,numbers)
	}
}	//这就是递归
复制代码

用递归实现

递归

特点

函数不停调用自己，每次调用的参数略有不同

当满足某个简单条件时，则实现一个简单的调用

最终算出结果

理解

可以用代入法快速理解递归

可以用调用栈快速理解递归

长度为2的数组排序

代码

let sort2 = ([a,b]) => {
	if(a < b){
		return [a,b]	//这里的[a,b]和上面的[a,b]是两个不同的数组
	}else{
		return [b,a]
	}
}
复制代码

优化代码

let sort2 = ([a,b]) =>
	a < b ? [a,b] : [a,b]
复制代码

长度为3的数组排序

代码

let sort3 = ([a,b,c]) => {
	return [min([a,b,c]),sort2([???])]
}	//无法将最小值从数组里删掉
复制代码

改进代码

let sort3 = (numbers) => {
	let index = minIndex(numbers)
	let min = numbers[index]
	numbers.splice(index,1)	//从numbers里删掉min
	return [min].concat(sort2(numbers))
}
复制代码

minIndex的实现

let minIndex = (numbers) => numbers.indexOf(min(numbers))	
	//这是一个取巧的办法，如果有两个相同的数，也只会返回第一个数的index
复制代码

长度为4的数组排序

代码

let sort4 = (numbers) => {
	let index = minIndex(numbers)
	let min = numbers[index]
	numbers.splice(index,1)
	return [min].concat(sort3(numbers))
}
复制代码

长度为N的数组排序

代码

let sort = (numbers) => {
	if(numbers.length > 2){
		let index = minIndex(numbers)
		let min = numbers[index]
		numbers.splice(index,1)
		return [min].concat(sort(numbers))
	}else{
		return numbers[0] < numbers[1] ? numbers : numbers.reverse()
	}
}
复制代码

用循环实现

minIndex

永远都有两种写法：“递归”和“循环”

重写minIndex

目前的minIndex：

let minIndex = (numbers) => {
	numbers.indexOf(min(numbers))
}
let min = (numbers) => {
	return min(
		[numbers[0],min(numbers.slice(1))]
	)
}
复制代码

重写minIndex：

let minIndex = (numbers) => {
	let index = 0
	for(let i = 1; i < numbers.length; i++){
		if(numbers[i] < numbers[index]){
			index = i
		}
	}
	return index
}
复制代码

重写sort

目前的sort：

let sort = (numbers) => {
	if(numbers.length > 2){
		let index = minIndex(numbers)
		let min = numbers[index]
		numbers.splice(index,1)
		return [min].concat(sort(numbers))
	}else{
		return numbers[0] < numbers[1] ? numbers : numbers.reverse()
	}
}
复制代码

重写sort：

let sort = (numbers) => {
	for(let i = 0; i < ???; i++){
		let index = minIndex(numbers)
		//index是当前最小数的下标，index对应的数应当放到i处
		swap(numbers, index, i)
	}
}
复制代码

实现swap

let swap = (array, i ,j) => {
	let temp = array[i]
	array[i] = array[j]
	array[j] = temp
}
swap(numbers,1,2)
复制代码

错误地实现swap：

let swap = (a,b) => {
	let temp = a
	a = b
	b = temp
}
swap(numbers[1],numbers[2])
复制代码

numbers[1]和numbers[2]的值原封不动，这是因为a、b是简单类型，传参的时候会复制值。而上面正确swap写法，numbers是对象，传参复制地址。

那么???是什么呢？

假设numbers的长度n=4，那么比较只需要进行到i=2就可以，所以上面代码???补充为numbers.length-1

minIndex查找范围有问题

let index = minIndex(numbers)这句话有问题，如果上次循环已经找到了第一个最小的数字，那么之后找最小数字之时，就要忽略第一个数字。

let index = minIndex(numbers.slice(i)) + i

后面+i，因为如果不加，那么index总是从0数起，splice减去了i，需要再后面补上i，这样index才能对应正确的minIndex

最终代码

let sort = (numbers) => {
	for(let i = 0; i < numbers.length - 1; i++){
		console.log(`----`)
		console.log(`i: ${i}`)
		let index = minIndex(numbers.slice(i)) + i
		console.log(`index: ${index}`)
		console.log(`min: ${numbers[index]}`)
		if(index !== i){
			swap(numbers, index, i)
			console.log(`swap ${index}: ${i}`)
			console.log(numbers)
		}
	}
	return numbers
}
复制代码

补充函数

let swap = (array, i ,j) => {
	let temp = array[i]
	array[i] = array[j]
	array[j] = temp
}
let minIndex = (numbers) => {
	let index = 0
	for(let i = 1; i < numbers.length; i++){
		if(numbers[i] < numbers[index]){
			index = i
		}
	}
	return index
}
复制代码

快速排序

quick sort

递归思路

以某某为基准，小的去前面，大的去后面

只需要重复说这句话，就能排序

快排源码

let quickSort = arr => {
	if(arr.length <= 1){return arr;}
	let pivotIndex = Math.floor(arr.length / 2);	//pivot 中心点
	let pivot = arr.splice(pivotIndex,1)[0];
	let left = [];
	let right = [];
	for(let i = 0; i < arr.length; i++){
		if(arr[i] < pivot){
			left.push(arr[i])
		}else{
			right.push(arr[i])
		}
	}
		return quickSort(left).concat([pivot],quickSort(right))
}
复制代码

归并排序

merge sort

递归思路

不以某某为基准，左边一半排好序，右边一半排好序

然后把左右两边合并(merge)起来

归并排序源码

let mergeSort = arr => {
	let k = arr.length
	if(k === 1){return arr}
	let left = arr.slice(0,Math.floor(k/2))
	let right = arr.slice(Math.floor(k/2))
	return merge(mergeSort(left),mergeSort(right))
}
let merge = (a,b) => {
	if(a.length === 0) return b
	if(b.length === 0) return a
	return a[0] > b[0]
	? [b[0]].concat(merge(a,b.slice(1)))
	: [a[0]].concat(merge(a.slice(1),b))
}
复制代码

计数排序

counting sort

递归思路

用一个哈希表作记录

发现数字N就记为N: 1，如果再次发现N就加1

最后把哈希表的key全部打印，假设N: m，那么N需要打印m次

记录数组的同时，也会记录一个max，遍历后会从小到大依次打印出来。

计数排序源码

let countSort = arr => {
	let hashTable ={}, max = 0, result = []
	for(let i = 0; i < arr.length; i++){	//遍历数组
		if(!(arr[i] in hashTable)){
			hashTable[arr[i]] = 1
		}else{
			hashTable[arr[i]] += 1
		}
		if(arr[i] > max){max = arr[i]}
	}
	for(let j = 0; j <= max; j++){	//遍历哈希表
		if(j in hashTable){
			for(let i = 0; i < hashTable[j]; i++){
				result.push(j)
			}
		}
	}
	return result
}
复制代码

计数排序的特点

数据结构不同

使用了额外的hashTable

只遍历数组一遍（不过还要遍历依次hashTable）

这就是“用空间换时间”

时间复杂度对比

选择排序O(n^2)

快速排序O(n log2 n)

归并排序O(n log2 n)

计数排序O(n + max)，最少

其他排序

冒泡排序

插入排序

点击 INS

希尔排序

选择Shell Sort

基数排序

点击RAD

7.3 数据结构

队列&栈

队列 Queue

先进先出 FIFO 的数组

题目

请实现一个餐厅叫号网页，点击“取号”按钮生成一个号码，点击“叫号”按钮显示“请X号就餐”

代码

queue.push为入队

queue.shift为出队

栈 Stack

后进先出 LIFO 的数组

举例

JS函数的调用栈call stack就是一个栈

假设f1调用了f2，f2又调用了f3

那么f3结束后应该回到f2，f2结束后应该回到f1

代码

function f1(){let a = 1; return a + f2()}
function f2(){let b = 2; return b + f3()}
function f3(){let c = 3; return c}
f1()
复制代码

链表 Linked List

queue-demo-1

一个链一个

实际使用

let array = [1,2,3]
array.__proto__ === Array.prototype
Array.prototype.__proto__ === Object.prototype
复制代码

从这个角度看，对象就是链表——

代码

list = create(value)
node = get(index)
append(node,value)
remove(node)
travel(list,fn)
复制代码

链表的变形

双向链表

每个节点有一个previous指向上一个节点

循环链表

最后一个节点的next指向头节点

哈希表 key-value pairs

场景

假设哈希表hash里有一万对key-value，比如name: 'River', age: 18, p1: 'property'...

如何使得读取hash['xxx']速度最快

解决办法

不做任何优化，hash['xxx']需要遍历所有key，O(n)

对key排序，使用二分查找，O(log2 n)

用字符串对应的ASCII数字做索引，O(1)

对索引做除法取余数，O(1)，冲突了就顺延。

树 Tree

实际使用

中国的省市区，可以看成一棵树

公司的层级结构，可以看成一棵树

网页中的节点，可以看成一棵树

代码

let tree = createTree(value)
let node = createNode(value)
addChild(tree,node)
removeChild(node1,node2)
travel(tree)
复制代码