aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--beautiful_array.c64
-rw-r--r--beautiful_array.py27
-rw-r--r--earliest_latest_rounds_players_compete.c61
-rw-r--r--earliest_latest_rounds_players_compete.py49
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))