锐客网

  1. 首页 > 睿知 > it技术 > >

一些编码Tips

IT知识编码tips

【一些编码Tips】犀渠玉剑良家子，白马金羁侠少年。这篇文章主要讲述一些编码Tips相关的知识，希望能为你提供帮助。
递归控制如何证明递归函数正确执行？

  • 数学归纳法中的数学/自然语言< --> 程序语言
递归书写方法
  • 严格定义递归函数作用，包括参数，返回值，Side-effct
  • 先一般，后特殊
  • 每次调用必须缩小问题规模
  • 每次问题规模缩小程度必须为1
链表创建
Head --> 1--> 2--> 3--> 4--> 5--> null
为何面试喜欢问链表（单向）
  • 容易理解
  • 代码难写
  • 通过链表本身考察代码的能力
链表反转
列出所有组合（side effect）
  • combinations([1, 2, 3, 4], 2):
  • [1, 2]、[1、3]、[1、4]、[2、3]、[2、4]、[3、4]
递归缺点：
  • 函数调用开销
  • stack overflow
  • 问题规模：n million栈大小
循环控制递归 --> 非递归
  • 一般化的方法仍需要使用栈
  • 代码复杂，不根本解决问题
Node CreateLinkedList(List< Integer> values)

循环不变式（loop invariant）
  • 是一句断言定义各变量所满足的条件
  • ??Var a, b；??
  • ??While()??
????
循环书写方法
  • 定义循环不变式，并在循环体每次结束后保持循环不变式
  • 先一般，后特殊
  • 每次必须向前推进循环不变式中涉及的变量值
  • 每次推进的规模必须为1
链表反转
链表中delete_if
  1. 去重
  2. 头节点没有previous怎么办？
  1. 特殊处理
  2. 增加虚拟头节点
边界控制例如：二分查找在二序数组中查找元素k，返回k所在下标??binarySearch([1, 2, 10, 15, 100], 15) == 3??
二分查找思路：
  • 规定要查找的值k可能在的数组arr内下标区间a, b
  • 计算区间a，b的中间点m
  • 若k< arr[m]，将区间缩小为a, m。继续二分查找
  • 若k> arr[m]，将区间缩小为m, b。继续二分查找
数据结构树 -- 重点与难点
在白板上写程序：白板、纸笔、Word文档、记事本修改不便；缩进不便；对齐困难
心里不抵触；
先思考后写；
不要惧怕修改/重写
回顾列表：
  • 数组--随机访问
  • 链表
  • 队列、栈-- 访问有讲究
树：
  • 二叉树
  • 搜索树
  • 堆/优先队列
栈/队列/优先队列
Map< K, V> / Set< K>
  • HashMap / HashSet --> K.hashCode()
  • TreeMap / TreeSet -- > K implements Comparable
图：
  • 无向图
  • 有向图
  • 有向无环图
  • 图的算法--复杂，面试一般不出算法题
  • 深度优先遍历
  • 广度优先遍历
  • 拓扑排序
  • 最短路径/最小生成树
数学归纳法 -- 用在编码上用于证明断言对所有自然数成立
  1. 证明对于N=1成立
  1. 证明N> 1时：如果对于N-1成立，那么对于N成立
数学归纳法法则：求证：1+2+3+4+...+n=n(n+1)/2
  • 1 = 1*2/2
  • 如果1+2+3+...+(n-1) = (n-1)n/2
  • 那么1+2+3+...+n = 1+2+3+...+(n-1)+n=(n-1)n/2+n = (n(n-1)+2n)/2=n(n+1)/2
int sum(int n)
if (n == 1)
return 1;
return sum(n-1)+n;


    推荐阅读


    上一篇：音频 3A 处理实践，让你的应用更「动听」

    下一篇：干货合集│最好用的 python 库都在这