diff options
-rw-r--r-- | beautiful_array.c | 64 | ||||
-rw-r--r-- | beautiful_array.py | 27 | ||||
-rw-r--r-- | earliest_latest_rounds_players_compete.c | 61 | ||||
-rw-r--r-- | earliest_latest_rounds_players_compete.py | 49 |
4 files changed, 201 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/earliest_latest_rounds_players_compete.c b/earliest_latest_rounds_players_compete.c new file mode 100644 index 0000000..3784964 --- /dev/null +++ b/earliest_latest_rounds_players_compete.c @@ -0,0 +1,61 @@ +// 1900. The Earliest and Latest Rounds Where Players Compete +#include "leetcode.h" + +/* + * there is a tournament where 'n' players are participating. the players are + * standing a single row and are numbered from 1 to 'n' based on their initial + * standing position. the tournament consists of multiple rounds. in each round, + * the i'th player from the front of the row competes against the i'th player + * from the end of the row, and the winner advances to the next round. when the + * number of players is odd for the current round, te player is in the middle + * automatically advances to the next round. after each round is over, the + * winners are lined back up in the row based on the original ordering assigned + * to them initially. the players numbered 'firstPlayer' and 'secondPlayer' are + * the best in the tournament. they can win agsainst any other player beofre + * they compete against each other. if any two other players compete against + * each other, either of them might win, and thus you may choose the outcome of + * this round. + */ + +int *earliestAndLatest(int n, int firstPlayer, int secondPlayer, + int *returnSize) { + *returnSize = 2; + int *ans = (int *)malloc(*returnSize * sizeof(int)); + int first = firstPlayer, second = secondPlayer; + if (first + second == n + 1) { + ans[0] = ans[1] = 1; + return ans; + } + if (first + second > n + 1) { + int tmp = first; + first = n + 1 - second; + second = n + 1 - tmp; + } + int pre = 1; + int pos = (32 - __builtin_clz(n - 1) < n + 1 - second) + ? 32 - __builtin_clz(n - 1) + : n + 1 - second; + if (first + second == n) { + if (!(first % 2)) + pre = (first + 2 < second) ? 2 : 1 + __builtin_ctz(first); + } else if (first + 1 == second) { + pre = 32 - __builtin_clz((n - 1) / (first + second - 1)); + pre += __builtin_ctz((n - 1) >> pre); + } else if (first + second <= (n + 1) / 2) + pre = 32 - __builtin_clz((n - 1) / (first + second - 1)); + ans[0] = pre + 1; + ans[1] = pos; + return ans; +} + +int main() { + int rs1, *eal1 = earliestAndLatest(11, 2, 4, &rs1); + int rs2, *eal2 = earliestAndLatest(5, 1, 5, &rs2); + for (int i = 0; i < rs1; i++) + printf("%d ", eal1[i]); // expect: 3 4 + printf("\n"); + for (int i = 0; i < rs2; i++) + printf("%d ", eal2[i]); // expect: 1 1 + printf("\n"); + free(eal1), free(eal2); +} diff --git a/earliest_latest_rounds_players_compete.py b/earliest_latest_rounds_players_compete.py new file mode 100644 index 0000000..4cf08d9 --- /dev/null +++ b/earliest_latest_rounds_players_compete.py @@ -0,0 +1,49 @@ +# 1900. The Earliest and Latest Rounds Where Players Compete + +""" +there is a tournament where 'n' players are participating. the players are +standing a single row and are numbered from 1 to 'n' based on their initial +standing position. the tournament consists of multiple rounds. in each round, +the i'th player from the front of the row competes against the i'th player +from the end of the row, and the winner advances to the next round. when the +number of players is odd for the current round, te player is in the middle +automatically advances to the next round. after each round is over, the +winners are lined back up in the row based on the original ordering assigned +to them initially. the players numbered 'firstPlayer' and 'secondPlayer' are +the best in the tournament. they can win agsainst any other player beofre +they compete against each other. if any two other players compete against +each other, either of them might win, and thus you may choose the outcome of +this round. +""" + + +class Solution(object): + def earliestAndLatest(self, n, firstPlayer, secondPlayer): + """ + :type n: int + :type firstPlayer: int + :type secondPlayer: int + :rtype: List[int] + """ + + ans = set() + + def dp(r, l, m, q): + if l > r: + dp(r, l, m, q) + if l == r: + ans.add(q) + for i in range(1, l + 1): + for j in range(l - i + 1, r - i + 1): + if not (m + 1) // 2 >= i + j >= l + r - m // 2: + continue + dp(i, j, (m + 1) // 2, q + 1) + + dp(firstPlayer, n - secondPlayer + 1, n, 1) + return [min(ans), max(ans)] + + +if __name__ == "__main__": + obj = Solution() + print(obj.earliestAndLatest(n=11, firstPlayer=2, secondPlayer=4)) + print(obj.earliestAndLatest(n=5, firstPlayer=1, secondPlayer=5)) |