leetcode

commit f0f19d97c5ac7b87520e1c92eaead1f36b470312
parent 6f930ea50d5d4c75483b0224942a3a9a288c86de
Author: Jack Sangdahl <jack@pngu.org>
Date:   Fri, 28 Jun 2024 14:53:45 -0600

386. lexicographical numbers

Diffstat:
A
lexicographical_numbers.c
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
M
lexicographical_numbers.cpp
 | 
19
++++++++++++++++++-
A
lexicographical_numbers.py
 | 
31
+++++++++++++++++++++++++++++++

3 files changed, 93 insertions(+), 1 deletion(-)
diff --git a/lexicographical_numbers.c b/lexicographical_numbers.c
@@ -0,0 +1,44 @@
+// 386. Lexicographical Numbers
+#include "leetcode.h"
+
+/*
+ * given an integer 'n', return all the numbers in the range '[1, n]' sorted in
+ * lexicographical order. you must write an algorithm that runs in O(n) time
+ * complexity and uses O(1) extra space.
+ */
+
+void lex(int *res, int n, int i, int digit, int *k) {
+  if (!digit)
+    return;
+  for (int j = i * 10; j < (i + 1) * 10 && j <= n; j++) {
+    res[(*k)++] = j;
+    lex(res, n, j, digit - 1, k);
+  }
+}
+
+int *lexicalOrder(int n, int *returnSize) {
+  int *ans = (int *)malloc((n + 1) * sizeof(int));
+  int tmp = n, max_digit = 0, k = 0;
+  while (tmp) {
+    tmp /= 10;
+    max_digit++;
+  }
+  for (int i = 1; i < 10 && i <= n; i++) {
+    ans[k++] = i;
+    lex(ans, n, i, max_digit, &k);
+  }
+  *returnSize = k;
+  return ans;
+}
+
+int main() {
+  int rs1, rs2;
+  int *lo1 = lexicalOrder(13, &rs1), *lo2 = lexicalOrder(2, &rs2);
+  for (int i = 0; i < rs1; i++)
+    printf("%d ", lo1[i]); // expect: [1,10,11,12,13,2,3,4,5,6,7,8,9]
+  printf("\n");
+  for (int i = 0; i < rs2; i++)
+    printf("%d ", lo2[i]); // expect: [1,2]
+  printf("\n");
+  free(lo1), free(lo2);
+}
diff --git a/lexicographical_numbers.cpp b/lexicographical_numbers.cpp
@@ -1,6 +1,12 @@
-// dnw
+// 386. Lexicographical Numbers
 #include "leetcode.h"
 
+/*
+ * given an integer 'n', return all the numbers in the range '[1, n]' sorted in
+ * lexicographical order. you must write an algorithm that runs in O(n) time
+ * complexity and uses O(1) extra space.
+ */
+
 class Solution {
 public:
   vector<int> ans;
@@ -24,3 +30,14 @@ private:
     }
   }
 };
+
+int main() {
+  Solution obj;
+  vector<int> lo1 = obj.lexicalOrder(13), lo2 = obj.lexicalOrder(2);
+  for (int i = 0; i < lo1.size(); i++)
+    printf("%d ", lo1[i]); // expect: [1,10,11,12,13,2,3,4,5,6,7,8,9]
+  printf("\n");
+  for (int i = 0; i < lo2.size(); i++)
+    printf("%d ", lo2[i]); // expect: [1,2]
+  printf("\n");
+}
diff --git a/lexicographical_numbers.py b/lexicographical_numbers.py
@@ -0,0 +1,31 @@
+# 386. Lexicographical Numbers
+
+"""
+given an integer 'n', return all the numbers in the range '[1, n]' sorted in
+lexicographical order. you must write an algorithm that runs in O(n) time
+complexity and uses O(1) extra space.
+"""
+
+
+class Solution(object):
+    def lexicalOrder(self, n):
+        """
+        :type n: int
+        :rtype: List[int]
+        """
+        ans = [1]
+        while len(ans) < n:
+            tmp = ans[-1] * 10
+            while tmp > n:
+                tmp /= 10
+                tmp += 1
+                while tmp % 10 == 0:
+                    tmp /= 10
+            ans.append(tmp)
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.lexicalOrder(13))
+    print(obj.lexicalOrder(2))