aboutsummaryrefslogtreecommitdiff
path: root/reveal_cards_incr_order.c
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /reveal_cards_incr_order.c
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'reveal_cards_incr_order.c')
-rw-r--r--reveal_cards_incr_order.c72
1 files changed, 72 insertions, 0 deletions
diff --git a/reveal_cards_incr_order.c b/reveal_cards_incr_order.c
new file mode 100644
index 0000000..eab5c20
--- /dev/null
+++ b/reveal_cards_incr_order.c
@@ -0,0 +1,72 @@
+// 950. Reveal Cards In Increasing Order
+#include "leetcode.h"
+
+/*
+ * given an integer array 'deck'. there is a deck of cards where every card has
+ * a unique integer. the integer on the i'th card is 'deck[i]'. you can order
+ * the deck in any order you want. initially, all the cards start face down
+ * (unrevealed) in one deck. you will do the following steps repeatedly until
+ * all cards are revealed. take the top card of the deck, reveal it, and take it
+ * out of the deck. if there are still cards in the deck, then put the next top
+ * card of the deck at the bottom of the deck. if there are still unrevealed
+ * cards, go back to step 1, otherwise stop. return an ordering of the deck that
+ * would reveal the cards in increasing order.
+ */
+
+struct ListNode {
+ int val;
+ struct ListNode *next;
+};
+
+typedef struct ListNode l_node;
+
+int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; }
+
+int *deckRevealedIncreasing(int *deck, int deckSize, int *returnSize) {
+ l_node *head = malloc(sizeof(l_node));
+ head->val = 0;
+ l_node *tmp = head;
+ for (int i = 1; i < deckSize; i++) {
+ l_node *n = malloc(sizeof(l_node));
+ n->val = i;
+ tmp->next = n;
+ tmp = n;
+ }
+ l_node *tail = tmp;
+ tail->next = NULL;
+ tmp = head;
+ l_node *post;
+ while (tmp->next && tmp->next->next) {
+ post = tmp->next;
+ tmp->next = tmp->next->next;
+ tail->next = post;
+ tail = post;
+ tail->next = NULL;
+ tmp = tmp->next;
+ }
+ int *ans = malloc(deckSize * sizeof(int));
+ qsort(deck, deckSize, sizeof(int), cmp);
+ tmp = head;
+ l_node *ptr;
+ for (int i = 0; i < deckSize; i++) {
+ ans[tmp->val] = deck[i];
+ ptr = tmp;
+ tmp = tmp->next;
+ free(ptr);
+ }
+ *returnSize = deckSize;
+ return ans;
+}
+
+int main() {
+ int d1[] = {17, 13, 11, 2, 3, 5, 7}, d2[] = {1, 1000}, rs1, rs2;
+ int *dri1 = deckRevealedIncreasing(d1, ARRAY_SIZE(d1), &rs1);
+ int *dri2 = deckRevealedIncreasing(d2, ARRAY_SIZE(d2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", dri1[i]); // expect: 2,13,3,11,5,17,7
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", dri2[i]); // expect: 1,1000
+ printf("\n");
+ free(dri1), free(dri2);
+}