《剑指Offer》-10代码的鲁棒性

发表于 | 分类于

剑指offer原文：

  • 鲁棒是英文Robust的音译，有时也翻译成健壮性。所谓的鲁棒性是指程序能够判断输入是否合乎规范要求，并对不合要求的输入予以合理的处理。
  • 容错性是鲁棒性的一个重要体现。

链表中倒数第k个节点

题目描述
输入一个链表，输出该链表中倒数第k个结点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindKthToTail(head, k)
{
    // write code here
    let array=[];
    if(!head){
        return false;
    }
    let node=head;
    while(node){
        array.push(node);
        node=node.next;
    }
    return array[array.length-k];
}

总结：
把这个链表放到一数组里，再寻找。

方法二 双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function FindKthToTail(head, k)
{
    // write code here
    if(!head || k<=0){
        return false;
    }
    let fast=head,
        slow=head;
    for(var i=1;i<k;i++){
        if(fast.next){
            fast=fast.next;
        }else{
            return false; //防止k超出数组的长度
        }
    }
    while(fast.next){
        fast=fast.next;
        slow=slow.next;
    }
    return slow;
}

总结：
设置两个指针，一快一慢，两指针保持k-1的距离差，当快指针到达链表最后一结点时，慢结点刚好到达倒数第k的位置

反转链表

题目描述
输入一个链表，反转链表后，输出新链表的表头。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function ReverseList(pHead)
{
    // write code here
    if(pHead==null){
        return null;
    }
    var pre,next;
    while(pHead!==null){
        next=pHead.next; //先用next保存head的下一个节点的信息
        pHead.next=pre;  //第一次循环PHead.next=null，构建链表尾部，让当前节点指向pre，pre为上次循环保存的节点，从而实现反转
        pre=pHead;    //保存当前节点
        pHead=next;  //向后移动一个节点，继续下一次的指针反转
    }
    return  pre;
}

合并两个排序的链表

题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function Merge(pHead1, pHead2)
{
    // write code here
    var New=new ListNode(),
        Head=New;
    while(pHead2 && pHead1){ //两个链表都有值时，进行比较排序
        if(pHead2.val>=pHead1.val){
            New.next=pHead1;
            pHead1=pHead1.next;
        }
        else{
            New.next=pHead2;
            pHead2=pHead2.next;
        }
        New=New.next;
    }
    //在任何一个链表为空后把另一个链表的剩余部分直接接在最后面
    if(pHead1 && !pHead2){
        New.next=pHead1;
    }
    if(pHead2 && !pHead1){
        New.next=pHead2;
    }
    return Head.next;
}

树的子结构

题目描述
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function HasSubtree(pRoot1, pRoot2)
{
    // write code here
    if(pRoot1==null || pRoot2==null) return false; //都不为零时，才进行判断，否则直接返回false
    return isSubtree(pRoot1,pRoot2)||
        isSubtree(pRoot1.left,pRoot2)||
        isSubtree(pRoot1.right,pRoot2);
}

function isSubtree(Root1, Root2){
    if(Root2==null) return true; //
    if(Root1==null) return false;//若“子结构”存在子树，母结构不存在，则不是子结构
    if(Root1.val==Root2.val){
        return isSubtree(Root1.left,Root2.left)&&
            isSubtree(Root1.right,Root2.right);
    }else{
        return false;
    }
}

总结：
如果A有一部分子树的结构和B是一样的，则称B是A的子结构。
当根节点相同时递归调用isSubtree()函数，继续判断左子树或右子树是否相同
若root1子树存在，而root2子树不存在时，判断为true（这是特殊情况）
除此之外，若root2子树存在，root1不存在 或者 两个树的根节点存在但不相同时，均返回false

0%