aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--find_max_len_valid_subseq1.c53
-rw-r--r--find_max_len_valid_subseq1.py28
-rw-r--r--longest_absolute_file_path.c69
-rw-r--r--longest_absolute_file_path.py41
-rw-r--r--valid_word.c38
-rw-r--r--valid_word.py40
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"))