斐波那契数列在算法题中比较经典，故出此文以此铭记。
题目：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39

暴力递归实现

1
2
3
4
function Fibonacci(n){
	if(n == 0 || n == 1) return n
	return Fibonacci(n-1) + Fibonacci(n-2)
}

数组保存计算缓存，减少计算

1
2
3
4
5
6
7
8
function Fibonacci(n){
	let arr = [0,1]
	return Fib(n)
	function Fib(n){
		if(arr[n] !== undefined ) return arr[n] //计算过的不用再计算
		return arr[n] = Fib(n-1) + Fib(n-2)   
	}
}

动态规划

1
2
3
4
5
6
7
8
function Fibonacci(n){
	let a = 0 //第一项
	let b = 1 //第二项
	for(let i = 2;i< n;i++ ){ //从第二项开始到n-1项
		[a,b] = [b,a+b]
	}
	return a+b
}

感觉这篇幅有点短，好吧再加几个算法题^_^

经典算法二分查找

题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function Find(target,array){
	for(let i =0 ;i<array.length;i++){
		let low = 0 //每行的开始索引
		let height = array[i].length - 1 //每行的最大索引
		while(low <= height){			//对每一行的数组进行二分查找
			let mid = Math.floor((low+height)/2) 
			if(target > array[i][mid]){
				low = mid + 1
			}else if(target < array[i][mid]){
				height = mid -1
			}else{
				return true
			}
		}
	}
	return false //没有找到
}

此题还有一种更好的思路：既然是递增数组，那我们就比较一下每一行数组最大的元素，如果此数大于这一行的最大元素则去下一行数组比较，如果此数小于这一行的最大元素则去前一列比较；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Find(target,array){
	let row = 0
	let col = array[0].length -1
	let len = array.length
	while(row < len && 0 <= col){ //row是索引要小于行数，col要大于0
		if(target > array[row][col]){
			row++
		}else if(target < array[row][col]){
			col--
		}else{
			return true
		}
	}
	return false
}

链表

链表也是数据结构中的一种，由指针指向。
题目：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{
    let ArrayList = []
    while(head){
        ArrayList.push(head.val)
        head = head.next
    }
    ArrayList.reverse()
    return ArrayList
}

JavaScript实现队列

队列是数据结构中的一种，先进先出FIFO,我们用数组来实现它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function Queue(){
	let arr = []
	this.pop = function(){
		if(arr.length <= 0) return
		return arr.shift()
	}
	this.push = function(data){
		arr.push(data)
	}
}
let queue = new Queue()
queue.push(1)
queue.push(2)
queue.push(3)
queue.pop() //1

JavaScript实现栈

栈是数据结构中的一种，先进先出FILO,我们用数组来实现它。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Stack(){
	let value = []
	this.pop = function(){
		if(value.length <= 0) return
		return value.pop()
	}
	this.push = function(data){
		value.push(data)
	}
}

let stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.pop() //3

好了此次的文章就写到这了，祝高三学子高考顺利！！！