剑指offer

发表于

也不是我写的啦，看到的简单记录下最优解法，68个都记一下吧。
先一半。
3.数组中重复数字：
将值为i的元素调整到第i个位置求解。
4.二维数组查找：
从右上角开始，小于它的数在其左边，大于它的数在其右边。
5.空格替换：

两个指针从最右边遍历，遇到空格填充替换字符。

6.逆序打印链表：
递归、头插法、栈。
7.根据前序遍历和中序遍历重建二叉树（不含重复数）：
前序第一个值为根，把中序分两部分。
private Map<Integer, Integer> indexForInOrders = new HashMap<>();
8.给定二叉树和一个节点，找其中序遍历下一个节点(节点有指向父节点指针):
右子树不为空，为右子树最左节点；否则向上找第一个左链接指向的树包含该节点的祖先节点。
9.两个栈实现队列：
一个处理push，另一个处理pop，出的时候先进pop再出。
10.斐波那契数列：用数组缓存一下计算过的数据。
n个21矩形覆盖一个2n，几种方法；跳台阶（1or2步）：找递推公式。
变态跳台阶（1or2or…n步）：等比数列f(n) = 2f(n-1)；动态规划。
11.输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素：
用改良二分法，将数组一分为二，一个是包含最小元素的新旋转数组，另一个是非递减排序的数组（第一个元素一个小于等于最后一个元素），多次二分即可。
12.字符矩阵路径：
回溯法（暴力搜索）。
13.机器人运动范围：
回溯深搜。
14.一根升子剪多段，每段长度乘积最大：
贪心，优先3、2；动态规划。
15.输出一个数二进制表示中1的个数：
n&(n-1)位运算，每做一次ans++，至0。
16.base（浮点数） 的 exponent（整数） 次方：
如图
(xx)n/可以递归求解。
17.打印从1到最大n位数：
char数组存储数字，回溯法得到所有数。
18.O(1)时间删除链表节点（删重复节点类似）：
非尾节点，将下一个节点值给它，把下一个删了；尾节点则将它前面一个节点指向null。
19.正则表达式匹配（.一个，a任意个a）：
dp[0][0] = true;
for (int i = 1; i <= n; i++)
if (pattern[i - 1] == ‘‘)
dp[0][i] = dp[0][i - 2];

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.')
            dp[i][j] = dp[i - 1][j - 1];
        else if (pattern[j - 1] == '*')
            if (pattern[j - 2] == str[i - 1] || pattern[j - 2] == '.') {
                dp[i][j] |= dp[i][j - 1]; // a* counts as single a
                dp[i][j] |= dp[i - 1][j]; // a* counts as multiple a
                dp[i][j] |= dp[i][j - 2]; // a* counts as empty
            } else
                dp[i][j] = dp[i][j - 2];  // a* only counts as empty

20.表示数值的字符串：
正则表达式匹配，return new String(str).matches(“[+-]?\d*(\.\d+)?([eE][+-]?\d+)?”);
[] ： 字符集合
() ： 分组
? ： 重复 0 ~ 1 次
+ ： 重复 1 ~ n 次
* ： 重复 0 ~ n 次
. ： 任意字符
\. ： 转义后的 .
\d ： 数字
21.调整数组顺序使奇数位于偶数前面：
创新数组或者冒泡。
双向链表。
22.链表中倒数第 K 个结点：
设置两个指针 P1 和 P2，先让 P1 移动 K 个节点，再同时移动。
23.链表中环的入口结点：
一个指针每次移动两个，另一个指针每次移动一个，存在环必定相遇，此点即入口。
24.反转链表：
递归，或者头插法迭代。
25.合并两个排序的链表：
递归或者迭代。
26.树的子结构：