Huahua’s Tech Road

花花酱 LeetCode 1283. Find the Smallest Divisor Given a Threshold

By zxi on December 8, 2019

Given an array of integers nums and an integer threshold, we will choose a positive integer divisor and divide all the array by it and sum the result of the division. Find the smallest divisor such that the result mentioned above is less than or equal to threshold.

Each result of division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

It is guaranteed that there will be an answer.

Example 1:

Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1. 
If the divisor is 4 we can get a sum to 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).

Example 2:

Input: nums = [2,3,5,7,11], threshold = 11
Output: 3

Example 3:

Input: nums = [19], threshold = 5
Output: 4

Solution: Binary Search

Time complexity: O(nlogk)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int smallestDivisor(vector<int>& nums, int threshold) {

auto sums = [&](int d) {

int s = 0;

for (int n : nums)

s += (n + (d - 1)) / d;

return s;

};

int l = 1;

int r = 1e6;

while (l < r) {

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

if (sums(m) <= threshold)

r = m;

else

l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1281. Subtract the Product and Sum of Digits of an Integer

By zxi on December 8, 2019

Given an integer number n, return the difference between the product of its digits and the sum of its digits.

Example 1:

Input: n = 234

Output: 15

Explanation:

Product of digits = 2 * 3 * 4 = 24

Sum of digits = 2 + 3 + 4 = 9

Result = 24 - 9 = 15

Example 2:

Input: n = 4421

Output: 21

Explanation:

Product of digits = 4 * 4 * 2 * 1 = 32

Sum of digits = 4 + 4 + 2 + 1 = 11

Result = 32 - 11 = 21

Constraints:

1 <= n <= 10^5

Solution: Simulation

Time complexity: O(logn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int subtractProductAndSum(int n) {

int p = 1;

int s = 0;

while (n) {

const int d = n % 10;

p *= d;

s += d;

n /= 10;

}

return p - s;

}

};

花花酱 LeetCode 132. Palindrome Partitioning II

By zxi on December 7, 2019

Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example:

Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution: DP

dp[i] := min cuts of s[0~i]
dp[i] = min{dp[j] + 1} if s[j+1~i] is a palindrome.

Time complexity: O(n^2)
Space complexity: O(n^2)

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// valid[i][j] = 1 if s[i~j] is palindrome, otherwise 0

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

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

for (int l = 2; l <= n; ++l)

for (int i = 0, j = i + l - 1; j < n; ++i, ++j)

valid[i][j] = s[i] == s[j] && valid[i + 1][j - 1];

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

if (valid[0][i]) {

dp[i] = 0;

continue;

}

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

if (valid[j + 1][i])

dp[i] = min(dp[i], dp[j] + 1);

}

return dp[n - 1];

}

};

DP v2

C++

// Author: Huahua

class Solution {

public:

int minCut(string s) {

const int n = s.length();

// dp[i] = min cuts of s[0~i]

vector<int> dp(n, n);

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

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

for (int i = m, j = m + d; i >= 0 && j < n && s[i] == s[j]; --i, ++j)

dp[j] = min(dp[j], (i ? (dp[i - 1] + 1) : 0));

return dp[n - 1];

}

};

花花酱 LeetCode 405. Convert a Number to Hexadecimal

By zxi on December 7, 2019

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.
The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
The given number is guaranteed to fit within the range of a 32-bit signed integer.
You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:

Input:
26

Output:
“1a”
Example 2:

Input:
-1

Output:
“ffffffff”

Solution: Simulation

if input is negative, add 2^32 to it (e.g. set the highest bit to 1)
while num is non zero, mod it by 16 and prepend the remainder to ans string, then divide num by 16.

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

constexpr char kHex[] = "0123456789abcdef";

class Solution {

public:

string toHex(int num) {

if (num == 0) return "0";

long t = num < 0 ? (1LL << 32) + num : num;

string ans;

while (t) {

ans = kHex[t % 16] + ans;

t /= 16;

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 1283. Find the Smallest Divisor Given a Threshold

Solution: Binary Search

C++

花花酱 LeetCode 1282. Group the People Given the Group Size They Belong To

Solution: HashMap + Greedy

C++

花花酱 LeetCode 1281. Subtract the Product and Sum of Digits of an Integer

Solution: Simulation

C++

花花酱 LeetCode 132. Palindrome Partitioning II

Solution: DP

C++

C++

Related Problems

花花酱 LeetCode 405. Convert a Number to Hexadecimal

Solution: Simulation

C++