行走的轮子

戒急用忍


  • 首页

  • 归档

  • 标签

  • 到此一游

  • 搜索

LeetCode 990. Satisfiability of Equality Equations

发表于 2019-02-12   |   分类于 LeetCode , Java   |   ❤

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

题目要求

Given an array equations of strings that represent relationships between variables, each string equations[i] has length 4 and takes one of two different forms: "a==b" or "a!=b". Here, a and b are lowercase letters (not necessarily different) that represent one-letter variable names.

Return true if and only if it is possible to assign integers to variable names so as to satisfy all the given equations.

Example 1:

Input: [“a==b”,”b!=a”]
Output: false
Explanation: If we assign say, a = 1 and b = 1, then the first equation is satisfied, but not the second. There is no way to assign the variables to satisfy both equations.

Example 2:

Input: [“b==a”,”a==b”]
Output: true
Explanation: We could assign a = 1 and b = 1 to satisfy both equations.

Example 3:

Input: [“a==b”,”b==c”,”a==c”]
Output: true

Example 4:

Input: [“a==b”,”b!=c”,”c==a”]
Output: false

Example 5:

Input: [“c==c”,”b==d”,”x!=z”]
Output: true

Note:

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] and equations[i][3] are lowercase letters
  4. equations[i][1] is either '=' or '!'
  5. equations[i][2] is '='

题意解析

给出一个字符串数组,每个字符串的长度为4,中间两个字符为==或者!=,而第一个和最后一个为字母,代表一个数字。
判断这些等式是否都能满足。

阅读全文 »

LeetCode 991. Broken Calculator

发表于 2019-02-12   |   分类于 LeetCode , Java   |   ❤

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

题目要求

On a broken calculator that has a number showing on its display, we can perform two operations:

  • Double: Multiply the number on the display by 2, or;
  • Decrement: Subtract 1 from the number on the display.
    Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

  1. 1 <= X <= 10^9
  2. 1 <= Y <= 10^9

题意解析

目前有一个坏了的计算器,只能有两个操作,一个是加倍也就是乘以2,另外一个是减一。
现在两个数字,X和Y,在使用这个坏计算器的基础上,从X得到Y的最少操作次数。

阅读全文 »

LeetCode 794. Valid Tic-Tac-Toe State

发表于 2018-03-09   |   分类于 LeetCode , Java   |   ❤

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

题目要求

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游戏就是小时候的井字格游戏,这里不再详细解释这个游戏了。这道题的目的是求出当前游戏是否处于非法状态。

阅读全文 »

LeetCode 792. Number of Matching Subsequences

发表于 2018-03-09   |   分类于 LeetCode , Java   |   ❤

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

题目要求

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子序列的单词数目。

阅读全文 »

LeetCode 795. Number of Subarrays with Bounded Maximum

发表于 2018-03-07   |   分类于 LeetCode , Java   |   ❤

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

题目要求

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之间。

阅读全文 »

解析java9中的Unsafe

发表于 2018-01-18   |   分类于 Java , 源码   |   ❤

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

写在前面

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

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

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

阅读全文 »

Java并发源码之LongAdder

发表于 2018-01-11   |   分类于 Java , 源码   |   ❤

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

前言

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
*/

阅读全文 »

Java并发源码之AtomicLong

发表于 2017-11-17   |   分类于 Java , 源码   |   ❤

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

并发计数的问题

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

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

结果如下:

阅读全文 »

LeetCode 718. Maximum Length of Repeated Subarray

发表于 2017-10-31   |   分类于 LeetCode , Java   |   ❤

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

题目要求

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

题意解析

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

阅读全文 »

LeetCode 673. Number of Longest Increasing Subsequence

发表于 2017-10-17   |   分类于 LeetCode , Java   |   ❤

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

题目要求

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.

题意解析

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

阅读全文 »
12…37
Jerky Lu

Jerky Lu

戒急用忍

364 日志
45 分类
75 标签
GitHub Weibo
友情链接
  • 李琼写文章的地方
  • 落影流年
  • Koihik's Blog
© 2020 Jerky Lu
京ICP备15007413号-1
主题 - NexT.Mist