EventBus最直接的好处就是解耦,但因为内部实现是反射,小项目无所谓,大项目的话性能不是很好。
本次要介绍的是AndroidEventBus,而不是greenrobot的EventBus,其使用注解,使用方便,但效率比不上EventBus。订阅函数支持tag(类似广播接收器的Action)使得事件的投递更加准确,能适应更多使用场景。其github项目地址为:androideventbus下面介绍其用法。
select * from utils
EventBus最直接的好处就是解耦,但因为内部实现是反射,小项目无所谓,大项目的话性能不是很好。
本次要介绍的是AndroidEventBus,而不是greenrobot的EventBus,其使用注解,使用方便,但效率比不上EventBus。订阅函数支持tag(类似广播接收器的Action)使得事件的投递更加准确,能适应更多使用场景。其github项目地址为:androideventbus下面介绍其用法。
题目描述
This English game is a simple English words connection game.
The rules are as follows: there are N English words in a dictionary, and every word has its own weight v. There is a weight if the corresponding word is used. Now there is a target string X. You have to pick some words in the dictionary, and then connect them to form X. At the same time, the sum weight of the words you picked must be the biggest.
题目描述
Little A is one member of ACM team. He had just won the gold in World Final. To celebrate, he decided to invite all to have one meal. As bowl, knife and other tableware is not enough in the kitchen, Little A goes to take backup tableware in warehouse. There are many boxes in warehouse, one box contains only one thing, and each box is marked by the name of things inside it. For example, if “basketball” is written on the box, which means the box contains only basketball. With these marks, Little A wants to find out the tableware easily. So, the problem for you is to help him, find out all the tableware from all boxes in the warehouse.
(The tableware only contains: bowl, knife, fork and chopsticks.)
Total Accepted: 91860
Total Submissions: 392114
Difficulty: Easy
Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.
For example, "A man, a plan, a canal: Panama"
is a palindrome.
"race a car"
is not a palindrome.
Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.
For the purpose of this problem, we define empty string as valid palindrome.
Total Accepted: 54299
Total Submissions: 230350
Difficulty: Easy
Description:
Count the number of prime numbers less than a non-negative number, _n_.
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
Hint:
Let’s start with a isPrime function. To determine if a number is prime, we need to check if it is not divisible by any number less than _n_. The runtime complexity of isPrime function would be O(_n_) and hence counting the total prime numbers up to _n_ would be O(_n_2). Could we do better?
As we know the number must not be divisible by any number > _n_ / 2, we can immediately cut the total iterations half by dividing only up to _n_ / 2. Could we still do better?
Let’s write down all of 12’s factors:
1 | 2 × 6 = 12 |
As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √_n_ because, if _n_ is divisible by some number _p_, then _n_ = _p_ × _q_ and since _p_ ≤ _q_, we could derive that _p_ ≤ √_n_. Our total runtime has now improved to O(_n_1.5), which is slightly better. Is there a faster approach?
1 | public int countPrimes(int n) { |
The Sieve of Eratosthenes is one of the most efficient ways to find all prime numbers up to _n_. But don’t let that name scare you, I promise that the concept is surprisingly simple.Sieve of Eratosthenes: algorithm steps for primes below 121. “Sieve of Eratosthenes Animation” by SKopp is licensed under CC BY 2.0. We start off with a table of _n_ numbers. Let’s look at the first number, 2. We know all multiples of 2 must not be primes, so we mark them off as non-primes. Then we look at the next number, 3. Similarly, all multiples of 3 such as 3 × 2 = 6, 3 × 3 = 9, … must not be primes, so we mark them off as well. Now we look at the next number, 4, which was already marked off. What does this tell you? Should you mark off all multiples of 4 as well?
4 is not a prime because it is divisible by 2, which means all multiples of 4 must also be divisible by 2 and were already marked off. So we can skip 4 immediately and go to the next number, 5. Now, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, … can be marked off. There is a slight optimization here, we do not need to start from 5 × 2 = 10. Where should we start marking off?
In fact, we can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is _p_, we can always mark off multiples of _p_ starting at _p_2, then in increments of _p_: _p_2 + _p_, _p_2 + 2_p_, … Now what should be the terminating loop condition?
It is easy to say that the terminating loop condition is _p_ < _n_, which is certainly correct but not efficient. Do you still remember Hint #3?
Yes, the terminating loop condition can be _p_ < √_n_, as all non-primes ≥ √_n_ must have already been marked off. When the loop terminates, all the numbers in the table that are non-marked are prime. The Sieve of Eratosthenes uses an extra O(_n_) memory and its runtime complexity is O(_n_ log log _n_). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.
public int countPrimes(int n) { boolean[] isPrime = new boolean[n]; for (int i = 2; i < n; i++) { isPrime[i] = true; } // Loop's ending condition is i * i < n instead of i < sqrt(n) // to avoid repeatedly calling an expensive function sqrt(). for (int i = 2; i * i < n; i++) { if (!isPrime[i]) continue; for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) count++; } return count; }
Total Accepted: 125501
Total Submissions: 532378
Difficulty: Easy
Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
click to show spoilers.
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Total Accepted: 20875
Total Submissions: 85065
Difficulty: Easy
Given an integer array nums, find the sum of the elements between indices _i_ and _j_ (_i_ ≤ _j_), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
Total Accepted: 75848
Total Submissions: 283546
Difficulty: Easy
Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100"
.
Total Accepted: 39482
Total Submissions: 145556
Difficulty: Easy
Given a singly linked list, determine if it is a palindrome.
Follow up:
Could you do it in O(n) time and O(1) space?
Total Accepted: 36923
Total Submissions: 135278
Difficulty: Easy
Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
1 / \ 2 3 \ 5
All root-to-leaf paths are:
["1->2->5", "1->3"]