昆明网络推广公司排名,三明seo培训,好的网站设计特点,注册域名需要多久代码鲁棒性
鲁棒是robust的音译#xff0c;就是健壮性。指程序能够判断输入是否符合规范#xff0c;对不合要求的输入能够给出合理的结果。容错性是鲁棒的一个重要体现。不鲁棒的代码发生异常的时候#xff0c;会出现不可预测的异常#xff0c;或者程序奔溃。由于鲁棒性非…代码鲁棒性
鲁棒是robust的音译就是健壮性。指程序能够判断输入是否符合规范对不合要求的输入能够给出合理的结果。容错性是鲁棒的一个重要体现。不鲁棒的代码发生异常的时候会出现不可预测的异常或者程序奔溃。由于鲁棒性非常重要因此我们在写代码的时候必须进行防御性编程这个必须成为我们编程的一种习惯编码过程中应该能够预见可能出现的问题并适当处理。
最容易出错的双指针操作
链表中倒数第K个节点题目输入一个链表输出链表中倒数第k个结点。例如链表依次是1,23,45,6倒数第三个就是4。我们依然用之前我们在讲解链表实现时候的链表对象定义
分析
此处题目要求的应该是单向链表因为双向链表没有复杂度可言。为了得到倒数第K个节点并且不能从尾部遍历同样的案例从尾部到头打印单向链表我们在之前的文章数据结构与算法–链表实现以及应用中已经有详细的分析此处同样也可以利用这种方法。以上方法中借助其他数据接口栈实现时间复杂度是O(Nk)空间复杂度O(2n)。应该还有更加高效率的算法我们还是从头遍历链表假设有n个节点那么倒数第k个节点从头开始数是第n-k1 个节点如果我们能得到节点个数n大小那么直接从头遍历n-k1个就得到倒数第k个了 。我们用双指针实现利用两个指针中间步数的差值来得到倒数第k个比如我们需要n-k1的差距也就是n-k-1当指针A 走到末尾的时候指针B需要走k-1 的距离那么此时B指针指向的就是倒数第k个例如倒数第2 个那么B就比A 少走了2-1 1 步骤就是指向倒数第二个了。如下图 如上图一中P1走两步P2 则指向头结点接着继续两个指针P1 P2一起向前走当P1走到链表尾则P2,正好走到倒数第三位置。如下diam实现 /**** 查找单向链表倒数第k个节点*/public static ListNode findLastKNode(ListNode head, int k){if(head null || k 0){return new ListNode(-1);}ListNode beforeNode head;ListNode afterNode head;for (int i 0; i k - 1; i) {if(beforeNode.getNext() ! null){beforeNode beforeNode.getNext();}else {return new ListNode(-1);}}//确保有 k 个节点if(beforeNode.getNext() null){return new ListNode(-1);}while (beforeNode.getNext() ! null){beforeNode beforeNode.getNext();afterNode afterNode.getNext();}return afterNode;}
鲁棒性分析
双指针方法中需要注意的点还是挺多的 当我们输入head 结点为null时候回由于代码会范问空指针内存次数程序会奔溃输入head为头肩底的链表节点总数少于k个此时我们需要先走k-1 步骤如果正好k-1个节点那么之后的步骤会抛出NPL如果少于k-1个节点则此时就已经npl输入参数k为0 的时候此时 k-1 -1非法数值-1 二进制位符号位1 此时会读成数据位此时数据变为4294967295此时for循环将会超过执行次数。
相关问题
问题一求单向链表中介节点奇数个返回中间节点偶数个返回中间两个任意一个同样双指针A,B A每个循环走一步B每个循环走两步B到末尾则A就在中间节点问题二求解单向链表是否环形链表同样双指针A,BA走一步B走两步如果到最后B追上了A 则环形如果B到最后null则不是环形
最容易死循环的链表问题
题目定义一个函数输入链表头结点反转并输出反转后的链表头结点。
分析
我们依然用 之前链表的实现文章中定义的链表节点如下
public class ListNode implements ComparableListNode {private Integer value;private ListNode next;
......
}链表反转涉及到每个节点的指针操作非常容易出现死循环问题为了正确理解整个过程我们应该首先借助图形来直观的分析。如下 我一开始还是想到双指正方法第一步骤分别指向钱两个节点并且改变本节点的指针指向我们此时需要知道的是本节点信息上一个节点信息这里都符合得到下一图步骤。 但是此时我们无法循环到下一个节点3 因此逻辑无法成立我们需要借助第三个指针P3如下图 如上我们可以得到本节点信息上一个节点信息下一个节点信息在经过p2 指针的转向后我们无法通过P2.next得到下一个节点因此我们循环时候需要做如下调整 P2 P1 P1 P3 P3P3.next然后接着操作P1 节点指针继续循环到最后p3.Next为null为止如下图最终状态 如上最终状态因为我们每次只修改了P1 节点的指针指向所以循环结束后还有最后节点没有处理我们需要在循环结束后处理。 如上分析我有如下实现 /*** 反转单向链表* */public static ListNode reverOverListNode(ListNode head){if(head null){return head;}ListNode before head;ListNode middle head;ListNode after head;if(middle.getNext() null){return head;}middle middle.getNext();if(middle.getNext() null){middle.setNext(before);head.setNext(null);return middle;}after middle.getNext();while (after.getNext() ! null){middle.setNext(before);before middle;middle after;after after.getNext();}//处理最后两个节点的指针head.setNext(null);middle.setNext(before);after.setNext(middle);return after;}鲁棒性分析
在指针操作时候最容易出现的三个问题 输入的链表头指针是努力或者整个链表只有一个节点必须在前三个步骤中判断反转后出现环形链表在如上处理过程中最容易忽略的头节点指针指向null导致环形链表链表断裂 最后一个步骤没有对最后的节点进行指针指向操作导致最后一个节点处断裂。
合并两个排序的链表 题目输入两个递增的链表合并这两个链表并使得新的链表中节点任然按原有顺序有序。如下图 链表一链表而是两个递增链表合并两个链表得到链表三 这个问题我们需要注意的和上一个问题类似还是链表断裂问题还有环形链表问题因为需要同时操作两个链表的指针。 我们有如下分析 将一二个链表看出需要处理的一个组比较第一个元素得到小的一个剔除当成新链表的head节点 将1 节点剔除后将剩下的链表1 链表2 看成是一个整体仍然比较第一个节点的大小继续如上步骤 继续同样的逻辑合并剩余的节点这是典型的递归流程我们可以定义递归函数完成合并过程。.如上分析有如下代码 /*** 递归合并两个顺序链表* */public static ListNode mixTwoSortList(ListNode sortOne, ListNode sortTwo){if(sortOne null sortTwo null){return new ListNode();}if(sortOne null){return sortTwo;}if(sortTwo null){return sortOne;}ListNode mergeHead null;if(sortOne.getValue() sortTwo.getValue()){mergeHead sortOne;mergeHead.setNext(mixTwoSortList(sortOne.getNext(), sortTwo));}else {mergeHead sortTwo;mergeHead.setNext(mixTwoSortList(sortTwo.getNext(), sortOne));}return mergeHead;}
鲁棒性分析
首先还是空指针问题一旦输入空链表立刻npl因此我们应该对空链表单独处理
更加复杂的指针操作案例树的子结构
题目输入两颗二叉树AB判断B是不是A树的子结构。二叉树的定义我们用之前章节中讲解的二叉树实现原理中定义的树节点来实现。
/*** 二叉树节点对象定义** author liaojiamin* Date:Created in 15:24 2020/12/11*/
public class BinaryNode {private Object element;private BinaryNode left;private BinaryNode right;
......
}例如有如下两棵二叉树A中有一部分子树结构和B是一直的因此B是A的子结构 依据之前二叉树实现原理 的分析树操作中指针比值链表更加复杂与树相关的问题我们通常都会用递归去解决。 如上题中查找A中包含B可分为两步 第一步在A树中查找B的根节点一样的节点R如果找到执行下一步第二步判断A中以R为根节点的子树与B树的结构是否一致 用如上图来分析 首先在A中找 8 这个节点发现A的根节点就是8 我们将A以8节点为根节点的树与B节点比较将8 的左子树看成完整的树与B中左子树 比较还是按第一步骤逻辑 发现不同则不需第三部如果相同则需要将8 的右子树看出完整的树与B中右子树比较还是按第一步骤逻辑。如果以上都不同则回到第一步将A的左子树看出是一个完整的树与B的根节点比较依次逻辑遍历整个A树直到找到B一样结构或者遍历到叶子节点为止。 依据如上分析我们有如下递归实现其中某些函数是用之前文章 二叉树实现原理的某些功能
/*** 判断 A树中是否包含B树* author liaojiamin* Date:Created in 16:43 2021/3/30*/
public class BinaryNodeComparable {/*** 递归方式遍历树* */public static boolean isComparable(BinaryNode tree1, BinaryNode tree2){if(tree1 null || tree2 null){return false;}boolean result false;if(tree1.compareTo(tree2.getElement()) 0){result tree1HaveTree2(tree1, tree2);}if(!result){result isComparable(tree1.getLeft(), tree2);}if(!result){result isComparable(tree1.getRight(), tree2);}return result;}/*** 依次比较跟左右节点* */public static boolean tree1HaveTree2(BinaryNode tree1, BinaryNode tree2){//t2 遍历完了并且都一致则存在包含if(tree2 null){return true;}//t2 不为空t1 为空 则不存在包含if(tree1 null){return false;}if(tree1.compareTo(tree2.getElement()) ! 0){return false;}return tree1HaveTree2(tree1.getLeft(), tree2.getLeft()) tree1HaveTree2(tree1.getRight(), tree2.getRight());}public static void main(String[] args) {BinaryNode node1 new BinaryNode(null, null, null);BinarySearchTree tree1 new BinarySearchTree();Random random new Random();for (int i 0; i 20; i) {node1 tree1.insert(Integer.valueOf(i), node1);}tree1.printTree(node1);System.out.println(-------------);BinaryNode node2 new BinaryNode(null, null, null);BinarySearchTree tree2 new BinarySearchTree();for (int i 0; i 3; i) {node2 tree2.insert(Integer.valueOf(i), node2);}tree2.printTree(node2);System.out.println(isComparable(node1, node2));}
}以上考察二叉树遍历算法的理解 以及递归的能力考察代码的鲁棒性每个题型都有大量的指针操作稍不注意就会有npl奔溃。我们应该在程序开始的时候采用防御性编程的方式每次范问指针地址之前都需要考虑这个指针是否有可能是null
上一篇数据结构与算法–代码完整性案例分析 下一篇数据结构与算法–解决问题的方法- 二叉树的的镜像
