Kosmos
---我们总得选择一条路去前行---
剑指offer_Part2
友情提示: 代码在这里
本文参照该仓库学习,大家可以star
12 矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
13 机器人的运动范围
地上有一个 m 行和 n 列的方格。一个机器人从坐标 (0, 0) 的格子开始移动，每一次只能向左右上下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 k 的格子。
例如，当 k 为 18 时，机器人能够进入方格 (35,37)，因为 3+5+3+7=18。但是，它不能进入方格 (35,38)，因为 3+5+3+8=19。请问该机器人能够达到多少个格子？
14 剪绳子
把一根绳子剪成多段，并且使得每段的长度乘积最大。
贪心
尽可能多剪长度为 3 的绳子，并且不允许有长度为 1 的绳子出现。如果出现了，就从已经切好长度为 3 的绳子中拿出一段与长度为 1 的绳子重新组合，把它们切成两段长度为 2 的绳子。
证明：当 n >= 5 时，3(n - 3) - n = 2n - 9 > 0，且 2(n - 2) - n = n - 4 > 0。因此在 n >= 5 的情况下，将绳子剪成一段为 2 或者 3，得到的乘积会更大。又因为 3(n - 3) - 2(n - 2) = n - 5 >= 0，所以剪成一段长度为 3 比长度为 2 得到的乘积更大。
动态规划
15 二进制中 1 的个数
输入一个整数，输出该数二进制表示中 1 的个数。
return Integer.bitCount(n); (......amazing)
16 数值的整数次方
给定一个 double 类型的浮点数 base 和 int 类型的整数 exponent，求 base 的 exponent 次方。
递归 不要用pow(即使可以通过)
17 打印从 1 到最大的 n 位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数即 999。
由于 n 可能会非常大，因此不能直接用 int 表示数字，而是用 char 数组进行存储。
使用回溯法得到所有的数。
18 在 O(1) 时间内删除链表节点
① 如果该节点不是尾节点，那么可以直接将下一个节点的值赋给该节点，然后令该节点指向下下个节点，再删除下一个节点，时间复杂度为 O(1)。
② 如果链表只有一个节点，那么直接删除
否则，就需要先遍历链表，找到节点的前一个节点，然后让前一个节点指向 null，时间复杂度为 O(N)。
综上，如果进行 N 次操作，那么大约需要操作节点的次数为 N-1+N=2N-1，其中 N-1 表示 N-1 个不是尾节点的每个节点以 O(1) 的时间复杂度操作节点的总次数，N 表示 1 个尾节点以 O(N) 的时间复杂度操作节点的总次数。(2N-1)/N ~ 2，因此该算法的平均时间复杂度为 O(1)。
18-2 删除链表中重复的结点
通过递归将不重复的返回
19 正则表达式匹配
请实现一个函数用来匹配包括 '.' 和 '' 的正则表达式。模式中的字符 '.' 表示任意一个字符，而 '' 表示它前面的字符可以出现任意次（包含 0 次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串 "aaa" 与模式 "a.a" 和 "abaca" 匹配，但是与 "aa.a" 和 "ab*a" 均不匹配。
应该注意到，'.' 是用来当做一个任意字符，而 '' 是用来重复前面的字符。这两个的作用不同，不能把 '.' 的作用和 '' 进行类比，从而把它当成重复前面字符一次。
标题：剑指offer_Part2