花花酱 LeetCode 554. Brick Wall

By zxi on March 22, 2018

Problem

https://leetcode.com/problems/brick-wall/description/

题目大意：从小到下切一刀，最少会切到多少块砖。

There is a brick wall in front of you. The wall is rectangular and has several rows of bricks. The bricks have the same height but different width. You want to draw a vertical line from the top to the bottom and cross the least bricks.

The brick wall is represented by a list of rows. Each row is a list of integers representing the width of each brick in this row from left to right.

If your line go through the edge of a brick, then the brick is not considered as crossed. You need to find out how to draw the line to cross the least bricks and return the number of crossed bricks.

You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.

Example:

Input: 
[[1,2,2,1],
 [3,1,2],
 [1,3,2],
 [2,4],
 [3,1,2],
 [1,3,1,1]]
Output: 2
Explanation:

Note:

The width sum of bricks in different rows are the same and won’t exceed INT_MAX.
The number of bricks in each row is in range [1,10,000]. The height of wall is in range [1,10,000]. Total number of bricks of the wall won’t exceed 20,000.

Solution: HashTable

Count boundaries, cut at the location with most common boundaries.

Time complexity: O(|bricks|)

Space complexity: O(|bricks|)

C++

// Author: Huahua

// Running time: 42 ms

class Solution {

public:

int leastBricks(vector<vector<int>>& wall) {

unordered_map<int, int> count;

int max_count = 0;

for (const auto& bricks : wall) {

int s = 0;

for (int i = 0; i < bricks.size() - 1; ++i) {

s += bricks[i];

max_count = max(max_count, ++count[s]);

}

return wall.size() - max_count;

}

};

花花酱 LeetCode 553. Optimal Division

By zxi on March 22, 2018

Problem

https://leetcode.com/problems/optimal-division/description/

题目大意：给你一个连除的表达式，让你加一些括号使得表达式的值最大。

Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.

However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.

Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant, 
since they don't influence the operation priority. So you should return "1000/(100/10/2)". 

Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

Note:

The length of the input array is [1, 10].
Elements in the given array will be in range [2, 1000].
There is only one optimal division for each test case.

Solution: Math

For: X1/X2/X3/…/Xn, X1/(X2/X3/…/Xn) > X1/X2/(X3/…/Xn) > X1/X2/X3/(…/Xn)

X1/(X2/X3/…/Xn) is the max value.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

string optimalDivision(vector<int>& nums) {

string ans = to_string(nums[0]);

if (nums.size() == 1) return ans;

else if (nums.size() == 2) return ans + "/" + to_string(nums[1]);

ans += "/(" + to_string(nums[1]);

for (int i = 2; i < nums.size(); ++i)

ans += "/" + to_string(nums[i]);

ans += ")";

return ans;

}

};

花花酱 LeetCode 552. Student Attendance Record II

By zxi on March 22, 2018

Problem

Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 10⁹ + 7.

A student attendance record is a string that only contains the following three characters:

‘A’ : Absent.
‘L’ : Late.
‘P’ : Present.

A record is regarded as rewardable if it doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late).

Example 1:

Input: n = 2
Output: 8 
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times.

Note: The value of n won’t exceed 100,000.

Solution

C++

DFS w/ memorization (stack overflow)

class Solution {

public:

int checkRecord(int n) {

m_ = vector<vector<int>>(n + 1, vector<int>(6, 0));

if (n >= 100000) return 0;

return dfs(n, 1, 2);

}

private:

vector<vector<int>> m_;

// number of solutions of using at most A As and L Ls

long dfs(int n, int A, int L) {

if (n == 0) return 1;

int key = A * 3 + L;

if (m_[n][key]) return m_[n][key];

long ans = 0;

ans += dfs(n - 1, A, 2); // 'P', reset number of Ls

if (A > 0)

ans += dfs(n - 1, A - 1, 2); // 'A', reset number of Ls

if (L > 0)

ans += dfs(n - 1, A, L - 1); // 'L'

return m_[n][key] = (ans % 1000000007);

}

};

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 129 ms

class Solution {

public:

int checkRecord(int n) {

constexpr int kMod = 1000000007;

vector<long> dp(6, 1);

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

vector<long> tmp(6);

for (int A = 0; A <= 1; ++A)

for (int L = 0; L <= 2; ++L) {

const int key = getKey(A, L);

tmp[key] += dp[getKey(A, 2)];

if (A > 0) tmp[key] += dp[getKey(A - 1, 2)];

if (L > 0) tmp[key] += dp[getKey(A, L - 1)];

tmp[key] %= kMod;

}

dp.swap(tmp);

}

return dp[5];

}

private:

inline int getKey(int A, int L) { return A * 3 + L; }

};

花花酱 LeetCode 541. Reverse String II

By zxi on March 21, 2018

Problem

题目大意：把字符串分成块，每块长度2k，单独反转每一块的前k的字符。

https://leetcode.com/problems/reverse-string-ii/description/

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]

Solution

C++

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

string reverseStr(string s, int k) {

const int n = s.length();

for (int i = 0; i <= n / k; i += 2)

std::reverse(s.begin() + i * k, s.begin() + min(n, (i + 1) * k));

return s;

}

};

Problem

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

The number of time points in the given list is at least 2 and won’t exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.

Solution

Time complexity: O(nlog1440)

Space complexity: O(n)

C++

// Author: huahua

// Running time: 16 ms

class Solution {

public:

int findMinDifference(vector<string>& timePoints) {

constexpr int kMins = 24 * 60;

set<int> seen;

for (const string& time : timePoints) {

int m = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));

if (!seen.insert(m).second) return 0;

}

int ans = (*seen.begin() - *seen.rbegin() + kMins) % kMins;

const int* l = nullptr;

for (const int& t : seen) {

if (l) ans = min(ans, t - *l);

l = &t;

}

return ans;

}

};

花花酱 LeetCode 554. Brick Wall

Problem

Solution: HashTable

花花酱 LeetCode 553. Optimal Division

Problem

Example:

Note:

Solution: Math

花花酱 LeetCode 552. Student Attendance Record II

Problem

Solution

花花酱 LeetCode 541. Reverse String II

Problem

Solution

Related Problems

花花酱 LeetCode 539. Minimum Time Difference

Problem

Solution

Huahua's Tech Road

花花酱 LeetCode 554. Brick Wall

Problem

Solution: HashTable

花花酱 LeetCode 553. Optimal Division

Problem

Example:

Note:

Solution: Math

花花酱 LeetCode 552. Student Attendance Record II

Problem

Solution

花花酱 LeetCode 541. Reverse String II

Problem

Solution

Related Problems

花花酱 LeetCode 539. Minimum Time Difference

Problem

Solution