Java版剑指Offer：编程题解

剑指offer

leetcode

需积分: 9 178 浏览量更新于2024-07-18 收藏 3.83MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"这是《剑指Offer》一书的Java版代码实现，由GitHub用户Cyc2018贡献，仅供学习交流，禁止商业用途。书中涵盖了许多经典的算法和数据结构问题，适合准备面试和提升编程能力。" 这篇文章是关于《剑指Offer》一书中的Java代码实现，该书是针对面试和提升编程技能的一本经典著作，特别是对于准备面试的程序员来说，书中的题目和解决方案极具参考价值。以下是对部分题目及其涉及知识点的详细说明： 1. **实现Singleton**：设计模式之一，确保一个类只有一个实例，并提供全局访问点。 2. **数组中重复的数字**：涉及到数组操作和哈希映射，用于找出数组中重复的元素。 3. **二维数组中的查找**：在二维数组中寻找特定元素，可能涉及到遍历算法。 4. **替换空格**：字符串处理，将空格替换为指定字符，如"%20"。 5. **从尾到头打印链表**：链表操作，需反转链表的遍历方向。 6. **重建二叉树**：根据前序遍历和中序遍历结果构建二叉树。 7. **二叉树的下一个结点**：二叉树的邻接节点查找，可能需要借助辅助栈来实现。 8. **用两个栈实现队列**：数据结构转换，利用栈的特性模拟队列的入队和出队操作。 9. **斐波那契数列**：递归或动态规划求解，如使用缓存避免重复计算。 10. **跳台阶**：动态规划问题，如青蛙跳台阶。 11. **旋转数组的最小数字**：数组操作，找到旋转数组中的最小值。 12. **矩阵中的路径**：深度优先搜索（DFS）或广度优先搜索（BFS）在网格中的应用。 13. **机器人的运动范围**：坐标系统内的移动，可能涉及到BFS或DFS。 14. **剪绳子**：动态规划，最大化两个数相乘的结果。 15. **二进制中1的个数**：位操作，快速统计二进制表示中1的个数。 16. **数值的整数次方**：快速幂运算，提高计算效率。 17. **打印从1到最大的n位数**：动态规划生成多位数序列。 18. **删除链表节点**：链表操作，包括头节点和非头节点的删除。 19. **正则表达式匹配**：字符串匹配算法，如KMP或Rabin-Karp。 20. **表示数值的字符串**：字符串解析，将字符串转换为数值。 21. **调整数组顺序使奇数位于偶数前面**：数组操作，可以使用双指针法。 22. **链表中倒数第K个结点**：链表操作，如快慢指针法。 23. **链表中环的入口结点**：链表环检测，如Floyd算法或双指针法。 24. **反转链表**：链表操作，将链表节点顺序反转。 25. **合并两个排序的链表**：链表操作，将两个有序链表合并为一个有序链表。 26. **树的子结构**：树的相似性判断，可能使用深度优先搜索。 27. **二叉树的镜像**：树的翻转，通过交换左右子节点实现。 28. **对称的二叉树**：树的对称性判断，通常使用递归或层次遍历。 29. **顺时针打印矩阵**：矩阵操作，按照顺时针方向打印矩阵。 30. **包含min函数的栈**：自定义栈数据结构，同时支持最小值查询。 31. **栈的压入、弹出序列**：栈的性质验证，检查给定序列是否合法。 32. **从上往下打印二叉树**：层次遍历二叉树，可以使用队列实现。 33. **二叉搜索树的后序遍历序列**：二叉树遍历，后序遍历具有特定性质。 34. **二叉树中和为某一值的路径**：树的路径搜索，可以使用DFS或BFS。 35. **复杂链表的复制**：链表操作，复制链表并保持原链表的结构。 36. **二叉搜索树与双向链表**：将二叉搜索树转换为有序双向链表。 37. **序列化二叉树**：二叉树的序列化与反序列化，常用方法有前序遍历编码。 38. **字符串的排列**：全排列问题，可以使用回溯法。 39. **数组中出现次数超过一半的数字**：摩尔投票法，找出数组中出现次数过半的元素。 40. **最小的K个数**：快速选择算法，找到数组中最小的K个数。 41. **数据流中的中位数**：数据流中的中位数维护，可以使用最小堆和最大堆。 42. **连续子数组的最大和**： Kadane's Algorithm，找到连续子数组的最大和。 43. **从1到n整数中1出现的次数**：位操作和数学分析，计算1在所有1到n的整数中出现的次数。 44. **数字序列中的某一位数字**：数组和位操作，找到数字序列中特定位置的数字。 45. **把数组排成最小的数**：字符串操作，将数组元素组合成最小的数字字符串。 46. **把数字翻译成字符串**：数字与字符串之间的转换，如将数字转化为罗马数字。 47. **礼物的最大价值**：动态规划，求解最优策略。 48. **最长不含重复字符的子字符串**：滑动窗口算法，找到最长无重复字符的子串。 49. **丑数**：动态规划或递归，找到第N个丑数。 50. **第一个只出现一次的字符位置**：字符串操作，找到第一次出现且只出现一次的字符。 51. **数组中的逆序对**：排序或归并思想，计算数组中逆序对的数量。 52. **两个链表的第一个公共结点**：链表操作，找到两个链表的交点。以上内容涵盖了算法、数据结构、字符串处理、数学逻辑等多个方面，对于提升编程技能和面试准备非常有帮助。

资源详情

资源推荐

2018/12/11 剑指 offer 题解.md

file:///G:/%E7%A0%94%E7%A9%B6%E7%94%9F/%E5%88%B7%E9%A2%98/CS-Notes/notes/%E5%89%91%E6%8C%87%20offer%20%E9

…

10/55

解题思路

如果使用递归求解，会重复计算一些子问题。例如，计算 f(10) 需要计算 f(9) 和 f(8)，计算 f(9) 需要计算 f(8) 和 f(7)，可以看到 f(8)

被重复计算了。

递归是将一个问题划分成多个子问题求解，动态规划也是如此，但是动态规划会把子问题的解缓存起来，从而避免重复求解子问

题。

public int Fibonacci(int n) {

if (n <= 1)

return n;

int[] fib = new int[n + 1];

fib[1] = 1;

for (int i = 2; i <= n; i++)

fib[i] = fib[i - 1] + fib[i - 2];

return fib[n];

}

考虑到第 i 项只与第 i-1 和第 i-2 项有关，因此只需要存储前两项的值就能求解第 i 项，从而将空间复杂度由 O(N) 降低为 O(1)。

public int Fibonacci(int n) {

if (n <= 1)

return n;

int pre2 = 0, pre1 = 1;

int fib = 0;

for (int i = 2; i <= n; i++) {

fib = pre2 + pre1;

pre2 = pre1;

pre1 = fib;

}

return fib;

}

由于待求解的 n 小于 40，因此可以将前 40 项的结果先进行计算，之后就能以 O(1) 时间复杂度得到第 n 项的值了。

public class

Solution

{

private int[] fib = new int[40];

public Solution() {

fib[1] = 1;

fib[2] = 2;

剩余54页未读，继续阅读

Bidlin

粉丝: 16
资源: 24

Java版剑指Offer：编程题解

最新资源