LeetCode[218]: The Skyline Problem

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

BuildingsSkyline Contour

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

  • The number of buildings in any input list is guaranteed to be in the range [0, 10000].
  • The input list is already sorted in ascending order by the left x position Li.
  • The output list must be sorted by the x position.
  • There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

思路:

观察发现,skyline的points的横坐标一定是某个building的左边界或者右边界。算法如下:
从左到右扫描,当我们遇到一个楼的左边界时,把它push到一个heap中。如果这个楼的高度比heap中最高的楼还高,那么这个point一定属于所求的set。当我们遇到一个building的右边界时,我们需要将其从heap中pop掉,如果heap中max height有变化,则push到结果中。

 

Hackerrank: Count Luck

Problem:

Ron and Hermione are deep in the Forbidden Forest collecting potion ingredients, and they’ve managed to lose their way. The path out of the forest is blocked, so they must make their way to a portkey that will transport them back to Hogwarts.

Consider the forest as an grid. Each cell is either empty (represented by .) or blocked by a tree (represented by ). Ron and Hermione can move (together inside a single cell) LEFT, RIGHT, UP, and DOWNthrough empty cells, but they cannot travel through a tree cell. Their starting cell is marked with the character , and the cell with the portkey is marked with a . The upper-left corner is indexed as .

In example above, Ron and Hermione are located at index and the portkey is at . Each cell is indexed according to Matrix Conventions

Hermione decides it’s time to find the portkey and leave. Each time they are able to move in more than one direction, she waves her wand and it points to the correct direction. Ron is betting that she will have to wave her wand exactly times. Can you determine if Ron’s guesses are correct?

Note: It is guaranteed that there is only one path from the starting location to the portkey.

Input Format

The first line contains an integer, , the number of test cases.

Each test case is described as follows:
The first line contains space-separated integers, and , respectively, denoting the forest matrix.
The subsequent lines each contain a string of length describing a row of the forest matrix.
The last line contains an integer, , denoting Ron’s guess as to how many times Hermione will wave her wand.

Constraints

  • There will be exactly one and one in the forest.
  • Exactly one path exists between and .

Output Format

On a new line for each test case, print if Ron impresses Hermione by guessing correctly; otherwise, print .

Sample Input

Sample Output

Explanation

For each test case , denotes the number of times Hermione waves her wand.

Case 0: Hermione waves her wand at , giving us . Because , we print on a new line.
Case 1: Hermione waves her wand at , , and , giving us . Because , we print on a new line.
Case 2: Hermione waves her wand at , , and , giving us . Because and , and we print on a new line.

思路:
这个题是个深搜,只不过需要在途中数valid的neighbor的个数。需要注意的细节是:1. 起始位置没有设为’X’而是’M’,在开始搜索的时候也没有改变其值,因此在isValid函数中需要加一个判断是否是’M’,或者就直接在开始的时候将其改为’X’;2. 只有在valid的path中的岔路口才计入最后的count中。

Code:

 

Hackerrank: Bricks Game

You and your friend decide to play a game using a stack consisting of N bricks. In this game, you can alternatively remove 1, 2 or 3 bricks from the top, and the numbers etched on the removed bricks are added to your score. You have to play so that you obtain the maximum possible score. It is given that your friend will also play optimally and you make the first move.

Input Format

First line will contain an integer T i.e. number of test cases. There will be two lines corresponding to each test case: first line will contain a number N i.e. number of elements in the stack and next line will contain N numbers i.e. numbers etched on bricks from top to bottom.

Constraints

1 ≤ T ≤ 5
1 ≤ N ≤ 105
0 ≤ each number on brick ≤ 109

Output Format

For each test case, print a single line containing your maximum score.

Sample Input

Sample Output

Explanation

In first test case, you will pick 999,1,1. If you play in any other way, you will not get a score of 1001.
In second case, best option will be to pick up the first brick (with 0 score) at first. Then your friend will choose the next three blocks, and you will get the last brick.

 

思路:
这个题关键就是观察出 f(i) 状态时player1能得到的maxScore 就是 sum[i] – max(f(i+1), f(i+2), f(i+3))

Code:

 

LeetCode[412]: Fizz Buzz

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

Example:
n = 15,

Return:
[
“1”,
“2”,
“Fizz”,
“4”,
“Buzz”,
“Fizz”,
“7”,
“8”,
“Fizz”,
“Buzz”,
“11”,
“Fizz”,
“13”,
“14”,
“FizzBuzz”
]

题很简单,直接上代码:

 

Count Inversions in an array

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If array is already sorted then inversion count is 0. If array is sorted in reverse order that inversion count is the maximum.
Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:
The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

 

LeetCode[401]: Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:
Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

我直接暴力深搜了:

 

LeetCode[421]: Maximum XOR of Two Numbers in an Array

Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].

Could you do this in O(n) runtime?

Input: [3, 10, 5, 25, 2, 8] Output: 28

我的思路是这样的:
如果第一位为1的subset和第一位为0的subset都不为空,那么result的第一位为1;如果“第一位为1的subset中,第二位为1的subset”和
“第一位为0的subset中,第二位为0的subset”都不为空,或者“” “”则result第二位为1
可以用trie,也可以直接递归。
有点像validate symetric tree
代码还没改对呢。。。

 

LeetCode[352]: Data Stream as Disjoint Intervals

Given a data stream input of non-negative integers a1, a2, …, an, …, summarize the numbers seen so far as a list of disjoint intervals.

For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, …, then the summary will be:
[1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7]

Follow up:
What if there are lots of merges and the number of disjoint intervals are small compared to the data stream’s size?

我就是直接用vector存了当前的intervals,把[INT_MIN, INT_MIN]和[INT_MAX, INT_MAX] push到vector里面了,这样就不需要考虑vector是空的时候要怎么样,如果要在第一个interval前面插入interval要怎么样了。

代码(118 ms, 93.85%):

 

LeetCode[416]: Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.

Example 1:
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

分析:如果所有值加起来为奇数则直接返回false。最一开始我是直接上DFS,结果超时了,时间复杂度应该是T(n) = n * T(n-1) => O(n!) ,代码长这样:

再一看的话,其实是一个背包问题,于是DP了:

 

Find subarray with given sum

Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

分析:
读完题,会想要问:是不是找到一个subarray就可以,还是需要找到所有的subarray?另外,像这个题中提到了continuous subarray, 有的时候题中没有说是不是连续的就得问面试官了。

由于我们知道整个array都是非负数,那么在subarray里每添加一个元素都只可能使当前sum增加。因此,我们可以keep一个window,当当前的sum小于target的时候,window向后扩张一位;当sum大于target时,window的start position向后推一位;等于target时返回window的起始和终点即可。
这个算法的时间复杂度是O(n),因为对于array中每一个元素,there are at most 2 operations performed。

Follow up 1: What if the array contains negative numbers?

我们可以用一个hash table来存cumulative sum,意思是table[i]存的是从index 0加到index i的和。因为 sum(i, j) = sum(0, j) – sum(0, i-1),所以在累加sum时,在hash table里查找一下 sum(0, j) – target,如果存在,那么说明此时 i就是所求。这个算法时间复杂度是O(n),空间是O(n)。

Follow up 2: If there is no subarray found, return the subarray whose sum is the closest to the target sum.

 

Follow up 3: What if the subarray do not need to be continuous?

这样的话,那其实可以看做是一个搜索路径的问题,DFS就可以了。复杂度O(n^2).