Huahua’s Tech Road

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

}

};

花花酱 LeetCode 1278. Palindrome Partitioning III

By zxi on December 2, 2019

You are given a string s containing lowercase letters and an integer k. You need to :

First, change some characters of s to other lowercase English letters.
Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

Example 1:

Input: s = "abc", k = 2
Output: 1
Explanation: You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input: s = "aabbc", k = 3
Output: 0
Explanation: You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input: s = "leetcode", k = 8
Output: 0

Constraints:

1 <= k <= s.length <= 100.
s only contains lowercase English letters.

Solution: DP

dp[i][k] := min changes to make s[0~i] into k palindromes
dp[i][k] = min(dp[j][k – 1] + cost(j + 1, i)) 0 <= j < i

ans = dp[n-1][K]

Time complexity: O(n^2 * K) = O(n^3)
Space complexity: O(n*n + n*K) = O(n^2)

C++

// Author: Huahua, 8 ms, 9.1 MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

auto minChange = [&](int i, int j) {

int c = 0;

while (i < j)

if (s[i++] != s[j--]) ++c;

return c;

};

vector<vector<int>> cost(n, vector<int>(n));

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

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

cost[i][j] = minChange(i, j);

// dp[i][j] := min changes to make s[0~i] into k palindromes

vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2));

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

dp[i][1] = cost[0][i];

for (int k = 1; k <= K; ++k)

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

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

}

return dp[n - 1][K];

}

};

C++/DP+DP

// Author: Huahua, 4 ms, 9.1MB

class Solution {

public:

int palindromePartition(string s, int K) {

const int n = s.length();

vector<vector<int>> cost(n, vector<int>(n));

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

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

cost[i][j] = (s[i] != s[j]) + cost[i + 1][j - 1];

vector<vector<int>> dp(n, vector<int>(K + 1, INT_MAX / 2));

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

dp[i][1] = cost[0][i];

for (int k = 2; k <= K; ++k)

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

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

}

return dp[n - 1][K];

}

};

Python3

// Author: Huahua

import functools

class Solution:

def palindromePartition(self, s: str, K: int) -> int:

@functools.lru_cache(None)

def cost(i: int, j: int) -> int:

if i >= j: return 0

return cost(i + 1, j - 1) + (1 if s[i] != s[j] else 0)

@functools.lru_cache(None)

def dp(i: int, k: int) -> int:

if k == 1: return cost(0, i)

if k == i + 1: return 0

if k > i + 1: return 1**9

return min([dp(j, k - 1) + cost(j + 1, i) for j in range(i)])

return dp(len(s) - 1, K)

花花酱 LeetCode 1277. Count Square Submatrices with All Ones

By zxi on December 1, 2019

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

Example 1:

Input: matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
Output: 15
Explanation: 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is  1 square of side 3.
Total number of squares = 10 + 4 + 1 = 15.

Example 2:

Input: matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
Output: 7
Explanation: 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7.

Constraints:

1 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

Solution: DP

dp[i][j] := edge of largest square with bottom right corner at (i, j)
dp[i][j] = min(dp[i – 1][j], dp[i – 1][j – 1], dp[i][j – 1]) if m[i][j] == 1 else 0
ans = sum(dp)

Time complexity: O(n*m)
Space complexity: O(n*m)

C++

// Author: Huahua

class Solution {

public:

int countSquares(vector<vector<int>>& matrix) {

const int n = matrix.size();

const int m = matrix[0].size();

// dp[i][j] := edge of largest square with right bottom corner at (i, j)

vector<vector<int>> dp(n, vector<int>(m));

int ans = 0;

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

for (int j = 0; j < m; ++j) {

dp[i][j] = matrix[i][j];

if (i && j && dp[i][j])

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

ans += dp[i][j];

}

return ans;

}

};

Huahua's Tech Road

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

花花酱 LeetCode 1278. Palindrome Partitioning III

Solution: DP

C++

C++/DP+DP

Python3

花花酱 LeetCode 1277. Count Square Submatrices with All Ones

Solution: DP

C++