WRY

Where Are You?
You are on the brave land,
To experience, to remember...

0%

剑指offer

不再维护!,请参见

剑指 Offer 03. 数组中重复的数字

n个数的数组,数值分布在[0, n-1]之间,找出其中的任一重复数字。

要求:

  • 时间O(nlogn) & 空间O(1).
  • 时间O(n) & 空间O(n).
  • 时间O(n) & 空间O(1).
  • 若不能修改原数组,要求时间O(nlogn) & 空间O(1).

分别对应:排序,哈希,找座,二分

剑指 Offer 14- II. 剪绳子 II

长度n>1的绳子剪成m>1段,使其乘积最大

解答思路:

  • 动态规划
  • 贪心算法

剑指 Offer 16. 数值的整数次方

快速求幂,从二进制和二分法的角度,分别对应非递归和递归的实现思路。

注意:乘以-1的时候,int越界的问题

剑指 Offer 17. 打印从1到最大的n位数

大数问题,string来表示,转为“全排列”的问题

剑指 Offer 19. 正则表达式匹配

两种解法:

  • 递归

  • 动态规划

    f[i][j] 代表 A 的前 i 个和 B 的前 j 个能否匹配

剑指 Offer 20. 表示数值的字符串

和C++文档相比,允许前后多处空格

状态转移图

剑指 Offer 51. 数组中的逆序对

实现一个递归算法,在合并的过程中,如果左右两个数字相等,应该如何处理?

将左侧的数字移到临时数组,右侧不动,(左侧后面的数字仍有可能大于右侧当前值),Eg:

1
2
1,2,3
1,2

剑指 Offer 52. 两个链表的第一个公共节点

三种解法

剑指 Offer 56 - II. 数组中数字出现的次数 II

从统计每个位置1的数量出发,对3取模获取到最终的结果。优化解法:状态机模拟每个位置1的数量变化。