Leecode-070-Climbing Stairs

思路：动态规划

题目描述

每次爬楼梯可以爬1个或者2个台阶，你有多少种不同的方法可以爬到楼顶？

注意：给定的n是一个正整数。

1
2
3
4
5

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

1
2
3
4
5
6

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

Leecode-337-打家劫舍 III

思路：动态规划

题目描述：

你又是一个专业的小偷。。。。

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

1
2
3
4
5
6
7
8
9
10

输入: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

输出: 7 
解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7.

1
2
3
4
5
6
7
8
9
10

输入: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

输出: 9
解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9.

Leecode-1306-Jump Game III

思路：深度优先遍历/DFS

题目描述

• 这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。

• 当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - arr[i]。

• 请你判断自己是否能够跳到对应元素值为 0 的 任意 下标处

示例：

1
2
3
4
5
6

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3

1
2
3
4
5

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true 
解释：
到达值为 0 的下标 3 有以下可能方案： 
下标 0 -> 下标 4 -> 下标 1 -> 下标 3

1
2
3

输入：arr = [3,0,2,1,2], start = 2
输出：false
解释：无法到达值为 0 的下标 1 处。

Leecode-543-Diameter of Binary Tree

思路：深度优先搜索

说在前面

说在前面：看本题之前，先去把Leetcode-104-二叉树的最大深度 做一下，效果会更好。（这两题有异曲同工之妙）。

Leecode-045-Jump Game II

思路：贪心算法

题目描述

本题是上一题（Leetode-55-跳跃游戏）的扩展题。

来看题目描述：

1
2
3
4

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

• 给定一个非负整数数组，你最初位于数组的第一个位置。
• 数组中的每个元素代表你在该位置可以跳跃的最大长度。
• 目标是使用最少的跳跃次数到达数组的最后一个位置。

JDK1.8源码-10-java.util.Stack

前序：之前我们学完了Vector,接下来开始学习Stack。Stack很简单，它继承了Vector。

1. 简介

• Stack叫做栈
• 特性是：先进后出（FILO:First in Last Out）

• java工具包中的Stack继承于Vecotr(矢量队列)
• 由于Vector是通过数组实现的，这就意味着Stack也是通过数组实现的。
• 当然LinkedList也可以当做栈使用。

JDK1.8源码-09-java.util.Vector

学完ArrayList和LinkedList之后，我们接着学习Vector。

1. 简介

1
2
3

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector是矢量队列，它是JDK1.0版本添加的类。继承于AbstractList,实现了List接口。

JDK1.8源码-08-java.util.HashSet

在JDK1.8中，HashMap是用 数组+链表+红黑树构成，相对于早期版本的JDK HashMap实现，新增了红黑树作为底层的数据结构，在数据量较大且哈希碰撞较多的时候，能够极大的增加检索的效率。

了解了HashMap的具体实现后，再来了解HashMap作为底层数据结构的HashSet。

(如果不了解 HashMap 的实现原理，建议先看看 HashMap，不然直接看 HashSet 是很难看懂的）

JDK1.8源码-08-java.util.HashMap

本篇来介绍在 JDK1.8 中 HashMap 的源码实现，这也是最常用的一个集合。但是在介绍 HashMap 之前，我们先介绍什么是 Hash表。

B站很好的HashMap视频： https://www.bilibili.com/video/BV1LJ411W7dP

JUC-13-异步回调

1. 简介

1. Future

2. CompletableFuture< T >