diff options
-rw-r--r-- | beautiful_array.c | 64 | ||||
-rw-r--r-- | beautiful_array.py | 27 | ||||
-rw-r--r-- | find_max_non_decr_arr_len.c | 53 | ||||
-rw-r--r-- | find_max_non_decr_arr_len.py | 39 | ||||
-rw-r--r-- | reschedule_meetings_max_free2.c | 50 | ||||
-rw-r--r-- | reschedule_meetings_max_free2.py | 46 |
6 files changed, 279 insertions, 0 deletions
diff --git a/beautiful_array.c b/beautiful_array.c new file mode 100644 index 0000000..d384066 --- /dev/null +++ b/beautiful_array.c @@ -0,0 +1,64 @@ +// 932. Beautiful Array +#include "leetcode.h" + +/* + * an array 'nums' of length 'n' is beautiful if 'nums' is a permutation of the + * integers in the range '[1, n]', and for every '0 <= i < j < n', there is no + * index 'k' with 'i < k < j' where '2 * nums[k] == nums[i] + nums[j]'. given + * the integer 'n', return any beautiful array 'nums' of length 'n'. there will + * be at least one valid answer for the given 'n'. + */ + +int *build_arr(int n, int **ans) { + if (ans[n]) + return ans[n]; + int *res = (int *)malloc(n * sizeof(int)); + if (n == 1) + res[0] = 1; + else { + int j = 0; + int *odds = build_arr((n + 1) / 2, ans); + for (int k = 0; k < (n + 1) / 2; k++) + res[k] = 2 * odds[k] - 1; + int *evens = build_arr(n / 2, ans); + for (int k = 0; k < n / 2; k++) + res[((n + 1) / 2) + k] = 2 * evens[k]; + } + ans[n] = res; + return res; +} + +int *beautifulArray(int n, int *returnSize) { + int *ans = (int *)malloc(n * sizeof(int)); + *returnSize = n; + if (n == 1) { + ans[0] = 1; + return ans; + } + if (n == 2) { + ans[0] = 1; + ans[1] = 2; + return ans; + } + int **res = (int **)malloc((n + 1) * sizeof(int *)); + for (int i = 0; i < n + 1; i++) + res[i] = NULL; + ans = build_arr(n, res); + *returnSize = n; + for (int i = 0; i < n; i++) + free(res[i]); + free(res); + return ans; +} + +int main() { + int rs1, *ba1 = beautifulArray(4, &rs1); + int rs2, *ba2 = beautifulArray(5, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", ba1[i]); // expect: 2 1 4 3 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", ba2[i]); // expect: 3 1 2 5 4 + printf("\n"); + free(ba1), free(ba2); +} diff --git a/beautiful_array.py b/beautiful_array.py new file mode 100644 index 0000000..1cbbfeb --- /dev/null +++ b/beautiful_array.py @@ -0,0 +1,27 @@ +# 932. Beautiful Array + +""" +an array 'nums' of length 'n' is beautiful if 'nums' is a permutation of the +integers in the range '[1, n]', and for every '0 <= i < j < n', there is no +index 'k' with 'i < k < j' where '2 nums[k] == nums[i] + nums[j]'. given +the integer 'n', return any beautiful array 'nums' of length 'n'. there will +be at least one valid answer for the given 'n'. +""" + + +class Solution(object): + def beautifulArray(self, n): + """ + :type n: int + :rtype: List[int] + """ + ans = [1] + while len(ans) < n: + ans = [i * 2 - 1 for i in ans] + [i * 2 for i in ans] + return [i for i in ans if i <= n] + + +if __name__ == "__main__": + obj = Solution() + print(obj.beautifulArray(n=4)) + print(obj.beautifulArray(n=5)) diff --git a/find_max_non_decr_arr_len.c b/find_max_non_decr_arr_len.c new file mode 100644 index 0000000..0f218b4 --- /dev/null +++ b/find_max_non_decr_arr_len.c @@ -0,0 +1,53 @@ +// 2945. Find Maximum Non-decreasing Array Length +#include "leetcode.h" + +/* + * you are given a 0-indexed integer array 'nums'. you can perform any number of + * operations, where each operation involves selecting a subarray of the array + * and replacing it with the sum of its elements. for example, if the given + * array is '[1, 3, 5, 6]' and you select '[3, 5]', the array will convert to + * '[1, 8, 6]'. return the maximum length of a non-decreasing array that can be + * made after applying the aforementioned operations. a subarray is a contiguous + * non-empty sequence of elements within an array + */ + +struct node { + int px; + int rx; + int ml; +}; + +int findMaximumLength(int *nums, int numsSize) { + struct node *dp = (struct node *)malloc((numsSize + 1) * sizeof(int)); + int dpl = 1, px = 0; + memset(&dp[0], 0, sizeof(struct node)); + for (int i = 1, j = 0; i <= numsSize; ++i) { + px += nums[i - 1]; + if (j >= dpl) + j = dpl - 1; + while (j + 1 < dpl) { + if (!(px >= dp[j + 1].rx + dp[j + 1].px)) + break; + ++j; + } + int ml = dp[j].ml + 1, rx = px - dp[j].px; + while (1) { + if (rx + px >= dp[dpl - 1].rx + dp[dpl - 1].px) + break; + --dpl; + } + dp[dpl].px = px; + dp[dpl].rx = rx; + dp[dpl].ml = ml; + } + int ans = dp[dpl - 1].ml; + free(dp); + return ans; +} + +int main() { + int n1[] = {5, 2, 2}, n2[] = {1, 2, 3, 4}, n3[] = {4, 3, 2, 6}; + printf("%d\n", findMaximumLength(n1, ARRAY_SIZE(n1))); // expect: 1 + printf("%d\n", findMaximumLength(n2, ARRAY_SIZE(n2))); // expect: 4 + printf("%d\n", findMaximumLength(n3, ARRAY_SIZE(n3))); // expect: 3 +} diff --git a/find_max_non_decr_arr_len.py b/find_max_non_decr_arr_len.py new file mode 100644 index 0000000..1621d70 --- /dev/null +++ b/find_max_non_decr_arr_len.py @@ -0,0 +1,39 @@ +# 2945. Find Maximum Non-decreasing Array Length +from itertools import accumulate +from bisect import bisect_left + +""" +you are given a 0-indexed integer array 'nums'. you can perform any number of +operations, where each operation involves selecting a subarray of the array +and replacing it with the sum of its elements. for example, if the given +array is '[1, 3, 5, 6]' and you select '[3, 5]', the array will convert to +'[1, 8, 6]'. return the maximum length of a non-decreasing array that can be +made after applying the aforementioned operations. a subarray is a contiguous +non-empty sequence of elements within an array +""" + + +class Solution(object): + def findMaximumLength(self, nums): + """ + :type nums: List[int] + :rtype: int + """ + n = len(nums) + acc = list(accumulate(nums, initial=0)) + pre = [0] * (n + 2) + dp = [0] * (n + 1) + i = 0 + for j, k in enumerate(nums, 1): + i = max(i, pre[j]) + dp[j] = dp[i] + 1 + l = bisect_left(acc, acc[j] * 2 - acc[i]) + pre[l] = j + return dp[n] + + +if __name__ == "__main__": + obj = Solution() + print(obj.findMaximumLength(nums=[5, 2, 2])) + print(obj.findMaximumLength(nums=[1, 2, 3, 4])) + print(obj.findMaximumLength(nums=[4, 3, 2, 6])) diff --git a/reschedule_meetings_max_free2.c b/reschedule_meetings_max_free2.c new file mode 100644 index 0000000..2ad0165 --- /dev/null +++ b/reschedule_meetings_max_free2.c @@ -0,0 +1,50 @@ +// 3440. Reschedule Meetings for Maximum Free Time II +#include "leetcode.h" + +/* + * you are given an integer 'eventTime' denoting the duration of an event. you + * are also given two integer arrays 'startTime' and 'endTime', each of length + * 'n'. these represent the start and end times of 'n' non-overlapping meetings + * that occur during the event between time 't = 0' and time 't = eventTime' + * where the i't meeting occurs during the time '[startTime[i], endTime[i]]'. + * you can reschedule at most one meeting by moving its start time while + * maintaining the same duration such that the meetings remain non-overlapping, + * to maximise the longest continuous period of free time during the event. + * return the maximum amount of free time possible after rearranging the + * meetings. + */ + +int maxFreeTime(int eventTime, int *startTime, int startTimeSize, int *endTime, + int endTimeSize) { + int n = startTimeSize, ans = 0, left = 0, curr; + int *gap = (int *)malloc((n + 1) * sizeof(int)); + int *largest = (int *)malloc((n + 1) * sizeof(int)); + gap[0] = startTime[0]; + for (int i = 1; i < n; i++) + gap[i] = startTime[i] - endTime[i - 1]; + gap[n] = eventTime - endTime[n - 1]; + largest[n] = 0; + for (int i = 1; i >= 0; i--) + largest[i] = fmax(largest[i + 1], gap[i + 1]); + for (int i = 1; i <= n; i++) { + curr = endTime[i - 1] - startTime[i - 1]; + if (curr <= fmax(left, largest[i])) + ans = fmax(ans, gap[i - 1] + gap[i] + curr); + ans = fmax(ans, gap[i - 1] + gap[i]); + left = fmax(left, gap[i - 1]); + } + free(gap), free(largest); + return ans; +} + +int main() { + int st1[] = {1, 3}, et1[] = {2, 5}; + int st2[] = {0, 7, 9}, et2[] = {1, 8, 10}; + int st3[] = {0, 3, 7, 9}, et3[] = {1, 4, 8, 10}; + printf("%d\n", maxFreeTime(5, st1, ARRAY_SIZE(st1), et1, + ARRAY_SIZE(et1))); // expect: 2 + printf("%d\n", maxFreeTime(10, st2, ARRAY_SIZE(st2), et2, + ARRAY_SIZE(et2))); // expect: 7 + printf("%d\n", maxFreeTime(10, st3, ARRAY_SIZE(st3), et3, + ARRAY_SIZE(et3))); // expect: 6 +} diff --git a/reschedule_meetings_max_free2.py b/reschedule_meetings_max_free2.py new file mode 100644 index 0000000..d508bc7 --- /dev/null +++ b/reschedule_meetings_max_free2.py @@ -0,0 +1,46 @@ +# 3440. Reschedule Meetings for Maximum Free Time II + +""" +you are given an integer 'eventTime' denoting the duration of an event. you +are also given two integer arrays 'startTime' and 'endTime', each of length +'n'. these represent the start and end times of 'n' non-overlapping meetings +that occur during the event between time 't = 0' and time 't = eventTime' +where the i't meeting occurs during the time '[startTime[i], endTime[i]]'. +you can reschedule at most one meeting by moving its start time while +maintaining the same duration such that the meetings remain non-overlapping, +to maximise the longest continuous period of free time during the event. +return the maximum amount of free time possible after rearranging the +meetings. +""" + + +class Solution(object): + def maxFreeTime(self, eventTime, startTime, endTime): + """ + :type eventTime: int + :type startTime: List[int] + :type endTime: List[int] + :rtype: int + """ + ans, left = 0, 0 + gap = [startTime[0]] + largest = [0] * len(gap) + for i in range(1, len(startTime)): + gap.append(startTime[i] - endTime[i - 1]) + gap.append(eventTime - endTime[-1]) + for i in range(len(gap) - 2, -1, -1): + largest[i] = max(largest[i + 1], gap[i + 1]) + for i in range(1, len(gap)): + curr = endTime[i - 1] - startTime[i - 1] + if curr <= max(left, largest[i]): + ans = max(ans, gap[i - 1] + gap[i] + curr) + ans = max(ans, gap[i - 1] + gap[i]) + left = max(left, gap[i - 1]) + return ans + + +if __name__ == "__main__": + obj = Solution() + print(obj.maxFreeTime(eventTime=5, startTime=[1, 3], endTime=[2, 5])) + print(obj.maxFreeTime(eventTime=10, startTime=[0, 7, 9], endTime=[1, 8, 10])) + print(obj.maxFreeTime(eventTime=10, startTime=[0, 3, 7, 9], endTime=[1, 4, 8, 10])) |