1. 爬楼梯

image-20200702164140831
我的思路:

写出前五项观察结果:

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);
}
}
执行结果:
image-20200702164353193

由于递归及其耗费时间,时间复杂度为 O(2^n),导致求解超时

更好的解法:

fig1

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;
}
}
image-20200702164659173

2. 删除排序链表中的重复元素

image-20200702170926322
我的思路:

循环遍历链表:

  • 当 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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
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;
}
}

3. 合并两个有序数组

image-20200702202006718
解体思路:

考虑从右往左递归,这样不需要额外的数组占用额外的空间

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--];
}
}
}

4. 相同的树

image-20200703162444481
我的思路:

使用中序遍历的方法遍历两个二叉树,将结果保存在 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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
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;
}
}
}