翻书问题或者走台阶问题。
问:共有n个台阶,每次只能上1个台阶或者2个台阶,共有多少种方法爬完台阶?共有n页书,每次只能翻1页或者2页书,共有多少种方法翻完全书?
ps:本质上是斐波那契数列问题。假设只有一个台阶,则只有一种跳法,f(1)=1;如果两个台阶,那么有两种跳法:1,一次跳一级,2,一次跳两级,f(2) = 2。如果大于2的n级台阶,那么一次跳一级台阶,剩下还有n-1级台阶,有f(n-1)种跳法。假如一次跳2级台阶,剩下n-2级台阶,有f(n-2)中跳法。这就表示f(n) = f(n-1)+f(n-2)。
function fibonacci(n) {
if (n === 1 || n === 2) {
return n;
} else {
return fibonacci(n-1) + fibonacci(n-2)
}
}
// 一个记忆化的斐波那契数列
let tem = [0, 1]
function fibonacci(n) {
let result = tem[n]
if(typeof result !== 'number') {
result = fibonacci(n-1)+fibonacci(n-2)
tem[n] = result // 将每次 fibonacci(n) 的值都缓存下来
}
return result
}
// 动态规划:从底部开始解决问题, 将所有小问题解决掉, 然后合并成一个整体解决方案, 从而解决掉整个大问题 。
function fibonacci(n) {
let last = 1;
let nextLast = 1;
let result = 1;
for (let i = 2; i < n; ++i) {
result = last + nextLast;
nextLast = last;
last = result;
}
return result;
}二分查找。
数组array包含了顺序的元素,[1,2,3,...,10],查找目标元素t是否在数组中。
我们已经提前知道数组是顺序排列的,比如递增顺序。
时间复杂度为O(logN)
递推公式:
f(N) = f(N/2) + O(1) = f(N/4) + 2 * O(1)
假设 N = 2 ^ M
最后可以推出
f(N) = O(logN)
let list = [1,2,3,4,5,6,7,8,9,10]
function binarySearch(array, t) {
let left = 0, right = array.length - 1;
while(left
let mid = parseInt((right - left)/2)
if(array[mid] < t) {
left = mid + 1
} else if(array[mid] > t) {
right = mid - 1
} else {
return true
}
}
return false
}
// 递归写法
function binarySearch2(array, t, left, right) {
if(left > right) return -1
let mid = parseInt((right - left)/2) + left
if(array[mid] === t) {
return mid
}else if(array[mid] < t){
return binarySearch2(array, t, mid + 1, right)
}else if(array[mid] > t){
return binarySearch2(array, t, left, mid - 1)
}
}
let test1 = binarySearch(list, 5)
let test2 = binarySearch2(list, 5, 0, list.length-1)
console.log(test1, test2)背包问题
function main(volume, value, c){
let tArray = []
let useGoodsNo = []
for(let i = 0, l = volume.length; i
tArray[i] = []
useGoodsNo[i] = 0
for(let j = 0; j
if(i == 0 || j == 0){
tArray[i][j] = 0
}
}
}
volume.unshift(0) //让i = 1的时候对应的是1号物品
value.unshift(0)
for(let i = 1, l = volume.length; i < l; i++) { // i从1开始 tArray[0][j]已经填满
for(let j = 1; j
if(j < volume[i]){
tArray[i][j] = tArray[i-1][j]
} else {
//如果装了剩下的体积
let leftVolume = j - volume[i]
// 当前物品的价值
let curValue = value[i]
// 剩下的体积的价值是 (tArray[i - 1]因为0 1背包,不能重复放同个物品)
let leftValue = tArray[i - 1][leftVolume]
tArray[i][j] = Math.max(tArray[i-1][j], curValue+leftValue)
}
}
}
// 填满表格
console.table(tArray)
// 逆向获取物品
let C = c
for(let i = value.length-1; i > 0; i--){
if(tArray[i][C] > tArray[i-1][C]){
useGoodsNo[i] = 1
C = C - volume[i]
}
}
console.table(useGoodsNo) // 所选的物品
console.log(tArray[value.length-1][c]) // 最大价值
}
main([2,3,4,5], [3,4,5,6], 8)展平数组
// 展平数组 [[1, 2], 3, [[[4], 5]]] => [1, 2, 3, 4, 5]
function flatten(arr) {
return [].concat(
...arr.map(x => Array.isArray(x) ? flatten(x) : x)
)
}随机打乱数组
function shuffle(arr) {
for(let i = 0; i < arr.length-1; i++){
const j = i + Math.floor(Math.random() * (arr.length - i))
[arr[i], arr[j]] = [arr[j], arr[i]]
}
}函数节流
// 函数节流
function throttle(func, delay = 60) {
let lock = false
return (...args) => {
if(lock) return
func(...args)
lock = true
setTimeout(()=> {
lock = false
}, delay)
}
}柯里化
//对于curry(foo),g函数参数足够4个,就调用foo(a,b,c,d),如果小于4就返回一个可以继续积累参数的函数
const curry = func => {
const g = (...allAtgs) => allArgs.length >= func.length ?
func(...allArgs) : (...args) => g(...allAtgs, ...args)
return g
}
const foo = curry((a, b, c, d) =>{
console.log(a, b, c, d)
})
foo(1)(2)(3)(4) // 1 2 3 4
foo(1)(2)(3) // 不返回
const f = foo(1)(2)(3)
f(4) // 1 2 3 4 5Y组合子
const y = function(le) {
return function (f) {
return f(f)
}(function (f) {
return le(
function(...x) {
return (f(f))(...x)
}
)
})
}
const curryY = func => y(
g => {
(...allArgs) => {
allArgs.length >= func.length ? func(...allArgs) : (...args) =>g(...allArgs, ...args)
}
}
)
const foo = curryY((a, b, c, d) => {
console.log(a, b, c, d)
})
foo(1)(2)(3)(4)链表
链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。
function ListNode(val) {
this.val = val
this.next = null
}
let node1 = new ListNode(1)
let node2 = new ListNode(2)
let node3 = new ListNode(3)
node1.next = node2
node2.next = node3
console.log(node1)
function recursiveTraverse(head) {
if(head != null) {
console.log(head.val)
recursiveTraverse(head.next)
}
}
recursiveTraverse(node1)
// 翻转一条单向链表
// 输入 1 -> 2 -> 3 -> null
// 输出 3 -> 2 -> 1 -> null
function reverseLinkedList(head){
let dummy = head
let tem = dummy
while(head != null && head.next != null){
dummy = head.next
head.next = dummy.next
dummy.next = tem
tem = dummy
}
return dummy
}
let reverseLink = reverseLinkedList(node1)
console.log(reverseLink)二叉树
function TreeNode(val) {
this.val = val
this.left = null
this.right = null
}
let root = new TreeNode(2)
root.left = new TreeNode(1)
root.right = new TreeNode(3)
console.log(root)
/*
* 2
* / \
* 1 3
*/
/*
中序遍历:(
定义:
1,中序遍历左子树
2,遍历根节点
3,中序遍历右子树
)
前序遍历:(
定义:
1,遍历根节点
2,前序遍历左子树
3,前序遍历右子树
)
后序遍历:(
定义:
1,后序遍历左子树
2,后序遍历右子树
3,遍历根节点
)
*/
function inOrder(root) {
if(root) {
console.log('前',root.val) // 2 1 3
inOrder(root.left)
console.log('中',root.val) // 1 2 3
inOrder(root.right)
console.log('后',root.val) // 1 3 2
}
}
inOrder(root)
/*
二叉查找树/二叉搜索树:(
定义:
左子树的所有节点的值小于根节点
右子树的所有节点的值大于根节点
左子树和右子树都是二叉查找树
)
二叉搜索树的中序遍历就是排好序的元素。
*/
function binarySearchTreeFind(root, target) {
if(!root) return false
if(root.val === target) {
return true
} else if(root.val < target){
return binarySearchTreeFind(root.right, target)
} else if(root.val > target) {
return binarySearchTreeFind(root.left, target)
}
}
console.log(binarySearchTreeFind(root, 1))栈
First In Last Out(FILO)
先进后出,后进先出
function Stack(){
this.stack = []
this.isEmpth = function(){
return this.size() === 0
}
this.size = function() {
return this.stack.length
}
// 出栈
this.pop = function(){
if(this.isEmpth()){
return null
} else {
return this.stack.pop()
}
}
// 进栈
this.push = function (val){
return this.stack.push(val)
}
// 返回栈顶元素
this.peak= function(){
if(this.isEmpth()) {
return null
} else {
return this.stack[this.stack.length - 1]
}
}
}
let test = new Stack()
test.push(1)
console.log(test.peak())
console.log(test.isEmpth())
test.pop()
console.log(test.peak())队列
First In First Out(FIFO)
先进先出
function Queue() {
this.queue = []
this.size = function() {
return this.queue.length
}
this.isEmpty = function(){
return this.size() === 0
}
// 入队列
this.enqueue = function (val){
this.queue.unshift(val)
}
// 出队列
this.dequeue = function(){
if(this.isEmpty()){
return null
} else {
return this.queue.pop()
}
}
}
let test = new Queue()
test.enqueue(1)
test.enqueue(2)
console.log(test.queue)
test.dequeue()
console.log(test.queue)
领取专属 10元无门槛券
私享最新 技术干货