剑指offer笔记（十） 第63题至第68题 完结篇

剑指offer笔记（六） 第40题至第46题 完结篇

• 前言
• 一、JZ63 股票的最大利润
• 二、JZ64 求 1 + 2 + ... + n
• 三、JZ65 不用加减乘除做加法
• 四、JZ66 构建乘积数组
• 五、JZ67 把字符串转换成整数
• 六、JZ68-1 二叉搜索树的最近公共祖先
• 七、JZ68-2 二叉树的最近公共祖先
• 八、总结

---

前言

这次主要记录剑指offer的7道题，主要使用的语言是python，下面将对这7道题的一些感悟和知识点进行汇总！

---

提示：以下是本篇文章正文内容，下面案例可供参考 截图来源于LeetCode

一、JZ63 股票的最大利润

  这是一道非常有趣的“画图题”，下面的截图来自本题的LC官方题解，画出折线图，找到最低点和最高点，做差即可！注意只能是数组的后面减去前面，可不要 prices[0] - prices[1] 哦！

以下为程序源码：

二、JZ64 求 1 + 2 + … + n

  不用循环的话，就自身递归！详情看代码。

以下为程序源码

三、JZ65 不用加减乘除做加法

  不多说，K神讲得太好了，附上链接！

以下为程序源码：

四、JZ66 构建乘积数组

  暴力破解是不行的，会超出时间限制，且内存占用过大！这时候就需要认真考虑一下是否有什么秒方法，可以成功跳过一位乘上其他的呢？想请看代码，可以自己试着在本上画一画理解。

以下为程序源码：

五、JZ67 把字符串转换成整数

  很长的一道题，对于python而言，使用正则表达式是一个非常不错的选择，可以学习记一下！另外，这里的打表模拟过程特别像FPGA里面的状态机，挺好理解的，耐心看下特别有助于理解题意。


以下为程序源码：

六、JZ68-1 二叉搜索树的最近公共祖先

  递归，YYDS！

以下为程序源码：

七、JZ68-2 二叉树的最近公共祖先

  没有二叉搜索树的强大特性，那么在进行递归的时候就需要多考虑一些情况的出现，也就是None的问题，详情看代码。

以下为程序源码：

八、总结

  不知不觉，上周又忘写了！害，补上。
  至此，剑指offer篇算是刷全了，其实早在上个月月底我就已经刷完了，不过忘得也差不多了，我感觉这样写出来的博客并不好看，所以想记录一下我深度学习过程中遇到的一些问题的解决办法或者一些很好的代码。如果有看到的朋友，麻烦给个赞啊！