Xóa N chữ số để được số lớn nhất

#1

Các bác hướng em cách giải bài này theo python với ạ. Cảm ơn MN ạ

  1. 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
#2

Xoá cực tiểu địa phương đầu tiên N lần

7 Likes
#3

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

#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 :thinking:

5 Likes
#7

À, mình nhầm :sweat_smile:.

1 Like
#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
#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 :thinking:. Hình như kết quả là 293 thì phải.

3 Likes
#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

  1. 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)
  2. 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
  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
  4. 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
  5. 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 :V

thuậ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 :V

Tố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 :thinking:

À 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
#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ào

Ví dụ bên dưới là mình làm tới bước #2

my_string = '92091'
my_number = 3


def find_max(string_s):
    list_of_num = []
    for j in range(len(list(string_s))):
        list_TEMP = list(string_s).copy()
        list_TEMP.pop(j)
        list_of_num.append(int(''.join(list_TEMP)))
    return str(max(list_of_num))


i = 0
while i < my_number:
    i = i + 1
    my_string = find_max(my_string)

print(my_string)

Output:

99
[Finished in 0.5s]

6 Likes
#13

Bạn đã chạy thử đoạn code bên trên chưa?

2 Likes
#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 =]

S = '38921'
N = 2
for _ in range(N):
    S = max([c for i, c in enumerate(S) if i != j] for j in range(len(S)))
print(int(''.join(S)))
6 Likes
#15

Cảm ơn bác nhé hehehe

#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á :smiley:

4 Likes
#17

Bạn học lớp mấy rồi?

1 Like
#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
#19

Giải thích hộ mình code này với ạ

#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ôi

vd: 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]

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?