diff options
-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_remap_digit.c | 30 | ||||
-rw-r--r-- | max_diff_remap_digit.py | 26 | ||||
-rw-r--r-- | valid_square.c | 46 | ||||
-rw-r--r-- | valid_square.py | 41 |
7 files changed, 383 insertions, 0 deletions
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_remap_digit.c b/max_diff_remap_digit.c new file mode 100644 index 0000000..3eff54a --- /dev/null +++ b/max_diff_remap_digit.c @@ -0,0 +1,30 @@ +// 2566. Maximum Difference by Remapping a Digit +#include "leetcode.h" + +/* + * you are given an integer 'num'. you know that bob will sneakily remap one of + * the 10 possible digits to another digit. return the difference between the + * maximum and minimum values bob can make by remapping exactly one digit in + * nums. + */ + +int minMaxDifference(int num) { + int min = num, max = num; + for (int i = 0; i < 10; ++i) { + int low = 0, high = 0, mult = 1; + for (int j = num; j; j /= 10) { + bool replace = j % 10 == i; + low += (replace ? 0 : j % 10) * mult; + high += (replace ? 9 : j % 10) * mult; + mult *= 10; + } + min = fmin(min, low); + max = fmax(max, high); + } + return max - min; +} + +int main() { + printf("%d\n", minMaxDifference(11891)); // expect: 99009 + printf("%d\n", minMaxDifference(90)); // expect: 99 +} diff --git a/max_diff_remap_digit.py b/max_diff_remap_digit.py new file mode 100644 index 0000000..5d802ed --- /dev/null +++ b/max_diff_remap_digit.py @@ -0,0 +1,26 @@ +# 2566. Maximum Difference by Remapping a Digit + +""" +you are given an integer 'num'. you know that bob will sneakily remap one of +the 10 possible digits to another digit. return the difference between the +maximum and minimum values bob can make by remapping exactly one digit in +nums. +""" + + +class Solution(object): + def minMaxDifference(self, num): + """ + :type num: int + :rtype: int + """ + num, i = str(num), 0 + while num[i] == "9" and i < len(num) - 1: + i += 1 + return int(num.replace(num[i], "9")) - int(num.replace(num[0], "0")) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minMaxDifference(num=11891)) + print(obj.minMaxDifference(num=90)) diff --git a/valid_square.c b/valid_square.c new file mode 100644 index 0000000..8d1bd06 --- /dev/null +++ b/valid_square.c @@ -0,0 +1,46 @@ +// 593. Valid Square +#include "leetcode.h" + +/* + * given the coordinates of four points in a 2d space 'p1 .. p4', return true if + * the four points oncstruct a square. the coordinate of a point 'p_i' is + * represented as '[x_i, y_i]'. the input is not given in any order. a valid + * square has four equal sides with positive length and four equal angles + * (90-degree angles) + */ + +int dist(int x, int y) { return x * x + y * y; } + +bool validSquare(int *p1, int p1Size, int *p2, int p2Size, int *p3, int p3Size, + int *p4, int p4Size) { + int *p[4] = {p1, p2, p3, p4}, e[2] = {0}; + for (int i = 0; i < 4; i++) { + for (int j = i + 1; j < 4; j++) { + int n = dist(p[i][0] - p[j][0], p[i][1] - p[j][1]); + if (!n) + return false; + if (n == e[0] || (!e[0] && n != e[1])) + e[0] = n; + else if (n == e[1] || (!e[1] && n != e[0])) + e[1] = n; + else + return false; + } + } + return true; +} + +int main() { + int p11[] = {0, 0}, p21[] = {1, 1}, p31[] = {1, 0}, p41[] = {0, 1}; + int p12[] = {0, 0}, p22[] = {1, 1}, p32[] = {1, 0}, p42[] = {0, 12}; + int p13[] = {1, 0}, p23[] = {-1, 0}, p33[] = {0, 1}, p43[] = {0, -1}; + printf("%d\n", + validSquare(p11, ARRAY_SIZE(p11), p21, ARRAY_SIZE(p21), p31, + ARRAY_SIZE(p31), p41, ARRAY_SIZE(p41))); // expect: 1 + printf("%d\n", + validSquare(p12, ARRAY_SIZE(p12), p22, ARRAY_SIZE(p22), p32, + ARRAY_SIZE(p32), p42, ARRAY_SIZE(p42))); // expect: 0 + printf("%d\n", + validSquare(p13, ARRAY_SIZE(p13), p23, ARRAY_SIZE(p23), p33, + ARRAY_SIZE(p33), p43, ARRAY_SIZE(p43))); // expect: 1 +} diff --git a/valid_square.py b/valid_square.py new file mode 100644 index 0000000..a9a75c1 --- /dev/null +++ b/valid_square.py @@ -0,0 +1,41 @@ +# 593. Valid Square + +""" +given the coordinates of four points in a 2d space 'p1 .. p4', return true if +the four points oncstruct a square. the coordinate of a point 'p_i' is +represented as '[x_i, y_i]'. the input is not given in any order. a valid +square has four equal sides with positive length and four equal angles +(90-degree angles) +""" + + +class Solution(object): + def validSquare(self, p1, p2, p3, p4): + """ + :type p1: List[int] + :type p2: List[int] + :type p3: List[int] + :type p4: List[int] + :rtype: bool + """ + + def dist(p, q): + return (p[0] - q[0]) ** 2 + (p[1] - q[1]) ** 2 + + def check(p1, p2, p3, p4): + if p1[0] + p2[0] != p3[0] + p4[0] or p1[1] + p2[1] != p3[1] + p4[1]: + return False + if dist(p1, p2) != dist(p3, p4) or dist(p1, p4) != dist(p2, p4): + return False + if p1 == p2: + return False + return True + + return check(p1, p2, p3, p4) or check(p1, p3, p2, p4) or check(p1, p4, p2, p3) + + +if __name__ == "__main__": + obj = Solution() + print(obj.validSquare(p1=[0, 0], p2=[1, 1], p3=[1, 0], p4=[0, 1])) + print(obj.validSquare(p1=[0, 0], p2=[1, 1], p3=[1, 0], p4=[0, 12])) + print(obj.validSquare(p1=[1, 0], p2=[-1, 0], p3=[0, 1], p4=[0, -1])) |