版权声明：本文为博主原创文章，转载请注明出处，谢谢!

关于LinkedList

似乎我们在工作中很少用到LinkedList，大部分都是使用ArrayList。先来看一下LinkedList的定义吧，它是List和Deque接口的双向链表实现；实现所有可选列表操作，并允许所有元素（包括null）；所有的操作都实在操作双向列表；索引到列表中的操作将从开始或结束遍历列表，以更接近指定的索引为准。从这个定义来看，这个LinkedList更适合较多插入和删除元素，较少读取元素，因为插入和删除元素不涉及重排数据。

至于Deque是什么。Deque是支持两端元素插入和移除的线性集合，而名称deque是双端队列(double ended queue)的缩写，通常发音为deck。既然它是个列表，那它确实继承了Queue，也支持所有与Queue相关的进、出方法。本文不再对deque做详细说明。

LinkedList主要成员变量

下面是LinkedList的主要成员变量。可以看到包含头指针和尾指针，而Node也是双向链表节点的表示，也就是说LinkedList真的是双向链表表示的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 列表大小
transient int size = 0;
/**
 * 指向头结点的指针
 */
transient Node<E> first;
/**
 * 指向尾节点的指针
 */
transient Node<E> last;
// Node类
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

关于ArrayList

相信ArrayList是小伙伴们在Java开发中经常会使用的类之一。那么ArrayList究竟是一个什么类呢。大概来说它是List接口的可调整大小的数组实现。 实现所有可选列表操作，并允许所有元素，包括null。除了实现List接口之外，他的类还提供了一些方法来操纵数组的内部大小来存储列表。 也就是说ArrayList内部是由数组实现，往ArrayList中放置元素也是默认按照先后顺序进行放置；它的大小是可调整的，不用像使用数组一样担心它不够存放数据（这里排除内存限制）。

总的来说ArrayList不论从使用还是理解上都是比较简单的，那么让我们来分析一下其中的一些关键方法吧。

关键成员变量

下面列出了ArrayList的关键成员变量，数量并不多，可以看到元素在ArrayList中是存储在数组中的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

	
/**
 * 存储元素的数组缓冲区
 * ArrayList的容量是此数组缓冲区的长度
 * 空ArrayList的elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * 当插入第一个元素后大小为DEFAULT_CAPACITY
 */
transient Object[] elementData; // non-private to simplify nested class access
/**
 * ArrayList的大小，即存储元素的数量
 *
 * @serial
 */
private int size;

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

题目要求

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5

Example 3:

Input: [1,2,3,4,4,5]
Output: False

Note:

The length of the input is in range of [1, 10000]

题意解析

给一个数组，数组中的数字按顺序排列并且存在重复数字，需要将这个数组拆分为几个子数组。子数组的至少包含3个连续数字。返回是否可以满足这样的拆分。

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

题目要求

You are given an integer array sorted in ascending order (may contain duplicates), you need to split them into several subsequences, where each subsequences consist of at least 3 consecutive integers. Return whether you can make such a split.

Example 1:

Input: [1,2,3,3,4,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3
3, 4, 5

Example 2:

Input: [1,2,3,3,4,4,5,5]
Output: True
Explanation:
You can split them into two consecutive subsequences :
1, 2, 3, 4, 5
3, 4, 5

Example 3:

Input: [1,2,3,4,4,5]
Output: False

Note:

The length of the input is in range of [1, 10000]

题意解析

给一个数组，数组中的数字按顺序排列并且存在重复数字，需要将这个数组拆分为几个子数组。子数组的至少包含3个连续数字。返回是否可以满足这样的拆分。

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

题目要求

In the world of Dota2, there are two parties: the Radiant and the Dire.

The Dota2 senate consists of senators coming from two parties. Now the senate wants to make a decision about a change in the Dota2 game. The voting for this change is a round-based procedure. In each round, each senator can exercise one of the two rights:

1. Ban one senator's right:
   A senator can make another senator lose all his rights in this and all the following rounds.
2. Announce the victory:
   If this senator found the senators who still have rights to vote are all from the same party, he can announce the victory and make the decision about the change in the game.

Given a string representing each senator’s party belonging. The character ‘R’ and ‘D’ represent the Radiant party and the Dire party respectively. Then if there are n senators, the size of the given string will be n.

The round-based procedure starts from the first senator to the last senator in the given order. This procedure will last until the end of voting. All the senators who have lost their rights will be skipped during the procedure.

Suppose every senator is smart enough and will play the best strategy for his own party, you need to predict which party will finally announce the victory and make the change in the Dota2 game. The output should be Radiant or Dire.

Example 1:

Input: “RD”
Output: “Radiant”
Explanation: The first senator comes from Radiant and he can just ban the next senator’s right in the round 1.
And the second senator can’t exercise any rights any more since his right has been banned.
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:

Input: “RDD”
Output: “Dire”
Explanation:
The first senator comes from Radiant and he can just ban the next senator’s right in the round 1.
And the second senator can’t exercise any rights anymore since his right has been banned.
And the third senator comes from Dire and he can ban the first senator’s right in the round 1.
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

Note:
The length of the given string will in the range [1, 10,000].

题意解析

Dota2有两个政党，光明党与黑暗党（好扯）。参议院的参议员也都属于这两个政党。现在参议员们决定要对Data2做出改变，当然每个政党希望的改变是不一样的，需要投票决定。投票是一个回合制程序。在每一轮中，每个参议员都可以行使两种权利之一。一种权利是让另一个政党的参议员在这一轮以及以后的每一轮没有任何权利；另一种是在参议会中只剩一个政党的参议员有权利的时候代表这个政党的胜利。

给出一个代表每个参议员党派归属的字符串，只包含两种字母，R和D，R代表Radiant，D代表Dire，如果有n个参议员那么字符串的长度就为n。

回合制程序从第一个参议员开始，到最后一个指定的参议员。这个程序将持续到投票结束。所有失去权利的参议员都将在程序中被跳过。假设每个参议员是足够聪明，会为自己的当事人发挥最好的策略，你需要预测哪一方将最终宣布胜利并在DOTA2游戏的变化。输出应该是辐射或可怕的。

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

关于HashMap

相信同学们在Coding（搬砖）的过程中经常会用到HashMap，那么HashMap到底是个什么东东呢？
以JDK8来讲，HashMap继承Map接口，在Map接口中描述Map是“An object that maps keys to values. A map cannot contain duplicate keys each key can map to at most one value.” 也就是说Map是一个映射键值的对象。映射中不能包含重复键，并且每个键可以映射到最多一个值。HashMap实现了Map接口，并且为基本操作（如：get、put）提供了常量时间的性能。

HashMap主要成员变量

下面的代码注释里详细的说明了HashMap的几个重要的成员变量。从这几个变量中可以分析得出，所有的键值对都存放在table变量中，而table变量的大小不是固定不变的，是在动态变化的，而且大小始终为2的幂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * HashMap的表结构，在首次使用的时候进行初始化，然后在需要的时候进行大小调整
 * 表的大小始终为2的幂
 * 初始值为16（DEFAULT_INITIAL_CAPACITY）
 */
transient Node<K,V>[] table;
/**
 * 映射项集合
 */
transient Set<Map.Entry<K,V>> entrySet;
/**
 * Map中映射对的数量
 */
transient int size;
/**
 * 这个HashMap已被结构化修改的次数
 * 结构修改是改变HashMap中的映射数或者修改其内部结构（例如rehash）的修改次数。
 * 此字段用于使HashMap的Collection-views上迭代器更快的失效。 （请参阅ConcurrentModificationException）。
 */
transient int modCount;
/**
 * 下一次调整大小的阈值 (capacity * load factor).
 */
int threshold;
/**
 * 负载系数，默认为0.75f（DEFAULT_LOAD_FACTOR）
 */
final float loadFactor;

从上面的代码总可以看到，table属性的类型为Node，这个Node实现了Map.Entry接口，所以本质上还是Map.Entry。另外，HashMap包含另外一种TreeNode，TreeNode本身为红黑树结构。在HashMap中，当一个普通Node（Plain Node）的长度大于一定值时会转换为TreeNode，而TreeNode长度小于一定值时会转换普通Node。

从下面的代码中可以看到，Node实现了Map.Entry接口，并且本身为链表结构，这样是为了处理不同键值可能会出现相同Hash的情况。

1
2
3
4
5
6
7
8
9

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        // 下一个Node'指针'
        Node<K,V> next;
        ...
    }

Unsafe类说明

从这个类的名字Unsafe上来说这个类就是一个不安全的类，也是不开放给用户直接使用的（当然我们还是可以通过其他一些方法用到）。
这个类在jdk源码中多个类中用到，主要作用是任意内存地址位置处读写数据，外加一下CAS操作。它的大部分操作都是绕过JVM通过JNI完成的，因此它所分配的内存需要手动free，所以是非常危险的。但是Unsafe中很多（但不是所有）方法都很有用，且有些情况下，除了使用JNI，没有其他方法弄够完成同样的事情。
至于研究它的起因，是因为我最近在看jdk8的ConcurrentHashMap，这个版本的主要函数就是用过Unsafe来完成的。

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

String简要说明

大家都知道Java中String是不可变类。也就是说如果有一个String初始化的值位”Hello”，如果把它赋值为”Hello World!”，那么不是在原内存地址上修改数据，而是重新生成了一个新对象并重新指向这个对象。而在Java虚拟机中，字符串是直接放在常量池中的，而且关于String比较相关的题目很多，这篇文章不做详细描述。

一个简单的例子

下面的代码会生成几个String，先不要着急的往下看答案，自己想想。

1

String str = "Hello" + "World" + "!";

这个问题主要还是考察了Java虚拟机对String中”+”运算符的特殊处理，我们来看一下编译生成的class是什么样的。见下图。

看到String HelloWorld!是不是很惊讶，是的，这段代码只生成了一个字符串。

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

为什么要增加畅言评论

之前一直在用多说评论，但是多说就要关闭了，就是在2017年6月1日。所以必须在这之前改用新的评论系统，不然的话博客就要不能评论了（然而并没有什么人给我评论）。然后就是选择用什么评论系统了，也没有什么可参考，随便选了一个。

至于为什么要自己添加，因为我的Next版本很旧了，但是自己做过很多改动不想更新到最新版本。

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

题目要求

In the video game Fallout 4, the quest “Road to Freedom” requires players to reach a metal dial called the “Freedom Trail Ring”, and use the dial to spell a specific keyword in order to open the door.

Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at 12:00 direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:
You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring’s characters at the 12:00 direction, where this character must equal to the character key[i].
If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you’ve finished all the spelling.

Example:

Input: ring = “godding”, key = “gd”
Output: 4
Explanation:
For the first key character ‘g’, since it is already in place, we just need 1 step to spell this character.
For the second key character ‘d’, we need to rotate the ring “godding” anticlockwise by two steps to make it become >”ddinggo”.
Also, we need 1 more step for spelling.
So the final output is 4.

Note:

1. Length of both ring and key will be in range 1 to 100.
2. There are only lowercase letters in both strings and might be some duplcate characters in both strings.
3. It’s guaranteed that string key could always be spelled by rotating the string ring.

题意解析

题目来自于辐射4这个游戏。有一个圆盘，圆盘上有几个英文字母，圆盘12点方向代表当前选中的字母，通过这个圆盘拼出一个和题目一样的字符串，求出最小的步数。

圆盘可以顺时针或者逆时针旋转，每旋转一个字母代表1步，当12点方向是需要的英文字母时，按确定按钮，这个按也算一步。