Posts tagged as “partition”

花花酱 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 937. Reorder Log Files

By zxi on November 10, 2018

Problem

https://leetcode.com/problems/reorder-log-files/description/

You have an array of logs. Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier. Then, either:

Each word after the identifier will consist only of lowercase letters, or;
Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs. It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log. The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties. The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Note:

0 <= logs.length <= 100
3 <= logs[i].length <= 100
logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution: Partition + Sort

partition the array such that all digit logs are after all letter logs
sort the letter logs part based on the log content

Time complexity: O(n + aloga)

Space complexity: O(n)

C++

class Solution {

public:

vector<string> reorderLogFiles(vector<string>& logs) {

auto alpha_end = std::stable_partition(begin(logs), end(logs),

[](const string& log){ return isalpha(log.back()); });

std::sort(begin(logs), alpha_end, [](const string& a, const string& b){

return a.substr(a.find(' ')) < b.substr(b.find(' '));

});

return logs;

}

};

花花酱 LeetCode 561. Array Partition I

By zxi on August 16, 2018

Problem

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a₁, b₁), (a₂, b₂), …, (a_n, b_n) which makes sum of min(a_i, b_i) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].

Solution 1: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

std::sort(nums.begin(), nums.end());

int ans = 0;

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

ans += nums[i];

return ans;

}

};

Solution 2: HashTable

Time complexity: O(n + max(nums) – min(nums))

Space complexity: O(max(nums) – min(nums))

// Author: Huahua

// Running time: 39 ms

class Solution {

public:

int arrayPairSum(vector<int>& nums) {

const int max_val = *max_element(begin(nums), end(nums));

const int min_val = *min_element(begin(nums), end(nums));

const int offset = -min_val;

vector<int> c(max_val - min_val + 1);

for (int num : nums)

++c[num + offset];

int ans = 0;

int index = 0;

int n = min_val;

while (n <= max_val) {

if (c[n + offset] == 0) {

++n;

continue;

}

ans += (++index & 1) ? n : 0;

--c[n + offset];

}

return ans;

}

};

花花酱 LeetCode 886. Possible Bipartition

By zxi on August 12, 2018

Problem

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Solution: Graph Coloring

Color a node with one color, and color all it’s disliked nodes with another color, if can not finish return false.

Time complexity: O(V+E)

Space complexity: O(V+E)

C++ / DFS

// Author: Huahua

// Running time: 96 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

g_ = vector<vector<int>>(N);

for (const auto& d : dislikes) {

g_[d[0] - 1].push_back(d[1] - 1);

g_[d[1] - 1].push_back(d[0] - 1);

}

colors_ = vector<int>(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors_[i] == 0 && !dfs(i, 1)) return false;

return true;

}

private:

vector<vector<int>> g_;

vector<int> colors_;

bool dfs(int cur, int color) {

colors_[cur] = color;

for (int nxt : g_[cur]) {

if (colors_[nxt] == color) return false;

if (colors_[nxt] == 0 && !dfs(nxt, -color)) return false;

}

return true;

}

};

C++ / BFS

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

vector<vector<int>> g(N);

for (const auto& d : dislikes) {

g[d[0] - 1].push_back(d[1] - 1);

g[d[1] - 1].push_back(d[0] - 1);

}

queue<int> q;

vector<int> colors(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors[i] != 0) continue;

q.push(i);

colors[i] = 1;

while (!q.empty()) {

int cur = q.front(); q.pop();

for (int nxt : g[cur]) {

if (colors[nxt] == colors[cur]) return false;

if (colors[nxt] != 0) continue;

colors[nxt] = -colors[cur];

q.push(nxt);

}

return true;

}

};

Posts tagged as “partition”

花花酱 LeetCode 1278. Palindrome Partitioning III

Solution: DP

C++

C++/DP+DP

Python3

花花酱 LeetCode 86. Partition List

Solution: Two dummy heads

C++

花花酱 LeetCode 937. Reorder Log Files

Problem

Solution: Partition + Sort

C++

花花酱 LeetCode 561. Array Partition I

Problem

Solution 1: Sorting

Solution 2: HashTable

花花酱 LeetCode 886. Possible Bipartition

Problem

Solution: Graph Coloring

C++ / DFS

C++ / BFS

Related Problem