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

题目要求

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点方向是需要的英文字母时，按确定按钮，这个按也算一步。

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

题目要求

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input:
s = “abpcplea”, d = [“ale”,”apple”,”monkey”,”plea”]

Output:
“apple”

Example 2:

Input:
s = “abpcplea”, d = [“a”,”b”,”c”]

Output:
“a”

Note:

1. All the strings in the input will only contain lower-case letters.
2. The size of the dictionary won’t exceed 1,000.
3. The length of all the strings in the input won’t exceed 1,000.

题意解析

给出一个String A和一个String数组，在String数组中找到最长的String B，这个String可以满足从A中删除一些字母得到。如果满足的字符串有多个，则选择字母序最小的字符串。

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

题目要求

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: [“23:59”,”00:00”]
Output: 1
Note:

1. The number of time points in the given list is at least 2 and won’t exceed 20000.
2. The input time is legal and ranges from 00:00 to 23:59.

题意解析

计算最短的时间间隔，注意24小时制值得变化。

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

题目要求

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

题意解析

完成短链接的编解码。

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

题目要求

Let’s play the minesweeper game (Wikipedia), online game)!

You are given a 2D char matrix representing the game board. ‘M’ represents an unrevealed mine, ‘E’ represents an unrevealed empty square, ‘B’ represents a revealed blank square that has no adjacent (above, below, left, right, and all 4 diagonals) mines, digit (‘1’ to ‘8’) represents how many mines are adjacent to this revealed square, and finally ‘X’ represents a revealed mine.

Now given the next click position (row and column indices) among all the unrevealed squares (‘M’ or ‘E’), return the board after revealing this position according to the following rules:

If a mine (‘M’) is revealed, then the game is over - change it to ‘X’.
If an empty square (‘E’) with no adjacent mines is revealed, then change it to revealed blank (‘B’) and all of its adjacent unrevealed squares should be revealed recursively.
If an empty square (‘E’) with at least one adjacent mine is revealed, then change it to a digit (‘1’ to ‘8’) representing the number of adjacent mines.
Return the board when no more squares will be revealed.

Example 1:

Input:

[[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘M’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘E’, ‘E’, ‘E’],
[‘E’, ‘E’, ‘E’, ‘E’, ‘E’]]

Click : [3,0]

Output:

[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],
[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]

Explanation:

Example 2:

Input:

[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘M’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],
[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]

Click : [1,2]

Output:

[[‘B’, ‘1’, ‘E’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘X’, ‘1’, ‘B’],
[‘B’, ‘1’, ‘1’, ‘1’, ‘B’],
[‘B’, ‘B’, ‘B’, ‘B’, ‘B’]]

Explanation:

Note:

1. The range of the input matrix’s height and width is [1,50].
2. The click position will only be an unrevealed square (‘M’ or ‘E’), which also means the input board contains at least one clickable square.
3. The input board won’t be a stage when game is over (some mines have been revealed).
4. For simplicity, not mentioned rules should be ignored in this problem. For example, you don’t need to reveal all the unrevealed mines when the game is over, consider any cases that you will win the game or flag any squares.

题意解析

这个题指的是扫雷游戏。在扫雷游戏中，用二维矩阵标识当前的扫雷状态。没有被发掘的空块标记为'E'，没有被发掘的雷为'M'，发掘之后的空块标记为'N'，发掘之后的块标记为'X'，另外数字1-8表示该块周围有几个雷。

给出一个二维矩阵标识当天扫雷游戏的状态，然后给出下一步，求出走完下一步之后的游戏状态。