aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-15 13:40:38 -0600
committerJack Sangdahl <[email protected]>2024-09-15 13:40:38 -0600
commit8850c53cf77d11bc3a4baf25eaf4a8292511c35b (patch)
treec59c1778fec6fd791b63f4ffec49c7b5b56dd3f8
parentccbfd54d4a6c45f92f556f4aab02b099703d197d (diff)
downloadleetcode-8850c53cf77d11bc3a4baf25eaf4a8292511c35b.tar.gz
leetcode-8850c53cf77d11bc3a4baf25eaf4a8292511c35b.zip
1054. distant barcodes
-rw-r--r--distant_barcodes.c46
-rw-r--r--distant_barcodes.py29
2 files changed, 75 insertions, 0 deletions
diff --git a/distant_barcodes.c b/distant_barcodes.c
new file mode 100644
index 0000000..f68da8d
--- /dev/null
+++ b/distant_barcodes.c
@@ -0,0 +1,46 @@
+// 1054. Distant Barcodes
+#include "leetcode.h"
+
+/*
+ * in a warehouse, there is a row of barcodes where the i'th barcode is
+ * 'barcodes[i]'. rearrange the barcodes so that no two adjacent barcodes are
+ * equal. you may return any answer, and it is guaranteed that an answer exists
+ */
+
+int cmp(const void *a, const void *b) { return (*(int *)b - *(int *)a); }
+
+int *rearrangeBarcodes(int *barcodes, int barcodesSize, int *returnSize) {
+ int *cnt = (int *)calloc(1e4 + 1, sizeof(int)), max_val = 0;
+ for (int i = 0; i < barcodesSize; i++) {
+ cnt[barcodes[i]] = (cnt[barcodes[i]] + 0x10000) | barcodes[i];
+ max_val = fmax(max_val, barcodes[i]);
+ }
+ qsort(cnt, max_val + 1, sizeof(int), cmp);
+ int idx = 0, b_idx = 0;
+ while (cnt[idx]) {
+ int curr = cnt[idx] & 0xFFFF;
+ cnt[idx] >>= 16;
+ for (int i = 0; i < cnt[idx]; i++) {
+ barcodes[b_idx] = curr;
+ b_idx += 2;
+ if (b_idx >= barcodesSize)
+ b_idx = 1;
+ }
+ cnt[idx++] = 0;
+ }
+ *returnSize = barcodesSize;
+ return barcodes;
+}
+
+int main() {
+ int b1[] = {1, 1, 1, 2, 2, 2}, b2[] = {1, 1, 1, 1, 2, 2, 3, 3}, rs1, rs2;
+ int *rb1 = rearrangeBarcodes(b1, ARRAY_SIZE(b1), &rs1);
+ int *rb2 = rearrangeBarcodes(b2, ARRAY_SIZE(b2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", rb1[i]); // expect: 2,1,2,1,2,1
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", rb2[i]); // expect: 1,3,1,3,1,2,1,2
+ printf("\n");
+ free(rb1), free(rb2);
+}
diff --git a/distant_barcodes.py b/distant_barcodes.py
new file mode 100644
index 0000000..e0fbb74
--- /dev/null
+++ b/distant_barcodes.py
@@ -0,0 +1,29 @@
+# 1054. Distant Barcodes
+from collections import Counter
+
+"""
+in a warehouse, there is a row of barcodes where the i'th barcode is
+'barcodes[i]'. rearrange the barcodes so that no two adjacent barcodes are
+equal. you may return any answer, and it is guaranteed that an answer exists
+"""
+
+
+class Solution(object):
+ def rearrangeBarcodes(self, barcodes):
+ """
+ :type barcodes: List[int]
+ :rtype: List[int]
+ """
+ cnt = Counter(barcodes)
+ barcodes.sort(key=lambda b: (cnt[b], b))
+ barcodes[1::2], barcodes[::2] = (
+ barcodes[0 : len(barcodes) / 2],
+ barcodes[len(barcodes) / 2 :],
+ )
+ return barcodes
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.rearrangeBarcodes(barcodes=[1, 1, 1, 2, 2, 2]))
+ print(obj.rearrangeBarcodes(barcodes=[1, 1, 1, 1, 2, 2, 3, 3]))