25
4
Địa chỉ câu hỏi: https://leetcode.com/problems/monotone-increasing-digits/description/
Cho số nguyên N không âm, tìm số lớn nhất nhỏ hơn hoặc bằng N có các chữ số tăng dần đơn điệu.
(Hãy nhớ rằng một số nguyên có các chữ số tăng dần đơn điệu khi và chỉ khi mỗi cặp chữ số liền kề x và y thỏa mãn x <= y.)
Ví dụ 1:
Trung tâm cá nhân
Điều phát hành
từ bỏĐầu vào: N = 10 Đầu ra: 9
Ví dụ 2:
Đầu vào: N = 1234 Đầu ra: 1234
Ví dụ 3:
Đầu vào: N = 332 Đầu ra: 299
Lưu ý: N là số nguyên trong khoảng [0, 10^9].
Tìm số lớn nhất nhỏ hơn số này trong đó mỗi chữ số đều tăng dần.
Chia các số cho trong câu hỏi thành mảng cho dễ hiểu. Nếu hiểu được điều này thì chúng ta cần tìm mảng tăng lớn nhất.
Cách thực hiện là tìm vị trí giảm dần đầu tiên. Có hai tình huống:
Trường hợp 1: Với 14267, vị trí giảm dần đầu tiên là 4 nên đổi 4 thành 3 và đổi tất cả các số sau 4 thành 9. Ta được 13999;
Trường hợp 2: Đối với 1444267 thì vị trí giảm dần đầu tiên là 4 cuối cùng. Nếu chỉ xử lý 4 số cuối theo trường hợp 1 thì kết quả là 1443999, vẫn chưa đúng nghĩa câu hỏi. Vì vậy, bạn cần tìm số 4 ở vị trí đầu tiên, sau đó thực hiện thao tác case1, để có được 1399999.
Khi tôi viết mã, tôi đã làm theo thứ tự ngược lại, sau đó tôi đã mắc lỗi và viết num[i] > num[i - 1] hoặc (ind != -1 và num[i] == num[i - 1]). Tại sao nó không thể là num[i] == num[i - 1]? Vì làm như vậy sẽ tìm được vị trí bằng nhau cuối cùng, còn ta chỉ cần tìm vị trí bằng nhau đầu tiên mà thôi.
Độ phức tạp về thời gian là O(n) và độ phức tạp về không gian là O(n).
Mã này như sau:
class Giải pháp: def monotoneIncreasingDigits(self, N): """ :type N: int :rtype: int """ if N < 10: return N num = [int(n) for n in str(N)[:: -1]] n = len(num) ind = -1 for i in range(1, n): if num[i] > num[i - 1] hoặc (ind != -1 và num[i] == num[ind]): ind = i if ind == -1: return N res = '9' * ind + str(num[ind] - 1) + "".join(map(str , num[ind + 1:])) return int(res[::-1])
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Nếu bạn không sử dụng thứ tự ngược lại, bạn cũng có thể làm:
class Giải pháp: def monotoneIncreasingDigits(self, N): """ :type N: int :rtype: int """ if N < 10: return N num = [int(n) for n in str(N)] n = len(num) ind = n - 1 for i in range(n - 2, -1, -1): if num[i] > num[i + 1] hoặc (ind != n - 1 và num[i] == num[ind]): ind = i if ind == n - 1: return N num[ind] -= 1 for i in range(ind + 1, n): num[i] = 9 trả về int("".join(map(str, num)))
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Tài liệu tham khảo:
https://leetcode.com/problems/monotone-increasing-digits/discuss/109794/Simple-Python-solution-w-Explanation
DDKK.COM Brother Kuaikan-hướng dẫn, trang thông tin lập trình dành cho lập trình viên, bản quyền thuộc về tác giả gốc
Bài viết này được viết bởi:nến tuyết tiêu cực Được ủy quyền xuất bản, không tổ chức, cá nhân nào được chuyển tiếp nếu không có sự cho phép của tác giả
25
4
0
fiddle :http://jsfiddle.net/rtucgv74/ Tôi đang cố gắng khớp ký tự đầu tiên với số có 3 chữ số. Vì vậy, mã bên dưới sẽ cảnh báo f234. Nhưng thay vào đó nó trả về null? Mã nguồn: varreg
Sao chép mã như sau: Dim strOk,strNo strOk = "12312321$12
Tôi muốn tìm mẫu {a number}/{a number}/{a string}. Tôi có thể làm cho số/số hoạt động nhưng khi tôi thêm/chuỗi thì không. Ví dụ tôi đang cố gắng tìm: 15
Tôi, tôi đang tạo một mẫu biểu thức chính quy để kiểm tra xem một chuỗi có phải là: number.number.number như thế này: 1.1.1 0.20.2 58.55541.5221 Trong java tôi sử dụng chuỗi này: Private static Patt
Tôi có một chuỗi và tôi cần kiểm tra xem nó có chứa số/số ở cuối chuỗi hay không và cần tăng số/chữ số đó lên cuối chuỗi +1 Tôi sẽ nhận được chuỗi sau string2 =giả sử_name_1 string3
Tôi đang tìm biểu thức chính quy (số/số) như (1/2) Số phải có 1-3 chữ số. Tôi sử dụng Java. Tôi nghĩ vấn đề của tôi sâu sắc hơn biểu thức thông thường. Tôi không thể làm việc này String s="(1/15)";
Ai đó có thể giúp tôi hiểu tại sao tôi gặp lỗi loại khi sử dụng đoạn mã sau không: function sumOfTwoNumbersInArray(a: [number, number]) { return a[0] +
Tôi đã từng thấy một số người gặp phải vấn đề tương tự trước đây, nhưng họ có vẻ khác nhau nên giải pháp cũng khác nhau. Vì vậy, đây là: Tôi đang cố gắng trả về phạm vi kích thước đã biết của một trang tính trong Google Apps Script như thế này: var myRange
Tôi đang cố gắng hiểu mô-đun biểu thức chính quy trong python. Tôi đang cố gắng làm cho chương trình của mình khớp với mẫu sau từ một dòng văn bản do người dùng nhập: Các số trong khoảng 8-13 "/" Các số trong khoảng 0-15 Ví dụ: 2/8, 13/11, 10/9, vân vân. Mẫu tôi nghĩ ra
Nói một cách đơn giản, chương trình tôi đang thực hiện yêu cầu tôi phải chia đầu vào của máy quét (ví dụ: 2 giăm bông và phô mai 5,5). Nó sẽ đọc các đơn đặt hàng tạp hóa và chia chúng thành ba mảng. Tôi nên sử dụng string.split và có thể chia đầu vào này thành ba phần bất kể từ ở giữa
(số) & (-số) nghĩa là gì? Tôi đã tìm kiếm nhưng không tìm thấy nghĩa tôi muốn dùng i & (-i) trong vòng lặp for, ví dụ: for (i = 0; i 110000 . Đối với i không có giá trị nào cao hơn
Cần đặt ID hình ảnh thành một số var number = $(this).attr('rel'); number =parseInt(number);
Tôi có một hàm mà tôi muốn đảm bảo rằng nó chấp nhận một chuỗi theo sau là một số. Và tùy chọn, thêm các cặp số chuỗi. Giống như một bộ dữ liệu, nhưng "vô hạn" số lần: const fn = (...args: [string, number] | [s
Tôi muốn sao chép thay đổi của số đầu vào "Có sẵn" và cộng hoặc trừ nó vào "Tổng" Nếu người đó thay đổi "Có sẵn" thành "3", "Tổng" sẽ trở thành "9". Nếu người dùng thay đổi "Có sẵn" thành "5", "Tổng" sẽ trở thành "11". $('#id1').b
Tôi gặp sự cố đơn giản liên quan đến dây bị đứt trong R. Tôi đang cố gắng dán nhưng tôi gặp khó khăn khi ngắt quãng giữa (ký tự/số). Lưu ý rằng các giá trị được chứa trong vectơ (V1=81,V2=55,V3=25) Tôi đã thử mã này: cat(p
Thật khó để nói những gì đang được hỏi ở đây. Câu hỏi mơ hồ, mơ hồ, không đầy đủ, quá rộng hoặc hùng biện và không thể trả lời hợp lý ở dạng hiện tại. Để được trợ giúp làm rõ vấn đề này để bạn có thể mở lại, hãy truy cập trung tâm trợ giúp. Đã đóng
Tôi đang gặp lỗi sau trong Bản mô tả: Đối số của loại 'số []' không thể gán cho tham số của loại 'số' I
Trong hướng dẫn này, bạn sẽ tìm hiểu về số JavaScript thông qua các ví dụ. Trong JavaScript, số là kiểu dữ liệu cơ bản. Ví dụ: const a = 3; const b = 3.13; không giống như một số ngôn ngữ lập trình khác
Tôi đã đọc trên MDN Giới thiệu lại về JavaScript rằng số JavaScript chỉ là loại chính xác của dấu phẩy động, không có số nguyên trong JavaScript. Tuy nhiên, JavaScript có hai chức năng, pa
Chúng tôi quản lý hàng tồn kho của mình trong Excel. Tôi biết điều này hơi lỗi thời, nhưng chúng tôi đang phát triển một công ty kinh doanh và tất cả tiền của chúng tôi bị kẹt vào hoạt động kinh doanh và không có tiền để đầu tư vào CNTT. Vì vậy, tôi đang tự hỏi liệu tôi có thể sử dụng Excel theo chương trình để tự động hoàn thành số sản phẩm không? đây là một sản phẩm
Tôi là một lập trình viên xuất sắc, rất giỏi!