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--longest_absolute_file_path.c69
-rw-r--r--longest_absolute_file_path.py41
4 files changed, 235 insertions, 0 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/longest_absolute_file_path.c b/longest_absolute_file_path.c
new file mode 100644
index 0000000..996dc9d
--- /dev/null
+++ b/longest_absolute_file_path.c
@@ -0,0 +1,69 @@
+// 388. Longest Absolute File Path
+#include "leetcode.h"
+
+/*
+ * suppose we have a file system that stores both files and directories. every
+ * file and directory has a unique absolute path in the file system which is the
+ * order of directories that must be opened to reach the file/directory it self,
+ * all concatenated by '/'s. each directory name consists of letters, digits,
+ * and/or spaces. each filename is of the form 'name.extension', where 'name'
+ * and 'extension' consist of letters, digits, and/or spaces. given a string
+ * 'input' representing the file system in the explained format, return the
+ * length of the longest absolute path to a file in the abstracted file system.
+ * if there ino file in the system, return 0
+ */
+
+int dir_level(char *d) {
+ int i = 0;
+ while (d[i] && d[i] == '\t')
+ i++;
+ return i;
+}
+
+int entry_len(char *d, bool *is_file) {
+ int i = 0;
+ while (d[i] && d[i] != '\n') {
+ if (d[i] == '.')
+ *is_file = true;
+ i++;
+ }
+ return i;
+}
+
+int find_path(char *input, int l, int *max, int clen) {
+ int n = 0, tclen, dl, dlen;
+ bool is_file;
+ while (input[n]) {
+ tclen = clen;
+ if (input[n] && input[n] == '\n')
+ ++n;
+ dl = dir_level(&input[n]);
+ if (dl != l)
+ break;
+ n += dl;
+ is_file = false;
+ dlen = entry_len(&input[n], &is_file);
+ tclen += dlen + (dl > 0 ? 1 : 0);
+ if (is_file && tclen > *max)
+ *max = tclen;
+ n += dlen;
+ n += find_path(&input[n], l + 1, max, tclen);
+ }
+ return n;
+}
+
+int lengthLongestPath(char *input) {
+ int max = 0;
+ find_path(&input[0], 0, &max, 0);
+ return max;
+}
+
+int main() {
+ char *i1 = "dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext";
+ char *i2 = "dir\n\tsubdir1\n\t\tfile1."
+ "ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext";
+ char *i3 = "a";
+ printf("%d\n", lengthLongestPath(i1)); // expect: 20
+ printf("%d\n", lengthLongestPath(i2)); // expect: 32
+ printf("%d\n", lengthLongestPath(i3)); // expect: 0
+}
diff --git a/longest_absolute_file_path.py b/longest_absolute_file_path.py
new file mode 100644
index 0000000..c0142bd
--- /dev/null
+++ b/longest_absolute_file_path.py
@@ -0,0 +1,41 @@
+# 388. Longest Absolute File Path
+
+"""
+suppose we have a file system that stores both files and directories. every
+file and directory has a unique absolute path in the file system which is the
+order of directories that must be opened to reach the file/directory it self,
+all concatenated by '/'s. each directory name consists of letters, digits,
+and/or spaces. each filename is of the form 'name.extension', where 'name'
+and 'extension' consist of letters, digits, and/or spaces. given a string
+'input' representing the file system in the explained format, return the
+length of the longest absolute path to a file in the abstracted file system.
+if there ino file in the system, return 0
+"""
+
+
+class Solution(object):
+ def lengthLongestPath(self, input):
+ """
+ :type input: str
+ :rtype: int
+ """
+ max_len, path_len = 0, {0: 0}
+ for i in input.splitlines():
+ name = i.lstrip("\t")
+ depth = len(i) - len(name)
+ if "." in name:
+ max_len = max(max_len, path_len[depth] + len(name))
+ else:
+ path_len[depth + 1] = path_len[depth] + len(name) + 1
+ return max_len
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.lengthLongestPath(input="dir\n\tsubdir1\n\tsubdir2\n\t\tfile.ext"))
+ print(
+ obj.lengthLongestPath(
+ input="dir\n\tsubdir1\n\t\tfile1.ext\n\t\tsubsubdir1\n\tsubdir2\n\t\tsubsubdir2\n\t\t\tfile2.ext"
+ )
+ )
+ print(obj.lengthLongestPath(input="a"))