我的思路:
写出前五项观察结果:
1:1
2:2
3:3
4:5
5:8
……
可知结果为斐波那契数列,直接用递归的方法求解斐波那契数列第 n 项
代码实现:
1 2 3 4 5 6 7
| class Solution { public int climbStairs(int n) { if (n == 1) return 1; if (n == 2) return 2; return climbStairs(n - 1) + climbStairs(n - 2); } }
|
执行结果:
由于递归及其耗费时间,时间复杂度为 O(2^n),导致求解超时
更好的解法:
1 2 3 4 5 6 7 8 9 10 11
| class Solution { public int climbStairs(int n) { int p = 0, q = 0, r = 1; for (int i = 1; i <= n; i++) { p = q; q = r; r = p + q; } return r; } }
|
我的思路:
循环遍历链表:
- 当 node 的值与 node.next 值相同时,node.next 后移
- 否则 node 后移
代码实现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
|
class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode node = head; while (node != null && node.next != null) { if (node.val == node.next.val) { node.next = node.next.next; } else { node = node.next; } } return head; } }
|
解体思路:
考虑从右往左递归,这样不需要额外的数组占用额外的空间
1 2 3 4 5 6 7 8 9 10 11 12 13
| class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p = m-- + n-- - 1; while (m >= 0 && n >= 0) { nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--]; } while (n >= 0) { nums1[p--] = nums2[n--]; } } }
|
我的思路:
使用中序遍历的方法遍历两个二叉树,将结果保存在 List 中,最终比较两个 List 是否相同
问题在于我在中序遍历的时候使用递归,每次递归都要创建一个全新的 List ,故无法完整保存二叉树的全部节点信息
更好的思路:
递归遍历二叉树……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
|
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } if (p.val == q.val) { return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); } else { return false; } } }
|