java动态规划算阶乘_javascript算法学习-持续更新1.求n项累加和
function sum(n){
return (n/2)*(n-1)
}
时间复杂度：O(1) 常数时间复杂度
2.判断⼀个数是不是质数
质数的特点：
1.除了1以外的⾃然数如果只能被1和它本⾝整除这个数就是质数
2.质数还有⼀个特点，就是它总是等于 6x-1(等同于6x+5) 或者 6x+1，其中 x 是⼤于等于1的⾃然数
3.合数 能被除1和本⾝以外的数整除， 这个数⼀定⼩于等于合数的开平⽅
需求分析：
1 既不是质数也不是合数
⼩于等于3的数，是否⼤于1可判断是不是质数
不是6的倍数两侧的⼀定不是质数 number % 6 != 1 && number % 6 !=5
i = 2；i<=Math.sqrt(number);i++; number % i === 0 false 否则 true
function isPrime(number){
if(number<=3){
return number>1
}
// 不在6的倍数两侧的⼀定不是质数
if (number % 6 != 1 && number % 6 != 5) {
return false;
}
for(let i =2;i<= Math.sqrt(number);i++){
if(number%i === 0){
return false
}
}
return true
}
时间复杂度：O(开平⽅n)
2-1 扩展
统计所有⼩于⾮负整数 n 的质数的数量。 (leetcode-cn/problems/count-primes)
⽰例 1：
输⼊：n = 10 输出：4 解释：⼩于 10 的质数⼀共有 4 个, 它们是 2, 3, 5, 7 。 ⽰例 2：输⼊：n = 0 输出：0 ⽰例 3：
输⼊：n = 1 输出：0
提⽰：
0 <= n <= 5 * 106
第⼀种⽅法 枚举 + ⽤上⾯的isPrime⽅法
var countPrimes = function(n){
let count = 0
n--
for(let i = 2;i
if(isPrime(n)){
count ++
}
}
return count
}
function isPrime(n){
if(n<=3){
return n>1
}
if(n % 6 != 1 && n % 6 !=5){
return false
}
for(let i = 2;i<=Math.sqrt(n);i++){
if(n%i ===0) return false
}
return true
}
第⼆种⽅法埃⽒筛
解题思路
质数的倍数是合数。n以内，从2起，顺序标记质数的倍数为合数
每到⼀个质数，结果+1。返回结果。过程如图
var countPrimes = function(n) {
for(var i = 2, r = 0, isPrime = Array(n).fill(true); i < n; i++)
if(isPrime[i]) {
r++
for(var j = 2 * i; j < n; j += i) isPrime[j] = false
}
return r
};
知识补充：Array(n).fill(true) 创建⼀个长度为n的数组并且填充值为true
埃⽒筛 · 优化
上图中黄⾊数字，被重复标记。例如10，2时标记1次，5时⼜1次。如何减少重复呢？ 举例5。16以内，从2起，5的倍数，5 * 2，5 * 3。在2和3时倍数时，被标记过 n以内，从2起，任意数i的倍数，i * 2，i * 3 … i * i … i * x(x > i) < n 在i之前的倍数，⼀定在遍历到i前，被标记过
代码
var countPrimes = function(n) { for(var i = 2, r = 0, isPrime = new Array(n).fill(true); i < n; i++) if(isPrime[i]) { r++ for(var j = i * i; j < n; j += i) isPrime[j] = false } return r };
奇数筛
javascript动态效果思路：
质数⼀定是奇数，偶数⼀定不是质数(2除外)。只要在奇数范围标记合数，未标记的是质数
奇数乘以偶数⼀定是偶数，只⽤奇数乘以奇数，确保在奇数范围内标记
⽤上⾯两条优化埃⽒筛解法，过程如图
var countPrimes = function(n){
let primeArr = new Array(n)
let square = Math.sqrt(n)
let count = n >2?1:0
let t = 0
for(let i = 3;i
if(!primeArr[i]){
count++
if(i <= square){
for(let j = i;(t=i*j)
primeArr[t] = true
}
}
}
}
return count
}
个⼈总结：奇数+2 得到的还是奇数
4.计算N的阶乘 n! (递归⽅法)
如果n = 5 5! = 5 * 4 * 3 * 2 * 1
function factorial(number){
if(number <= 1){
return 1
}
return number*factorial(number-1)
}
时间复杂度：O(n)
5.是不是2的整数次幂
需求分析
⼩于1的肯定不是2的整数次幂
如果⼀个数对2取余数不等于0肯定不是2的整数次幂
⼀个数除以2得到商和余数，商不等于1 & 取余数不等于0，直到最后商等于1，余数等于0返回true，否则是false 8%2 =0 8 / 2 = 4
4%2 =0 4/2 = 2
2%2 = 0 2/2 = 1
得到商1 余0 得出结论8 是2的整数次幂
function isPowerTwo(n){
if(n<1) return fasle
let devideNumber = n
while(devideNumber != 1){
if(devideNumber %2 != 0){
return false
}
devideNumber = devideNumber / 2
}
return true
}
时间复杂度：O(logn) 对数时间复杂度
2.求斐波拉(那)契数列指定位置的值 (从底层构建)
function fibNum(number){
let fibArray = [1,1]
for(let i =2;i
fibArray.push(fibArray[i-2]+fibArray[i-1])
}
return fibArray[number]
}
时间复杂度：O(n) 线性时间复杂度
什么是动态规划
动态规划是解决多阶段决策过程中最优化的⼀种有效的数学⽅法
递归 Recursion + 存储数据 Memoization
⾮常适合重复计算 通过存储数据避免不必要的递归步骤
可能导致重复的⼯作 中间结果被存储并重复使⽤
动态规划
递归 + 斐波那契数列 算法
从底层构建 也就是⾃下⽽上⽅法 到的是下标
需求分析：
创建中间值变量result
进到函数体执⾏，先验证传进来的中间值memo是否存在，存在则直接返回
因为斐波那契数列前两项为1 ，所以当n 值为0 或者 1的时候，直接返回1
否则 中间值result 赋值回调函数 fib(n-1,memo) + fib(n-2,memo)
条件外赋值 memo[n] = result
返回result
function fib(n,memo={}){
let result // 存储中间值
if(memo[n]) return memo[n] // 验证这个中间值是否存在，若存在就返回结果，if(n === 0 || n === 1){
result = 1
}else{
result = fib(n-1,memo) + fib(n-2,memo)
}
memo[n] = result