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

题目要求

A Tic-Tac-Toe board is given as a string array board. Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.

The board is a 3 x 3 array, and consists of characters " ", "X", and "O". The “ “ character represents an empty square.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (“ “).
• The first player always places “X” characters, while the second player always places “O” characters.
• “X” and “O” characters are always placed into empty squares, never filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Example 1:
Input: board = [“O “, “ “, “ “]
Output: false
Explanation: The first player always plays “X”.

Example 2:
Input: board = [“XOX”, “ X “, “ “]
Output: false
Explanation: Players take turns making moves.

Example 3:
Input: board = [“XXX”, “ “, “OOO”]
Output: false

Example 4:
Input: board = [“XOX”, “O O”, “XOX”]
Output: true

Note:

• board is a length-3 array of strings, where each string board[i] has length 3.
• Each board[i][j] is a character in the set {" ", "X", "O"}.

题意解析

这里的Tic-Tac-Toe游戏就是小时候的井字格游戏，这里不再详细解释这个游戏了。这道题的目的是求出当前游戏是否处于非法状态。

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

题目要求

Given string S and a dictionary of words words, find the number of words[i] that is a subsequence of S.

Example :
Input:
S = “abcde”
words = [“a”, “bb”, “acd”, “ace”]
Output: 3
Explanation: There are three words in words that are a subsequence of S: “a”, “acd”, “ace”.

Note:

• All words in words and S will only consists of lowercase letters.
• The length of S will be in the range of [1, 50000].
• The length of words will be in the range of [1, 5000].
• The length of words[i] will be in the range of [1, 50].

题意解析

现在有一个字符串S和一个单词字典words，求出words满足是S子序列的单词数目。

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

题目要求

We are given an array A of positive integers, and two positive integers L and R (L <= R).

Return the number of (contiguous, non-empty) subarrays such that the value of the maximum array element in that subarray is at least L and at most R.

Example :
Input:
A = [2, 1, 4, 3]
L = 2
R = 3
Output: 3
Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].

Note:

• L, R and A[i] will be an integer in the range [0, 10^9].
• The length of A will be in the range of [1, 50000].

题意解析

现在有一个A正整数数组，两个正整数L和R，其中L <= R。
求满足下面要求的子数组数量：子数组中的最大数介于L和R之间。

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

写在前面

关于Unsafe我之前写过一个文章Unsafe类初探，有兴趣的话可以先看下。这里先说一下这个类的重要性吧。

其实在一般的应用中这个类并没有作用，但是在一些场景下它是不可替代的，这里可以举一个常见的例子。我们都知道Java与C++、C不同，可以说是最大的不同，是没有办法直接操作内存，默认都是由JVM进行内存分配和垃圾回收，但是这种方式往往在垃圾回收时由于STW太长导致服务短暂或较长时间停止，而且这种问题即使调JVM参数也无法根本的解决，甚至无任何好转。但是使用Unsafe，我们即使在Java中也可以手动操作内存，这样可以大大减少垃圾回收时间而且可以减少堆内内存的使用。

但是一直有传言，java9的时候将会把这个类删除，这是个灾难性的消息，因为有很多应用现在依赖于它。不过就目前的java9版本来看这个类并没有删除，而且还更加易于使用。

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

前言

AtomicLong我已经在之前的文章Java并发源码之AtomicLong中做了详细的介绍。但是除了AtomicLong，还存在另外一个高效的并发计数类，那就是LongAdder。LongAdder官方文档的说明如下。我就不对这段文字做详细的说明了，简单来说，这个类用于在多线程情况下的求和。

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

/**
 * One or more variables that together maintain an initially zero
 * {@code long} sum.  When updates (method {@link #add}) are contended
 * across threads, the set of variables may grow dynamically to reduce
 * contention. Method {@link #sum} (or, equivalently, {@link
 * #longValue}) returns the current total combined across the
 * variables maintaining the sum.
 *
 * <p>This class is usually preferable to {@link AtomicLong} when
 * multiple threads update a common sum that is used for purposes such
 * as collecting statistics, not for fine-grained synchronization
 * control.  Under low update contention, the two classes have similar
 * characteristics. But under high contention, expected throughput of
 * this class is significantly higher, at the expense of higher space
 * consumption.
 *
 * <p>LongAdders can be used with a {@link
 * java.util.concurrent.ConcurrentHashMap} to maintain a scalable
 * frequency map (a form of histogram or multiset). For example, to
 * add a count to a {@code ConcurrentHashMap<String,LongAdder> freqs},
 * initializing if not already present, you can use {@code
 * freqs.computeIfAbsent(k -> new LongAdder()).increment();}
 *
 * <p>This class extends {@link Number}, but does <em>not</em> define
 * methods such as {@code equals}, {@code hashCode} and {@code
 * compareTo} because instances are expected to be mutated, and so are
 * not useful as collection keys.
 *
 * @since 1.8
 * @author Doug Lea
 */

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

并发计数的问题

我这里要老生常谈了，因为这个例子我感觉应该很多人都见过，就是两个线程并发计数，但是最后计数的结果和我们的期望不同，代码如下。

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

public static long i = 0;
  public static void main(String[] args) throws Exception {
      Thread thread1 = new Thread(){
        @Override
        public void run(){
            for(int m = 0; m < 500000; m++){
                i++;
            }
        }
      };
      Thread thread2 = new Thread(){
          @Override
          public void run(){
              for(int m = 0; m < 500000; m++){
                  i++;
              }
          }
      };
      thread1.start();
      thread2.start();
      Thread.sleep(1000L);
      System.out.println("i = " + i);
  }

结果如下：

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

题目要求

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].

Note:

1. 1 <= len(A), len(B) <= 1000
2. 0 <= A[i], B[i] < 100

题意解析

给两个个数组，返回两个数组中显示的子数组的最大长度。

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

题目要求

Given an unsorted array of integers, find the number of longest increasing subsequence.

Example 1:

Input: [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequence are [1, 3, 4, 7] and [1, 3, 5, 7].
Example 2:
Input: [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences’ length is 1, so output 5.

Note: Length of the given array will be not exceed 2000 and the answer is guaranteed to be fit in 32-bit signed int.

题意解析

给一个数组，求出数组中最长递增子序列的个数，子序列不要求连续。

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

前言

上一篇文章《Java并发源码之ReentrantLock(一)》中，对ReentrantLock的结构、作用、主要成员变量、主要方法等做了详细分析说明。本文将对主要的lock、unlock方法进行分析，分别包括公平锁和非公平锁。

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

ReentrantLock介绍

ReentrantLock是一个可重入的互斥锁，与使用synchronized方法和语句访问的隐式监视锁具有相同的基本行为和语义，但具有扩展功能。ReentrantLock属于最后一个成功加锁并且还没有释放锁的线程。当一个线程请求lock时，如果锁不属于任何线程，将立马得到这个锁；如果锁已经被当前线程拥有，当前线程会立即返回。

下面这个图是与ReentrantLock相关的UML类图，可以看到ReentrantLock实现了Lock和Serializable接口，表示它实现了lock()、unlock()等Lock的接口方法，并且是一个可以序列化的类。ReentrantLock主要成员变量为Sync，Sync是一个抽象类，继承了AbstractQueuedSynchronizer（简称AQS），AQS提供了一个基于FIFO队列，可以用于构建锁或者其他相关同步装置的基础框架，本文不详细介绍。而Sync有两个实现类：NonfairSync和FairSync，分别代表非公平锁和公平锁。也就是说ReentrantLock中所有的锁操作都是由sync这个成员变量完成的。