花花酱 LeetCode 856. Score of Parentheses

By zxi on June 26, 2018

Problem

Given a balanced parentheses string S, compute the score of the string based on the following rule:

() has score 1
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: "()"
Output: 1

Example 2:

Input: "(())"
Output: 2

Example 3:

Input: "()()"
Output: 2

Example 4:

Input: "(()(()))"
Output: 6

Solution1: Recursion

Time complexity: O(n^2)

Space complexity: O(n)

// Author: Huahua

// Running time: 4ms

class Solution {

public:

int scoreOfParentheses(string S) {

return score(S, 0, S.length() - 1);

}

private:

int score(const string& S, int l, int r) {

if (r - l == 1) return 1; // "()"

int b = 0;

for (int i = l; i < r; ++i) {

if (S[i] == '(') ++b;

if (S[i] == ')') --b;

if (b == 0) // balanced

// score("(A)(B)") = score("(A)") + score("(B)")

return score(S, l, i) + score(S, i + 1, r);

}

// score("(A)") = 2 * score("A")

return 2 * score(S, l + 1, r - 1);

}

};

Solution2: Counting

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int scoreOfParentheses(string S) {

int ans = 0;

int d = -1;

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

d += S[i] == '(' ? 1 : -1;

if (S[i] == '(' && S[i + 1] == ')')

ans += 1 << d;

}

return ans;

}

};

花话酱 LeetCode 859. Buddy Strings

By zxi on June 26, 2018

Problem

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Example 1:

Input: A = "ab", B = "ba"
Output: true

Example 2:

Input: A = "ab", B = "ab"
Output: false

Example 3:

Input: A = "aa", B = "aa"
Output: true

Example 4:

Input: A = "aaaaaaabc", B = "aaaaaaacb"
Output: true

Example 5:

Input: A = "", B = "aa"
Output: false

Note:

0 <= A.length <= 20000
0 <= B.length <= 20000
A and B consist only of lowercase letters.

Solution: HashTable

Time complexity: O(n)

Space complexity: O(26)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

bool buddyStrings(string A, string B) {

if (A.length() != B.length()) return false;

vector<int> ca(26);

vector<int> cb(26);

int diff = 0;

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

if (A[i] != B[i] && diff++ > 2) return false;

++ca[A[i]-'a'];

++cb[B[i]-'a'];

}

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

if (diff == 0 && ca[i] > 1) return true;

if (ca[i] != cb[i]) return false;

}

return diff == 2;

}

};

花花酱 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 856. Score of Parentheses

Problem

Solution1: Recursion

Solution2: Counting

花话酱 LeetCode 859. Buddy Strings

Problem

Solution: HashTable

花花酱 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

Huahua's Tech Road

花花酱 LeetCode 856. Score of Parentheses

Problem

Solution1: Recursion

Solution2: Counting

花话酱 LeetCode 859. Buddy Strings

Problem

Solution: HashTable

花花酱 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