Cần giúp ý tưởng làm bài tập về chuỗi

Đây là bài tập, mình cần phải làm, mình chưa tìm dc giải thuật nào cả, bạn nào có thể hướng dẫn mình được không,code mẫu cho mình bằng ngôn ngữ javascript giúp mình với, mình cảm ơn nhiều nhiều…

Đây là code mình viết theo ý tưởng của bạn Tên Gì Cũng Được nhưng , chạy vẫn chưa đúng, ai biết giúp mình với:

var str=‘bbbbb’;
var subStr=[];
for(let i=0;i<str.length;i++){
if(!subStr.includes(str[i])){
subStr.push(str[i]);
}
}
var isArrange=true;
for(let i=0;i<subStr.length;i++){
var count=0;
for(let j=0;j<str.length;j++){
if(subStr[i]===str[i]){
count++;
}
}
if(count>str.length+1/3){
isArrange=false;
break;
}
}
console.log(isArrange);

Trong ví dụ của đề đã có gợi ý rồi.
Lên trang Geeksforgeeks.org mà tìm.

6 Likes

Phương châm ở DNH là:
Người thảo luận để tìm ra cách giải hay cho một bài toán khó sẽ trở thành lập trình viên giỏi. Người hay hỏi bài tập thì không. Còn bạn thì sao?

Trong trường hợp của bạn thì bạn nên thử xem một video tổng hợp hết các kiến thức cơ bản về Javascript cho người mới bắt đầu. Mình đề xuất video này của Programming with Mosh, video tiếng Anh nhưng có phụ đề đàng hoàng, giải thích dễ hiểu, thời lượng video cũng chỉ khoảng 45 phút thôi, chưa đến một tiếng như trên thumbnail:

7 Likes

Do thời hạn bài làm đã đến rất gần r, trc khi post bài mình cũng đã tìm hiểu đọc rất nhieuf, quá nản vì chưa tìm dc giải pháp , thời gian nộp bài thì càng đến gần nên mình ms quyết định post lên đây để tìm giải pháp bài tập này code như thế nào r mình học theo code để hiểu code đó. Dù sao thì cũng cảm ơn bạn. Mình vẫn rất cần ai đó code mẫu bằng js ạ :sleepy:

1 Like

Không có kí tự nào xuất hiện quá (len + 1)//2 +1

4 Likes

cảm ơn bạn, để mình thử code theo hướng này

Bạn ơi, sao code mình viết theo ý tưởng của bạn lại ko dc , nhỉ , hiz. đây là code mình viết:

var str='bbbbb';
var subStr=[];
for(let i=0;i<str.length;i++){
  if(!subStr.includes(str[i])){
    subStr.push(str[i]);
  }
}
var isArrange=true;
for(let i=0;i<subStr.length;i++){
  var count=0;
  for(let j=0;j<str.length;j++){
    if(subStr[i]===str[i]){
      count++;
    }
  }
  if(count>str.length+1/3){
    isArrange=false;
    break;
  }
}
console.log(isArrange);

Điều kiện cần: Từ 1 đến n có \lceil\frac{n}{2}\rceil số lẻ, nếu tần suất vượt quá số này thì phải xếp vào vị trí chẵn nữa mới đủ => loại.
Điều kiện đủ: Theo thứ tự tần suất giảm dần, xếp từng kí tự vào vị trí lẻ, còn bao nhiêu thì xếp vào vị trí chẵn.

Nếu có một loại kí tự vừa nằm vị trí chẵn vừa nằm vị trí lẻ thì tần suất của nó nhỏ hơn \lceil\frac{n}{2}\rceil. Ánh xạ từ chẵn thành lẻ thì do số số lẻ lớn hơn tần suất nên không bị đụng nhau.

5 Likes

Khó hiểu quá bạn ơi @@ đọc mà ko hiểu

Cách trâu nhất là bạn sinh hoán vị chuỗi để kiểm tra

Cái thuật toán sinh hoán vị nó chạy lâu lắm, sẽ có n! trường hợp , n là độ dài chuỗi, bạn nên tham khỏa link này nè

Tóm lại là lập bảng tần suất rồi duyệt qua là được :smiley:

p/s: vừa thêm phần chứng minh :smiley:

4 Likes

nhắc lại: (len + 1)//2 +1
bạn cần xem lại kiến thức về toán của mình, sự ưu tiên của phép toán, mình đâu rảnh đâu mà không viết là 3 luôn mà ghi 2+1
phép // là chia lấy nguyên

7 Likes

rồi đẻ mình thử lại bạn ạ, cảm ơn bạn nha

mình vẫn chưa hiểu điều kiện đủ có ý nghĩa gì khi mà điều kiện cần (cũng chính là cái mình đã đưa ra như ở trên) đã đủ kiểm tra?
phần cuối bài vô cùng tối nghĩa và cũng không hiểu ban đang nói gì
đã là chứng mình thì phải dùng những câu từ dễ hiểu, ngắn gọn và xúc tích chứ không phải giống như giải thích trực tiếp bằng lời mà có thể ghi như vậy được

với chuỗi có n kí tự thì có L = (n//2 + n%2) kí tự lẻC = (n//2) kí tự chẵn
do L >= C nên để có thể sắp xếp được như đề bài mô tả, thì không có kí tự nào trong chuỗi xuất hiện quá L lần.
Gọi f là tần suất xuất hiện của một kí tự bất kì trong chuỗi. Công thức f <= L
công thức trên cũng tương đương với comment ở trên (f < L + 1)

chứng minh:
gọi fx là tần suất xuất hiện của kí tự x bất kì trong chuỗi.
Để thõa mãn điều kiện đề bài, [mỗi kí tự bên phải của kí tự x] trong chuỗi phải [khác x]
[số lượng kí tự bên trái của kí tự x] = fx - 1 (trừ 1 là vì có thể loại đi 1 kí tự ở tần cùng bên phải có thể là rỗng mà vẫn thõa mãn điều kiện)
như vậy đồ dài tối thiểu của chuỗi cần có để thõa mãn điều kiện là LEN_min = fx + fx - 1 = 2*fx - 1
LEN >= 2*fx - 1
fx <= (LEN + 1)//2
công thức cuối cùng để // thay vì / là do fx luôn nguyên

8 Likes

Tên Gì Cũng Được Ơi, mình đã sửa lại và code chạy được r !! Mình mới test thử 1 vài cases thì đang chạy được r, chưa biết ổn định thế nào nhưng tại vì vui quá nên mình phải comment lên đây để bạn biết đó, cảm ơn nhiều nha!!

2 Likes

Bạn chỉ chứng minh mỗi phần là các chuỗi hợp lệ đều có tính chất như thế mà thôi.

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