diff options
63 files changed, 2727 insertions, 120 deletions
diff --git a/apply_operations_max_score.c b/apply_operations_max_score.c new file mode 100644 index 0000000..166c756 --- /dev/null +++ b/apply_operations_max_score.c @@ -0,0 +1,92 @@ +// 2818. Apply Operations to Maximize Score +#include "leetcode.h" + +/* + * you are given an array 'nums' of 'n' positive integers and an integer 'k'. + * initially, you start with a score of 1. you have to maxmise your score by + * applying the following operation at most 'k' times: chose any non-empty + * element 'x' of 'nums[l .. r]' with the highest prime score. if multiple such + * elements exist, choose the one with the smallest index. multiple your score + * 'x'. return the maximum possible score after applying at most 'k' operations. + * since the answer may be very large, return it module '10e9+7' + */ + +static int mod = 1e9 + 7, *vals; + +void prime_score(int *score, int upper) { + memset(score, 0, upper * sizeof(int)); + for (int i = 2; i < upper; i++) + if (!score[i]) + for (int j = i; j < upper; j += i) + score[j] += 1; +} + +long long mod_pow(long long base, long long exp, long long mod) { + long long res = 1; + while (exp) { + if (exp % 2 == 1) + res = (res * base) % mod; + base = (base * base) % mod; + exp /= 2; + } + return res; +} + +int cmp(const void *a, const void *b) { + return vals[*(int *)b] - vals[*(int *)a]; +} + +int maximumScore(int *nums, int n, int k) { + int upper = 0; + for (int i = 0; i < n; i++) { + if (nums[i] > upper) + upper = nums[i]; + } + upper++; + int *score = (int *)malloc(upper * sizeof(int)); + int *next = (int *)malloc(n * sizeof(int)); + int *prev = (int *)malloc(n * sizeof(int)); + int *stack = (int *)malloc(n * sizeof(int)); + prime_score(score, upper); + int top = -1, ans = 1; + for (int i = 0; i < n; i++) { + while (top >= 0 && score[nums[i]] > score[nums[stack[top]]]) + top--; + prev[i] = (top >= 0) ? stack[top] : -1; + stack[++top] = i; + } + top = -1; + for (int i = n - 1; i >= 0; i--) { + while (top >= 0 && score[nums[i]] >= score[nums[stack[top]]]) + top--; + next[i] = (top >= 0) ? stack[top] : n; + stack[++top] = i; + } + int *indices = (int *)malloc(n * sizeof(int)); + for (int i = 0; i < n; i++) + indices[i] = i; + vals = nums; + qsort(indices, n, sizeof(int), cmp); + for (int i = 0; i < n && k > 0; i++) { + int idx = indices[i], num = nums[idx]; + long long operations = (long long)(idx - prev[idx]) * (next[idx] - idx); + if (operations > k) + operations = k; + ans = (ans * mod_pow(num, operations, mod)) % mod; + k -= operations; + if (!k) + break; + } + free(score); + free(next); + free(prev); + free(stack); + free(indices); + return ans; +} + +int main() { + int n1[] = {8, 3, 9, 3, 8}, n2[] = {19, 12, 14, 6, 10, 18}; + printf("%d\n", maximumScore(n1, ARRAY_SIZE(n1), 2)); // expect: 81 + printf("%d\n", maximumScore(n2, ARRAY_SIZE(n2), 3)); // expect: 4788 +} diff --git a/apply_operations_max_score.py b/apply_operations_max_score.py new file mode 100644 index 0000000..d0834de --- /dev/null +++ b/apply_operations_max_score.py @@ -0,0 +1,72 @@ +# 2818. Apply Operations to Maximize Score + +""" +you are given an array 'nums' of 'n' positive integers and an integer 'k'. +initially, you start with a score of 1. you have to maxmise your score by +applying the following operation at most 'k' times: chose any non-empty +element 'x' of 'nums[l .. r]' with the highest prime score. if multiple such +elements exist, choose the one with the smallest index. multiple your score +'x'. return the maximum possible score after applying at most 'k' operations. +since the answer may be very large, return it module '10e9+7' +""" + + +class Solution(object): + mod = 10**9 + 7 + + def mod_pow(self, x, n): + res = 1 + while n > 0: + if n % 2 == 1: + res = (res * x) % self.mod + x = (x * x) % self.mod + n //= 2 + return res + + def maximumScore(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + n = len(nums) + upper = max(nums) + 1 + prime = [True] * upper + prime[0] = prime[1] = False + score = [0] * upper + for i in range(2, upper): + if prime[i]: + for j in range(i, upper, i): + score[j] += 1 + prime[j] = False + next, stk = [n] * n, [] + for i in range(n - 1, -1, -1): + while stk and score[nums[i]] >= score[nums[stk[-1]]]: + stk.pop() + next[i] = stk[-1] if stk else n + stk.append(i) + prev, stk = [-1] * n, [] + for i in range(n): + while stk and score[nums[i]] > score[nums[stk[-1]]]: + stk.pop() + prev[i] = stk[-1] if stk else -1 + stk.append(i) + ans = 1 + tuples = [[nums[i], i] for i in range(n)] + tuples.sort(reverse=True) + for num, idx in tuples: + operations = min( + (idx - prev[idx]) * (next[idx] - idx), + k, + ) + ans = (ans * self.mod_pow(num, operations)) % self.mod + k -= operations + if k == 0: + return ans + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumScore(nums=[8, 3, 9, 3, 8], k=2)) + print(obj.maximumScore(nums=[19, 12, 14, 6, 10, 18], k=3)) diff --git a/beautiful_arrangement.c b/beautiful_arrangement.c new file mode 100644 index 0000000..bc341da --- /dev/null +++ b/beautiful_arrangement.c @@ -0,0 +1,23 @@ +// 526. Beautiful Arrangement +#include "leetcode.h" + +/* + * suppose you have 'n' integers labeled 1 through 'n'. a permutation of those + * 'n' integers 'perm' (1-indexed) is considered a beautiful arrangement if for + * every 'i' ('1 <= i <= n') either of the following is true: 'perm[i]' is + * divisible by 'i', and 'i' is divisible by 'perm[i]'. given an integer 'n', + * return the number of the beautiful arrangements that you can construct. + */ + +int countArrangement(int n) { + static int ans[12] = {8, 10, 36, 41, 132, 250, + 700, 750, 4010, 4237, 10680, 24679}; + if (n < 4) + return n; + return ans[n - 4]; +} + +int main() { + printf("%d\n", countArrangement(2)); // expect: 2 + printf("%d\n", countArrangement(1)); // expect: 1 +} diff --git a/beautiful_arrangement.py b/beautiful_arrangement.py new file mode 100644 index 0000000..2a10829 --- /dev/null +++ b/beautiful_arrangement.py @@ -0,0 +1,34 @@ +# 526. Beautiful Arrangement + +""" +suppose you have 'n' integers labeled 1 through 'n'. a permutation of those +'n' integers 'perm' (1-indexed) is considered a beautiful arrangement if for +every 'i' ('1 <= i <= n') either of the following is true: 'perm[i]' is +divisible by 'i', and 'i' is divisible by 'perm[i]'. given an integer 'n', +return the number of the beautiful arrangements that you can construct. +""" + + +class Solution(object): + def countArrangement(self, n): + """ + :type n: int + :rtype: int + """ + + def dfs(mask, place): + if place == 0: + return 1 + res = 0 + for i in range(n): + if not mask & 1 << i and ((i + 1) % place == 0 or place % (i + 1) == 0): + res += dfs(mask ^ 1 << i, place - 1) + return res + + return dfs(0, n) + + +if __name__ == "__main__": + obj = Solution() + print(obj.countArrangement(n=2)) + print(obj.countArrangement(n=1)) diff --git a/brainpower.c b/brainpower.c index dc414bb..5bff250 100644 --- a/brainpower.c +++ b/brainpower.c @@ -1,7 +1,5 @@ // 2140. Solving Questions With Brainpower -#include <math.h> -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given a 0-indexed 2d integer array 'questions' where 'questions[i] = @@ -11,15 +9,14 @@ * will earn you 'pointsi' points, but you will be unable to solve each of the * next 'brainpoweri' questions. if you skip question 'i', yo get to make the * decision on the next question. return maximum points you can score. - * */ -long long mostPoints(int **questions, int questions_size, - int *questions_col_size) { - long long *dp = malloc((questions_size + 1) * sizeof(long long)); - dp[questions_size] = 0; - for (int i = questions_size - 1; i >= 0; i--) { - int k = fmin(i + questions[i][1] + 1, questions_size); +long long mostPoints(int **questions, int questionsSize, + int *questionsColSize) { + long long *dp = (long long *)malloc((questionsSize + 1) * sizeof(long long)); + dp[questionsSize] = 0; + for (int i = questionsSize - 1; i >= 0; i--) { + int k = fmin(i + questions[i][1] + 1, questionsSize); dp[i] = fmax(questions[i][0] + dp[k], dp[i + 1]); } long long ans = dp[0]; @@ -28,8 +25,11 @@ long long mostPoints(int **questions, int questions_size, } int main() { - int q1[4][2] = {{3, 2}, {4, 3}, {4, 4}, {2, 5}}, qs1 = 4, qcs1[] = {}; - int q2[5][2] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}, qs2 = 5, qcs2[] = {}; - printf("%lld\n", mostPoints(q1, qs1, qcs1)); // expect: 5 - printf("%lld\n", mostPoints(q2, qs2, qcs2)); // expect: 7 + int q1i[4][2] = {{3, 2}, {4, 3}, {4, 4}, {2, 5}}, + q2i[5][2] = {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}}; + struct two_d_arr q1, q2; + two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i); + two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i); + printf("%lld\n", mostPoints(q1.arr, q1.row_size, q1.col_size)); // expect: 5 + printf("%lld\n", mostPoints(q2.arr, q2.row_size, q2.col_size)); // expect: 7 } diff --git a/brainpower.py b/brainpower.py new file mode 100644 index 0000000..24c149c --- /dev/null +++ b/brainpower.py @@ -0,0 +1,30 @@ +# 2140. Solving Questions With Brainpower + +""" +given a 0-indexed 2d integer array 'questions' where 'questions[i] = +[pointsi, brainpoweri]'. the array describes the questions of an exam, where +you have to process the questions in order (ie starting from question 0) and +make a decision whether to solve or skip each question. solving question 'i' +will earn you 'pointsi' points, but you will be unable to solve each of the +next 'brainpoweri' questions. if you skip question 'i', yo get to make the +decision on the next question. return maximum points you can score. +""" + + +class Solution(object): + def mostPoints(self, questions): + """ + :type questions: List[List[int]] + :rtype: int + """ + dp = [0] * (len(questions) + 1) + for i in range(len(questions) - 1, -1, -1): + points, jump = questions[i][0], questions[i][1] + dp[i] = max(points + dp[min(jump + i + 1, len(questions))], dp[i + 1]) + return dp[0] + + +if __name__ == "__main__": + obj = Solution() + print(obj.mostPoints(questions=[[3, 2], [4, 3], [4, 4], [2, 5]])) + print(obj.mostPoints(questions=[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]])) diff --git a/check_grid_cut_section.c b/check_grid_cut_section.c new file mode 100644 index 0000000..2884222 --- /dev/null +++ b/check_grid_cut_section.c @@ -0,0 +1,80 @@ +// 3394. Check if Grid can be Cut into Sections +#include "leetcode.h" + +/* + * you are given an integer 'n' representing the dimensions of an 'n * n' grid + * with the origin at the bottom-left corner of the grid. you are also given a + * 2d array of coordinates 'rectangles', where 'rectangles[i]' is in the form + * '[start_x, start_y, end_x, end_y]' representing a rectangle on the grid. note + * that the rectangles do not overlap. your task is to determine if it is + * possible to make either two horizontal or two vertical cuts on the grid such + * that each of the three resulting formed by the cuts contains at least one + * rectangle. every rectangle belongs to exactly one section. return 'true' if + * such cuts can be made. otherwise, return 'false'. + */ + +int cmp_y(const void *a, const void *b) { + int *aa = *(int **)a, *bb = *(int **)b; + return aa[1] - bb[1]; +} + +int cmp_x(const void *a, const void *b) { + int *aa = *(int **)a, *bb = *(int **)b; + return aa[0] - bb[0]; +} + +bool check_x(int n, int **rectangles, int rectanglesSize) { + qsort(rectangles, rectanglesSize, sizeof(int *), cmp_y); + int intervals = 1, curr[2] = {rectangles[0][1], rectangles[0][3]}; + for (int i = 1; i < rectanglesSize; i++) { + if (rectangles[i][1] >= curr[1]) { + if (++intervals == 3) + return true; + curr[0] = rectangles[i][1]; + curr[1] = rectangles[i][3]; + } else if (rectangles[i][3] > curr[1]) + curr[1] = rectangles[i][3]; + } + return false; +} + +bool check_y(int n, int **rectangles, int rectanglesSize) { + qsort(rectangles, rectanglesSize, sizeof(int *), cmp_x); + int intervals = 1, curr[2] = {rectangles[0][0], rectangles[0][2]}; + for (int i = 1; i < rectanglesSize; i++) { + if (rectangles[i][0] >= curr[1]) { + if (++intervals == 3) + return true; + curr[0] = rectangles[i][0]; + curr[1] = rectangles[i][2]; + } else if (rectangles[i][2] > curr[1]) + curr[1] = rectangles[i][2]; + } + return false; +} + +bool checkValidCuts(int n, int **rectangles, int rectanglesSize, + int *rectanglesColSize) { + return check_y(n, rectangles, rectanglesSize) || + check_x(n, rectangles, rectanglesSize); +} + +int main() { + int r1i[4][4] = {{1, 0, 5, 2}, {0, 2, 2, 4}, {3, 2, 5, 3}, {0, 4, 4, 5}}; + int r2i[4][4] = {{0, 0, 1, 1}, {2, 0, 3, 4}, {0, 2, 2, 3}, {3, 0, 4, 3}}; + int r3i[5][4] = { + {0, 2, 2, 4}, {1, 0, 3, 2}, {2, 2, 3, 4}, {3, 0, 4, 2}, {3, 2, 4, 4}}; + struct two_d_arr r1, r2, r3; + two_d_arr_init(&r1, ARRAY_SIZE(r1i), ARRAY_SIZE(r1i[0]), r1i); + two_d_arr_init(&r2, ARRAY_SIZE(r2i), ARRAY_SIZE(r2i[0]), r2i); + two_d_arr_init(&r3, ARRAY_SIZE(r3i), ARRAY_SIZE(r3i[0]), r3i); + printf("%d\n", + checkValidCuts(5, r1.arr, r1.row_size, r1.col_size)); // expect: 1 + printf("%d\n", + checkValidCuts(4, r2.arr, r2.row_size, r2.col_size)); // expect: 1 + printf("%d\n", + checkValidCuts(4, r3.arr, r3.row_size, r3.col_size)); // expect: 0 + two_d_arr_free(&r1); + two_d_arr_free(&r2); + two_d_arr_free(&r3); +} diff --git a/check_grid_cut_section.py b/check_grid_cut_section.py new file mode 100644 index 0000000..b2869f7 --- /dev/null +++ b/check_grid_cut_section.py @@ -0,0 +1,60 @@ +# 3394. Check if Grid can be Cut into Sections + +""" +you are given an integer 'n' representing the dimensions of an 'n n' grid +with the origin at the bottom-left corner of the grid. you are also given a +2d array of coordinates 'rectangles', where 'rectangles[i]' is in the form +'[start_x, start_y, end_x, end_y]' representing a rectangle on the grid. note +that the rectangles do not overlap. your task is to determine if it is +possible to make either two horizontal or two vertical cuts on the grid such +that each of the three resulting formed by the cuts contains at least one +rectangle. every rectangle belongs to exactly one section. return 'true' if +such cuts can be made. otherwise, return 'false'. +""" + + +class Solution(object): + def checkValidCuts(self, n, rectangles): + """ + :type n: int + :type rectangles: List[List[int]] + :rtype: bool + """ + + def check(rectangles): + rectangles.sort() + res, pre = 0, rectangles[0][1] + for i, j in rectangles: + res += pre <= i + pre = max(pre, j) + return res > 1 + + return check([i[::2] for i in rectangles]) or check( + [i[1::2] for i in rectangles] + ) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.checkValidCuts( + n=5, rectangles=[[1, 0, 5, 2], [0, 2, 2, 4], [3, 2, 5, 3], [0, 4, 4, 5]] + ) + ) + print( + obj.checkValidCuts( + n=4, rectangles=[[0, 0, 1, 1], [2, 0, 3, 4], [0, 2, 2, 3], [3, 0, 4, 3]] + ) + ) + print( + obj.checkValidCuts( + n=4, + rectangles=[ + [0, 2, 2, 4], + [1, 0, 3, 2], + [2, 2, 3, 4], + [3, 0, 4, 2], + [3, 2, 4, 4], + ], + ) + ) diff --git a/convert_num_hex.c b/convert_num_hex.c new file mode 100644 index 0000000..421706b --- /dev/null +++ b/convert_num_hex.c @@ -0,0 +1,35 @@ +// 405. Convert a Number to Hexadecimal +#include "leetcode.h" + +/* + * given a 32 bit integer 'num', return a string representing its hexadecimal + * representation. for negative integers, two's complement method is used. all + * the letters in the answer string should be lowercase characters, nd there not + * be any leading zeros in the answer except for the zero itself. note: you are + * not allowed to use any built-in library method to directly solve this + * problem. + */ + +char *toHex(int num) { + char *ans = (char *)malloc(sizeof(char) * 10), step; + uint x = num, i = 0; + ans[9] = '\0'; + while (1) { + step = x & 0xF; + ans[8 - i] = step > 9 ? 'a' + step - 10 : '0' + step; + x >>= 4; + if (!x) + break; + i++; + } + return &ans[8 - i]; +} + +int main() { + char *th1 = toHex(26); + char *th2 = toHex(-1); + printf("%s\n", th1); // expect: 1a + printf("%s\n", th2); // expect: ffffffff + free(th1); + free(th2); +} diff --git a/convert_num_hex.py b/convert_num_hex.py new file mode 100644 index 0000000..65ca796 --- /dev/null +++ b/convert_num_hex.py @@ -0,0 +1,29 @@ +# 405. Convert a Number to Hexadecimal + +""" +given a 32 bit integer 'num', return a string representing its hexadecimal +representation. for negative integers, two's complement method is used. all +the letters in the answer string should be lowercase characters, nd there not +be any leading zeros in the answer except for the zero itself. note: you are +not allowed to use any built-in library method to directly solve this +problem. +""" + + +class Solution(object): + def toHex(self, num): + """ + :type num: int + :rtype: str + """ + map, ans, num = "0123456789abcdef", "", num & 0xFFFFFFFF + while num: + ans += map[num % 16] + num >>= 4 + return ans[::-1] or "0" + + +if __name__ == "__main__": + obj = Solution() + print(obj.toHex(num=26)) + print(obj.toHex(num=-1)) diff --git a/count_days_without_meeting.c b/count_days_without_meeting.c new file mode 100644 index 0000000..9e1ff35 --- /dev/null +++ b/count_days_without_meeting.c @@ -0,0 +1,47 @@ +// 3169. Count Days Without Meetings +#include "leetcode.h" + +/* + * you are given a positive integer 'days' representing the total number of days + * an employee is available for work (starting from day 1). you are given a 2d + * integer array 'meetings' of size 'n' where 'meetings[i] = [start_i, end_i]' + * represents the starting and ending days of meeting 'i' (inclusive). return + * the count of days when the employee is available for work, but no meetings + * are scheduled. + */ + +int cmp(const void *a, const void *b) { + int *aa = *(int **)a, *bb = *(int **)b; + return aa[0] == bb[0] ? aa[1] - bb[1] : aa[0] - bb[0]; +} + +int countDays(int days, int **meetings, int meetingsSize, + int *meetingsColSize) { + qsort(meetings, meetingsSize, sizeof(int *), cmp); + int idx = 0, start = meetings[idx][0], end = meetings[idx++][1]; + while (idx < meetingsSize) { + if (meetings[idx][0] > end) { + days -= (end - start + 1); + start = meetings[idx][0]; + end = meetings[idx][1]; + } else + end = end > meetings[idx][1] ? end : meetings[idx][1]; + ++idx; + } + return days - (end - start + 1); +} + +int main() { + int m1i[3][2] = {{5, 7}, {1, 3}, {9, 10}}, m2i[2][2] = {{2, 4}, {1, 3}}, + m3i[1][2] = {{1, 6}}; + struct two_d_arr m1, m2, m3; + two_d_arr_init(&m1, ARRAY_SIZE(m1i), ARRAY_SIZE(m1i[0]), m1i); + two_d_arr_init(&m2, ARRAY_SIZE(m2i), ARRAY_SIZE(m2i[0]), m2i); + two_d_arr_init(&m3, ARRAY_SIZE(m3i), ARRAY_SIZE(m3i[0]), m3i); + printf("%d\n", countDays(10, m1.arr, m1.row_size, m1.col_size)); // expect: 2 + printf("%d\n", countDays(5, m2.arr, m2.row_size, m2.col_size)); // expect: 1 + printf("%d\n", countDays(6, m3.arr, m3.row_size, m3.col_size)); // expect: 0 + two_d_arr_free(&m1); + two_d_arr_free(&m2); + two_d_arr_free(&m3); +} diff --git a/count_days_without_meeting.py b/count_days_without_meeting.py new file mode 100644 index 0000000..c1cee7d --- /dev/null +++ b/count_days_without_meeting.py @@ -0,0 +1,37 @@ +# 3169. Count Days Without Meetings + +""" +you are given a positive integer 'days' representing the total number of days +an employee is available for work (starting from day 1). you are given a 2d +integer array 'meetings' of size 'n' where 'meetings[i] = [start_i, end_i]' +represents the starting and ending days of meeting 'i' (inclusive). return +the count of days when the employee is available for work, but no meetings +are scheduled. +""" + + +class Solution(object): + def countDays(self, days, meetings): + """ + :type days: int + :type meetings: List[List[int]] + :rtype: int + """ + meetings.sort(key=lambda x: x[0]) + cnt, n = abs(meetings[0][0] - 1), len(meetings) + for i in range(1, n): + if meetings[i][0] <= meetings[i - 1][1]: + if meetings[i][1] < meetings[i - 1][1]: + meetings[i][1] = meetings[i - 1][1] + else: + day = meetings[i][0] - meetings[i - 1][1] + cnt += day - 1 + cnt += abs(meetings[n - 1][1] - days) + return cnt + + +if __name__ == "__main__": + obj = Solution() + print(obj.countDays(days=10, meetings=[[5, 7], [1, 3], [9, 10]])) + print(obj.countDays(days=5, meetings=[[2, 4], [1, 3]])) + print(obj.countDays(days=6, meetings=[[1, 6]])) diff --git a/count_num_complete_component.c b/count_num_complete_component.c new file mode 100644 index 0000000..a6ede23 --- /dev/null +++ b/count_num_complete_component.c @@ -0,0 +1,73 @@ +// 2685. Count the Number of Complete Components +#include "leetcode.h" + +/* + * you are given an integer 'n'. there is an undirected graph with 'n' vertices, + * numbered from 0 to 'n - 1'. you are given a 2d integer array 'edges' where + * 'edges[i] = [a_i, b_i]' denotes that there exists an undirected edge + * connecting vertices 'a_i' and 'b_i'. return the number of complete connected + * components of the graph. a connected component is a subgraph of a graph in + * which there exists a path between any two vertices and no vertex of the + * subgraph shares an edge with a vertex outside of the subgraph. a connected + * component is said to be complete if there exists an edge between every pair + * of its vertices + */ + +int countCompleteComponents(int n, int **edges, int edgesSize, + int *edgesColSize) { + int *vertices = (int *)calloc(n, sizeof(int)); + int *edge_cnt = (int *)calloc(n, sizeof(int)); + int *vert_cnt = (int *)calloc(n, sizeof(int)); + int group = 1, ans = 0; + for (int i = 0; i < edgesSize; i++) { + int v1 = edges[i][0]; + int v2 = edges[i][1]; + if (!(vertices[v1] + vertices[v2])) { + vertices[v1] = vertices[v2] = group; + edge_cnt[group] = 2; + vert_cnt[group++] = 1; + } else if (!vertices[v1]) { + vertices[v1] = vertices[v2]; + ++edge_cnt[vertices[v2]]; + ++vert_cnt[vertices[v2]]; + } else if (!vertices[v2]) { + vertices[v2] = vertices[v1]; + ++edge_cnt[vertices[v1]]; + ++vert_cnt[vertices[v1]]; + } else if (vertices[v1] == vertices[v2]) + ++vert_cnt[vertices[v1]]; + else { + vert_cnt[vertices[v1]] += vert_cnt[vertices[v2]] + 1; + edge_cnt[vertices[v1]] += edge_cnt[vertices[v2]]; + edge_cnt[vertices[v2]] = vert_cnt[vertices[v2]] = 0; + for (int i = 0; i < n; i++) + if (vertices[i] == vertices[v2]) + vertices[i] = vertices[v1]; + } + } + int connect_cnt = 0; + for (int i = 1; i < group; i++) { + int edges = edge_cnt[i], verts = vert_cnt[i]; + if (edges && (edges * (edges - 1) / 2 == verts)) + ++ans; + connect_cnt += edges; + } + free(vert_cnt); + free(edge_cnt); + free(vertices); + return ans + (n - connect_cnt); +} + +int main() { + int e1i[4][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}}, + e2i[5][2] = {{0, 1}, {0, 2}, {1, 2}, {3, 4}, {3, 5}}; + struct two_d_arr e1, e2; + two_d_arr_init(&e1, ARRAY_SIZE(e1i), ARRAY_SIZE(e1i[0]), e1i); + two_d_arr_init(&e2, ARRAY_SIZE(e2i), ARRAY_SIZE(e2i[0]), e2i); + printf("%d\n", countCompleteComponents(6, e1.arr, e1.row_size, + e1.col_size)); // expect: 3 + printf("%d\n", countCompleteComponents(6, e2.arr, e2.row_size, + e2.col_size)); // expect: 1 + two_d_arr_free(&e1); + two_d_arr_free(&e2); +} diff --git a/count_num_complete_component.py b/count_num_complete_component.py new file mode 100644 index 0000000..6b8a592 --- /dev/null +++ b/count_num_complete_component.py @@ -0,0 +1,48 @@ +# 2685. Count the Number of Complete Components + +""" +you are given an integer 'n'. there is an undirected graph with 'n' vertices, +numbered from 0 to 'n - 1'. you are given a 2d integer array 'edges' where +'edges[i] = [a_i, b_i]' denotes that there exists an undirected edge +connecting vertices 'a_i' and 'b_i'. return the number of complete connected +components of the graph. a connected component is a subgraph of a graph in +which there exists a path between any two vertices and no vertex of the +subgraph shares an edge with a vertex outside of the subgraph. a connected +component is said to be complete if there exists an edge between every pair +of its vertices +""" + + +class Solution(object): + def countCompleteComponents(self, n, edges): + """ + :type n: int + :type edges: List[List[int]] + :rtype: int + """ + graph = [[] for _ in range(n)] + for i, j in edges: + graph[i].append(j) + graph[j].append(i) + vis, ans = [False] * n, 0 + for i in range(n): + if vis[i]: + continue + bfs = [i] + vis[i] = True + for j in bfs: + for k in graph[j]: + if not vis[k]: + bfs.append(k) + vis[k] = True + if all(len(graph[j]) == len(bfs) - 1 for j in bfs): + ans += 1 + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.countCompleteComponents(n=6, edges=[[0, 1], [0, 2], [1, 2], [3, 4]])) + print( + obj.countCompleteComponents(n=6, edges=[[0, 1], [0, 2], [1, 2], [3, 4], [3, 5]]) + ) diff --git a/decode_string.c b/decode_string.c new file mode 100644 index 0000000..c476cb9 --- /dev/null +++ b/decode_string.c @@ -0,0 +1,114 @@ +// 394. Decode String +#include "leetcode.h" + +/* + * given an encoded string, return its decoded string. the encoding rule is + * 'k[encoded_string]' where the 'encoded_string' inside the square brackets is + * being repeated exactly 'k' times. note that 'k' is guaranteed to be a + * positive integer. you may assume that the input string is always valid; there + * are no extra white spaces, square brackets are well-formed, etc. furthermore, + * you may assume that the original data does not contain any digits, and that + * digits are only for those repeat numbers, 'k'. the test cases are generated + * such that the output will never exceed '10^5'. + */ + +struct node_time { + int times; + struct node_time *next; +}; + +struct node_char { + char c; + struct node_char *next; +}; + +void push_int(struct node_time **head, int val) { + struct node_time *new = (struct node_time *)malloc(sizeof(struct node_time)); + new->times = val; + new->next = *head; + *head = new; +} + +void push_char(struct node_char **head, char c) { + struct node_char *new = (struct node_char *)malloc(sizeof(struct node_char)); + new->c = c; + new->next = *head; + *head = new; +} + +int pop_int(struct node_time **head) { + struct node_time *tmp = *head; + int res = tmp->times; + *head = (*head)->next; + free(tmp); + return res; +} + +char pop_char(struct node_char **head) { + struct node_char *tmp = *head; + char res = tmp->c; + *head = (*head)->next; + free(tmp); + return res; +} + +int word_size(struct node_char *head) { + int n = 0; + while (head) { + if (head->c == '[') + break; + n++; + head = head->next; + } + return n; +} + +char *decodeString(char *s) { + struct node_time *int_stk = NULL; + struct node_char *char_stk = NULL; + int i = 0, n, k; + while (s[i]) { + if (s[i] >= '0' && s[i] <= '9') { + int num = atoi(&s[i]); + while (s[i] >= '0' && s[i] <= '9') + i++; + push_int(&int_stk, num); + } else if (s[i] > '9' && s[i] != ']') { + push_char(&char_stk, s[i]); + i++; + } else if (s[i] == '[') { + push_char(&char_stk, '['); + i++; + } else if (s[i] == ']') { + n = word_size(char_stk); + int times = pop_int(&int_stk); + char *word = (char *)malloc(n * sizeof(char)); + for (k = 0; k < n; k++) + word[k] = pop_char(&char_stk); + pop_char(&char_stk); + for (; times; times--) + for (k = n - 1; k >= 0; k--) + push_char(&char_stk, word[k]); + free(word); + i++; + } + } + n = word_size(char_stk); + char *ans = (char *)calloc(n + 1, sizeof(char)); + for (k = n - 1; k >= 0; k--) + ans[k] = pop_char(&char_stk); + return ans; +} + +int main() { + char *s1 = "3[a]2[bc]", *s2 = "3[a2[c]]", *s3 = "2[abc]3[cd]ef"; + char *ds1 = decodeString(s1); + char *ds2 = decodeString(s2); + char *ds3 = decodeString(s3); + printf("%s\n", ds1); // expect: aaabcbc + printf("%s\n", ds2); // expect: accaccacc + printf("%s\n", ds2); // expect: abcabccdcdcdef + free(ds1); + free(ds2); + free(ds3); +} diff --git a/decode_string.py b/decode_string.py new file mode 100644 index 0000000..e62c5b0 --- /dev/null +++ b/decode_string.py @@ -0,0 +1,43 @@ +# 394. Decode String + +""" +given an encoded string, return its decoded string. the encoding rule is +'k[encoded_string]' where the 'encoded_string' inside the square brackets is +being repeated exactly 'k' times. note that 'k' is guaranteed to be a +positive integer. you may assume that the input string is always valid; there +are no extra white spaces, square brackets are well-formed, etc. furthermore, +you may assume that the original data does not contain any digits, and that +digits are only for those repeat numbers, 'k'. the test cases are generated +such that the output will never exceed '10^5'. +""" + + +class Solution(object): + def decodeString(self, s): + """ + :type s: str + :rtype: str + """ + stk, curr_int, curr_str = [], 0, "" + for c in s: + if c == "[": + stk.append(curr_str) + stk.append(curr_int) + curr_str = "" + curr_int = 0 + elif c == "]": + num = stk.pop() + prev_str = stk.pop() + curr_str = prev_str + num * curr_str + elif c.isdigit(): + curr_int = curr_int * 10 + int(c) + else: + curr_str += c + return curr_str + + +if __name__ == "__main__": + obj = Solution() + print(obj.decodeString(s="3[a]2[bc]")) + print(obj.decodeString(s="3[a2[c]]")) + print(obj.decodeString(s="2[abc]3[cd]ef")) diff --git a/divide_array_equal_pair.c b/divide_array_equal_pair.c new file mode 100644 index 0000000..cc98130 --- /dev/null +++ b/divide_array_equal_pair.c @@ -0,0 +1,24 @@ +// 2206. Divide Array Into Equal Pairs +#include "leetcode.h" + +/* + * you are given an integer array 'nums' consisting of '2 * n' integers. you + * need to divide 'nums' into 'n' pairs such that: each element belongs to + * exactly one pair, and the elements present in a pair are equal. return true + * if 'nums' can be divided into 'n' pairs, otherwise return false. + */ + +bool divideArray(int *nums, int numsSize) { + int x1 = 0, x2 = 0; + for (int i = 0; i < numsSize; i++) { + x1 ^= nums[i]; + x2 ^= nums[i] + 1; + } + return !x1 && !x2; +} + +int main() { + int n1[] = {3, 2, 3, 2, 2, 2}, n2[] = {1, 2, 3, 4}; + printf("%d\n", divideArray(n1, ARRAY_SIZE(n1))); // expect: 1 + printf("%d\n", divideArray(n2, ARRAY_SIZE(n2))); // expect: 0 +} diff --git a/divide_array_equal_pair.py b/divide_array_equal_pair.py new file mode 100644 index 0000000..7555627 --- /dev/null +++ b/divide_array_equal_pair.py @@ -0,0 +1,26 @@ +# 2206. Divide Array Into Equal Pairs + +""" +you are given an integer array 'nums' consisting of '2 n' integers. you +need to divide 'nums' into 'n' pairs such that: each element belongs to +exactly one pair, and the elements present in a pair are equal. return true +if 'nums' can be divided into 'n' pairs, otherwise return false. +""" + + +class Solution(object): + def divideArray(self, nums): + """ + :type nums: List[int] + :rtype: bool + """ + vis = set() + for i in nums: + vis ^= {i} + return not vis + + +if __name__ == "__main__": + obj = Solution() + print(obj.divideArray(nums=[3, 2, 3, 2, 2, 2])) + print(obj.divideArray(nums=[1, 2, 3, 4])) diff --git a/find_kth_char_str_game2.c b/find_kth_char_str_game2.c new file mode 100644 index 0000000..08202e6 --- /dev/null +++ b/find_kth_char_str_game2.c @@ -0,0 +1,28 @@ +// 3307. Find the K-th Character in String Game II +#include "leetcode.h" + +/* + * alice and bob are playing a game. initially, alice has a string 'word = "a"'. + * you are given a positive integer 'k'. you are also given an integer array + * 'operations' where 'operations[i]' represents the type of i'th operation. now + * bob will ask alice to perform all operations in sequence: if 'operations[i] + * == 0', append a copy of 'word' to itself. if 'operations[i] == 1', generate a + * new string by changing each character in 'word' to its next character in the + * english alphabet, and append it to the origin 'word'. return the value of the + * k'th character in 'word' after performing all the operations. + */ + +char kthCharacter(long long k, int *operations, int operationsSize) { + int ans = 0; + k--; + for (int i = 0; i < operationsSize && i < 60; ++i) + if ((k >> i) % 2) + ans += operations[i]; + return (char)('a' + ans % 26); +} + +int main() { + int o1[] = {0, 0, 0}, o2[] = {0, 1, 0, 1}; + printf("%c\n", kthCharacter(5, o1, ARRAY_SIZE(o1))); // expect: a + printf("%c\n", kthCharacter(10, o2, ARRAY_SIZE(o2))); // expect: b +} diff --git a/find_kth_char_str_game2.py b/find_kth_char_str_game2.py new file mode 100644 index 0000000..118641e --- /dev/null +++ b/find_kth_char_str_game2.py @@ -0,0 +1,29 @@ +# 3307. Find the K-th Character in String Game II + +""" +alice and bob are playing a game. initially, alice has a string 'word = "a"'. +you are given a positive integer 'k'. you are also given an integer array +'operations' where 'operations[i]' represents the type of i'th operation. now +bob will ask alice to perform all operations in sequence: if 'operations[i] +== 0', append a copy of 'word' to itself. if 'operations[i] == 1', generate a +new string by changing each character in 'word' to its next character in the +english alphabet, and append it to the origin 'word'. return the value of the +k'th character in 'word' after performing all the operations. +""" + + +class Solution(object): + def kthCharacter(self, k, operations): + """ + :type k: int + :type operations: List[int] + :rtype: str + """ + ans = (k - 1) & sum(v << i for i, v in enumerate(operations)) + return chr(ord("a") + ans.bit_count() % 26) + + +if __name__ == "__main__": + obj = Solution() + print(obj.kthCharacter(k=5, operations=[0, 0, 0])) + print(obj.kthCharacter(k=10, operations=[0, 1, 0, 1])) diff --git a/house_robber4.c b/house_robber4.c new file mode 100644 index 0000000..2e1c6e3 --- /dev/null +++ b/house_robber4.c @@ -0,0 +1,36 @@ +// 2560. House Robber IV +#include "leetcode.h" + +/* + * there are several consecutive houses along a street, each of which has some + * money inside. there is also a robber, who wants to steal money from the + * homes, but he refuses to steal from adjacent homes. the capability of the + * robber is the maximum amount of money he steals from one house of all the + * houses he robbed. you are given an integer array 'nums' representing how much + * money is stahsed in each house. more formally, the i'th house from the left + * has 'nums[i]' dollars. you are also given an integer 'k', representing the + * minimum number of houses the robber will steal from. it is always possible to + * steal at least 'k' houses. return the minimum possible capability of the + * robber out of all the possible ways to steal at least 'k' houses. + */ + +int minCapability(int *nums, int numsSize, int k) { + int left = 1, right = 1e9; + while (left < right) { + int mid = (left + right) / 2, take = 0; + for (int i = 0; i < numsSize; i++) + if (nums[i] <= mid) + take++, i++; + if (take >= k) + right = mid; + else + left = mid + 1; + } + return left; +} + +int main() { + int n1[] = {2, 3, 5, 9}, n2[] = {2, 7, 9, 3, 1}; + printf("%d\n", minCapability(n1, ARRAY_SIZE(n1), 2)); // expect: 5 + printf("%d\n", minCapability(n2, ARRAY_SIZE(n2), 2)); // expect: 2 +} diff --git a/house_robber4.py b/house_robber4.py new file mode 100644 index 0000000..a8fb361 --- /dev/null +++ b/house_robber4.py @@ -0,0 +1,45 @@ +# 2560. House Robber IV + +""" +there are several consecutive houses along a street, each of which has some +money inside. there is also a robber, who wants to steal money from the +homes, but he refuses to steal from adjacent homes. the capability of the +robber is the maximum amount of money he steals from one house of all the +houses he robbed. you are given an integer array 'nums' representing how much +money is stahsed in each house. more formally, the i'th house from the left +has 'nums[i]' dollars. you are also given an integer 'k', representing the +minimum number of houses the robber will steal from. it is always possible to +steal at least 'k' houses. return the minimum possible capability of the +robber out of all the possible ways to steal at least 'k' houses. +""" + + +class Solution(object): + def minCapability(self, nums, k): + """ + :type nums: List[int] + :type k: int + :rtype: int + """ + left, right = min(nums), max(nums) + while left < right: + mid = (left + right) // 2 + prev, take = 0, False + for i in nums: + if prev: + prev = False + continue + if i <= mid: + take += 1 + prev = True + if take >= k: + right = mid + else: + left = mid + 1 + return left + + +if __name__ == "__main__": + obj = Solution() + print(obj.minCapability(nums=[2, 3, 5, 9], k=2)) + print(obj.minCapability(nums=[2, 7, 9, 3, 1], k=2)) diff --git a/largest_divisible_subset.c b/largest_divisible_subset.c index f540528..6d36c45 100644 --- a/largest_divisible_subset.c +++ b/largest_divisible_subset.c @@ -10,14 +10,14 @@ int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } -int *largestDivisibleSubset(int *nums, int nums_size, int *return_size) { - qsort(nums, nums_size, sizeof(int), cmp); - int *idx = malloc(nums_size * sizeof(int)); - int *cnt = malloc(nums_size * sizeof(int)); +int *largestDivisibleSubset(int *nums, int numsSize, int *returnSize) { + qsort(nums, numsSize, sizeof(int), cmp); + int *idx = (int *)malloc(numsSize * sizeof(int)); + int *cnt = (int *)malloc(numsSize * sizeof(int)); int max = 1, max_idx = 0, tmp; idx[0] = -1; cnt[0] = 1; - for (int i = 1; i < nums_size; i++) { + for (int i = 1; i < numsSize; i++) { idx[i] = -1; cnt[i] = 1; for (int j = i - 1; j >= 0; j--) @@ -33,25 +33,25 @@ int *largestDivisibleSubset(int *nums, int nums_size, int *return_size) { max_idx = i; } } - *return_size = max; - int *ans = malloc(max * sizeof(int)); + *returnSize = max; + int *ans = (int *)malloc(max * sizeof(int)); for (int i = max - 1; i >= 0; i--) { ans[i] = nums[max_idx]; max_idx = idx[max_idx]; } - free(idx), free(cnt); + free(idx); + free(cnt); return ans; } int main() { - int n1[] = {1, 2, 3}, n2[] = {1, 2, 4, 8}; - int rs1[] = {}, rs2[] = {}; - int *lds1 = largestDivisibleSubset(n1, ARRAY_SIZE(n1), rs1); - int *lds2 = largestDivisibleSubset(n2, ARRAY_SIZE(n2), rs2); - for (int i = 0; i < 2; i++) + int n1[] = {1, 2, 3}, n2[] = {1, 2, 4, 8}, rs1, rs2; + int *lds1 = largestDivisibleSubset(n1, ARRAY_SIZE(n1), &rs1); + int *lds2 = largestDivisibleSubset(n2, ARRAY_SIZE(n2), &rs2); + for (int i = 0; i < rs1; i++) printf("%d ", lds1[i]); // expect: 1 2 printf("\n"); - for (int i = 0; i < 4; i++) + for (int i = 0; i < rs2; i++) printf("%d ", lds2[i]); // expect: 1 2 4 8 printf("\n"); free(lds1), free(lds2); diff --git a/long_nice_subarr.c b/long_nice_subarr.c index cfa50f3..a655bbf 100644 --- a/long_nice_subarr.c +++ b/long_nice_subarr.c @@ -1,53 +1,28 @@ // 2401. Longest Nice Subarray -#include <stdbool.h> -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * given an array 'nums' consisting of positive integers. we call a subarray of - * 'nums' nice if the bitwise AND of every pair of elements that are in + * 'nums' nice if the bitwise cnt of every pair of elements that are in * different positions in the subarray is equal to 0. return the length of the * longest nice subarray. a subarray is contiguous part of an array. note that * subarrays of length 1 are always considered nice. */ -bool check(int *bit, int n) { - for (int i = 0; i < n; i++) - if (bit[i] > 1) - return false; - return true; -} - -int longestNiceSubarray(int *nums, int nums_size) { - int *bit = calloc(32, sizeof(int)); - int left = 0, right = 0; - while (right < nums_size) { - int k = nums[right], pos = 0; - while (k) { - if (k % 2 == 1) - bit[pos]++; - k /= 2; - pos++; - } - right++; - if (!check(bit, 32)) { - k = nums[left]; - pos = 0; - while (k) { - if (k % 2 == 1) - bit[pos]--; - k /= 2; - pos++; - } - left++; - } +int longestNiceSubarray(int *nums, int numsSize) { + int cnt = 0, i = 0, ans = 0; + for (int j = 0; j < numsSize; ++j) { + while (cnt & nums[j]) + cnt ^= nums[i++]; + cnt |= nums[j]; + ans = fmax(ans, j - i + 1); } - return right - left; + return ans; } int main() { - int n1[] = {1, 3, 8, 48, 10}, ns1 = 5; - int n2[] = {3, 1, 5, 11, 13}, ns2 = 5; - printf("%d\n", longestNiceSubarray(n1, ns1)); // expect: 3 - printf("%d\n", longestNiceSubarray(n2, ns2)); // expect: 1 + int n1[] = {1, 3, 8, 48, 10}; + int n2[] = {3, 1, 5, 11, 13}; + printf("%d\n", longestNiceSubarray(n1, ARRAY_SIZE(n1))); // expect: 3 + printf("%d\n", longestNiceSubarray(n2, ARRAY_SIZE(n2))); // expect: 1 } diff --git a/long_nice_subarr.py b/long_nice_subarr.py new file mode 100644 index 0000000..037743e --- /dev/null +++ b/long_nice_subarr.py @@ -0,0 +1,31 @@ +# 2401. Longest Nice Subarray + +""" +given an array 'nums' consisting of positive integers. we call a subarray of +'nums' nice if the bitwise cnt of every pair of elements that are in +different positions in the subarray is equal to 0. return the length of the +longest nice subarray. a subarray is contiguous part of an array. note that +subarrays of length 1 are always considered nice. +""" + + +class Solution(object): + def longestNiceSubarray(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + cnt, i, ans = 0, 0, 0 + for j in range(len(nums)): + while cnt & nums[j]: + cnt ^= nums[i] + i += 1 + cnt |= nums[j] + ans = max(ans, j - i + 1) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.longestNiceSubarray(nums=[1, 3, 8, 48, 10])) + print(obj.longestNiceSubarray(nums=[3, 1, 5, 11, 13])) diff --git a/low_common_ancestor_leaf.c b/low_common_ancestor_leaf.c new file mode 100644 index 0000000..87b5bf4 --- /dev/null +++ b/low_common_ancestor_leaf.c @@ -0,0 +1,49 @@ +// 1123. Lowest Common Ancestor of Deepest Leaves +#include "leetcode.h" + +/* + * given the 'root' of a binary tree, return the lowest common ancestor of its + * deepest leaves. recall that the node of a binary tree is a leaf if and only + * if it has no children, the depth of the root of the tree is 0. if the depth + * of a node is 'd', the depth of each of its children is 'd + 1'. and the + * lowest common ancestor of a set 's' is the node 'a' with the largest depth + * such that every node in 's' is in the subtree with root 'a'. + */ + +int depth(struct TreeNode *root) { + if (!root) + return 0; + int l = depth(root->left); + int r = depth(root->right); + return l > r ? l + 1 : r + 1; +} + +struct TreeNode *lcaDeepestLeaves(struct TreeNode *root) { + if (!root) + return NULL; + int l = depth(root->left); + int r = depth(root->right); + if (l == r) + return root; + return l > r ? lcaDeepestLeaves(root->left) : lcaDeepestLeaves(root->right); +} + +int main() { + int r1i[] = {3, 5, 1, 6, 2, 0, 8, -1, -1, 7, 4}, r2i[] = {1}, + r3i[] = {0, 1, 3, -1, 2}; + struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i)); + struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i)); + struct TreeNode *r3 = treenode_build(r3i, ARRAY_SIZE(r3i)); + struct TreeNode *lcadl1 = lcaDeepestLeaves(r1); + struct TreeNode *lcadl2 = lcaDeepestLeaves(r2); + struct TreeNode *lcadl3 = lcaDeepestLeaves(r3); + treenode_print(lcadl1); // expect: 2 7 4 + printf("\n"); + treenode_print(lcadl2); // expect: 1 + printf("\n"); + treenode_print(lcadl3); // expect: 2 + printf("\n"); + treenode_free(r1); + treenode_free(r2); + treenode_free(r3); +} diff --git a/low_common_ancestor_leaf.py b/low_common_ancestor_leaf.py new file mode 100644 index 0000000..4b0036f --- /dev/null +++ b/low_common_ancestor_leaf.py @@ -0,0 +1,48 @@ +# 1123. Lowest Common Ancestor of Deepest Leaves +import leetcode + +""" +given the 'root' of a binary tree, return the lowest common ancestor of its +deepest leaves. recall that the node of a binary tree is a leaf if and only +if it has no children, the depth of the root of the tree is 0. if the depth +of a node is 'd', the depth of each of its children is 'd + 1'. and the +lowest common ancestor of a set 's' is the node 'a' with the largest depth +such that every node in 's' is in the subtree with root 'a'. +""" + + +class Solution(object): + def lcaDeepestLeaves(self, root): + """ + :type root: Optional[TreeNode] + :rtype: Optional[TreeNode] + """ + + def depth(node): + if not node: + return 0 + return max(depth(node.left), depth(node.right)) + 1 + + def dfs(node, m, n): + if not node: + return None + if m - 1 == n: + return node + l = dfs(node.left, m, n + 1) + r = dfs(node.right, m, n + 1) + if l and r: + return node + return l if l else r + + m = depth(root) + return dfs(root, m, 0) + + +if __name__ == "__main__": + obj = Solution() + r1 = leetcode.treenode_build(root=[3, 5, 1, 6, 2, 0, 8, None, None, 7, 4]) + r2 = leetcode.treenode_build(root=[1]) + r3 = leetcode.treenode_build(root=[0, 1, 3, None, 2]) + print(obj.lcaDeepestLeaves(r1)) + print(obj.lcaDeepestLeaves(r2)) + print(obj.lcaDeepestLeaves(r3)) diff --git a/marbles_in_bags.c b/marbles_in_bags.c index 71c2560..95c1ee1 100644 --- a/marbles_in_bags.c +++ b/marbles_in_bags.c @@ -1,6 +1,5 @@ // 2551. Put Marbles in Bags -#include <stdio.h> -#include <stdlib.h> +#include "leetcode.h" /* * you have 'k' bags. you are given a 0-indexed integer array 'weights' where @@ -19,25 +18,24 @@ int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } -long long putMarbles(int *weights, int weights_size, int k) { - int n = weights_size; - if (n == k || k == 1) +long long putMarbles(int *weights, int weightsSize, int k) { + if (weightsSize == k || k == 1) return 0; - int *data = malloc((n - 1) * sizeof(int)); - for (int i = 0; i < n - 1; i++) - data[i] = weights[i] + weights[i + 1]; - qsort(data, n - 1, sizeof(int), cmp); - long long min = weights[0] + weights[n - 1]; - long long max = weights[0] + weights[n - 1]; + int *pairs = (int *)malloc((weightsSize - 1) * sizeof(int)); + for (int i = 0; i < weightsSize - 1; i++) + pairs[i] = weights[i] + weights[i + 1]; + qsort(pairs, weightsSize - 1, sizeof(int), cmp); + long long min, max; + min = max = weights[0] + weights[weightsSize - 1]; for (int i = 0; i < k - 1; i++) { - min += data[i]; - max += data[n - 2 - i]; + min += pairs[i]; + max += pairs[weightsSize - 2 - i]; } return max - min; } int main() { int w1[] = {1, 3, 5, 1}, w2[] = {1, 3}; - printf("%lld\n", putMarbles(w1, 4, 2)); // expect: 4 - printf("%lld\n", putMarbles(w2, 2, 2)); // expect: 0 + printf("%lld\n", putMarbles(w1, ARRAY_SIZE(w1), 2)); // expect: 4 + printf("%lld\n", putMarbles(w2, ARRAY_SIZE(w2), 2)); // expect: 0 } diff --git a/marbles_in_bags.py b/marbles_in_bags.py new file mode 100644 index 0000000..0cb520c --- /dev/null +++ b/marbles_in_bags.py @@ -0,0 +1,33 @@ +# 2551. Put Marbles in Bags + +""" +you have 'k' bags. you are given a 0-indexed integer array 'weights' where +'weights[i]' is the weight of the i'th marble. you are also given the integer +'k'. divide the marbles into the 'k' bags according to the following rules +- no bag is empty +- if the i'th marble and the j'th marble are in a bag, then all the marbles +with an index between the i'th and j'th indices should also be in that same +bag. +- if a bag onsists of all the marbles with an index from 'i' to 'j' +inclusively, then the cost of the bag is 'weights[i] + weights[j]' the score +after distributing the marbles is the sum of the costs of all the 'k' bags. +return the difference between the maximum and minimum scores among marble +distributions +""" + + +class Solution(object): + def putMarbles(self, weights, k): + """ + :type weights: List[int] + :type k: int + :rtype: int + """ + pairs = sorted([weights[i] + weights[i + 1] for i in range(len(weights) - 1)]) + return sum(pairs[len(pairs) - k + 1 :]) - sum(pairs[: k - 1]) + + +if __name__ == "__main__": + obj = Solution() + print(obj.putMarbles(weights=[1, 3, 5, 1], k=2)) + print(obj.putMarbles(weights=[1, 3], k=2)) diff --git a/max_candies_allocated_k_children.c b/max_candies_allocated_k_children.c new file mode 100644 index 0000000..45f105c --- /dev/null +++ b/max_candies_allocated_k_children.c @@ -0,0 +1,32 @@ +// 2226. Maximum Candies Allocated to K Children +#include "leetcode.h" + +/* + * you are given a 0-indexed integer array 'candies'. each element in the array + * denotes a pile of candies of size 'candies[i]'. you can divide each pile into + * any number of sub piles, but you cannot merge two piles together. you are + * also given an integer 'k'. you should allocate piles of candies to 'k' + * children such that each child gets the same number of candies. each child can + * be allocated candies from only one pile of candies, and some piles of candies + * may go unused. return the maximum number of candies each child can get + */ + +int maximumCandies(int *candies, int candiesSize, long long k) { + int l = 0, r = 1e7; + while (l < r) { + long long mid = (l + r + 1) / 2, cnt = 0; + for (int i = 0; i < candiesSize && cnt < k; ++i) + cnt += candies[i] / mid; + if (cnt >= k) + l = mid; + else + r = mid - 1; + } + return l; +} + +int main() { + int c1[] = {5, 8, 6}, c2[] = {2, 5}; + printf("%d\n", maximumCandies(c1, ARRAY_SIZE(c1), 3)); // expect: 5 + printf("%d\n", maximumCandies(c2, ARRAY_SIZE(c2), 11)); // expect: 0 +} diff --git a/max_candies_allocated_k_children.py b/max_candies_allocated_k_children.py new file mode 100644 index 0000000..139ab80 --- /dev/null +++ b/max_candies_allocated_k_children.py @@ -0,0 +1,34 @@ +# 2226. Maximum Candies Allocated to K Children + +""" +you are given a 0-indexed integer array 'candies'. each element in the array +denotes a pile of candies of size 'candies[i]'. you can divide each pile into +any number of sub piles, but you cannot merge two piles together. you are +also given an integer 'k'. you should allocate piles of candies to 'k' +children such that each child gets the same number of candies. each child can +be allocated candies from only one pile of candies, and some piles of candies +may go unused. return the maximum number of candies each child can get +""" + + +class Solution(object): + def maximumCandies(self, candies, k): + """ + :type candies: List[int] + :type k: int + :rtype: int + """ + l, r = 0, sum(candies) / k + while l < r: + mid = (l + r + 1) / 2 + if k > sum(i / mid for i in candies): + r = mid - 1 + else: + l = mid + return l + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumCandies(candies=[5, 8, 6], k=3)) + print(obj.maximumCandies(candies=[2, 5], k=11)) diff --git a/max_num_point_grid_query.c b/max_num_point_grid_query.c new file mode 100644 index 0000000..1fbe18a --- /dev/null +++ b/max_num_point_grid_query.c @@ -0,0 +1,122 @@ +// 2503. Maximum Number of Points From Grid Queries +#include "leetcode.h" + +/* + * you are given an 'm x n' integer matrix 'grid' and an array 'queries' of size + * 'k'. find an array 'answer' of size 'k' such that for each integer + * 'queries[i]' start in the top left cell of the matrix and repeat the + * following process: if 'queries[i]' is strictly greater than the value of the + * current cell that you are in, then you get one point if it is your first time + * visiting that cell, and you can move to any adjacent cell in all 4 + * directions, otherwise you do not get any points, and you end this process. + * after the process 'answer[i]' is the maximum number of ponts you can get. + * note that for each query, yu are allowed to visit the same cell multiple + * times. + */ + +struct list { + int val; + int x; + int y; +}; + +struct pp { + int val; + int place; +}; + +int cmp(const void *a, const void *b) { + return (*(struct pp *)a).val - (*(struct pp *)b).val; +} + +void input(int **grid, int gridSize, int gridColSize, int i, int j, + struct list *helper, int *cnt, bool **used, int *curr_point, + int curr_val) { + used[i][j] = true; + if (curr_val > grid[i][j]) { + *curr_point += 1; + if (i - 1 >= 0 && !used[i - 1][j]) + input(grid, gridSize, gridColSize, i - 1, j, helper, cnt, used, + curr_point, curr_val); + if (i + 1 < gridSize && !used[i + 1][j]) + input(grid, gridSize, gridColSize, i + 1, j, helper, cnt, used, + curr_point, curr_val); + if (j - 1 >= 0 && !used[i][j - 1]) + input(grid, gridSize, gridColSize, i, j - 1, helper, cnt, used, + curr_point, curr_val); + if (j + 1 < gridColSize && !used[i][j + 1]) + input(grid, gridSize, gridColSize, i, j + 1, helper, cnt, used, + curr_point, curr_val); + } else { + helper[*cnt].val = grid[i][j]; + helper[*cnt].x = i; + helper[*cnt].y = j; + (*cnt)++; + } +} + +int *maxPoints(int **grid, int gridSize, int *gridColSize, int *queries, + int queriesSize, int *returnSize) { + int curr_point = 0, c1 = 0, c2 = 0; + struct list *h1 = (struct list *)malloc((gridSize * (*gridColSize)) * + sizeof(struct list *)); + struct list *h2 = (struct list *)malloc((gridSize * (*gridColSize)) * + sizeof(struct list *)); + struct pp *revis = (struct pp *)malloc(queriesSize * sizeof(struct pp)); + for (int i = 0; i < queriesSize; i++) { + revis[i].val = queries[i]; + revis[i].place = i; + } + qsort(revis, queriesSize, sizeof(struct pp), cmp); + *returnSize = queriesSize; + int *ans = (int *)malloc(queriesSize * sizeof(int)); + bool **used = (bool **)malloc(queriesSize * sizeof(bool *)); + for (int i = 0; i < gridSize; i++) + used[i] = (bool *)calloc(*gridColSize, sizeof(bool)); + input(grid, gridSize, *gridColSize, 0, 0, h1, &c1, used, &curr_point, + revis[0].val); + ans[revis[0].place] = curr_point; + for (int i = 1; i < queriesSize; i++) { + if ((i & 1) == 1) { + c2 = 0; + for (int j = 0; j < c1; j++) + input(grid, gridSize, *gridColSize, h1[j].x, h1[j].y, h2, &c2, used, + &curr_point, revis[i].val); + } else { + c1 = 0; + for (int j = 0; j < c2; j++) + input(grid, gridSize, *gridColSize, h2[j].x, h2[j].y, h1, &c1, used, + &curr_point, revis[i].val); + } + ans[revis[i].place] = curr_point; + } + free(revis); + free(h1); + free(h2); + for (int i = 0; i < gridSize; i++) + free(used[i]); + free(used); + return ans; +} + +int main() { + int g1i[3][3] = {{1, 2, 3}, {2, 5, 7}, {3, 5, 1}}, q1[] = {5, 6, 2}, rs1; + int g2i[2][3] = {{5, 2, 1}, {1, 1, 2}}, q2[] = {3}, rs2; + struct two_d_arr g1, g2; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + int *mp1 = + maxPoints(g1.arr, g1.row_size, g1.col_size, q1, ARRAY_SIZE(q1), &rs1); + int *mp2 = + maxPoints(g2.arr, g2.row_size, g2.col_size, q2, ARRAY_SIZE(q2), &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", mp1[i]); // expect: 5 8 1 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", mp2[i]); // expect: 0 + printf("\n"); + free(mp1); + free(mp2); + two_d_arr_free(&g1); + two_d_arr_free(&g2); +} diff --git a/max_num_point_grid_query.py b/max_num_point_grid_query.py new file mode 100644 index 0000000..642a2ec --- /dev/null +++ b/max_num_point_grid_query.py @@ -0,0 +1,49 @@ +# 2503. Maximum Number of Points From Grid Queries +import heapq +from bisect import bisect_left + +""" +you are given an 'm x n' integer matrix 'grid' and an array 'queries' of size +'k'. find an array 'answer' of size 'k' such that for each integer +'queries[i]' start in the top left cell of the matrix and repeat the +following process: if 'queries[i]' is strictly greater than the value of the +current cell that you are in, then you get one point if it is your first time +visiting that cell, and you can move to any adjacent cell in all 4 +directions, otherwise you do not get any points, and you end this process. +after the process 'answer[i]' is the maximum number of ponts you can get. +note that for each query, yu are allowed to visit the same cell multiple +times. +""" + + +class Solution(object): + def maxPoints(self, grid, queries): + """ + :type grid: List[List[int]] + :type queries: List[int] + :rtype: List[int] + """ + n, m = len(grid), len(grid[0]) + heap = [(grid[0][0], 0, 0)] + v, order = {(0, 0)}, [] + while len(heap) > 0: + curr, i, j = heapq.heappop(heap) + order.append(curr) + for x, y in [(i - 1, j), (i, j - 1), (i + 1, j), (i, j + 1)]: + if 0 <= x < n and 0 <= y < m and (x, y) not in v: + v.add((x, y)) + heapq.heappush(heap, (grid[x][y], x, y)) + high = -1 + for i in range(len(order)): + high = max(high, order[i]) + order[i] = high + ans = [] + for i in queries: + ans.append(bisect_left(order, i)) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxPoints(grid=[[1, 2, 3], [2, 5, 7], [3, 5, 1]], queries=[5, 6, 2])) + print(obj.maxPoints(grid=[[5, 2, 1], [1, 1, 2]], queries=[3])) diff --git a/max_value_ordered_triplet1.c b/max_value_ordered_triplet1.c new file mode 100644 index 0000000..9a62e4a --- /dev/null +++ b/max_value_ordered_triplet1.c @@ -0,0 +1,28 @@ +// 2873. Maximum Value of an Ordered Triplet I +#include "leetcode.h" + +/* + * you are given a 0-indexed integer array 'nums'. return the maximum value over + * all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such + * triplets have a negative value, return 0. the value of a triplet of indices + * '(i, j, k)' is equal to '(nums[i] - nums[j]) * nums[k]' + */ + +long long maximumTripletValue(int *nums, int numsSize) { + if (numsSize < 3) + return 0; + long long ans = 0, curr = nums[0], diff = 0; + for (int i = 1; i < numsSize; i++) { + ans = fmax(ans, (long long)diff * nums[i]); + diff = fmax(diff, curr - nums[i]); + curr = fmax(curr, nums[i]); + } + return ans; +} + +int main() { + int n1[] = {12, 6, 1, 2, 7}, n2[] = {1, 10, 3, 4, 19}, n3[] = {1, 2, 3}; + printf("%lld\n", maximumTripletValue(n1, ARRAY_SIZE(n1))); // expect: 77 + printf("%lld\n", maximumTripletValue(n2, ARRAY_SIZE(n2))); // expect: 133 + printf("%lld\n", maximumTripletValue(n3, ARRAY_SIZE(n3))); // expect: 0 +} diff --git a/max_value_ordered_triplet1.py b/max_value_ordered_triplet1.py new file mode 100644 index 0000000..e91c340 --- /dev/null +++ b/max_value_ordered_triplet1.py @@ -0,0 +1,32 @@ +# 2873. Maximum Value of an Ordered Triplet I + +""" +you are given a 0-indexed integer array 'nums'. return the maximum value over +all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such +triplets have a negative value, return 0. the value of a triplet of indices +'(i, j, k)' is equal to '(nums[i] - nums[j]) nums[k]' +""" + + +class Solution(object): + def maximumTripletValue(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n = len(nums) + if n < 3: + return 0 + ans, curr, diff = 0, nums[0], 0 + for i in range(1, n): + ans = max(ans, diff * nums[i]) + diff = max(diff, curr - nums[i]) + curr = max(curr, nums[i]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumTripletValue(nums=[12, 6, 1, 2, 7])) + print(obj.maximumTripletValue(nums=[1, 10, 3, 4, 19])) + print(obj.maximumTripletValue(nums=[1, 2, 3])) diff --git a/max_value_ordered_triplet2.c b/max_value_ordered_triplet2.c new file mode 100644 index 0000000..d8151bd --- /dev/null +++ b/max_value_ordered_triplet2.c @@ -0,0 +1,28 @@ +// 2874. Maximum Value of an Ordered Triplet II +#include "leetcode.h" + +/* + * you are given a 0-indexed integer array 'nums'. return the maximum value over + * all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such + * triplets have a negative value, return 0. the value of a triplet of indices + * '(i, j, k)' is equal to '(nums[i] - nums[j]) * nums[k]' + */ + +long long maximumTripletValue(int *nums, int numsSize) { + if (numsSize < 3) + return 0; + long long ans = 0, curr = nums[0], diff = 0; + for (int i = 1; i < numsSize; i++) { + ans = fmax(ans, (long long)diff * nums[i]); + diff = fmax(diff, curr - nums[i]); + curr = fmax(curr, nums[i]); + } + return ans; +} + +int main() { + int n1[] = {12, 6, 1, 2, 7}, n2[] = {1, 10, 3, 4, 19}, n3[] = {1, 2, 3}; + printf("%lld\n", maximumTripletValue(n1, ARRAY_SIZE(n1))); // expect: 77 + printf("%lld\n", maximumTripletValue(n2, ARRAY_SIZE(n2))); // expect: 133 + printf("%lld\n", maximumTripletValue(n3, ARRAY_SIZE(n3))); // expect: 0 +} diff --git a/max_value_ordered_triplet2.py b/max_value_ordered_triplet2.py new file mode 100644 index 0000000..5673d61 --- /dev/null +++ b/max_value_ordered_triplet2.py @@ -0,0 +1,32 @@ +# 2874. Maximum Value of an Ordered Triplet II + +""" +you are given a 0-indexed integer array 'nums'. return the maximum value over +all triplets of indices '(i, j, k)' such that 'i < j < k'. if all such +triplets have a negative value, return 0. the value of a triplet of indices +'(i, j, k)' is equal to '(nums[i] - nums[j]) nums[k]' +""" + + +class Solution(object): + def maximumTripletValue(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n = len(nums) + if n < 3: + return 0 + ans, curr, diff = 0, nums[0], 0 + for i in range(1, n): + ans = max(ans, diff * nums[i]) + diff = max(diff, curr - nums[i]) + curr = max(curr, nums[i]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maximumTripletValue(nums=[12, 6, 1, 2, 7])) + print(obj.maximumTripletValue(nums=[1, 10, 3, 4, 19])) + print(obj.maximumTripletValue(nums=[1, 2, 3])) diff --git a/min_cost_walk_weight_graph.py b/min_cost_walk_weight_graph.py new file mode 100644 index 0000000..b1d2415 --- /dev/null +++ b/min_cost_walk_weight_graph.py @@ -0,0 +1,72 @@ +# 3108. Minimum Cost Walk in Weighted Graph + +""" +there is an undirected weighted graph with 'n' vertices labeled from 0 to 'n +- 1'. you are given the integer 'n' and an array 'edges', where 'edges[i] = +[u_i, v_i, w_i]' indicates that there is an edge between vertices 'u_i' and +'v_i' with a weight of 'w_i'. a walk on the graph is a sequence of vertices +and edges. the walk starts and ends with a vertex, and each edge connects the +vertex that comes before it and the vertex that comes after it. it's +important to note that a walk may visit the same edge or vertex more than +once. return the array 'answer' where 'answer[i]' denotes the minimum cost of +a walk for query 'i'. +""" + + +class UnionFind: + def __init__(self, size): + self.parent = [i for i in range(size)] + self.rank = [0 for _ in range(size)] + self.d = [~0 for _ in range(size)] + + def find(self, node): + if self.parent[node] != node: + self.parent[node] = self.find(self.parent[node]) + return self.parent[node] + + def union(self, a, b, val): + p1, p2 = self.find(a), self.find(b) + if self.rank[p1] > self.rank[p2]: + self.parent[p2] = p1 + self.d[p1] &= self.d[p2] & val + elif self.rank[p1] < self.rank[p2]: + self.parent[p1] = p2 + self.d[p2] &= self.d[p1] & val + else: + self.parent[p1] = p2 + self.d[p2] &= self.d[p1] & val + self.rank[p2] += 1 + + +class Solution(object): + def minimumCost(self, n, edges, query): + """ + :type n: int + :type edges: List[List[int]] + :type query: List[List[int]] + :rtype: List[int] + """ + uf = UnionFind(n) + for u, v, w in edges: + uf.union(u, v, w) + ans = [] + for u, v in query: + if uf.find(u) != uf.find(v): + ans.append(-1) + else: + ans.append(uf.d[uf.find(u)]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.minimumCost( + n=5, edges=[[0, 1, 7], [1, 3, 7], [1, 2, 1]], query=[[0, 3], [3, 4]] + ) + ) + print( + obj.minimumCost( + n=3, edges=[[0, 2, 7], [0, 1, 15], [1, 2, 6], [1, 2, 1]], query=[[1, 2]] + ) + ) diff --git a/min_idx_valid_split.c b/min_idx_valid_split.c new file mode 100644 index 0000000..fbb2b98 --- /dev/null +++ b/min_idx_valid_split.c @@ -0,0 +1,43 @@ +// 2780. Minimum Index of a Valid Split +#include "leetcode.h" + +/* + * an element 'x' of an integer array 'arr' of length 'm' is dominant if more + * than half the elements of 'arr' have a value of 'x'. you are given a + * 0-indexed integer array 'nums' of length 'n' with one dominant element. you + * can split 'nums' at an index 'i' into two arrays 'nums[0, ..., i]' and + * 'nums[i + 1, ..., n - 1]', but the split is only valid if '0 <= i < - 1' and + * the two arrays have the same dominant element. return the minimum index of a + * valid split. if no split exists, return -1. + */ + +int minimumIndex(int *nums, int numsSize) { + int dominant = nums[0], cnt = 0; + for (int i = 0; i < numsSize; i++) { + cnt = nums[i] == dominant ? cnt + 1 : cnt - 1; + if (!cnt) { + dominant = nums[i]; + cnt = 1; + } + } + int left = 0; + for (int i = 0; i < numsSize; i++) + if (nums[i] == dominant) + left++; + cnt = 0; + for (int i = 0; i < numsSize; i++) { + if (nums[i] == dominant) + cnt++; + if (cnt * 2 > (i + 1) && (left - cnt) * 2 > (numsSize - i - 1)) + return i; + } + return -1; +} + +int main() { + int n1[] = {1, 2, 2, 2}, n2[] = {2, 1, 3, 1, 1, 1, 7, 1, 2, 1}, + n3[] = {3, 3, 3, 3, 7, 2, 2}; + printf("%d\n", minimumIndex(n1, ARRAY_SIZE(n1))); // expect: 2 + printf("%d\n", minimumIndex(n2, ARRAY_SIZE(n2))); // expect: 4 + printf("%d\n", minimumIndex(n3, ARRAY_SIZE(n3))); // expect: -1 +} diff --git a/min_idx_valid_split.py b/min_idx_valid_split.py new file mode 100644 index 0000000..a03a65c --- /dev/null +++ b/min_idx_valid_split.py @@ -0,0 +1,35 @@ +# 2780. Minimum Index of a Valid Split +from collections import Counter + +""" +an element 'x' of an integer array 'arr' of length 'm' is dominant if more +than half the elements of 'arr' have a value of 'x'. you are given a +0-indexed integer array 'nums' of length 'n' with one dominant element. you +can split 'nums' at an index 'i' into two arrays 'nums[0, ..., i]' and +'nums[i + 1, ..., n - 1]', but the split is only valid if '0 <= i < - 1' and +the two arrays have the same dominant element. return the minimum index of a +valid split. if no split exists, return -1. +""" + + +class Solution(object): + def minimumIndex(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + dominant, cnt = max(Counter(nums).items(), key=lambda x: x[1]) + left, split = 0, 2 * cnt - len(nums) + if split < 2: + return -1 + for i, j in enumerate(nums): + left += 2 * (j == dominant) + if 1 < left - i <= split: + return i + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumIndex(nums=[1, 2, 2, 2])) + print(obj.minimumIndex(nums=[2, 1, 3, 1, 1, 1, 7, 1, 2, 1])) + print(obj.minimumIndex(nums=[3, 3, 3, 3, 7, 2, 2])) diff --git a/min_num_work_session.c b/min_num_work_session.c new file mode 100644 index 0000000..54f4190 --- /dev/null +++ b/min_num_work_session.c @@ -0,0 +1,58 @@ +// 1986. Minimum Number of Work Sessions to Finish the Tasks +#include "leetcode.h" + +/* + * there are 'n' tasks assigned to you. the task times are represented as an + * integer array 'tasks' of length 'n' where the i'th task takes 'tasks[i]' + * hours to finish. a work session is when you work for at most 'sessionTime' + * consecutive hours, and then take a break. given 'tasks' and 'sessionTime', + * return the minimum number of work sessions needed to finish all the tasks + * following the conditions. the tests are generated such that 'sessionTime' is + * greater or equal to the maximum element in 'tasks[i]'. + */ + +int work(int *tasks, int tasksSize, int completed, int sessionTime, + int time_remaining, int **dp) { + int cnt, min = INT_MAX; + if (completed == (1 << tasksSize) - 1) + return 0; + if (dp[completed][time_remaining] != -1) + return dp[completed][time_remaining]; + for (int i = 0; i < tasksSize; i++) { + if (!(completed & (1 << i))) { + completed |= (1 << i); + if (time_remaining - tasks[i] < 0) + cnt = work(tasks, tasksSize, completed, sessionTime, + sessionTime - tasks[i], dp) + + 1; + else + cnt = work(tasks, tasksSize, completed, sessionTime, + time_remaining - tasks[i], dp); + min = fmin(min, cnt); + completed &= ~(1 << i); + } + } + dp[completed][time_remaining] = min; + return min; +} + +int minSessions(int *tasks, int tasksSize, int sessionTime) { + int **dp = (int **)malloc((1 << tasksSize) * sizeof(int *)); + for (int i = 0; i < (1 << tasksSize); i++) { + dp[i] = (int *)malloc((sessionTime + 1) * sizeof(int)); + for (int j = 0; j <= sessionTime; j++) + dp[i][j] = -1; + } + int ans = work(tasks, tasksSize, 0, sessionTime, 0, dp); + for (int i = 0; i < (1 << tasksSize); i++) + free(dp[i]); + free(dp); + return ans; +} + +int main() { + int t1[] = {1, 2, 3}, t2[] = {3, 1, 3, 1, 1}, t3[] = {1, 2, 3, 4, 5}; + printf("%d\n", minSessions(t1, ARRAY_SIZE(t1), 3)); // expect: 2 + printf("%d\n", minSessions(t2, ARRAY_SIZE(t2), 8)); // expect: 2 + printf("%d\n", minSessions(t3, ARRAY_SIZE(t3), 15)); // expect: 1 +} diff --git a/min_num_work_session.py b/min_num_work_session.py new file mode 100644 index 0000000..9c0ca12 --- /dev/null +++ b/min_num_work_session.py @@ -0,0 +1,41 @@ +# 1986. Minimum Number of Work Sessions to Finish the Tasks + +""" +there are 'n' tasks assigned to you. the task times are represented as an +integer array 'tasks' of length 'n' where the i'th task takes 'tasks[i]' +hours to finish. a work session is when you work for at most 'sessionTime' +consecutive hours, and then take a break. given 'tasks' and 'sessionTime', +return the minimum number of work sessions needed to finish all the tasks +following the conditions. the tests are generated such that 'sessionTime' is +greater or equal to the maximum element in 'tasks[i]'. +""" + + +class Solution(object): + def minSessions(self, tasks, sessionTime): + """ + :type tasks: List[int] + :type sessionTime: int + :rtype: int + """ + n = len(tasks) + + def dp(mask): + if mask == 0: + return (1, 0) + res = (float("inf"), float("inf")) + for i in range(n): + if mask & (1 << i): + pieces, prev = dp(mask - (1 << i)) + full = prev + tasks[i] > sessionTime + res = min(res, (pieces + full, tasks[i] + (1 - full) * prev)) + return res + + return dp((1 << n) - 1)[0] + + +if __name__ == "__main__": + obj = Solution() + print(obj.minSessions(tasks=[1, 2, 3], sessionTime=3)) + print(obj.minSessions(tasks=[3, 1, 3, 1, 1], sessionTime=8)) + print(obj.minSessions(tasks=[1, 2, 3, 4, 5], sessionTime=15)) diff --git a/min_ops_bin_arr_1.c b/min_ops_bin_arr_1.c new file mode 100644 index 0000000..c589165 --- /dev/null +++ b/min_ops_bin_arr_1.c @@ -0,0 +1,29 @@ +// 3191. Minimum Operations to Make Binary Array Elements Equal to One I +#include "leetcode.h" + +/* + * you are given a binary array 'nums'. you can do the following operation on + * the array any number of times (possibly zero): choose any three consecutive + * elements from the array and flip all of them. flipping an element means + * changing its value from 0 to 1, and from 1 to 0. return the minimum number of + * operations required needed to make all elements in 'nums' equal to 1. if it + * is impossible, return -1. + */ + +int minOperations(int *nums, int numsSize) { + int cnt = 0; + for (int i = 0; i < numsSize - 2; i++) + if (!nums[i]) { + nums[i] ^= 1; + nums[i + 1] ^= 1; + nums[i + 2] ^= 1; + cnt++; + } + return nums[numsSize - 2] && nums[numsSize - 1] ? cnt : -1; +} + +int main() { + int n1[] = {0, 1, 1, 1, 0, 0}, n2[] = {0, 1, 1, 1}; + printf("%d\n", minOperations(n1, ARRAY_SIZE(n1))); // expect: 3 + printf("%d\n", minOperations(n2, ARRAY_SIZE(n2))); // expect: -1 +} diff --git a/min_ops_bin_arr_1.py b/min_ops_bin_arr_1.py new file mode 100644 index 0000000..eed3fea --- /dev/null +++ b/min_ops_bin_arr_1.py @@ -0,0 +1,32 @@ +# 3191. Minimum Operations to Make Binary Array Elements Equal to One I + +""" +you are given a binary array 'nums'. you can do the following operation on +the array any number of times (possibly zero): choose any three consecutive +elements from the array and flip all of them. flipping an element means +changing its value from 0 to 1, and from 1 to 0. return the minimum number of +operations required needed to make all elements in 'nums' equal to 1. if it +is impossible, return -1. +""" + + +class Solution(object): + def minOperations(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + cnt, n = 0, len(nums) + for i in range(n - 2): + if nums[i] == 0: + nums[i] ^= 1 + nums[i + 1] ^= 1 + nums[i + 2] ^= 1 + cnt += 1 + return cnt if nums[n - 2] == 1 and nums[n - 1] == 1 else -1 + + +if __name__ == "__main__": + obj = Solution() + print(obj.minOperations(nums=[0, 1, 1, 1, 0, 0])) + print(obj.minOperations(nums=[0, 1, 1, 1])) diff --git a/min_ops_uni_val_grid.c b/min_ops_uni_val_grid.c new file mode 100644 index 0000000..aa2f025 --- /dev/null +++ b/min_ops_uni_val_grid.c @@ -0,0 +1,49 @@ +// 2033. Minimum Operations to Make a Uni-Value Grid +#include "leetcode.h" + +/* + * you are given a 2d integer 'grid' of size 'm x n' and an integer 'x'. in one + * operation, you can add 'x' to or subtract 'x' from any element in the 'grid'. + * a uni-value grid is a grid where all the elements of it are equal. return the + * minimum number of operations to make the grid uni-valued. if it is not + * possible, return -1. + */ + +int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } + +int minOperations(int **grid, int gridSize, int *gridColSize, int x) { + int n = gridSize * (*gridColSize), idx = 0, mod = grid[0][0] % x; + int *vals = (int *)malloc(n * sizeof(int)); + for (int i = 0; i < gridSize; ++i) + for (int j = 0; j < *gridColSize; ++j) { + vals[idx] = grid[i][j]; + if (vals[idx++] % x != mod) { + free(vals); + return -1; + } + } + qsort(vals, n, sizeof(int), cmp); + int med = vals[n / 2], ans = 0; + for (int i = 0; i < n; i++) + ans += abs(med - vals[i]) / x; + free(vals); + return ans; +} + +int main() { + int g1i[2][2] = {{2, 4}, {6, 8}}, g2i[2][2] = {{1, 5}, {2, 3}}, + g3i[2][2] = {{1, 2}, {3, 4}}; + struct two_d_arr g1, g2, g3; + two_d_arr_init(&g1, ARRAY_SIZE(g1i), ARRAY_SIZE(g1i[0]), g1i); + two_d_arr_init(&g2, ARRAY_SIZE(g2i), ARRAY_SIZE(g2i[0]), g2i); + two_d_arr_init(&g3, ARRAY_SIZE(g3i), ARRAY_SIZE(g3i[0]), g3i); + printf("%d\n", + minOperations(g1.arr, g1.row_size, g1.col_size, 2)); // expect: 4 + printf("%d\n", + minOperations(g2.arr, g2.row_size, g2.col_size, 1)); // expect: 5 + printf("%d\n", + minOperations(g3.arr, g3.row_size, g3.col_size, 2)); // expect: -1 + two_d_arr_free(&g1); + two_d_arr_free(&g2); + two_d_arr_free(&g3); +} diff --git a/min_ops_uni_val_grid.py b/min_ops_uni_val_grid.py new file mode 100644 index 0000000..b417eb2 --- /dev/null +++ b/min_ops_uni_val_grid.py @@ -0,0 +1,32 @@ +# 2033. Minimum Operations to Make a Uni-Value Grid + +""" +you are given a 2d integer 'grid' of size 'm x n' and an integer 'x'. in one +operation, you can add 'x' to or subtract 'x' from any element in the 'grid'. +a uni-value grid is a grid where all the elements of it are equal. return the +minimum number of operations to make the grid uni-valued. if it is not +possible, return -1. +""" + + +class Solution(object): + def minOperations(self, grid, x): + """ + :type grid: List[List[int]] + :type x: int + :rtype: int + """ + vals = sorted([i for j in grid for i in j]) + diff = [abs(i - vals[0]) % x for i in vals] + if any(i != 0 for i in diff): + return -1 + med = vals[len(vals) // 2] + ans = sum(abs(i - med) // x for i in vals) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minOperations(grid=[[2, 4], [6, 8]], x=2)) + print(obj.minOperations(grid=[[1, 5], [2, 3]], x=1)) + print(obj.minOperations(grid=[[1, 2], [3, 4]], x=2)) diff --git a/min_time_repair_car.c b/min_time_repair_car.c new file mode 100644 index 0000000..ddd9dce --- /dev/null +++ b/min_time_repair_car.c @@ -0,0 +1,31 @@ +// 2594. Minimum Time to Repair Cars +#include "leetcode.h" + +/* + * you are given an integer array 'ranks' representing the ranks of some + * mechanics. 'ranks[i]' is the rank of the i'th mechanic. a mechanic with a + * rank 'r' can repair 'n' cars in 'r * n^2' minutes. you are also given an + * integer 'cars' representing the total number of cars waiting in the garage to + * be repaired. return the minimum time taken to repair all the cars. note: all + * the mechanics can repair the cars simultaneously. + */ + +long long repairCars(int *ranks, int ranksSize, int cars) { + long long left = 0, right = 1e14; + while (left < right) { + long long mid = left + (right - left) / 2, cnt = 0; + for (int i = 0; i < ranksSize; i++) + cnt += sqrt(mid / ranks[i]); + if (cnt < cars) + left = mid + 1; + else + right = mid; + } + return left; +} + +int main() { + int r1[] = {4, 2, 3, 1}, r2[] = {5, 1, 8}; + printf("%lld\n", repairCars(r1, ARRAY_SIZE(r1), 10)); // expect: 16 + printf("%lld\n", repairCars(r2, ARRAY_SIZE(r2), 6)); // expect: 16 +} diff --git a/min_time_repair_car.py b/min_time_repair_car.py new file mode 100644 index 0000000..7f8db29 --- /dev/null +++ b/min_time_repair_car.py @@ -0,0 +1,36 @@ +# 2594. Minimum Time to Repair Cars +import heapq +from collections import Counter + +""" +you are given an integer array 'ranks' representing the ranks of some +mechanics. 'ranks[i]' is the rank of the i'th mechanic. a mechanic with a +rank 'r' can repair 'n' cars in 'r n^2' minutes. you are also given an +integer 'cars' representing the total number of cars waiting in the garage to +be repaired. return the minimum time taken to repair all the cars. note: all +the mechanics can repair the cars simultaneously. +""" + + +class Solution(object): + def repairCars(self, ranks, cars): + """ + :type ranks: List[int] + :type cars: int + :rtype: int + """ + cnt = Counter(ranks) + h = [[i, i, 1, cnt[i]] for i in cnt] + heapq.heapify(h) + while cars > 0: + time, rank, k, count = heapq.heappop(h) + cars -= count + k += 1 + heapq.heappush(h, [rank * k * k, rank, k, count]) + return time + + +if __name__ == "__main__": + obj = Solution() + print(obj.repairCars(ranks=[4, 2, 3, 1], cars=10)) + print(obj.repairCars(ranks=[5, 1, 8], cars=6)) diff --git a/min_xor_sum_two_arr.c b/min_xor_sum_two_arr.c new file mode 100644 index 0000000..492a0f8 --- /dev/null +++ b/min_xor_sum_two_arr.c @@ -0,0 +1,35 @@ +// 1879. Minimum XOR Sum of Two Arrays +#include "leetcode.h" + +/* + * you are given two integer arrays 'nums1' and 'nums2' of length 'n'. the xor + * sum of the two integer arrays is '(nums1[0] ^ nums2[0]) + (nums1[1] ^ + * nums2[1]) + ...' (0-indexed). rearrange the elements of 'nums2' such that + * resulting xor sum is minimised. return the xor sum after the rearrangement. + */ + +static int dp[1 << 14] = {[0 ... 16383] = INT_MAX}; + +int dfs(int *nums1, int *nums2, int n, int i, int mask) { + if (i >= n) + return 0; + if (dp[mask] == -1) + for (int j = 0; j < n; ++j) + if (!(mask & (1 << j))) + dp[mask] = + fmin(dp[mask], (nums1[i] ^ nums2[j]) + + dfs(nums1, nums2, n, i + 1, mask + (1 << j))); + return dp[mask]; +} + +int minimumXORSum(int *nums1, int nums1Size, int *nums2, int nums2Size) { + return dfs(nums1, nums2, nums1Size, 0, 0); +} + +int main() { + int n11[] = {1, 2}, n21[] = {2, 3}, n12[] = {1, 0, 3}, n22[] = {5, 3, 4}; + printf("%d\n", minimumXORSum(n11, ARRAY_SIZE(n11), n21, + ARRAY_SIZE(n21))); // expect: 2 + printf("%d\n", minimumXORSum(n12, ARRAY_SIZE(n12), n22, + ARRAY_SIZE(n22))); // expect: 8 +} diff --git a/min_xor_sum_two_arr.py b/min_xor_sum_two_arr.py new file mode 100644 index 0000000..f54d44b --- /dev/null +++ b/min_xor_sum_two_arr.py @@ -0,0 +1,35 @@ +# 1879. Minimum XOR Sum of Two Arrays + +""" +you are given two integer arrays 'nums1' and 'nums2' of length 'n'. the xor +sum of the two integer arrays is '(nums1[0] ^ nums2[0]) + (nums1[1] ^ +nums2[1]) + ...' (0-indexed). rearrange the elements of 'nums2' such that +resulting xor sum is minimised. return the xor sum after the rearrangement. +""" + + +class Solution(object): + def minimumXORSum(self, nums1, nums2): + """ + :type nums1: List[int] + :type nums2: List[int] + :rtype: int + """ + + def dfs(mask): + i = bin(mask).count("1") + if i >= len(nums1): + return 0 + return min( + (nums1[i] ^ nums2[j]) + dfs(mask + (1 << j)) + for j in range(len(nums2)) + if mask & (1 << j) == 0 + ) + + return dfs(0) + + +if __name__ == "__main__": + obj = Solution() + print(obj.minimumXORSum(nums1=[1, 2], nums2=[2, 3])) + print(obj.minimumXORSum(nums1=[1, 0, 3], nums2=[5, 3, 4])) diff --git a/num_ways_arrive_dest.py b/num_ways_arrive_dest.py new file mode 100644 index 0000000..ee7f23f --- /dev/null +++ b/num_ways_arrive_dest.py @@ -0,0 +1,69 @@ +# 1976. Number of Ways to Arrive at Destination +from collections import defaultdict +import heapq + +""" +you are in a city that consists of 'n' intersections numbered from 0 to 'n - +1' with bi directional roads between some intersections. the inputs are +generated such that you can reach any intersection from any other +intersection and that there is at most one road between any two +intersections. you are given an integer 'n' and a 2d integer array 'roads' +where 'roads[i] = [u_i, v_i, t_i]' means that there is a road between +intersections 'u' and 'v' that takes 't' minutes to travel. you want to know +in how many ways you can travel from interseciton 0 to intersection 'n - 1'. +""" + + +class Solution(object): + def countPaths(self, n, roads): + """ + :type n: int + :type roads: List[List[int]] + :rtype: int + """ + graph = defaultdict(list) + for u, v, t in roads: + graph[u].append([v, t]) + graph[v].append([u, t]) + + def dijkstra(src): + dist, ways = [float("inf")] * n, [0] * n + pq = [(0, src)] + ways[src] = 1 + dist[src] = 0 + while pq: + d, u = heapq.heappop(pq) + if dist[u] < d: + continue + for v, t in graph[u]: + if dist[v] > d + t: + dist[v] = d + t + ways[v] = ways[u] + heapq.heappush(pq, (dist[v], v)) + elif dist[v] == d + t: + ways[v] = (ways[v] + ways[u]) % (10**9 + 7) + return ways[n - 1] + + return dijkstra(0) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.countPaths( + n=7, + roads=[ + [0, 6, 7], + [0, 1, 2], + [1, 2, 3], + [1, 3, 3], + [6, 3, 3], + [3, 5, 1], + [6, 5, 1], + [2, 5, 1], + [0, 4, 5], + [4, 6, 2], + ], + ) + ) + print(obj.countPaths(n=2, roads=[[1, 0, 10]])) diff --git a/other/min_cost_walk_weight_graph.cpp b/other/min_cost_walk_weight_graph.cpp new file mode 100644 index 0000000..79f3a8b --- /dev/null +++ b/other/min_cost_walk_weight_graph.cpp @@ -0,0 +1,72 @@ +// 3108. Minimum Cost Walk in Weighted Graph +#include "leetcode.h" + +/* + * there is an undirected weighted graph with 'n' vertices labeled from 0 to 'n + * - 1'. you are given the integer 'n' and an array 'edges', where 'edges[i] = + * [u_i, v_i, w_i]' indicates that there is an edge between vertices 'u_i' and + * 'v_i' with a weight of 'w_i'. a walk on the graph is a sequence of vertices + * and edges. the walk starts and ends with a vertex, and each edge connects the + * vertex that comes before it and the vertex that comes after it. it's + * important to note that a walk may visit the same edge or vertex more than + * once. return the array 'answer' where 'answer[i]' denotes the minimum cost of + * a walk for query 'i'. + */ + +class Solution { +public: + vector<int> minimumCost(int n, vector<vector<int>> &edges, + vector<vector<int>> &query) { + vector<vector<int>> adj(n); + vector<int> cnt(n, (1 << 30) - 1); + for (vector<int> e : edges) { + int u = e[0], v = e[1], k = e[2]; + adj[u].push_back(v); + adj[v].push_back(u); + cnt[u] &= k; + cnt[v] &= k; + } + queue<int> q; + vector<int> group(n, -1); + for (int i = 0; i < n; i++) { + if (group[i] == -1) { + group[i] = i; + q.push(i); + while (!q.empty()) { + int u = q.front(); + q.pop(); + cnt[i] &= cnt[u]; + for (int v : adj[u]) { + if (group[v] == -1) { + group[v] = i; + q.push(v); + } + } + } + } + } + vector<int> ans; + for (vector<int> qs : query) { + int s = qs[0], t = qs[1]; + if (s == t) + ans.push_back(0); + else + ans.push_back(group[s] == group[t] ? cnt[group[s]] : -1); + } + return ans; + } +}; + +int main() { + Solution obj; + vvd e1 = {{0, 1, 7}, {1, 3, 7}, {1, 2, 1}}, q1 = {{0, 3}, {3, 4}}; + vvd e2 = {{0, 2, 7}, {0, 1, 15}, {1, 2, 6}, {1, 2, 1}}, q2 = {{1, 2}}; + vector<int> mc1 = obj.minimumCost(5, e1, q1); + vector<int> mc2 = obj.minimumCost(3, e2, q2); + for (auto i : mc1) + printf("%d ", i); // expect: 1 -1 + printf("\n"); + for (auto i : mc2) + printf("%d ", i); // expect: 0 + printf("\n"); +} diff --git a/other/num_ways_arrive_dest.cpp b/other/num_ways_arrive_dest.cpp new file mode 100644 index 0000000..416d811 --- /dev/null +++ b/other/num_ways_arrive_dest.cpp @@ -0,0 +1,62 @@ +// 1976. Number of Ways to Arrive at Destination +#include "leetcode.h" + +/* + * you are in a city that consists of 'n' intersections numbered from 0 to 'n - + * 1' with bi directional roads between some intersections. the inputs are + * generated such that you can reach any intersection from any other + * intersection and that there is at most one road between any two + * intersections. you are given an integer 'n' and a 2d integer array 'roads' + * where 'roads[i] = [u_i, v_i, t_i]' means that there is a road between + * intersections 'u' and 'v' that takes 't' minutes to travel. you want to know + * in how many ways you can travel from interseciton 0 to intersection 'n - 1'. + */ + +class Solution { +public: + int countPaths(int n, vector<vector<int>> &roads) { + vector<vector<pair<long long, long long>>> graph(n); + for (auto &r : roads) { + long long u = r[0], v = r[1], t = r[2]; + graph[u].push_back({v, t}); + graph[v].push_back({u, t}); + } + return dijkstra(graph, n, 0); + } + +private: + int mod = 1e9 + 7; + int dijkstra(const vector<vector<pair<long long, long long>>> &graph, int n, + int src) { + vector<long long> dist(n, LONG_MAX), ways(n); + ways[src] = 1; + dist[src] = 0; + priority_queue<pair<long long, long long>, + vector<pair<long long, long long>>, greater<>> + pq; + pq.push({0, 0}); + while (!pq.empty()) { + auto [d, u] = pq.top(); + pq.pop(); + if (d > dist[u]) + continue; + for (auto [v, t] : graph[u]) { + if (dist[v] > d + t) { + dist[v] = d + t; + ways[v] = ways[u]; + } else if (dist[v] == d + t) + ways[v] = (ways[v] + ways[u]) % mod; + } + } + return ways[n - 1]; + } +}; + +int main() { + Solution obj; + vvd r1 = {{0, 6, 7}, {0, 1, 2}, {1, 2, 3}, {1, 3, 3}, {6, 3, 3}, + {3, 5, 1}, {6, 5, 1}, {2, 5, 1}, {0, 4, 5}, {4, 6, 2}}; + vvd r2 = {{1, 0, 10}}; + printf("%d\n", obj.countPaths(7, r1)); // expect: 4 + printf("%d\n", obj.countPaths(2, r2)); // expect: 1 +} diff --git a/partition_labels.c b/partition_labels.c new file mode 100644 index 0000000..eb06b60 --- /dev/null +++ b/partition_labels.c @@ -0,0 +1,42 @@ +// 763. Partition Labels +#include "leetcode.h" + +/* + * you are given a string 's'. we want to partition the string into as many + * parts as possible so that each letter appears in at most one part. for + * example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note + * that the partition is done so that after concatenating all the parts in + * order, the resultant string should be 's'. return a list of integers + * representing the size of these parts. + */ + +int *partitionLabels(char *s, int *returnSize) { + int n = strlen(s), start = 0, end = 0, curr = 0; + int *ans = (int *)calloc(n, sizeof(int)), hash[26] = {0}; + for (int i = 0; i < n; i++) + hash[s[i] - 'a'] = i; + for (int i = 0; i < n; i++) { + int prev = hash[s[i] - 'a']; + end = end > prev ? end : prev; + if (end == i) { + ans[curr++] = end - start + 1; + start = end + 1; + } + } + *returnSize = curr; + return ans; +} + +int main() { + char *s1 = "ababcbacadefegdehijhklij", *s2 = "eccbbbbdec"; + int rs1, *pl1 = partitionLabels(s1, &rs1); + int rs2, *pl2 = partitionLabels(s2, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", pl1[i]); // expect: 9 7 8 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", pl2[i]); // expect: 10 + printf("\n"); + free(pl1); + free(pl2); +} diff --git a/partition_labels.py b/partition_labels.py new file mode 100644 index 0000000..13556c5 --- /dev/null +++ b/partition_labels.py @@ -0,0 +1,34 @@ +# 763. Partition Labels + +""" +you are given a string 's'. we want to partition the string into as many +parts as possible so that each letter appears in at most one part. for +example, the string 'ababcc' can be partitioned into '["abab", "cc"]'. note +that the partition is done so that after concatenating all the parts in +order, the resultant string should be 's'. return a list of integers +representing the size of these parts. +""" + + +class Solution(object): + def partitionLabels(self, s): + """ + :type s: str + :rtype: List[int] + """ + curr, ans = 0, [0] + ends = {c: i for i, c in enumerate(s)} + while curr < len(s): + prev = ends[s[curr]] + while curr <= prev: + sym = s[curr] + prev = max(prev, ends[sym]) + curr += 1 + ans.append(curr) + return [ans[i] - ans[i - 1] for i in range(1, len(ans))] + + +if __name__ == "__main__": + obj = Solution() + print(obj.partitionLabels(s="ababcbacadefegdehijhklij")) + print(obj.partitionLabels(s="eccbbbbdec")) diff --git a/shopping_offers.c b/shopping_offers.c new file mode 100644 index 0000000..bc7b735 --- /dev/null +++ b/shopping_offers.c @@ -0,0 +1,122 @@ +// 638. Shopping Offers +#include "leetcode.h" + +/* + * in leetcode store, there are 'n' items to sell. each item has a price. + * however, there are some special offers, and a special offer consists of one + * or more different kinds of items with a sale price. you are given an integer + * array 'price' where 'price[i]' is the price of the i'th item, and an integer + * array 'needs' where 'needs[i]' is the number of pieces the i'th item you want + * to buy. you are also given an array 'special', where 'special[i]' is of size + * 'n + 1' where 'special[i][j]' is the number of pieces of the j'th item in the + * i'th other. return the lowest price you have to pay for exactly certain items + * as given, where you could make optimal use of the special offers. you are not + * allowed to buy more items that you want, even if that would lower the overall + * price. + */ + +#define MOD 1009 + +struct node { + struct node *next; + int key; + int val; +}; + +struct node *hash[MOD]; + +void hash_init(void) { memset((void *)hash, 0, sizeof(hash)); } + +void hash_push(int key, int val) { + int idx = key % MOD; + struct node *tmp = (struct node *)malloc(sizeof(struct node)); + tmp->key = key; + tmp->val = val; + tmp->next = hash[idx]; + hash[idx] = tmp; +} + +int hash_pop(int key) { + int idx = key % MOD; + struct node *tmp = hash[idx]; + for (; tmp; tmp = tmp->next) + if (tmp->key == key) + return tmp->val; + return -1; +} + +void hash_free(void) { + for (int i = 0; i < MOD; i++) + for (struct node *tmp = hash[i], *del; tmp;) { + del = tmp; + tmp = tmp->next; + free(del); + } +} + +int lowest_price(int n, int need, int *prices, int **special, int specialSize, + int *specialColSize) { + int min = INT_MAX, price = 0, tmp; + bool accept = true; + if (!need) + return 0; + price = hash_pop(need); + if (price >= 0) + return price; + price = 0; + tmp = need; + for (int i = 0; i < n; i++) { + price += prices[i] * (tmp & 0x0F); + tmp >>= 4; + } + min = fmin(min, price); + for (int i = 0; i < specialSize; i++) { + tmp = need; + accept = true; + for (int j = 0; j < n; j++) { + int quantity = (tmp >> (j * 4)) & 0x0F; + if (quantity >= special[i][j]) { + quantity -= special[i][j]; + tmp &= ~(0x0F << (j * 4)); + tmp |= (quantity << (j * 4)); + } else { + accept = false; + break; + } + } + if (accept) { + price = special[i][n] + lowest_price(n, tmp, prices, special, specialSize, + specialColSize); + min = fmin(min, price); + } + } + hash_push(need, min); + return min; +} + +int shoppingOffers(int *price, int priceSize, int **special, int specialSize, + int *specialColSize, int *needs, int needsSize) { + int need = 0, ans; + hash_init(); + for (int i = 0; i < needsSize; i++) + need |= (needs[i] << (i * 4)); + ans = lowest_price(priceSize, need, price, special, specialSize, + specialColSize); + hash_free(); + return ans; +} + +int main() { + int p1[] = {2, 5}, s1i[2][3] = {{3, 0, 5}, {1, 2, 10}}, n1[] = {3, 2}; + int p2[] = {2, 3, 4}, s2i[2][4] = {{1, 1, 0, 4}, {2, 2, 1, 9}}, + n2[] = {1, 2, 1}; + struct two_d_arr s1, s2; + two_d_arr_init(&s1, ARRAY_SIZE(s1i), ARRAY_SIZE(s1i[0]), s1i); + two_d_arr_init(&s2, ARRAY_SIZE(s2i), ARRAY_SIZE(s2i[0]), s2i); + printf("%d\n", shoppingOffers(p1, ARRAY_SIZE(p1), s1.arr, s1.row_size, + s1.col_size, n1, ARRAY_SIZE(n1))); // expect: 14 + printf("%d\n", shoppingOffers(p2, ARRAY_SIZE(p2), s2.arr, s2.row_size, + s2.col_size, n2, ARRAY_SIZE(n2))); // expect: 11 + two_d_arr_free(&s1); + two_d_arr_free(&s2); +} diff --git a/shopping_offers.py b/shopping_offers.py new file mode 100644 index 0000000..42da709 --- /dev/null +++ b/shopping_offers.py @@ -0,0 +1,49 @@ +# 638. Shopping Offers + +""" +in leetcode store, there are 'n' items to sell. each item has a price. +however, there are some special offers, and a special offer consists of one +or more different kinds of items with a sale price. you are given an integer +array 'price' where 'price[i]' is the price of the i'th item, and an integer +array 'needs' where 'needs[i]' is the number of pieces the i'th item you want +to buy. you are also given an array 'special', where 'special[i]' is of size +'n + 1' where 'special[i][j]' is the number of pieces of the j'th item in the +i'th other. return the lowest price you have to pay for exactly certain items +as given, where you could make optimal use of the special offers. you are not +allowed to buy more items that you want, even if that would lower the overall +price. +""" + + +class Solution(object): + def shoppingOffers(self, price, special, needs): + """ + :type price: List[int] + :type special: List[List[int]] + :type needs: List[int] + :rtype: int + """ + dp = {} + + def dfs(curr): + val = sum(curr[i] * price[i] for i in range(len(needs))) + for *spec, cost in special: + tmp = [curr[j] - spec[j] for j in range(len(needs))] + if min(tmp) >= 0: # skip deals that exceed needs + val = min(val, dp.get(tuple(tmp), dfs(tmp)) + cost) + dp[tuple(curr)] = val + return val + + return dfs(needs) + + +if __name__ == "__main__": + obj = Solution() + print( + obj.shoppingOffers(price=[2, 5], special=[[3, 0, 5], [1, 2, 10]], needs=[3, 2]) + ) + print( + obj.shoppingOffers( + price=[2, 3, 4], special=[[1, 1, 0, 4], [2, 2, 1, 9]], needs=[1, 2, 1] + ) + ) diff --git a/sum_subset_xor.c b/sum_subset_xor.c index cb51647..7c32618 100644 --- a/sum_subset_xor.c +++ b/sum_subset_xor.c @@ -8,26 +8,11 @@ * if 'a' can be obtained from 'b' by deleting some elements of 'b'. */ -void backtrack(int *nums, int numsSize, int tar, int idx, int *cnt) { - if (idx == numsSize) { - return; - } else { - for (int i = idx; i < numsSize; i++) { - tar ^= nums[i]; - *cnt += tar; - backtrack(nums, numsSize, tar, i + 1, cnt); - tar ^= nums[i]; - } - } -} - int subsetXORSum(int *nums, int numsSize) { - int ans = 0; - for (int i = 0; i < numsSize; i++) { - ans += nums[i]; - backtrack(nums, numsSize, nums[i], i + 1, &ans); - } - return ans; + int all = 0, mult = 1 << (numsSize - 1); + for (int i = 0; i < numsSize; i++) + all |= nums[i]; + return all * mult; } int main() { diff --git a/sum_subset_xor.py b/sum_subset_xor.py index deb88ed..0560197 100644 --- a/sum_subset_xor.py +++ b/sum_subset_xor.py @@ -1,4 +1,6 @@ # 1863. Sum of All Subset XOR Totals +from functools import reduce +from operator import or_ """ the xor total of an array is defined as the bitwise xor of all its elements @@ -14,25 +16,7 @@ class Solution(object): :type nums: List[int] :rtype: int """ - - def backtrack(nums, idx, tar, cnt): - if idx == len(nums): - cnt.append(tar[:]) - return - tar.append(nums[idx]) - backtrack(nums, idx + 1, tar, cnt) - tar.pop() - backtrack(nums, idx + 1, tar, cnt) - - cnt = [] - backtrack(nums, 0, [], cnt) - ans = 0 - for i in cnt: - total = 0 - for n in i: - total ^= n - ans += total - return ans + return reduce(or_, nums) << (len(nums) - 1) if __name__ == "__main__": diff --git a/total_hamming_distance.c b/total_hamming_distance.c new file mode 100644 index 0000000..571f417 --- /dev/null +++ b/total_hamming_distance.c @@ -0,0 +1,25 @@ +// 477. Total Hamming Distance +#include "leetcode.h" + +/* + * the hamming distance between two integers is the number of positions at which + * the corresponding bits are different. given an integer array 'nums', return + * the sum of hamming distances between all the pairs of the integers in 'nums'. + */ + +int totalHammingDistance(int *nums, int numsSize) { + int total = 0; + for (int i = 0; i < 32; i++) { + int cnt = 0; + for (int j = 0; j < numsSize; j++) + cnt += (nums[j] >> i) & 1; + total += cnt * (numsSize - cnt); + } + return total; +} + +int main() { + int n1[] = {4, 14, 2}, n2[] = {4, 14, 4}; + printf("%d\n", totalHammingDistance(n1, ARRAY_SIZE(n1))); // expect: 6 + printf("%d\n", totalHammingDistance(n2, ARRAY_SIZE(n2))); // expect: 4 +} diff --git a/total_hamming_distance.py b/total_hamming_distance.py new file mode 100644 index 0000000..3098372 --- /dev/null +++ b/total_hamming_distance.py @@ -0,0 +1,27 @@ +# 477. Total Hamming Distance + +""" +the hamming distance between two integers is the number of positions at which +the corresponding bits are different. given an integer array 'nums', return +the sum of hamming distances between all the pairs of the integers in 'nums'. +""" + + +class Solution(object): + def totalHammingDistance(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + bits = [[0, 0] for _ in range(32)] + for i in nums: + for j in bits: + j[i % 2] += 1 + i /= 2 + return sum(x * y for x, y in bits) + + +if __name__ == "__main__": + obj = Solution() + print(obj.totalHammingDistance(nums=[4, 14, 2])) + print(obj.totalHammingDistance(nums=[4, 14, 4])) diff --git a/zero_array_transformation2.c b/zero_array_transformation2.c new file mode 100644 index 0000000..4532469 --- /dev/null +++ b/zero_array_transformation2.c @@ -0,0 +1,71 @@ +// 3356. Zero Array Transformation II +#include "leetcode.h" + +/* + * you are given an integer array 'nums' of length 'n' and a 2d array 'queries' + * where 'queries[i] [l_i, r_i, val_i]'. each 'queries[i]' represents the + * following action on 'nums': decrement the value at each index in the range + * '[l_i, r_i]' in 'nums' by at most 'val_i'. the amount by which each value is + * decremented can be chosen independently for each index. a zero array is an + * array with all its elements equal to 0. return the minimum possible + * non-negative value of 'k', such that after processing the first 'k' queries + * in sequence, 'nums' becomes a zero array. if no such 'k' exists, return -1. + */ + +bool can_cover(int *nums, int n, int **queries, int k) { + int *diff = (int *)calloc(n + 1, sizeof(int)); + for (int i = 0; i < k; i++) { + int l = queries[i][0]; + int r = queries[i][1]; + int val = queries[i][2]; + diff[l] += val; + if (r + 1 < n) + diff[r + 1] -= val; + } + int sum = 0; + for (int i = 0; i < n; i++) { + sum += diff[i]; + if (sum < nums[i]) { + free(diff); + return false; + } + } + free(diff); + return true; +} + +int minZeroArray(int *nums, int numsSize, int **queries, int queriesSize, + int *queriesColSize) { + int already_zero = 1; + for (int i = 0; i < numsSize; i++) + if (nums[i]) { + already_zero = 0; + break; + } + if (already_zero) + return 0; + int l = 1, r = queriesSize, ans = -1; + while (l <= r) { + int mid = l + (r - l) / 2; + if (can_cover(nums, numsSize, queries, mid)) { + ans = mid; + r = mid - 1; + } else + l = mid + 1; + } + return ans; +} + +int main() { + int n1[] = {2, 0, 2}, q1i[3][3] = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}}; + int n2[] = {4, 3, 2, 1}, q2i[2][3] = {{1, 3, 2}, {0, 2, 1}}; + struct two_d_arr q1, q2; + two_d_arr_init(&q1, ARRAY_SIZE(q1i), ARRAY_SIZE(q1i[0]), q1i); + two_d_arr_init(&q2, ARRAY_SIZE(q2i), ARRAY_SIZE(q2i[0]), q2i); + printf("%d\n", minZeroArray(n1, ARRAY_SIZE(n1), q1.arr, q1.row_size, + q1.col_size)); // expect: 2 + printf("%d\n", minZeroArray(n2, ARRAY_SIZE(n2), q2.arr, q2.row_size, + q2.col_size)); // expect: -1 + two_d_arr_free(&q1); + two_d_arr_free(&q2); +} diff --git a/zero_array_transformation2.py b/zero_array_transformation2.py new file mode 100644 index 0000000..1b462e5 --- /dev/null +++ b/zero_array_transformation2.py @@ -0,0 +1,41 @@ +# 3356. Zero Array Transformation II + +""" +you are given an integer array 'nums' of length 'n' and a 2d array 'queries' +where 'queries[i] [l_i, r_i, val_i]'. each 'queries[i]' represents the +following action on 'nums': decrement the value at each index in the range +'[l_i, r_i]' in 'nums' by at most 'val_i'. the amount by which each value is +decremented can be chosen independently for each index. a zero array is an +array with all its elements equal to 0. return the minimum possible +non-negative value of 'k', such that after processing the first 'k' queries +in sequence, 'nums' becomes a zero array. if no such 'k' exists, return -1. +""" + + +class Solution(object): + def minZeroArray(self, nums, queries): + """ + :type nums: List[int] + :type queries: List[List[int]] + :rtype: int + """ + n, ans, k = len(nums), 0, 0 + cnt = [0 for _ in range(n + 1)] + for i in range(n): + while k + cnt[i] < nums[i]: + ans += 1 + if ans - 1 >= len(queries): + return -1 + l, r, val = queries[ans - 1] + if r < i: + continue + cnt[max(l, i)] += val + cnt[r + 1] -= val + k += cnt[i] + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.minZeroArray(nums=[2, 0, 2], queries=[[0, 2, 1], [0, 2, 1], [1, 1, 3]])) + print(obj.minZeroArray(nums=[4, 3, 2, 1], queries=[[1, 3, 2], [0, 2, 1]])) |