花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

By zxi on June 23, 2018

Problem

There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it’s horizontal, y-coordinates don’t matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 10⁴ balloons.

An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with x_start and x_endbursts by an arrow shot at x if x_start ≤ x ≤ x_end. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.

Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]

Output:
2

Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

Solution: Sweep Line

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 82 ms

class Solution {

public:

int findMinArrowShots(vector<pair<int, int>>& points) {

if (points.empty()) return 0;

sort(points.begin(), points.end(),

[&](const pair<int,int>& a, const pair<int,int>& b){

return a.second < b.second;

});

int right = points.front().second;

int ans = 1;

for (const auto& point : points) {

if (point.first > right) {

right = point.second;

++ans;

}

return ans;

}

};

Problem

Let’s call an array A a mountain if the following properties hold:

A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

Input: [0,2,1,0]
Output: 1

Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.

Solution1: Liner Scan

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

for (int i = 1; i < A.size(); ++i)

if (A[i] < A[i - 1]) return i - 1;

}

};

C++/STL

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

return max_element(begin(A), end(A)) - begin(A);

}

};

Solution 2: Binary Search

Find the smallest l such that A[l] > A[l + 1].

Time complexity: O(logn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

int l = 0;

int r = A.size();

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

};

Java

// Author: Huahua, 3 ms

class Solution {

public int peakIndexInMountainArray(int[] A) {

int l = 0;

int r = A.length;

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

Python3

# Author: Huahua, 40 ms

class Solution:

def peakIndexInMountainArray(self, A):

l, r = 0, len(A)

while l < r:

m = l + (r - l) // 2

if A[m] > A[m + 1]:

r = m

else:

l = m + 1

return l

花花酱 LeetCode 848. Shifting Letters

By zxi on June 11, 2018

Problem

We have a string S of lowercase letters, and an integer array shifts.

Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').

For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.

Now for each shifts[i] = x, we want to shift the first i+1 letters of S, x times.

Return the final string after all such shifts to S are applied.

Example 1:

Input: S = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 
We start with "abc".
After shifting the first 1 letters of S by 3, we have "dbc".
After shifting the first 2 letters of S by 5, we have "igc".
After shifting the first 3 letters of S by 9, we have "rpl", the answer.

Note:

1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 54 ms

class Solution {

public:

string shiftingLetters(string S, vector<int>& shifts) {

int c = 0;

for (int i = shifts.size() - 1; i >= 0; --i) {

c += (shifts[i] % 26);

S[i] = (S[i] - 'a' + c) % 26 + 'a';

}

return S;

}

};

花花酱 LeetCode 849. Maximize Distance to Closest Person

By zxi on June 11, 2018

Problem

In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty.

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.

Return that maximum distance to closest person.

Example 1:

Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

Input: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:

1 <= seats.length <= 20000
seats contains only 0s or 1s, at least one 0, and at least one 1.

Solution

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int maxDistToClosest(vector<int>& seats) {

int n = seats.size();

int prev = -1;

int ans = 0;

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

if (i == n) ans = max(ans, n - prev - 1);

else if (seats[i]) {

if (prev == -1) ans = i;

else ans = max(ans, (i - prev) / 2);

prev = i;

}

return ans;

}

};

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

By zxi on June 3, 2018

Problem

题目大意：求顶点覆盖的最短路径。

https://leetcode.com/problems/shortest-path-visiting-all-nodes/description/

An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph.

graph.length = N, and j != i is in the list graph[i] exactly once, if and only if nodes i and j are connected.

Return the length of the shortest path that visits every node. You may start and stop at any node, you may revisit nodes multiple times, and you may reuse edges.

Example 1:

Input: [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: One possible path is [1,0,2,0,3]

Example 2:

Input: [[1],[0,2,4],[1,3,4],[2],[1,2]]
Output: 4
Explanation: One possible path is [0,1,4,2,3]

Solution: BFS

Time complexity: O(n*2^n)

Space complexity: O(n*2^n)

C++

// Author: Huahua

// Running time: 34 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int kAns = (1 << (graph.size())) - 1;

queue<pair<int, int>> q;

unordered_set<int> visited; // (cur_node << 16) | state

for (int i = 0; i < graph.size(); ++i)

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int n = p.first;

int state = p.second;

if (state == kAns) return steps;

int key = (n << 16) | state;

if (visited.count(key)) continue;

visited.insert(key);

for (int next : graph[n])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

C++ / vector

// Author: Huahua

// Running time: 10 ms

class Solution {

public:

int shortestPathLength(vector<vector<int>>& graph) {

const int n = graph.size();

const int kAns = (1 << n) - 1;

queue<pair<int, int>> q;

vector<vector<int>> visited(n, vector<int>(1 << n));

for (int i = 0; i < n; ++i)

q.push({i, 1 << i});

int steps = 0;

while (!q.empty()) {

int s = q.size();

while (s--) {

auto p = q.front();

q.pop();

int node = p.first;

int state = p.second;

if (state == kAns) return steps;

if (visited[node][state]) continue;

visited[node][state] = 1;

for (int next : graph[node])

q.push({next, state | (1 << next)});

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

Problem

Solution: Sweep Line

Related Problems

花花酱 LeetCode 852. Peak Index in a Mountain Array

Problem

Solution1: Liner Scan

C++

C++/STL

Solution 2: Binary Search

C++

Java

Python3

花花酱 LeetCode 848. Shifting Letters

Problem

Solution

花花酱 LeetCode 849. Maximize Distance to Closest Person

Problem

Solution

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

Problem

Solution: BFS

Related Problems

Huahua's Tech Road

花花酱 LeetCode 452. Minimum Number of Arrows to Burst Balloons

Problem

Solution: Sweep Line

Related Problems

花花酱 LeetCode 852. Peak Index in a Mountain Array

Problem

Solution1: Liner Scan

C++

C++/STL

Solution 2: Binary Search

C++

Java

Python3

花花酱 LeetCode 848. Shifting Letters

Problem

Solution

花花酱 LeetCode 849. Maximize Distance to Closest Person

Problem

Solution

花花酱 LeetCode 847. Shortest Path Visiting All Nodes

Problem

Solution: BFS

Related Problems