花花酱 LeetCode 507. Perfect Number

By zxi on March 22, 2018

Problem

题目大意：判断一个数的因数和是不是等于它本身。

https://leetcode.com/problems/perfect-number/description/

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)

Solution: Brute Force

Try allnumbers from 1 to n – 1.

Time complexity: O(n) TLE for prime numbers

Space complexity: O(1)

Solution: Math

Try all numbers from 2 to sqrt(n).

If number i is a divisor of n then n/i is another one.

Be careful about the case when i == n/i, only one should be added to the sum.

Time complexity: O(sqrt(n))

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

bool checkPerfectNumber(int num) {

if (num <= 1) return false;

int sum = 1;

for (int i = 2; i <= sqrt(num); ++i)

if (num % i == 0) sum += i + ((i == num / i) ? 0 : num / i);

return sum == num;

}

};

花花酱 LeetCode 560. Subarray Sum Equals K

By zxi on March 22, 2018

Problem

题目大意：给你一个数组，问有多少子数组的和为k。

https://leetcode.com/problems/subarray-sum-equals-k/description/

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

Input:nums = [1,1,1], k = 2
Output: 2

Note:

The length of the array is in range [1, 20,000].
The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Solution -1: Brute Force

For every pair of i,j, check sum(nums[i:j]) in O(j-i) = O(n)

Time complexity: O(n^3) TLE

Space complexity: O(1)

Solution 0: Brute Force + Prefix sun

Precompute the prefix sum and check sum of nums[i:j] in O(1)

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 490 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

const int n = nums.size();

vector<int> sums(n + 1, 0);

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

sums[i] = sums[i - 1] + nums[i - 1];

int ans = 0;

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

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

if (sums[j + 1] - sums[i] == k) ++ans;

return ans;

}

};

Solution 1: Running Prefix sum

Keep tracking the prefix sums and their counts.

s -> count: how many arrays nums[0:j] (j < i) that has sum of s

cur_sum = sum(nums[0:i])

check how many arrays nums[0:j] (j < i) that has sum (cur_sum – k)

then there are the same number of arrays nums[j+1: i] that have sum k.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int subarraySum(vector<int>& nums, int k) {

if (nums.empty()) return 0;

unordered_map<int, int> counts{{0,1}};

int cur_sum = 0;

int ans = 0;

for (const int num : nums) {

cur_sum += num;

ans += counts[cur_sum - k];

++counts[cur_sum];

}

return ans;

}

};

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

};

Huahua's Tech Road

花花酱 LeetCode 507. Perfect Number

Problem

Solution: Brute Force

Solution: Math

花花酱 LeetCode 560. Subarray Sum Equals K

Problem

Solution -1: Brute Force

Solution 0: Brute Force + Prefix sun

Solution 1: Running Prefix sum

花花酱 LeetCode 554. Brick Wall

Problem

Solution: HashTable

花花酱 LeetCode 553. Optimal Division

Problem

Example:

Note:

Solution: Math

花花酱 LeetCode 552. Student Attendance Record II

Problem

Solution