- 时间复杂度 O(1) O(n) O(n²) O(2ⁿ)
记得有次面试, 让我求1 + … n, 我说用for循环. 当时竟然都忘了等差数列公式了…
一个简单的求和
let res = 0 // 1
for(let i; i < arr.length; i++){ // 1res += arr[i] // n
}let res = 0
for(const item of number){ 比上面的更简洁, 但似乎不能breakres += item
}
num.reduce((a, b) => a + b) 归并,当时时间复杂度并没有降低
2*n => n
- what & why
- Examples & Different Algorithms
- Different Solution Approaches: Recursion, , Greedy Algorithms (how to tackle and solve problems)
Basics & Time Complexity 基础 和 时间复杂度
Math Algorithms 数学算法
Recursion & Dynamic Programming 递归和动态编程
Search Algorithms 搜索算法
Sorting Algorithms 排序
Space Complexity
Sets(Arrays) Algorithms
More Complex Algorithms & A Blueprint
leetcode 509 斐波那契数列
解法1, 递归, 最简单, 性能最差
O(2²)
function fib(n) {if (n < 2) {return n}return fib(n - 1) + fib(n - 2)
}
解法2 递归 + 数组记录, O(n) Bottom-up Approach
let arr = [0, 1, 1]
function getFib(n) {if (n <= 2) return arr[n]return arr[n] = getFib(n - 1) + getFib(n- 2)
}console.log(getFib(20))
感觉这种是最好理解的
var fib = function (n) {let arr = [0, 1, 1]for(let i = 3; i <= n; i++){arr[i] = arr[i - 1] + arr[i - 2]}return arr[n]
};
不用数组, 用变量倒
let fib = function (n) {let arr = [0, 1, 1]if (n < 2) return arr[n]// 分别代表 dp[i - 1] 和 dp[i - 2]let dp_i_1 = 1, dp_i_2 = 0for (let i = 2; i <= n; i++) {// dp[i] = dp[i - 1] + dp[i - 2];const dp_i = dp_i_1 + dp_i_2dp_i_2 = dp_i_1dp_i_1 = dp_i}return dp_i_1};
leetcode 866. 回文素数
素数
var primePalindrome = function(n) {if(n === 1) return 2let max = 12 * Math.pow(10,8)for(let i = n; i < max; i++) {if(isH(i) && isPrime(i)) {return i}}// 判断是不是素数function isPrime(v){for(let i = 2; i <= Math.sqrt(v); i ++){if(v % i === 0){return false}}return true}function isPalindrome(v) {let str = String(v)let l = 0,r = str.length - 1while (l < r) {if (str[l] !== str[r]) return falsel++r--}return true}
};
卡在了 9989900 超时了....
Math.min(1,2,3)
Math.max(1,2,3)
leetcode 231. 2的幂 isPowerOfTwo
- & 是全 1 才为 1
- 5 & 12 => 4
0101 => 5
1100 => 12
0100 => 4
一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1。位运算 n&(n-1) 在算法中挺常见的，作用是消除二进制表示中的最后一个 1，可以判断 2 的指数。
/*** @param {number} n* @return {boolean}*/
var isPowerOfTwo = function(n) {if(n < 1) return falsereturn (n & (n - 1)) == 0;
};
var isPowerOfTwo = function(n) {let divide = nwhile(divide !== 1) {if(divide %2 !== 0) return falsedivide = divide / 2}return true
};
阶乘 54321
recurive 递归写法 O(n)
function factorail() {if(number === 1) {return 1}return number * factorial(number - 1)
}
performance.now()
参考
bilibili视频
