剑指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” 均不匹配。

应该注意到,’.’ 是用来当做一个任意字符,而 ‘‘ 是用来重复前面的字符。这两个的作用不同,不能把 ‘.’ 的作用和 ‘‘ 进行类比,从而把它当成重复前面字符一次。