编码技巧

发表于 | 分类于 | | 阅读次数:
字数统计: 543 字 | 阅读时长 ≈ 2 分钟

公理

数学归纳法是编码的基础。

计算机思维的本质是递归和分治。

递归控制

直接从当前问题开始思考。然后调用下一个问题/前一个问题

递归书写方法

（1）严格定义递归函数，包括参数、返回值、side-effect（因为递归而改变的变量、状态等，理想情况下是运行完后没有，全局变量改回去）

（2）先一般，后特殊：即先写递归体，不要先写边界条件（边界条件通过递归体无法运行的条件来约束）。

（3）每次调用必须缩小问题规模

（4）每次问题规模缩小程度必须为1

例子

  1. 链表反转

这个视频是个很好的例子！

直接考虑当前节点，所以必须是考虑它的下一个节点已完成的情况，在此基础上进行。

先写递归体，然后再看递归体中可能不满足的情况再写边界条件。

链接: https://pan.baidu.com/s/1Fjr1KEJGC0Ou68xj2smrvQ 提取码: x9iy

循环控制

考虑从中间过程开始顺序思考。

原理

循环不变式：是一句断言定义各变量所满足的条件。

--进入、循环、及结束时，条件均不变

书写方法

（1）==定义==循环不变式，并在循环体每次结束后==保持==循环不变式

（2）先一般，后特殊。（从中间某个过程出发来思考）

（3）每次必须向前推进循环不变式中涉及的变量值

（4）每次推进的规模必须为1

例题

（1）链表反转

循环不变式是：

newHead指向反转成功的链表，currentHead指向还没有反转的链表。

newHead=null;

currentHead= head;

 

while(){

循环不变式保持

next = currentHead.next();

currentHead.setNext(newHead);

newHead = currentHead;

currentHead = next;

循环不变式保持

}

 

循环体里不能运行下去的条件是，currentHead.next();这一句，currentHead=null，因此while括号里的条件就是！=null

 

退出循环时，循环不变式依旧成立。

链接: https://pan.baidu.com/s/1ENYSShcKC1lfwoLknC79Hw 提取码: cs88

 

显示 Gitment 评论