剑指offer笔记（二） 第11题至第17题

剑指offer笔记（二） 第11题至第17题"/>

剑指offer笔记（二） 第11题至第17题

剑指offer笔记（二） 第11题至第17题

• 前言
• 一、JZ11 旋转数组的最小数字
• 二、JZ12 矩阵中的路径
• 三、JZ13 机器人的移动范围
• 四、JZ14 剪绳子
• 五、JZ15 二进制中 1 的个数
• 六、JZ16 数值的整数次方
• 七、JZ17 打印从1到最大的n位数
• 八、总结

前言

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

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

一、JZ11 旋转数组的最小数字

  旋转数组就是两个升序的子数组组成，因而指针的移动在左右数组之间切换令mid=（left+right）/2
  1）当numbers[mid] > numbers[right] 则left = mid+1;#跑到后面的数组
  2）当numbers[mid] < numbemidrs[right] 则right = mid;#准确定位到前面的数组 [1,5,1]的特例
  3）当numbers[mid] = numbers[right] 则right = right-1;

以下为程序源码：

二、JZ12 矩阵中的路径

  这道题没需要用回溯法和深度优先搜索，参考香辣鸡排蛋包饭的讲解视频去理解这道题比较顺利一些，下图为整体的理解思路，图片截自香辣鸡排蛋包饭的视频。

  其中涉及到路径重复的问题，如下图所示，每一次的覆盖均有数据进行记录 ，因而如果回到上一层，依旧可以对原数据进行还原

以下为程序源码：

三、JZ13 机器人的移动范围

  此题与JZ12 很是相近，但涉及到动态规划问题，参见蛋包饭 的讲解视频和图片对其进行理解。

以下为程序源码：

四、JZ14 剪绳子

  这里直接贪心（数学推导）来看了。
  具体 数据推到如下图所示

以下为程序源码：

五、JZ15 二进制中 1 的个数

  比较简单且经典的一道题，令 n 与 (n-1) 位与 即可！

以下为程序源码：

六、JZ16 数值的整数次方

  这道题就不细细描述了，LeetCode官方的解释非常棒，想了解直接去走这道题就行！这里主要的一个难点就是：二进制与十进制的来回认知问题，另外Krahets大神地讲解非常地棒，特别推荐去看一下！下面的截图来自Krahets的讲解内容。

以下为程序源码：

七、JZ17 打印从1到最大的n位数

  这道题就不多说了，参见我的另外一篇blog：JZ17 大数的打印

八、总结

  慢慢步入正轨，最近的生活学习有些乏力，需要多运动一下，另外忽然觉着安妮宝贝的一句话特别棒：
  任何一件事情，只要心甘情愿，总是能够变得简单！
  希望如此吧！
  不过，最后仍然附上一句我特别喜欢的英文诗，节选自喜剧大师卓别林的 As I began to love myself ：
  Even stars collide, out of their crashing new worlds are born;
  Today I know, THAT IS LIFE.
  美极了，有点 沉舟侧畔千帆过，病树前头万木春 的既视感了。 ha =-= ha