2017-11-11

# K Empty Slots(683)

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.

Example 1:

Example 2:

Solution:

# Longest Substring with At Most K Distinct Characters(340)

Given a string, find the length of the longest substring T that contains at most k distinct characters.

For example, Given s = `“eceba”` and k = 2,

T is “ece” which its length is 3.

This problem can be solved by sliding window.

Solution:

# Sentence Screen Fitting(418)

Given a `rows x cols` screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

1. A word cannot be split into two lines.
2. The order of words in the sentence must remain unchanged.
3. Two consecutive words in a line must be separated by a single space.
4. Total words in the sentence won’t exceed 100.
5. Length of each word is greater than 0 and won’t exceed 10.
6. 1 ≤ rows, cols ≤ 20,000.

Example 1:

Example 2:

Example 3:

Solution:

# Zigzag Iterator(281, follow up: what if are given k 1d vectors)

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

By calling next repeatedly until hasNext returns `false`, the order of elements returned by next should be: `[1, 3, 2, 4, 5, 6]`.

Follow up: What if you are given `k` 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question - Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for `k > 2` cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:

It should return

This is the follow up solution:

# Word Squares(425) (A good example of Trie)

Given a set of words (without duplicates), find all word squares you can build from them.

A sequence of words forms a valid word square if the kth row and column read the exact same string, where 0 ≤ k < max(numRows, numColumns).

For example, the word sequence `["ball","area","lead","lady"]` forms a word square because each word reads the same both horizontally and vertically.

Note:

1. There are at least 1 and at most 1000 words.
2. All words will have the exact same length.
3. Word length is at least 1 and at most 5.
4. Each word contains only lowercase English alphabet `a-z`.

Example 1:

Example 2:

Solution:

# Bomb Enemy (361, Dynamic Programming)

Given a 2D grid, each cell is either a wall `'W'`, an enemy `'E'` or empty `'0'` (the number zero), return the maximum enemies you can kill using one bomb.
The bomb kills all the enemies in the same row and column from the planted point until it hits the wall since the wall is too strong to be destroyed.
Note that you can only put the bomb at an empty cell.

Example:

Solution:

# Wiggle Sort(280)

Given an unsorted array `nums`, reorder it in-place such that `nums <= nums >= nums <= nums...`.

For example, given `nums = [3, 5, 2, 1, 6, 4]`, one possible answer is `[1, 6, 2, 5, 3, 4]`.

Solution:

# Maximum Vacation Days（568）

LeetCode wants to give one of its best employees the option to travel among N cities to collect algorithm problems. But all work and no play makes Jack a dull boy, you could take vacations in some particular cities and weeks. Your job is to schedule the traveling to maximize the number of vacation days you could take, but there are certain rules and restrictions you need to follow.

Rules and restrictions:

1. You can only travel among N cities, represented by indexes from 0 to N-1. Initially, you are in the city indexed 0 on Monday.
2. The cities are connected by flights. The flights are represented as a N*N matrix (not necessary symmetrical), called flightsrepresenting the airline status from the city i to the city j. If there is no flight from the city i to the city j, flights[i][j] = 0; Otherwise, flights[i][j] = 1. Also, flights[i][i] = 0 for all i.
3. You totally have K weeks (each week has 7 days) to travel. You can only take flights at most once per day and can only take flights on each week’s Monday morning. Since flight time is so short, we don’t consider the impact of flight time.
4. For each city, you can only have restricted vacation days in different weeks, given an N*K matrix called days representing this relationship. For the value of days[i][j], it represents the maximum days you could take vacation in the city i in the week j.

You’re given the flights matrix and days matrix, and you need to output the maximum vacation days you could take during K weeks.

Example 1:

Example 2:

Example 3:

Note:

1. N and K are positive integers, which are in the range of [1, 100].

2. In the matrix flights, all the values are integers in the range of [0, 1].

3. In the matrix days, all the values are integers in the range [0, 7].

4. You could stay at a city beyond the number of vacation days, but you should work on the extra days, which won’t be counted as vacation days.

5. If you fly from the city A to the city B and take the vacation on that day, the deduction towards vacation days will count towards the vacation days of city B in that week.

6. We don’t consider the impact of flight hours towards the calculation of vacation days.

Solution:

# Design Hit Counter(362)

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:

Follow up:
What if the number of hits per second could be very large? Does your design scale?

# Word Pattern II(291)

Given a `pattern` and a string `str`, find if `str` follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in `pattern` and a non-empty substring in `str`.

Examples:

1. pattern = `"abab"`, str = `"redblueredblue"` should return true.
2. pattern = `"aaaa"`, str = `"asdasdasdasd"` should return true.
3. pattern = `"aabb"`, str = `"xyzabcxzyabc"` should return false.

Notes:
You may assume both `pattern` and `str` contains only lowercase letters.

# My Calendar II(731)

Implement a `MyCalendarTwo` class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, `book(int start, int end)`. Formally, this represents a booking on the half open interval `[start, end)`, the range of real numbers `x` such that `start <= x < end`.

A triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method `MyCalendar.book`, return `true` if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return `false` and do not add the event to the calendar.

Your class will be called like this:

Example 1:

Note:

The number of calls to `MyCalendar.book` per test case will be at most `1000`.

In calls to `MyCalendar.book(start, end)`, `start` and `end` are integers in the range `[0, 10^9]`.

!!!Explanation: Overlap part is Math.max(start,t) < Math.min(end,t). Be sure about this idea, you can solve this problem more easily.

# Number of Islands II (305)

A 2d grid map of `m` rows and `n` columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given `m = 3, n = 3`, `positions = [[0,0], [0,1], [1,2], [2,1]]`.
Initially, the 2d grid `grid` is filled with water. (Assume 0 represents water and 1 represents land).

Operation #1: addLand(0, 0) turns the water at grid into a land.

Operation #2: addLand(0, 1) turns the water at grid into a land.

Operation #3: addLand(1, 2) turns the water at grid into a land.

Operation #4: addLand(2, 1) turns the water at grid into a land.

We return the result as an array: `[1, 1, 2, 3]`

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the `positions`?