假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢示例 1输入n 2输出2解释有两种方法可以爬到楼顶。1. 1 阶 1 阶2. 2 阶示例 2输入n 3输出3解释有三种方法可以爬到楼顶。1. 1 阶 1 阶 1 阶2. 1 阶 2 阶3. 2 阶 1 阶遇到这道题先看小例子找规律n 1只有一种 1所以f(1) 1n 2可以1 12所以f(2) 2n 3可以1 1 11 22 1所以f(3) 3n 4所有方法111111212121122所以f(4) 5要到 第 n 阶最后一步只能是情况1最后走 1 步那之前就在n-1阶方法数f(n-1)情况2最后走 2 步那之前就在n-2阶方法数f(n-2)所以f(n) f(n-1) f(n-2)这就是 斐波那契数列。动态规划解法状态dp[i] 到第 i 阶的方法数状态转移dp[i] dp[i-1] dp[i-2]初始化dp[1] 1dp[2] 2/** * param {number} n * return {number} */ var climbStairs function(n) { const dp new Array(n 1) dp[1] 1 dp[2] 2 for(let i 3;i n ;i){ dp[i] dp[i - 1] dp[i - 2] } return dp[n] };给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。判断这道会问链表最简单就说把链表放入数组里面找但是这样空间复杂度就上来了进阶的关键其实就是两个点第一如和快速找到链表的中间节点第二部如何反转前半部分或者后半部分的链表思考如果同时设立两个指针一个速度比另一个快一倍那么在满指针在一半链表的时候快指针到达了末尾这样就找了分割点let fast head let slow head while(fast.next ! null fast.next.next ! null ){ slow slow.next fast fast.next.next } slow slow.next这就是具体的实现然后接下来就是反转链表let prev null let curr slow while(curr ! null){ let next curr.next curr.next prev prev curr curr next } slow prev通过这两步就可以判断了/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val (valundefined ? 0 : val) * this.next (nextundefined ? null : next) * } */ /** * param {ListNode} head * return {boolean} */ var isPalindrome function(head) { if(head.next null) return true let fast head let slow head while(fast.next ! null fast.next.next ! null ){ slow slow.next fast fast.next.next } slow slow.next // ⭐ 反转后半部分链表 let prev null let curr slow while(curr ! null){ let next curr.next curr.next prev prev curr curr next } slow prev // 现在 slow 指向反转后的头 while(slow ! null){ if(head.val slow.val){ head head.next slow slow.next }else{ return false } } return true };