diff options
-rw-r--r-- | find_max_len_valid_subseq2.c | 68 | ||||
-rw-r--r-- | find_max_len_valid_subseq2.py | 57 | ||||
-rw-r--r-- | min_diff_sum_remove_elem.py | 51 | ||||
-rw-r--r-- | remove_subfolder_filesystem.c | 55 | ||||
-rw-r--r-- | remove_subfolder_filesystem.py | 18 |
5 files changed, 240 insertions, 9 deletions
diff --git a/find_max_len_valid_subseq2.c b/find_max_len_valid_subseq2.c new file mode 100644 index 0000000..3e60991 --- /dev/null +++ b/find_max_len_valid_subseq2.c @@ -0,0 +1,68 @@ +// 3202. Find the Maximum Length of Valid Subsequence II +#include "leetcode.h" + +/* + * you are given an integer array 'nums' and a positive integer 'k'. a + * subsequence 'sub' of 'nums' with length 'x' is called valid if it satisfies + * '(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x + * - 1]) % k'. return the length of the longest valid subsequence of 'nums' + */ + +int maximumLength(int *nums, int numsSize, int k) { + int *right = (int *)malloc(numsSize * sizeof(int)); + for (int i = 0; i < numsSize; ++i) + right[i] = nums[i] % k; + int **left = (int **)malloc(k * sizeof(int *)); + int *sizes = (int *)calloc(k, sizeof(int)); + for (int i = 0; i < k; ++i) + left[i] = (int *)malloc(numsSize * sizeof(int)); + for (int i = 0; i < numsSize; ++i) { + int rem = right[i]; + left[rem][sizes[rem]++] = i; + } + int max = 0; + for (int i = 0; i < k; ++i) + if (sizes[i] > max) + max = sizes[i]; + if (!k || k == 1) { + for (int i = 0; i < k; ++i) + free(left[i]); + free(left), free(right), free(sizes); + return max; + } + for (int x = 0; x < k; ++x) + for (int y = x + 1; y < k; ++y) { + int *a = left[x], la = sizes[x]; + int *b = left[y], lb = sizes[y]; + if (!la && !lb) + continue; + int i = 0, j = 0; + int sx = 0, sy = 0; + while (i < la || j < lb) { + if (j == lb || (i < la && a[i] < b[j])) { + int nx = sy > 0 ? sy + 1 : 1; + if (nx > sx) + sx = nx; + ++i; + } else { + int ny = sx > 0 ? sx + 1 : 1; + if (ny > sy) + sy = ny; + ++j; + } + } + int curr = sx > sy ? sx : sy; + if (curr > max) + max = curr; + } + for (int i = 0; i < k; ++i) + free(left[i]); + free(left), free(right), free(sizes); + return max; +} + +int main() { + int n1[] = {1, 2, 3, 4, 5}, n2[] = {1, 4, 2, 3, 1, 4}; + printf("%d\n", maximumLength(n1, ARRAY_SIZE(n1), 2)); // expect: 5 + printf("%d\n", maximumLength(n2, ARRAY_SIZE(n2), 3)); // expect: 4 +} diff --git a/find_max_len_valid_subseq2.py b/find_max_len_valid_subseq2.py new file mode 100644 index 0000000..6a1bfa4 --- /dev/null +++ b/find_max_len_valid_subseq2.py @@ -0,0 +1,57 @@ +# 3202. Find the Maximum Length of Valid Subsequence II + +""" +you are given an integer array 'nums' and a positive integer 'k'. a +subsequence 'sub' of 'nums' with length 'x' is called valid if it satisfies +'(sub[0] + sub[1]) % k == (sub[1] + sub[2]) % k == ... == (sub[x - 2] + sub[x +- 1]) % k'. return the length of the longest valid subsequence of 'nums' +""" + + +class Solution(object): + def maximumLength(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + left = [[] for _ in range(k)] + right = [i % k for i in nums] + for i, j in enumerate(right): + left[j].append(i) + m = max(len(i) for i in left) if k > 0 else 0 + if k == 0 or k == 1: + return m + for x in range(k): + for y in range(x + 1, k): + a, b = left[x], left[y] + la, lb = len(a), len(b) + if la == 0 and lb == 0: + continue + i, j = 0, 0 + sx, sy = 0, 0 + while i < la or j < lb: + if j == lb or (i < la and a[i] < b[j]): + nx = 1 + if sy > 0: + nx = sy + 1 + if nx > sx: + sx = nx + i += 1 + else: + ny = 1 + if sx > 0: + ny = sx + 1 + if ny > sy: + sy = ny + j += 1 + curr = max(sx, sy) + if curr > m: + m = curr + return m + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumLength(nums=[1, 2, 3, 4, 5], k=2)) + print(obj.maximumLength(nums=[1, 4, 2, 3, 1, 4], k=3)) diff --git a/min_diff_sum_remove_elem.py b/min_diff_sum_remove_elem.py new file mode 100644 index 0000000..40a6a18 --- /dev/null +++ b/min_diff_sum_remove_elem.py @@ -0,0 +1,51 @@ +# 2163. Minimum Difference in Sums After Removal of Elements +import heapq + +""" +you are given a 0-indexed integer array 'nums' consisting of '3 * n' +elements. you are allowed to remove any subsequence ofd elements of size +exactly 'n' from 'nums'. the remaining '2 * n' elements will be divided into +two equal parts: the first 'n' elements belonging to the first part and their +sum is 'sum_first', and the next 'n' elements belonging to the second part +and their sum is 'sum_second'. the difference in sums of the two parts is +denoted as 'sum_first - sum_second'. return the minimum different possible +between the sums of the two parts after the removal of 'n' elements. +""" + + +class Solution(object): + def minimumDifference(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n = len(nums) // 3 + diff = [0] * (n + 1) + heapq.heapify(pq_l := [-i for i in nums[:n]]) + heapq.heapify(pq_r := nums[2 * n :]) + total = sum(nums[:n]) + ans = total + for i in range(n, 2 * n + 1): + diff[i - n] = total + curr = nums[i] + if curr >= -pq_l[0]: + continue + total += curr + pq_l[0] + heapq.heapreplace(pq_l, -curr) + total = sum(nums[2 * n :]) + ans -= total + for i in range(2 * n - 1, n - 2, -1): + diff[i - n + 1] -= total + ans = min(ans, diff[i - n + 1]) + curr = nums[i] + if curr <= pq_r[0]: + continue + total += curr - pq_r[0] + heapq.heapreplace(pq_r, curr) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumDifference(nums=[3, 1, 2])) + print(obj.minimumDifference(nums=[7, 9, 5, 8, 1, 3])) diff --git a/remove_subfolder_filesystem.c b/remove_subfolder_filesystem.c new file mode 100644 index 0000000..c616906 --- /dev/null +++ b/remove_subfolder_filesystem.c @@ -0,0 +1,55 @@ +// 1233. Remove Sub-Folders from the Filesystem +#include "leetcode.h" + +/* + * given a list of folders 'folder', return the folders after removing all the + * sub-folders in those folders. you may return the answer in any order. if a + * 'folder[i]' is located within another 'folder[j]', it is called a sub-folder + * of it. a sub-folder of 'folder[j]' must start with 'folder[j]', followed by + * '/'. the format of a path is one ormore concatenated strings of the form: '/' + * followed by one or more lowercase english letters. + */ + +int cmp(const void *a, const void *b) { + return strcmp(*(char **)a, *(char **)b); +} + +char **removeSubfolders(char **folder, int folderSize, int *returnSize) { + qsort(folder, folderSize, sizeof(char *), cmp); + char **ans = (char **)malloc(folderSize * sizeof(char *)); + int curr = strlen(folder[0]); + ans[0] = folder[0]; + *returnSize = 1; + for (int i = 1; i < folderSize; i++) { + int new = strlen(folder[i]); + if (new <= curr || folder[i][curr] != '/' || + strncmp(ans[*returnSize - 1], folder[i], curr)) { + curr = new; + ans[*returnSize] = folder[i]; + (*returnSize)++; + } + } + return ans; +} + +int main() { + char *f1[] = {"/a", "/a/b", "/c/d", "/c/d/e", "/c/f"}; + char *f2[] = {"/a", "/a/b/c", "/a/b/d"}; + char *f3[] = {"/a/b/c", "/a/b/ca", "/a/b/d"}; + int rs1, rs2, rs3; + char **rsf1 = removeSubfolders(f1, ARRAY_SIZE(f1), &rs1); + char **rsf2 = removeSubfolders(f2, ARRAY_SIZE(f2), &rs2); + char **rsf3 = removeSubfolders(f3, ARRAY_SIZE(f3), &rs3); + for (int i = 0; i < rs1; i++) + printf("%s ", rsf1[i]); // expect: ["/a","/c/d","/c/f"] + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%s ", rsf2[i]); // expect: ["/a"] + printf("\n"); + for (int i = 0; i < rs3; i++) + printf("%s ", rsf3[i]); // expect: ["/a/b/c","/a/b/ca","/a/b/d"] + printf("\n"); + free(rsf1); + free(rsf2); + free(rsf3); +} diff --git a/remove_subfolder_filesystem.py b/remove_subfolder_filesystem.py index 484831f..8270975 100644 --- a/remove_subfolder_filesystem.py +++ b/remove_subfolder_filesystem.py @@ -16,15 +16,15 @@ class Solution(object): :type folder: List[str] :rtype: List[str] """ - folder.sort(key=lambda x: len(x)) - vis = set() - for i in folder: - for j in range(2, len(i)): - if i[j] == "/" and i[:j] in vis: - break - else: - vis.add(i) - return list(vis) + n = len(folder) + folder.sort() + ans = [] + ans.append(folder[0]) + for i in range(1, n): + last = ans[-1] + if not folder[i].startswith(last + "/"): + ans.append(folder[i]) + return ans if __name__ == "__main__": |