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-- | longest_absolute_file_path.c | 69 | ||||
-rw-r--r-- | longest_absolute_file_path.py | 41 |
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")) |