April 13, 2025
最直接的方法就是扫描三遍，<, = , > pivot。
时间复杂度：O(n)
空间复杂度：O(1) // no extra space used except for output
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: vector<int> pivotArray(vector<int>& nums, int pivot) { vector<int> ans; for (int x: nums) if (x < pivot) ans.push_back(x); for (int x : nums) if (x == pivot) ans.push_back(x); for (int x : nums) if (x > pivot) ans.push_back(x); return ans; } }; |
You are given a string s containing lowercase letters and an integer k. You need to :
s to other lowercase English letters.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.
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)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// 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]; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// 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]; } }; |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// 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) |
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:
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 <= 1003 <= logs[i].length <= 100logs[i] is guaranteed to have an identifier, and a word after the identifier.Time complexity: O(n + aloga)
Space complexity: O(n)
|
1 2 3 4 5 6 7 8 9 10 11 |
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; } }; |
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) 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:
Time complexity: O(nlogn)
Space complexity: O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// 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; } }; |
Time complexity: O(n + max(nums) – min(nums))
Space complexity: O(max(nums) – min(nums))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// 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; } }; |