一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶,求该青蛙跳上一个n级的台阶总共需要多少种跳法。
分析: 当n=1的时候,①只需要跳一次即可;只有一种跳法,即f(1)=1;
当n=2的时候,①可以先跳一级再跳一级,②也可以直接跳俩级;共有俩种跳法,即f(2)=2;
当n=3的时候,①一阶一阶跳即可;
②他可以从一级台阶上跳俩阶上来
③也可从二级台阶上跳一阶上来;即共有f(3)=f(2)+f(1);
所以当有n阶台阶时,且当n>2的时候,根据上面式子可推导出→ f(n)=f(n-1)+f(n-2)
所以很直白的看出就是个 斐波那契数列 ,有一点不同的是,斐波那契数列从1,1,2,3,5,8,13…开始的,而我们这是以1,2,3,5,8,13…开始的,少了前面的1
解决一系列问题的具体步骤
算法是一组用于解决特定问题或执行特定任务的有限步骤序列。这些步骤按照确定的顺序执行,以达到所需的结果。在计算机科学中,算法通常用于描述数据处理、自动化处理和数学运算的过程。算法可以用来解决各种问题,包括排序、搜索、路径规划等。
LRU是Least Recently Used(最近最少使用)的缩写。
在计算机科学中,LRU是一种页面置换算法,通常用于操作系统的虚拟内存管理中。
该算法根据页面(或者其他资源)的最近使用情况来进行置换,当需要置换时,选择最近最少被使用的页面进行替换。
这样可以保证最常用的页面保留在内存中,从而提高性能。
实例:vue keep-alive 缓存
LRU – 最近使用
缓存,有一个大小 const lru = new LRUCache(capacity)
提示
const lru = new LRUCache(2)
lru.put(1,1)
lru.put(2,2) // {1:1,2:2}
lru.get(1)
lru.put(3,3) // {1:1,3:3}
lru.get(2) // -1 (找不到)
lru.put(4,4) // {4:4,3:3}
实现代码
// 函数的 get 和 put 必须以 O(1)的时间复杂度运行
// get,得是个hash(Map,Set),而不能是数组
// ES6 迭代器
const LRUCache = function(capacity){
this.cacheQueue = new Map()
this.capacity = capacity
}
LRUCache.prototype.get = function(key){
if(this.cacheQueue.has(key)){ // 如果找到了,这个key对应的value要提升新鲜度
const result = this.cacheQueue.get(key)
// 删掉,然后再放进去,这样,这个就能在cacheQueue的队尾(队尾为最新鲜地方)
this.cacheQueue.delete(key)
this.cacheQueue.set(key,result)
return result
}
return -1 // 如果没有找到key,则直接返回 -1
}
LRUCache.prototype.put = function(key,value){
if(this.cacheQueue.has(key)){
// 如果找到了, 删掉
this.cacheQueue.delete(key)
}
if(this.cacheQueue.size >= this.capacity){
// 删除map的第一个元素,即最长时间未使用的
this.cacheQueue.set(key,value)
this.cacheQueue.delete(this.cacheQueue.keys().next().value)
} else {
this.cacheQueue.set(key,value)
}
}
ES6的Map是一种内置的数据结构,它存储键值对并允许你通过键快速查找值。
Map对象类似于对象,但不同之处在于Map的键可以是任意数据类型,而对象的键只能是字符串或Symbol。
Map还保留了插入顺序,这意味着当你遍历一个Map对象时,它会按照插入顺序返回键值对。
要创建一个新的Map,你需要使用new Map()语法。
例如:
const myMap = new Map();
你可以使用Map对象的set()方法添加键值对。
例如:
myMap.set('key1', 'value1');
myMap.set('key2', 'value2');
你可以使用Map对象的get()方法获取键对应的值。
例如:
const value1 = myMap.get('key1'); // 返回 'value1'
const value2 = myMap.get('key2'); // 返回 'value2'
你可以使用Map对象的has()方法检查Map中是否存在某个键。
例如:
const hasKey1 = myMap.has('key1'); // 返回 true
const hasKey3 = myMap.has('key3'); // 返回 false
你可以使用Map对象的delete()方法删除键值对。
例如:
myMap.delete('key1');
你可以使用Map对象的keys()、values()或entries()方法遍历Map中的键或值。
例如:
for (const key of myMap.keys()) {
console.log(key); // 输出键名
}
for (const value of myMap.values()) {
console.log(value); // 输出值
}
for (const [key, value] of myMap.entries()) {
console.log(key, value); // 输出键名和值
}
myMap.forEach((value, key) => {
console.log(key + ' = ' + value);
});
myMap.size; // 返回Map的大小
更多详细内容,请微信搜索“前端爱好者
“, 戳我 查看 。
leecode的地址:https://leetcode.cn/problems/linked-list-cycle/
链表:常见 – react源码
思路:快慢指针,两个(起点相同位置)指针,n步骤以后指针相遇
实现代码
head.next 指向下一个值
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function(head) {
let fast = slow = head
while(fast && fast.next){
fast = fast.next.next
slow = slow.next
if(fast === slow){
return true
}
}
return false
};
链表是一种数据结构,其中的元素以节点的形式按顺序排列。
每个节点都包含数据和指向下一个节点的引用。
相比数组,链表在插入和删除元素时更灵活,因为它们不需要连续的存储空间。
举例来说,一个简单的链表可以被定义如下:
Node 1: 23 -> Node 2
Node 2: 47 -> Node 3
Node 3: 95 -> null
在这个例子中,链表中的每个节点包含一个值和指向下一个节点的引用。
第一个节点包含值23,同时指向第二个节点,依此类推。最后一个节点指向null,表示链表的结束。
通过使用链表,我们可以轻松地插入或删除节点,而无需移动其他节点。
这使得链表在某些场景下比数组更为适用。
链表是一种物理存储结构上 非连续、非顺序 的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。
每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
链表有很多种不同的类型,包括单向链表、双向链表以及循环链表。
链表可以在多种编程语言中实现,例如C、C++和Java等。
先走根节点,然后左,然后右
先走左节点,然后根节点,然后右节点
先走左节点,然后右节点,然后再根节点
前/先序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
后序遍历: AEFDHZMG
前序遍历: A-B-D-F-G-H-I-E-C
中序遍历: F-D-H-G-I-B-E-A-C
后序遍历: F-H-I-G-D-E-B-C-A
const treeRoot = {
val: 1,
left: {
val: 2,
left: {
val: 4,
},
right: {
val: 5,
}
},
right: {
val: 3,
left: {
val: 6,
},
right: {
val: 7,
}
}
}
// 前序
const preOrder = function(node){
if(node){
// 如果有根节点
console.log(node.val)
preOrder(node.left)
preOrder(node.right)
}
}
preOrder(treeRoot)
// 中序
const inOrder = function(node){
if(node){
// 如果有根节点
inOrder(node.left)
console.log(node.val)
inOrder(node.right)
}
}
inOrder(treeRoot)
// 后序
const nextOrder = function(node){
if(node){
// 如果有根节点
nextOrder(node.left)
nextOrder(node.right)
console.log(node.val)
}
}
nextOrder(treeRoot)
leetcode地址:https://leetcode.cn/problems/binary-tree-level-order-traversal/
输入:root = [3,9,20,null,null,15,7]
输出:[[3],[9,20],[15,7]]
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
if(!root) return []
let queue = [root]
let result = []
// 开始遍历
while(queue.length){
let temQueue = []
let temResult = []
let len = queue.length
for(let i = 0; i < len; i++){
let node = queue.shift()
temResult.push(node.val)
node.left && temQueue.push(node.left)
node.right && temQueue.push(node.right)
}
// 循环完毕
result.push(temResult)
temResult = []
queue = temQueue
}
return result
};
**leetcode地址:**https://leetcode.cn/problems/maximum-depth-of-binary-tree/
直接return 上面层序的lengh
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var maxDepth = function(root) {
if(!root) return []
let queue = [root]
let result = []
// 开始遍历
while(queue.length){
let temQueue = []
let temResult = []
let len = queue.length
for(let i = 0; i < len; i++){
let node = queue.shift()
temResult.push(node.val)
node.left && temQueue.push(node.left)
node.right && temQueue.push(node.right)
}
// 循环完毕
result.push(temResult)
temResult = []
queue = temQueue
}
return result.length
};
使用DP方法
let maxDepth = function(root){
if(!root) return 0 // 如果没有根节点,则直接返回0
// 找左右叉的最大值
return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1
}
const arrayLike = document.querySelectorAll('div')
[...arrayLike]
Array.prototype.slice.call(arrayLike)
Array.prototype.concat.apply([],arrayLike)
Array.from(arrayLike)
Array.apply(null,arrayLike)
ES6新增了许多数组方法,主要包括以下几个:
find():返回数组中符合测试函数条件的第一个元素值。
const numbers = [10, 20, 30, 40];
const result = numbers.find(num => num > 25);
// 结果为30
findIndex():返回数组中符合测试函数条件的第一个元素索引。
const numbers = [10, 20, 30, 40];
const index = numbers.findIndex(num => num > 25);
// 结果为2(即元素30对应的索引)
forEach():对数组的每个元素执行提供的函数。
const numbers = [1, 2, 3];
numbers.forEach(num => console.log(num * 2));
// 输出2, 4, 6
map():对数组的每个元素执行提供的函数,并返回结果组成的新数组。
const numbers = [1, 2, 3];
const doubled = numbers.map(num => num * 2);
// 结果为[2, 4, 6]
filter():使用给定函数测试所有元素,并返回由所有通过测试的元素组成的新数组。
const numbers = [10, 15, 20, 25, 30];
const greaterThan20 = numbers.filter(num => num > 20);
// 结果为[25, 30]
这些方法在处理数组时非常有用,并且能够简化一些常见的操作。