js刷题爬坑---2、day 2

js刷题爬坑---2、day 2

一、总结

一句话总结:

在算法题中,拿数组来做存储中间量真的不要太方便,尤其是一些链表的操作里面,并且存储链表的节点值比存链表方便

1、记忆化递归的一个易错点就是保存中间值,而不是保存结果值?

记忆化递归只保存结果值,没有保持中间值(是对计算好的结果数据进行保存,并且因为递归的关系,所有的中间数据也都会被保存下来)
let cache_1=[0,1,2];
function jumpFloor_2(n){
    if(n==1) return 1;
    else if(n==2) return 2;
    if(cache_1[n]!==undefined) return cache_1[n];
    return cache_1[n]=jumpFloor_2(n-1)+jumpFloor_2(n-2);
}

2、记忆化递归保存结果值?

保存记忆化递归得到的结果,因为递归的关系,这样同样可以保存所有的中间数据
let cache_1=[0,1,2];
function jumpFloor_2(n){
    if(n==1) return 1;
    else if(n==2) return 2;
    if(cache_1[n]!==undefined) return cache_1[n];
    return cache_1[n]=jumpFloor_2(n-1)+jumpFloor_2(n-2);
}

3、js中判断元素是否为undefined?

if(cache_1[n]===undefined):比如数组中未被赋值的元素:算法题里面非常常用

4、记忆化递归缓存值的机制?

记忆化递归不是没有缓存值就去找(去算)缓存值,而是缓存了值就用缓存的值(没有的话就递归来算缓存值)
let cache=[,1,2];
function jumpFloor2(n){
    if(cache[n]!==undefined) return cache[n];
    return cache[n]=jumpFloor2(n-1)+jumpFloor2(n-2);
}

5、牛客网上n==0的情况没写有些情况下也会报数组非法访问?

请检查是否存在语法错误或者数组越界非法访问等情况
//矩形覆盖
let cache=[0,1,2];
function rectCover(number)
{
    // write code here
    let n=parseInt(number);
    if(cache[n]!==undefined) return cache[n];
    return cache[n]=rectCover(n-1)+rectCover(n-2);
}

6、js中的除法不是整除?

js中的除法不是整除,也就是5/2得到的是2.5而不是2,这个在做除法的时候要特别注意

7、判断元素为奇数的时候用n%2!=0,不要用n%2==1?

js中-1%2为-1而不是1,所以判断奇数偶数的时候,n%2!=0和n%2==1是有很大区别的

8、js也有位操作?

按位与(&)、按位或(|)、按位非(~)、按位异或(^)、有符号左移(<<)、有符号右移(>>)、无符号右移(>>>)
//输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
function NumberOf1(n)
{
    // write code here
    var count = 0,flag=1;
    while(flag){
        if(n&flag)count++;
        flag=flag<<1;
    }
    return count;
}

9、0的n次方为0?

Math.pow(0,exponent)为0

10、链表操作创建新的链表还不如用原来的链表?

链表操作创建新的链表还不如用原来的链表,起码节点个数一样,修改也只需要修改节点的值,也不用耗新的内存
//反转链表
//输入一个链表,反转链表后,输出新链表的表头。
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead)
{
    // write code here
    let arr=[];
    let node=pHead; 
    while(node){
        arr.push(node.val);
        node=node.next;
    }
    node =  pHead;
    while(node){
        node.val=arr.pop();
        node=node.next;
    }
    return pHead;
}

11、如果报超内存了,那数组里面存的东西可以存少一点?

如果报超内存了,那数组里面存的东西可以存少一点,不用存节点,存节点的值就好
//反转链表
//输入一个链表,反转链表后,输出新链表的表头。
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead)
{
    // write code here
    let arr=[];
    let node=pHead; 
    while(node){
        arr.push(node.val);
        node=node.next;
    }
    node =  pHead;
    while(node){
        node.val=arr.pop();
        node=node.next;
    }
    return pHead;
}

12、对于链表,最少都需要一个头指针和一个用来做遍历的指针?

对于链表,最少都需要一个头指针和一个用来做遍历的指针(无论是增加元素还是遍历链表)
//链表合并
function Merge(pHead1, pHead2)
{
    // write code here
    let head=new ListNode(-1);
    let p=head;
    while(pHead1&&pHead2){
        if(pHead1.val<pHead2.val){
            p.next=pHead1;
            pHead1=pHead1.next;
        }else{
            p.next=pHead2;
            pHead2=pHead2.next;
        }
        p=p.next;
    }
    if(pHead1) p.next=pHead1;
    if(pHead2) p.next=pHead2;
    return head.next;
}

二、内容在总结中

博客对应课程的视频位置:

 
原文地址:https://www.cnblogs.com/Renyi-Fan/p/12920876.html