diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /reveal_cards_incr_order.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'reveal_cards_incr_order.c')
-rw-r--r-- | reveal_cards_incr_order.c | 72 |
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); +} |