Xóa N Chữ Số để được Số Lớn Nhất - Programming - Dạy Nhau Học

Có thể bạn quan tâm

programmingpython Dolaem_2XT (LeBanCe) July 10, 2020, 1:47pm #1 Các bác hướng em cách giải bài này theo python với ạ. Cảm ơn MN ạ

Nhập 1 chuỗi S gồm toàn các chữ số và 1 số nguyên N. Hãy chỉ ra cách xóa đúng N kí tự ra khỏi S để S có giá trị lớn nhất.

1 Like noz1995 (Trần Hoàn) July 10, 2020, 10:17am #2 Xoá cực tiểu địa phương đầu tiên N lần7 Likes Dolaem_2XT (LeBanCe) July 10, 2020, 10:43am #3 Là sao ạ ? E mới học nên gà lắm bác ạ :(( tntxtnt (‏) July 10, 2020, 2:11pm #5 291 xóa 1 còn 29 xóa 2 còn 91 thì xóa 2 trước khi xóa 1, vậy sao xóa chữ số nhỏ nhất được

5 Likes HR16 (Gà Coder) July 10, 2020, 3:05pm #7 À, mình nhầm

.1 Like TaoLaoBidaoBanBanhBa July 10, 2020, 4:09pm #8 Ví dụ có string = ‘12093’ và số n = 2 Vậy phải xoá 2 số ở vị trí bất kỳ hay 2 số ở vị trí kế tiếp nhau ta?1 Like HR16 (Gà Coder) July 10, 2020, 4:22pm #9 @TaoLaoBidaoBanBanhBa Chắc là 2 số ở vị trí bất kì, đề bảo là xóa đúng N kí tự chứ không bảo là xóa đúng N kí tự ở vị trị kế tiếp nhau

. Hình như kết quả là 293 thì phải.3 Likes tntxtnt (‏) July 10, 2020, 5:01pm #10 xóa dần đần cực tiểu đầu tiên trong các chữ số là được :V Như noz1995 bảo là cực tiểu địa phương :V ko phải xóa chữ số nhỏ nhất :V

nếu chuỗi chữ số tăng vd 1\textcolor{red}12449 thì ta xóa chữ số nhỏ nhất (chữ số đầu tiên hay thứ 2 cũng được)

nếu chuỗi chữ số ko tăng thì ta xóa chữ số sau cùng, cũng là nhỏ nhất :V vd 98643\textcolor{red}3

nếu chuỗi tăng rồi giảm \textcolor{red}2\textcolor{blue}3541 thì ta xóa chữ số đầu tiên thay vì tìm min của chữ số đầu tiên/cuối cùng, vì xóa số đầu tiên thì chữ số thứ 2 đứng đầu sẽ tạo ra số lớn hơn chữ số đầu tiên đứng đầu: \textcolor{blue}3541 > \textcolor{red}2354

nếu chuỗi giảm rồi tăng 543\textcolor{red}26 thì ta xóa chữ số nhỏ nhất, chỉ có 1 cách :V

nếu chuỗi có chữ số giảm tăng giảm tăng hay tăng giảm tăng giảm nhiều lần thì tương tự như trường hợp 3, ta vẫn xóa chữ số đầu tiên của dãy tăng, vì chữ số kế tiếp nó tạo ra số lớn hơn là khi xóa những chữ số đầu tiên của các dãy tăng sau đó :V ví dụ 9876\textcolor{red}6\textcolor{blue}7134 thì xóa số 6 sẽ tạo ra 9876\textcolor{blue}7134 > 9876\textcolor{red}6734

lặp lại N lần là xong :Vthuật toán thì lặp tìm cặp chữ số liền kề nhau đầu tiên sao cho d_{i} < d_{i+1}, nếu tìm thấy thì xóa chữ số ở vị trí thứ i, nếu ko thấy thì xóa ở vị trí cuối cùng. Lặp N lần :VTối ưu hơn thì đừng reset i=0 chạy lại từ đầu sau mỗi lần lặp mà chạy tiếp tục luôn vì trước đó d_i \geq d_{i+1} rồi khỏi cần lặp lại

À mà chắc phải lùi i đi 1 đơn vị :V vd 9876\textcolor{orange}67134 xóa 6 ở i=4 thành 9876\textcolor{orange}7134 lúc này i trỏ tới 7 là thiếu rồi :V :V Nhưng khi lùi thì phải ktra i=0 hay ko nữa mới -1 được :V Thôi reset i=0 luôn cho đỡ nhức đầu =]]À nếu tìm d_{j-1} < d_j rồi xóa ở j-1 thì ko cần lùi j, chắc được =]7 Likes TaoLaoBidaoBanBanhBa July 11, 2020, 1:45am #11 Mình không biết có cách chính thống hay giải thuật nào không, nhưng nếu chỉ là remove 2 (hoặc n) số ở vị trí nào cũng được, thì cũng không phức tạp lắm.Cách làm của mình đơn giản là: #1. Dùng loop để remove 1 số ở tất cả các vị trí, cho hết các kết quả vào list, rồi chọn số lớn nhất #2. Dùng output của #1 và lặp lại n lần bước 1 #3. So sánh output của #2 với string gốc, để biết được n số cần remove là những số nàoVí dụ bên dưới là mình làm tới bước #2Output:

99 [Finished in 0.5s]

6 Likes TaoLaoBidaoBanBanhBa July 11, 2020, 2:04am #13 Bạn đã chạy thử đoạn code bên trên chưa?2 Likes tntxtnt (‏) July 11, 2020, 2:17am #14 à ra là chạy trâu xóa lần lượt tất cả à sorry đọc code chạy nhẩm thử thấy tưởng chỉ lấy max từ từ =]duyệt trâu thì cần 3 dòng thôi =]6 Likes Dolaem_2XT (LeBanCe) July 11, 2020, 4:22am #15 Cảm ơn bác nhé hehehe superthin (Vô Thin) July 12, 2020, 11:59pm #16 Hay! Mình chưa thử bài toàn này, chỉ đọc qua lời giải của bạn thì thấy rất thú vị, nó giống như cách người ta tát ao bắt cá

4 Likes noz1995 (Trần Hoàn) July 13, 2020, 1:22am #17

Là sao ạ ? E mới học nên gà lắm bác ạ :((

Bạn học lớp mấy rồi?1 Like TaoLaoBidaoBanBanhBa July 13, 2020, 2:02am #18 Vâng,mình nghĩ cách này khá đơn giản và không phải loop nhiều (vì số lần loop bị giới hạn bởi lượng chữ số của con số đang xử lý). Nhưng mặt khác mình không chắc là nó thể hiện được tinh thần của bài tập này.4 Likes myhuyen (MyHuyen) August 28, 2024, 2:56am #19 Giải thích hộ mình code này với ạ tntxtnt (‏) August 28, 2024, 3:14am #20 [c for i, c in enumerate(S) if i != j] là tạo mảng từ S bỏ 1 kí tự ở vị trí j ra, mà duyệt for j in range(len(S) nữa thì nó tạo ra đúng len(S) mảng mỗi mảng thiếu 1 số ở vị trí thứ j, rồi lấy max của các mảng này thôivd: 38921 ra 5 mảng con là [8,9,2,1], [3,9,2,1], [3,8,2,1], [3,8,9,1], [3,8,9,2] rồi lấy max trong 5 mảng này là [8,9,2,1]