diff options
-rw-r--r-- | find_max_len_valid_subseq1.c | 53 | ||||
-rw-r--r-- | find_max_len_valid_subseq1.py | 28 | ||||
-rw-r--r-- | longest_absolute_file_path.c | 69 | ||||
-rw-r--r-- | longest_absolute_file_path.py | 41 | ||||
-rw-r--r-- | valid_word.c | 38 | ||||
-rw-r--r-- | valid_word.py | 40 |
6 files changed, 269 insertions, 0 deletions
diff --git a/find_max_len_valid_subseq1.c b/find_max_len_valid_subseq1.c new file mode 100644 index 0000000..ecea5fc --- /dev/null +++ b/find_max_len_valid_subseq1.c @@ -0,0 +1,53 @@ +// 3201. Find the Maximum Length of Valid Subsequence I +#include "leetcode.h" + +/* + * you are given an integer array 'nums'. a subsequence 'sub' of 'nums' with + * length 'x' is called valid if it satisfies '(sub[0] + sub[1]) % 2 == (sub[1] + * + sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2'. return the legnth of + * the longest valid subsequences of 'nums'. a subsequence is an array that can + * be derived from another array by deleting some or no elements without + * changing the order of the remaining elements. + */ + +int maximumLength(int *nums, int numsSize) { + int odd_start = 0, even_start = 0; + for (int i = 0; i < numsSize; i++) { + if (!(nums[odd_start] % 2) && (nums[i] % 2 == 1)) + odd_start = i; + if ((nums[even_start] % 2 == 1) && !(nums[i] % 2)) + even_start = i; + } + int odd_cnt1 = 1, odd_i1 = odd_start, odd_cnt2 = 1, odd_i2 = even_start; + int even_cnt1 = 1, even_i1 = odd_start, even_cnt2 = 1, even_i2 = even_start; + for (int i = odd_start + 1; i < numsSize; i++) { + if ((nums[odd_i1] + nums[i]) % 2 == 1) { + odd_i1 = i; + odd_cnt1++; + } + if (!((nums[even_i1] + nums[i]) % 2)) { + even_i1 = i; + even_cnt1++; + } + } + for (int i = even_start + 1; i < numsSize; i++) { + if ((nums[odd_i2] + nums[i]) % 2 == 1) { + odd_i2 = i; + odd_cnt2++; + } + if (!((nums[even_i2] + nums[i]) % 2)) { + even_i2 = i; + even_cnt2++; + } + } + int odd_max = fmax(odd_cnt1, odd_cnt2); + int even_max = fmaxl(even_cnt1, even_cnt2); + return fmax(odd_max, even_max); +} + +int main() { + int n1[] = {1, 2, 3, 4}, n2[] = {1, 2, 1, 1, 2, 1, 2}, n3[] = {1, 3}; + printf("%d\n", maximumLength(n1, ARRAY_SIZE(n1))); // expect: 4 + printf("%d\n", maximumLength(n2, ARRAY_SIZE(n2))); // expect: 6 + printf("%d\n", maximumLength(n3, ARRAY_SIZE(n3))); // expect: 2 +} diff --git a/find_max_len_valid_subseq1.py b/find_max_len_valid_subseq1.py new file mode 100644 index 0000000..f940e7f --- /dev/null +++ b/find_max_len_valid_subseq1.py @@ -0,0 +1,28 @@ +# 3201. Find the Maximum Length of Valid Subsequence I +from itertools import groupby + +""" +you are given an integer array 'nums'. a subsequence 'sub' of 'nums' with +length 'x' is called valid if it satisfies '(sub[0] + sub[1]) % 2 == (sub[1] ++ sub[2]) % 2 == ... == (sub[x - 2] + sub[x - 1]) % 2'. return the legnth of +the longest valid subsequences of 'nums'. a subsequence is an array that can +be derived from another array by deleting some or no elements without +changing the order of the remaining elements. +""" + + +class Solution(object): + def maximumLength(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + nums = [i % 2 for i in nums] + return max(nums.count(0), nums.count(1), len(list(groupby(nums)))) + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumLength(nums=[1, 2, 3, 4])) + print(obj.maximumLength(nums=[1, 2, 1, 1, 2, 1, 2])) + print(obj.maximumLength(nums=[1, 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")) diff --git a/valid_word.c b/valid_word.c new file mode 100644 index 0000000..965e5b1 --- /dev/null +++ b/valid_word.c @@ -0,0 +1,38 @@ +// 3136. Valid Word +#include "leetcode.h" + +/* + * a word is considered valid if it contains a minimum of three characters, it + * contains only digits (0-9), and english letters (uppercase and lowercase), it + * includes at least one vowel, and it includes one consonant. you are given a + * string 'word'. return true if 'word' is valid, otherwise return false. + */ + +bool isvowel(char c) { + return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || + c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U'); +} + +bool isValid(char *word) { + bool vowel = false, consonant = false, invalid = false; + for (int i = 0; word[i]; i++) + if (isalnum(word[i])) { + if (isalpha(word[i])) { + if (isvowel(word[i])) + vowel = true; + else + consonant = true; + } + } else { + invalid = true; + break; + } + return (strlen(word) > 2 && vowel && consonant && !invalid); +} + +int main() { + char *w1 = "234Adas", *w2 = "b3", *w3 = "a3$e"; + printf("%d\n", isValid(w1)); // expect: 1 + printf("%d\n", isValid(w2)); // expect: 0 + printf("%d\n", isValid(w3)); // expect: 0 +} diff --git a/valid_word.py b/valid_word.py new file mode 100644 index 0000000..8728305 --- /dev/null +++ b/valid_word.py @@ -0,0 +1,40 @@ +# 3136. Valid Word + +""" +a word is considered valid if it contains a minimum of three characters, it +contains only digits (0-9), and english letters (uppercase and lowercase), it +includes at least one vowel, and it includes one consonant. you are given a +string 'word'. return true if 'word' is valid, otherwise return false. +""" + + +class Solution(object): + def isValid(self, word): + """ + :type word: str + :rtype: bool + """ + n, m = len(word), 0 + if n < 3: + return False + vowels = ( + 1 + | (1 << (ord("e") - 97)) + | (1 << (ord("o") - 97)) + | (1 << (ord("i") - 97)) + | (1 << (ord("u") - 97)) + ) + for i in word: + if not (i.isalpha() or i.isdigit()): + return False + if i.isalpha(): + j = ord(i) - 97 if ord(i) >= 97 else ord(i) - 65 + m |= 1 << (vowels >> j) & 1 + return m == 3 + + +if __name__ == "__main__": + obj = Solution() + print(obj.isValid(word="234Adas")) + print(obj.isValid(word="b3")) + print(obj.isValid(word="a3$e")) |