Algorithm revision

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:

1
2
3
4
5
Input:
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

1
2
3
4
Input:
flowers: [1,2,3]
k: 1
Output: -1

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int kEmptySlots(int[] flowers, int k) {
TreeSet<Integer> ts = new TreeSet<Integer>();
for(int i = 0 ; i < flowers.length; i++){
ts.add(flowers[i]);
Integer a = ts.lower(flowers[i]);
Integer b = ts.higher(flowers[i]);
if((a != null && flowers[i]-a-1 ==k) || (b != null && b-flowers[i]-1 == k)){
return i+1;//Attention: There is no zero day
}
}
return -1;
}
}

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int lengthOfLongestSubstringKDistinct(String s, int k) {
int[] hash = new int[256];
int num = 0,left=0,ans =0;
for(int i = 0; i < s.length(); i++){
if(hash[s.charAt(i)]++ == 0){
num += 1;
}
if(num > k){
while(--hash[s.charAt(left++)] > 0);
num -= 1;
}
ans = Math.max(ans, i-left+1);
}
return ans;
}
}

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:

1
2
3
4
5
6
7
8
9
10
11
Input:
rows = 2, cols = 8, sentence = ["hello", "world"]
Output:
1
Explanation:
hello---
world---
The character '-' signifies an empty space on the screen.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]
Output:
2
Explanation:
a-bcd-
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.

Example 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]
Output:
1
Explanation:
I-had
apple
pie-I
had--
The character '-' signifies an empty space on the screen.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public int wordsTyping(String[] sentence, int rows, int cols) {
String wholeSen = "";
for(String s : sentence){
wholeSen = wholeSen + s +" ";
}
int length = wholeSen.length(), start = 0;
for(int i = 0; i < rows; i++){
start += cols;
if(wholeSen.charAt(start%length) == ' '){
start += 1;
}
else{
while(start > 0 && wholeSen.charAt((start-1)%length) != ' '){
start -= 1;
}
}
}
System.out.println(start);
return start/length;
}
}

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:

1
2
v1 = [1, 2]
v2 = [3, 4, 5, 6]

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:

1
2
3
[1,2,3]
[4,5,6,7]
[8,9]

It should return

1
[1,4,8,2,5,9,3,6,7]

This is the follow up solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ZigzagIterator {
LinkedList<Iterator<Integer>> list;
public ZigzagIterator(List<List<Integer>> input) {
list = new LinkedList<Iterator<Integer>>();
for(List<Integer> ls : input) {
if(!ls.isEmpty()) {
list.add(ls.iterator());
}
}
}
public int next() {
Iterator<Integer> poll = list.remove();
int result = (Integer)poll.next();
if(poll.hasNext()) list.add(poll);
return result;
}
public boolean hasNext() {
return !list.isEmpty();
}
}

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.

1
2
3
4
b a l l
a r e a
l e a d
l a d y

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input:
["area","lead","wall","lady","ball"]
Output:
[
[ "wall",
"area",
"lead",
"lady"
],
[ "ball",
"area",
"lead",
"lady"
]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input:
["abat","baba","atan","atal"]
Output:
[
[ "baba",
"abat",
"baba",
"atan"
],
[ "baba",
"abat",
"baba",
"atal"
]
]
Explanation:
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

Solution:

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
class TrieNode {
List<String> startWith;
TrieNode[] children;
TrieNode() {
startWith = new ArrayList<>();
children = new TrieNode[26];
}
}
class Trie{
TrieNode root;
Trie(String[] words) {
root = new TrieNode();
for (String w : words) {
TrieNode cur = root;
for (char ch : w.toCharArray()) {
int idx = ch - 'a';
if (cur.children[idx] == null)
cur.children[idx] = new TrieNode();
cur.children[idx].startWith.add(w);
cur = cur.children[idx];
}
}
}
List<String> findByPrefix(String prefix){
List<String> ans = new ArrayList<String>();
TrieNode curr = root;
for(char ch:prefix.toCharArray()){
int idx = ch-'a';
if(curr.children[idx] == null){
return ans;
}
curr = curr.children[idx];
}
ans.addAll(curr.startWith);
return ans;
}
}
public List<List<String>> wordSquares(String[] words) {
List<List<String>> ans = new ArrayList<>();
if(words.length == 0){
return ans;
}
Trie root = new Trie(words);
int len = words[0].length();
List<String> ansBuilder = new ArrayList<String>();
for(String w: words){
ansBuilder.add(w);
search(len, root, ansBuilder,ans);
ansBuilder.remove(ansBuilder.size()-1);
}
return ans;
}
public void search(int length, Trie root, List<String> ansBuilder, List<List<String>> ans){
if(length == ansBuilder.size()){
ans.add(new ArrayList<String>(ansBuilder));
return ;
}
int idx = ansBuilder.size();
StringBuilder prefix = new StringBuilder();
for(String a : ansBuilder){
prefix.append(a.charAt(idx));
}
List<String> startWith = root.findByPrefix(prefix.toString());
for(String s:startWith){
ansBuilder.add(s);
search(length, root,ansBuilder, ans);
ansBuilder.remove(ansBuilder.size()-1);
}
}
}

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:

1
2
3
4
5
6
7
For the given grid
0 E 0 0
E 0 W E
0 E 0 0
return 3. (Placing a bomb at (1,1) kills 3 enemies)

Solution:

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
32
33
34
35
class Solution {
public int maxKilledEnemies(char[][] grid) {
int m = grid.length;
if(m == 0){
return 0;
}
int n = grid[0].length, row = 0;
int[] col = new int[n];
int ans = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(i == 0 || grid[i-1][j] == 'W'){
col[j] = 0;
for(int k = i; k < m && grid[k][j] != 'W'; k++){
if(grid[k][j] == 'E'){
col[j] += 1;
}
}
}
if(j == 0||grid[i][j-1] == 'W'){
row = 0;
for(int k = j; k < n && grid[i][k] != 'W'; k++){
if(grid[i][k] == 'E'){
row += 1;
}
}
}
if(grid[i][j] == '0'){
ans = Math.max(ans,row+col[j]);
}
}
}
return ans;
}
}

Wiggle Sort(280)

Given an unsorted array nums, reorder it in-place such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

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

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public void wiggleSort(int[] nums) {
boolean less = true;
for(int i = 0; i < nums.length-1;i++){
if(less){
if(nums[i] > nums[i+1]){
swap(nums, i, i+1);
}
}
else{
if(nums[i] < nums[i+1]){
swap(nums, i, i+1);
}
}
less = !less;
}
}
public void swap(int[] nums, int i, int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}

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:

1
2
3
4
5
6
7
8
9
10
Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation:
Ans = 6 + 3 + 3 = 12.
One of the best strategies is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day.
(Although you start at city 0, we could also fly to and start at other cities since it is Monday.)
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.

Example 2:

1
2
3
4
5
6
7
8
Input:flights = [[0,0,0],[0,0,0],[0,0,0]], days = [[1,1,1],[7,7,7],[7,7,7]]
Output: 3
Explanation:
Ans = 1 + 1 + 1 = 3.
Since there is no flights enable you to move to another city, you have to stay at city 0 for the whole 3 weeks.
For each week, you only have one day to play and six days to work.
So the maximum number of vacation days is 3.

Example 3:

1
2
3
4
5
6
7
8
9
Input:flights = [[0,1,1],[1,0,1],[1,1,0]], days = [[7,0,0],[0,7,0],[0,0,7]]
Output: 21
Explanation:
Ans = 7 + 7 + 7 = 21
One of the best strategies is:
1st week : stay at city 0, and play 7 days.
2nd week : fly from city 0 to city 1 on Monday, and play 7 days.
3rd week : fly from city 1 to city 2 on Monday, and play 7 days.

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:

    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
    class Solution {
    public int dfs(int[][] flights, int[][] days, int city, int week, int[][] dp){
    if(week == days[0].length){
    return 0;
    }
    if(dp[city][week] != -1){
    return dp[city][week];
    }
    int max = 0;
    for(int i = 0; i < flights.length;i++){
    if(flights[city][i] == 1 || i == city){
    max = Math.max(max, dfs(flights, days, i, week+1,dp)+days[i][week]);
    }
    }
    dp[city][week] = max;
    return max;
    }
    public int maxVacationDays(int[][] flights, int[][] days) {
    int[][] dp = new int[flights.length][days[0].length];
    for(int[] i : dp){
    Arrays.fill(i, -1);
    }
    return dfs(flights,days,0,0,dp);
    }
    }

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
HitCounter counter = new HitCounter();
// hit at timestamp 1.
counter.hit(1);
// hit at timestamp 2.
counter.hit(2);
// hit at timestamp 3.
counter.hit(3);
// get hits at timestamp 4, should return 3.
counter.getHits(4);
// hit at timestamp 300.
counter.hit(300);
// get hits at timestamp 300, should return 4.
counter.getHits(300);
// get hits at timestamp 301, should return 3.
counter.getHits(301);

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

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
32
33
34
35
36
37
38
39
40
41
class HitCounter {
int[] time;
int[] click;
/** Initialize your data structure here. */
public HitCounter() {
time = new int[300];
click = new int[300];
}
/** Record a hit.
@param timestamp - The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
int index = timestamp%300;
if(time[index] == timestamp){
click[index] += 1;
}
else{
time[index] = timestamp;
click[index] = 1;
}
}
/** Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
int ans = 0;
for(int i = 0; i < 300; i++){
if(timestamp - time[i] < 300){
ans += click[i];
}
}
return ans;
}
}
/**
* Your HitCounter object will be instantiated and called as such:
* HitCounter obj = new HitCounter();
* obj.hit(timestamp);
* int param_2 = obj.getHits(timestamp);
*/

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.

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
32
33
34
35
class Solution {
public boolean backTrack(String pattern, int i, String str, int j, HashMap<Character, String> hm, HashSet<String> hs){
if(pattern.length() == i && str.length() == j){
return true;
}
if(pattern.length() == i || str.length() == j){
return false;
}
char c = pattern.charAt(i);
if(hm.containsKey(c)){
String s = hm.get(c);
if(!str.startsWith(s,j)){
return false;
}
return backTrack(pattern,i+1,str,j+s.length(),hm,hs);
}
for(int k = j; k < str.length();k++){
String sub = str.substring(j,k+1);
if(hs.contains(sub)){
continue;
}
hm.put(c,sub);
hs.add(sub);
if(backTrack(pattern,i+1,str,k+1,hm,hs)){
return true;
}
hm.remove(c,sub);
hs.remove(sub);
}
return false;
}
public boolean wordPatternMatch(String pattern, String str) {
return backTrack(pattern,0,str,0,new HashMap<Character, String>(), new HashSet<String>());
}
}

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:

1
MyCalendar cal = new MyCalendar();
1
MyCalendar.book(start, end)

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
Explanation:
The first two events can be booked. The third event can be double booked.
The fourth event (5, 15) can't be booked, because it would result in a triple booking.
The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.
The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;
the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

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[0]) < Math.min(end,t[1]). Be sure about this idea, you can solve this problem more easily.

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
32
33
34
35
36
class MyCalendarTwo {
List<int[]> books;
private static class MyCalendar{
List<int[]> books = new ArrayList<int[]>();
public boolean book(int start,int end){
for(int[] b:books){
if(Math.max(start,b[0]) < Math.min(end,b[1]))return false;
}
books.add(new int[]{start,end});
return true;
}
}
public MyCalendarTwo() {
books = new ArrayList<int[]>();
}
public boolean book(int start, int end) {
MyCalendar overlap = new MyCalendar();
for(int[] b:books){
if(Math.max(start,b[0])<Math.min(end,b[1])){
if(!overlap.book(Math.max(start,b[0]),Math.min(end,b[1]))){
return false;
}
}
}
books.add(new int[]{start,end});
return true;
}
}
/**
* Your MyCalendarTwo object will be instantiated and called as such:
* MyCalendarTwo obj = new MyCalendarTwo();
* boolean param_1 = obj.book(start,end);
*/

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).

1
2
3
0 0 0
0 0 0
0 0 0

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

1
2
3
1 0 0
0 0 0 Number of islands = 1
0 0 0

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

1
2
3
1 1 0
0 0 0 Number of islands = 1
0 0 0

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

1
2
3
1 1 0
0 0 1 Number of islands = 2
0 0 0

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

1
2
3
1 1 0
0 0 1 Number of islands = 3
0 1 0

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?

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
32
33
34
35
36
37
38
39
40
class Solution {
int[][] dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> ans = new ArrayList<Integer>();
if(m <=0 || n <= 0){
return ans;
}
int[] roots = new int[m*n];
Arrays.fill(roots,-1);
int count = 0;
for(int[] p : positions){
int root = n*p[0]+p[1];
roots[root] = root;
count += 1;
for(int[] dir:dirs){
int x = p[0]+dir[0];
int y = p[1]+dir[1];
int nb = x*n+y;
if(x < 0 || x>=m||y<0||y>=n||roots[nb] == -1){
continue;
}
int rootnb = findIsland(roots, nb);
if(rootnb != root){
roots[root] = rootnb;
root = rootnb;
count -= 1;
}
}
ans.add(count);
}
return ans;
}
public int findIsland(int[] roots, int id){
while(roots[id] != id){
roots[id] = roots[roots[id]];
id = roots[id];
}
return id;
}
}

Comments: