Write a program that outputs the string representation of numbers from 1 to n.

But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”.

* Method 1:

```Java

class Solution {

public List<String> fizzBuzz(int n) {

List<String> result = new ArrayList<>();

for(int i = 1; i <= n; i++){

if(i % 15 == 0){

result.add("FizzBuzz");

}else if(i % 3 == 0){

result.add("Fizz");

}else if(i % 5 == 0){

result.add("Buzz");

}else{result.add("" + i);}

}

return result;

}

}

```

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Note:

* The length of the array is in range [1, 20,000].

* The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

* Method 1: Prefix sum O(n^2)

```Java

class Solution {

public int subarraySum(int[] nums, int k) {

if(nums == null || nums.length == 0) return 0;

int[] sum = new int[nums.length];

sum[0] = nums[0];

for(int i = 1; i < nums.length; i++){

sum[i] = sum[i - 1] + nums[i];

}

int res = 0;

for(int i = 0; i < nums.length; i++){

if(sum[i] == k) res++;

for(int j = 0; j < i; j++){

int temp = sum[i] - sum[j];

if(temp == k) res++;

}

}

return res;

}

}

```

* Method 2: HashMap + prefix sum

1. record the appearance frequency of the prefix sum.

2. record all of the sum.

3. for each sum, check how many times (sum - k) exists. | sum - k | k | => total is sum.

```Java

class Solution {

public int subarraySum(int[] nums, int k) {

if(nums == null || nums.length == 0) return 0;

int sum = 0, res = 0;

Map<Integer, Integer> map = new HashMap<>(); //key is prefix sum, value is frequency

map.put(0, 1);

for(int i = 0; i < nums.length; i++){

sum += nums[i];

Integer freq = map.get(sum - k);

if(freq != null) res += freq;

map.put(sum, map.getOrDefault(sum, 0) + 1);

}

return res;

}

}

```

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Note:

* The number of tasks is in the range [1, 10000].

* The integer n is in the range [0, 100].

* Method 1: Greedy

```Java

class Solution {

public int leastInterval(char[] tasks, int n) {

int[] freq = new int[26];

for(char c : tasks){

freq[c - 'A']++;

}

Arrays.sort(freq);

int i = 25;

while(i >= 0 && freq[i] == freq[25]){i--;}

return Math.max((n + 1) * (freq[25] - 1) + (25 - i), tasks.length);

}

}

```

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn't such day, output -1.

Note:

* The given array will be in the range [1, 20000].

* Method 1: TreeSet

```Java

class Solution {

public int kEmptySlots(int[] flowers, int k) {

if(flowers == null || flowers.length == 0) return -1;

TreeSet<Integer> set = new TreeSet<>();

for(int i = 0; i < flowers.length; i++){

Integer higher = set.higher(flowers[i]);

if(higher != null && higher - flowers[i] == k + 1) return i + 1;

Integer lower = set.lower(flowers[i]);

if(lower != null && flowers[i] - lower == k + 1) return i + 1;

set.add(flowers[i]);

}

return -1;

}

}

```

You are given an integer array A. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, ...) jumps in the series are called odd numbered jumps, and the (2nd, 4th, 6th, ...) jumps in the series are called even numbered jumps.

You may from index i jump forward to index j (with i < j) in the following way:

1. During odd numbered jumps (ie. jumps 1, 3, 5, ...), you jump to the index j such that A[i] <= A[j] and A[j] is the smallest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.

2. During even numbered jumps (ie. jumps 2, 4, 6, ...), you jump to the index j such that A[i] >= A[j] and A[j] is the largest possible value. If there are multiple such indexes j, you can only jump to the smallest such index j.

3. (It may be the case that for some index i, there are no legal jumps.)

A starting index is good if, starting from that index, you can reach the end of the array (index A.length - 1) by jumping some number of times (possibly 0 or more than once.)

Return the number of good starting indexes.

Note:

* 1 <= A.length <= 20000

* 0 <= A[i] < 100000

* Method 1: TreeSet

```Java

class Solution {

public int kEmptySlots(int[] flowers, int k) {

if(flowers == null || flowers.length == 0) return -1;

TreeSet<Integer> set = new TreeSet<>();

for(int i = 0; i < flowers.length; i++){

Integer higher = set.higher(flowers[i]);

if(higher != null && higher - flowers[i] == k + 1) return i + 1;

Integer lower = set.lower(flowers[i]);

if(lower != null && flowers[i] - lower == k + 1) return i + 1;

set.add(flowers[i]);

}

return -1;

}

}

```