1. 两数之和
方法一：暴力法（两层循环）时间复杂度：O(n^2) ，空间复杂度O(1)
方法二：两遍哈希表（第一遍构造哈希表，第二遍找答案），时间复杂度：O(n) 空间复杂度O(n)
方法三：一遍哈希表（最优解）时间复杂度：O(n) ，空间复杂度O(n)
11. 盛最多水的容器
方法一：暴力法（两层循环）时间复杂度：O(n^2) ，空间复杂度：O(1)
方法二：双指针法（前后两个指针向中间移动，最优解）时间复杂度：O(n) ，空间复杂度：O(1)
15. 三数之和
方法一：暴力法（三层循环），时间复杂度：O(n^3) ，空间复杂度：O(1)
方法二：哈希表（排序+两层循环），时间复杂度：O(n^2) ，空间复杂度：O(1)
方法三：排序+双指针，时间复杂度：O(n^2) ，空间复杂度：O(1)
21. 合并两个有序链表
方法一：迭代，时间复杂度：O(m+n) ，空间复杂度：O(1)
方法二：递归（没看明白），时间复杂度：O(m+n) ，空间复杂度：O(m+n)
24. 两两交换链表中的节点
方法一：迭代， 时间复杂度：O(n) ，空间复杂度：O(1)
方法二：递归，时间复杂度：O(n) ，空间复杂度：O(n)
25. K 个一组翻转链表
方法一：迭代+就地逆置法， 时间复杂度：O(n) ，空间复杂度：O(1)
方法二：迭代+尾插法， 时间复杂度：O(n) ，空间复杂度：O(1)
方式三：递归
26. 删除排序数组中的重复项
方法一：双指针， 时间复杂度：O(n) ，空间复杂度：O(1)
66. 加一
- 末位无进位，则末位加一即可，因为末位无进位，前面也不可能产生进位，比如 45 => 46
- 末位有进位，在中间位置进位停止，则需要找到进位的典型标志，即为当前位 %10后为 0，则前一位加 1，直到不为 0 为止，比如 499 => 500
- 末位有进位，并且一直进位到最前方导致结果多出一位，对于这种情况，需要在第 2 种情况遍历结束的基础上，进行单独处理，比如 999 => 1000
时间复杂度：O(n) ，空间复杂度：O(1)
70. 爬楼梯
方法一：暴力递归， 时间复杂度：O(2^n) ，空间复杂度：O(n)
方法二：记忆化递归，时间复杂度：O(n) ，空间复杂度：O(n)
方法三：动态规划（dp[i] = dp[i-1]+dp[i-2]），时间复杂度：O(n) ，空间复杂度：O(n)
方法四：斐波那契数列 ，时间复杂度：O(n) ，空间复杂度：O(1)
方法五：Binets 方法(矩阵相乘)，时间复杂度：O(logn) ，空间复杂度：O(1)
方法六：斐波那契公式，时间复杂度：O(logn) ，空间复杂度：O(1)
public class Solution {
public int climbStairs(int n) {
double sqrt5=Math.sqrt(5);
double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
return (int)(fibn/sqrt5);
}
}
88. 合并两个有序数组
方法一：合并排序，时间复杂度：O((m+n)log(m+n)) ，空间复杂度：O(1)
方法二：双指针从前往后，时间复杂度：O(m+n) ，空间复杂度：O(m)
方法三：双指针从后往前，时间复杂度：O(m+n) ，空间复杂度：O(1)
141. 环形链表
方法一：哈希表（set） ，时间复杂度：O(n) ，空间复杂度：O(n)
方法二：快慢指针，时间复杂度：O(n) ，空间复杂度：O(1)
142. 环形链表 II
方法一：哈希表（set） ，时间复杂度：O(n) ，空间复杂度：O(n)
方法二：快慢指针，时间复杂度：O(n) ，空间复杂度：O(1)
189. 旋转数组
方法一：暴力法（嵌套循环），时间复杂度：O(n*k) ，空间复杂度：O(1)
方法二：使用额外空间存储旋转后的数据，时间复杂度：O(n) ，空间复杂度：O(n)
方法三：使用环状替换（最优解），时间复杂度：O(n) ，空间复杂度：O(n)
方法四：三次反转，时间复杂度：O(n) ，空间复杂度：O(1)
方法五：Python切片，（nums[:] = nums[n-k:] + nums[:n-k] ）
206. 反转链表
方法一：就地逆置法， 时间复杂度：O(n) ，空间复杂度：O(1)
方法二：头插法， 时间复杂度：O(n) ，空间复杂度：O(1)
方法三：递归，时间复杂度：O(n) ，空间复杂度：O(n)
283. 移动零
最优解：双指针法（快慢指针，慢指针前都是非0，慢指针和当前指针之间都是0），时间复杂度：O(n) ，空间复杂度：O(1)
网友评论