diff options
Diffstat (limited to 'montone_increasing_digit.c')
-rw-r--r-- | montone_increasing_digit.c | 53 |
1 files changed, 53 insertions, 0 deletions
diff --git a/montone_increasing_digit.c b/montone_increasing_digit.c new file mode 100644 index 0000000..843db35 --- /dev/null +++ b/montone_increasing_digit.c @@ -0,0 +1,53 @@ +// 738. Monotone Increasing Digits +#include "leetcode.h" + +/* + * an integer has monotone increasing digits if and only if each pair of + * adjacent digts 'x' and 'y' satisfy 'x <= y'. given an integer 'n', return the + * largest number that is less than or equal to 'n' with monotone inccreasing + * digits + */ + +char *int_to_str(int n) { + char *res = malloc(11); + int val = n, idx = 0; + while (val) { + res[idx] = val % 10 + '0'; + val /= 10; + idx++; + } + res[idx] = '\0'; + for (int i = 0; i < idx / 2; i++) { + char tmp = res[i]; + res[i] = res[idx - 1 - i]; + res[idx - 1 - i] = tmp; + } + return res; +} + +int str_to_int(char *s) { + int n = strlen(s), val = 0; + for (int i = 0; i < n; i++) + val *= 10 + s[i] - '0'; + return val; +} + +int monotoneIncreasingDigits(int n) { + char *s = int_to_str(n); + int j = strlen(s), k = j; + for (int i = k - 1; i; i--) { + if (s[i] >= s[i - 1]) + continue; + s[i - 1]--; + j = i; + } + for (int i = j; i < k; i++) + s[i] = '9'; + return str_to_int(s); +} + +int main() { + printf("%d\n", monotoneIncreasingDigits(10)); // expect: 9 + printf("%d\n", monotoneIncreasingDigits(1234)); // expect: 1234 + printf("%d\n", monotoneIncreasingDigits(332)); // expect: 299 +} |