aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_max_len_valid_subseq2.c68
-rw-r--r--find_max_len_valid_subseq2.py57
-rw-r--r--min_diff_sum_remove_elem.py51
-rw-r--r--remove_subfolder_filesystem.c55
-rw-r--r--remove_subfolder_filesystem.py18
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__":