diff options
-rw-r--r-- | count_num_arr_k_match_elem.c | 48 | ||||
-rw-r--r-- | count_num_arr_k_match_elem.py | 28 | ||||
-rw-r--r-- | fizz_buzz_multithread.c | 145 | ||||
-rw-r--r-- | fizz_buzz_multithread.py | 94 | ||||
-rw-r--r-- | leetcode.h | 1 | ||||
-rw-r--r-- | max_diff_between_incr_elem.c | 25 | ||||
-rw-r--r-- | max_diff_between_incr_elem.py | 28 |
7 files changed, 369 insertions, 0 deletions
diff --git a/count_num_arr_k_match_elem.c b/count_num_arr_k_match_elem.c new file mode 100644 index 0000000..dd8838e --- /dev/null +++ b/count_num_arr_k_match_elem.c @@ -0,0 +1,48 @@ +// 3405. Count the Number of Arrays with K Matching Adjacent Elements +#include "leetcode.h" + +/* + * you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size + * 'n' is defined as follows: each element in 'arr' is in inclusive range '[1, + * m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition + * 'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed. + * since the answer may be very large, return it modulo 10^9+7. + */ + +const int mod = 1e9 + 7; + +long long mult(long long n, long long m) { return (n * m) % mod; } + +long long power(long long n, long long m) { + long long res = 1, base = n; + while (m > 0) { + if (m & 1) + res = mult(res, base); + base = mult(base, base); + m >>= 1; + } + return res; +} + +long long inv(long long n) { return power(n, mod - 2); } + +long long factorial(long long n) { + long long res = 1; + for (long long i = 2; i <= n; ++i) + res = mult(res, i); + return res; +} + +long long combine(long long n, long long m) { + return mult(factorial(n), inv(mult(factorial(m), factorial(n - m)))); +} + +int countGoodArrays(int n, int m, int k) { + return mult(mult(combine(n - 1, n - 1 - k), m), power(m - 1, n - 1 - k)); +} + +int main() { + printf("%d\n", countGoodArrays(3, 2, 1)); // expect: 4 + printf("%d\n", countGoodArrays(4, 2, 2)); // expect: 6 + printf("%d\n", countGoodArrays(5, 2, 0)); // expect: 2 +} diff --git a/count_num_arr_k_match_elem.py b/count_num_arr_k_match_elem.py new file mode 100644 index 0000000..a3bc73f --- /dev/null +++ b/count_num_arr_k_match_elem.py @@ -0,0 +1,28 @@ +# 3405. Count the Number of Arrays with K Matching Adjacent Elements +from math import comb + +""" +you are given three integers 'n', 'm', and 'k'. a good array 'arr' of size +'n' is defined as follows: each element in 'arr' is in inclusive range '[1, +m]', and exactly 'k' indices 'i' where '1 <= i < n' satisfy the condition +'arr[i - 1] == arr[i]'. return the number of good arrays that can be formed. +since the answer may be very large, return it modulo 10^9+7. +""" + + +class Solution(object): + def countGoodArrays(self, n, m, k): + """ + :type n: int + :type m: int + :type k: int + :rtype: int + """ + return m * pow(m - 1, n - k - 1, mod := 1**9 + 7) * comb(n - 1, k) % mod + + +if __name__ == "__main__": + obj = Solution() + print(obj.countGoodArrays(n=3, m=2, k=1)) + print(obj.countGoodArrays(n=4, m=2, k=2)) + print(obj.countGoodArrays(n=5, m=2, k=0)) diff --git a/fizz_buzz_multithread.c b/fizz_buzz_multithread.c new file mode 100644 index 0000000..67da100 --- /dev/null +++ b/fizz_buzz_multithread.c @@ -0,0 +1,145 @@ +// 1195. Fizz Buzz Multithreaded +#include "leetcode.h" + +/* + * you have the following functions: + * 'printFizz' prints the word "fizz" to the console + * 'printBuzz' prints the word "buzz" to the console + * 'printFizzBuzz' prints the word "fizzbuzz" to the console + * 'printNumber' that prints a given integer to the console + * you are given an instance of the class 'fizzbuzz' that has four functions + * 'fizz', 'buzz', 'fizzbuzz', and 'number'. the same instance of 'fizzbuzz' + * will be passed to four different threads. + * thread a calls 'fizz()' that should output the word "fizz" + * thread b calls 'buzz()' that should output the word "buzz" + * thread c calls 'fizzbuzz()' that should output the word "fizzbuzz" + * thread d calls 'number()' that should output the given integer + * modify the given class to output the series '[1, 2, "fizz", 4, "buzz", ...]' + * where the i'th toek of the series is. + */ + +typedef struct { + int n; + int curr; + int turn; +} FizzBuzz; + +pthread_mutex_t mutex; +pthread_cond_t cond; + +FizzBuzz *fizzBuzzCreate(int n) { + FizzBuzz *obj = (FizzBuzz *)malloc(sizeof(FizzBuzz)); + obj->n = n; + obj->curr = 1; + obj->turn = 0; + return obj; +} + +// Don't change the following declarations +void printNumber(int a); +void printFizz(); +void printBuzz(); +void printFizzBuzz(); + +int helper(FizzBuzz *obj, int turn) { + pthread_mutex_lock(&mutex); + while (obj->turn != turn && obj->curr <= obj->n) + pthread_cond_wait(&cond, &mutex); + if (obj->curr > obj->n) + return -1; + switch (turn) { + case 0: + printNumber(obj->curr); + break; + case 1: + printFizz(); + break; + case 2: + printBuzz(); + break; + case 3: + printFizzBuzz(); + break; + } + obj->curr++; + if ((obj->curr % 3 == 0) && (obj->curr % 5 == 0)) + obj->turn = 3; + else if (obj->curr % 3 == 0) + obj->turn = 1; + else if (obj->curr % 5 == 0) + obj->turn = 2; + else + obj->turn = 0; + pthread_cond_broadcast(&cond); + pthread_mutex_unlock(&mutex); + return 0; +} + +// printFizz() outputs "fizz". +void fizz(FizzBuzz *obj) { + while (1) + if (helper(obj, 1) == -1) + break; + pthread_mutex_unlock(&mutex); +} + +// printBuzz() outputs "buzz". +void buzz(FizzBuzz *obj) { + while (1) + if (helper(obj, 2) == -1) + break; + pthread_mutex_unlock(&mutex); +} + +// printFizzBuzz() outputs "fizzbuzz". +void fizzbuzz(FizzBuzz *obj) { + while (1) + if (helper(obj, 3) == -1) + break; + pthread_mutex_unlock(&mutex); +} + +// You may call global function `void printNumber(int x)` +// to output "x", where x is an integer. +void number(FizzBuzz *obj) { + while (1) + if (helper(obj, 0) == -1) + break; + pthread_mutex_unlock(&mutex); +} + +void fizzBuzzFree(FizzBuzz *obj) { + if (obj) + free(obj); +} + +void printNumber(int a) { printf("%d ", a); } + +void printFizz() { printf("fizz "); } + +void printBuzz() { printf("buzz "); } + +void printFizzBuzz() { printf("fizzbuzz "); } + +int main() { + FizzBuzz *obj1 = fizzBuzzCreate(15); + FizzBuzz *obj2 = fizzBuzzCreate(5); + pthread_t t1[4], t2[4]; + pthread_create(&t1[0], NULL, (void *)fizz, obj1); + pthread_create(&t1[1], NULL, (void *)buzz, obj1); + pthread_create(&t1[2], NULL, (void *)fizzbuzz, obj1); + pthread_create(&t1[3], NULL, (void *)number, obj1); + for (int i = 0; i < 4; i++) + pthread_join( + t1[i], + NULL); // expect: + // [1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"] + pthread_create(&t2[0], NULL, (void *)fizz, obj2); + pthread_create(&t2[1], NULL, (void *)buzz, obj2); + pthread_create(&t2[2], NULL, (void *)fizzbuzz, obj2); + pthread_create(&t2[3], NULL, (void *)number, obj2); + for (int i = 0; i < 4; i++) + pthread_join(t1[i], NULL); // expect: [1,2,"fizz",4,"buzz"] + fizzBuzzFree(obj1); + fizzBuzzFree(obj2); +} diff --git a/fizz_buzz_multithread.py b/fizz_buzz_multithread.py new file mode 100644 index 0000000..5292164 --- /dev/null +++ b/fizz_buzz_multithread.py @@ -0,0 +1,94 @@ +# 1195. Fizz Buzz Multithreaded +import threading + +""" +you have the following functions: +'printFizz' prints the word "fizz" to the console +'printBuzz' prints the word "buzz" to the console +'printFizzBuzz' prints the word "fizzbuzz" to the console +'printNumber' that prints a given integer to the console +you are given an instance of the class 'fizzbuzz' that has four functions +'fizz', 'buzz', 'fizzbuzz', and 'number'. the same instance of 'fizzbuzz' +will be passed to four different threads. +thread a calls 'fizz()' that should output the word "fizz" +thread b calls 'buzz()' that should output the word "buzz" +thread c calls 'fizzbuzz()' that should output the word "fizzbuzz" +thread d calls 'number()' that should output the given integer +modify the given class to output the series '[1, 2, "fizz", 4, "buzz", ...]' +where the i'th toek of the series is. +""" + + +class FizzBuzz(object): + def __init__(self, n): + self.n = n + self.f = threading.Lock() + self.b = threading.Lock() + self.fb = threading.Lock() + self.f.acquire() + self.b.acquire() + self.fb.acquire() + self.main = threading.Lock() + + # printFizz() outputs "fizz" + def fizz(self, printFizz): + """ + :type printFizz: method + :rtype: void + """ + while True: + self.f.acquire() + if self.n == 0: + return + printFizz() + self.main.release() + + # printBuzz() outputs "buzz" + def buzz(self, printBuzz): + """ + :type printBuzz: method + :rtype: void + """ + while True: + self.b.acquire() + if self.n == 0: + return + printBuzz() + self.main.release() + + # printFizzBuzz() outputs "fizzbuzz" + def fizzbuzz(self, printFizzBuzz): + """ + :type printFizzBuzz: method + :rtype: void + """ + while True: + self.fb.acquire() + if self.n == 0: + return + printFizzBuzz() + self.main.release() + + # printNumber(x) outputs "x", where x is an integer. + def number(self, printNumber): + """ + :type printNumber: method + :rtype: void + """ + for i in range(1, self.n + 1): + self.main.acquire() + if i % 15 == 0: + self.fb.release() + elif i % 3 == 0: + self.f.release() + elif i % 5 == 0: + self.b.release() + else: + printNumber(i) + self.main.release() + self.main.acquire() + self.n = 0 + self.f.release() + self.b.release() + self.fb.release() + return @@ -4,6 +4,7 @@ #include <ctype.h> #include <limits.h> #include <math.h> +#include <pthread.h> #include <stdbool.h> #include <stdint.h> #include <stdio.h> diff --git a/max_diff_between_incr_elem.c b/max_diff_between_incr_elem.c new file mode 100644 index 0000000..bf35ab0 --- /dev/null +++ b/max_diff_between_incr_elem.c @@ -0,0 +1,25 @@ +// 2016. Maximum Difference Between Increasing Elements +#include "leetcode.h" + +/* + * given a 0-indexed integer array 'nums' of size 'n', find the maximum + * difference between 'nums[i]' and 'nums[j]' (ie. 'nums[j] - nums[i]') such + * that '0 <= i < j < n' and 'nums[i] < nums[j]'. return the maximum difference. + * if no such 'i' and 'j' exist, return -1 + */ + +int maximumDifference(int *nums, int numsSize) { + int min = nums[0], ans = -1; + for (int i = 1; i < numsSize; ++i) { + ans = fmax(ans, nums[i] - min); + min = fmin(min, nums[i]); + } + return ans; +} + +int main() { + int n1[] = {7, 1, 5, 4}, n2[] = {9, 4, 3, 2}, n3[] = {1, 5, 2, 10}; + printf("%d\n", maximumDifference(n1, ARRAY_SIZE(n1))); // expect: 4 + printf("%d\n", maximumDifference(n2, ARRAY_SIZE(n2))); // expect: -1 + printf("%d\n", maximumDifference(n3, ARRAY_SIZE(n3))); // expect: 9 +} diff --git a/max_diff_between_incr_elem.py b/max_diff_between_incr_elem.py new file mode 100644 index 0000000..d277298 --- /dev/null +++ b/max_diff_between_incr_elem.py @@ -0,0 +1,28 @@ +# 2016. Maximum Difference Between Increasing Elements + +""" +given a 0-indexed integer array 'nums' of size 'n', find the maximum +difference between 'nums[i]' and 'nums[j]' (ie. 'nums[j] - nums[i]') such +that '0 <= i < j < n' and 'nums[i] < nums[j]'. return the maximum difference. +if no such 'i' and 'j' exist, return -1 +""" + + +class Solution(object): + def maximumDifference(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + minn, ans = nums[0], -1 + for i in range(len(nums)): + ans = max(ans, nums[i] - minn) + minn = min(minn, nums[i]) + return ans if ans != 0 else -1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumDifference(nums=[7, 1, 5, 4])) + print(obj.maximumDifference(nums=[9, 4, 3, 2])) + print(obj.maximumDifference(nums=[1, 5, 2, 10])) |