Tìm Kiếm Tài Năng Dạy Nhau Học

#1

Title cho ngầu vậy thôi ạ :smiley:
Ai có gạo thì góp thôi ạ :smile:

  1. Viết thuật toán để đảo ngược các kí tự alphabet trong 1 string, còn các kí tự khác (tạm gọi là các kí tự đặc biệt) ko thay đổi.
    Ví dụ:
  • Input: “a.b,c@d”
  • Output: “d.c,b@a”
  1. Viết thuật toán để trả về 1 tập con nhỏ nhất trong 1 tập các số tự nhiên cho trước, sao cho tổng các phần tử của tập con đó lớn hơn 1 số nguyên dương cho trước.
    tập con nhỏ nhất : là tập hợp có số phần tử ít nhất, sau đó là tổng các phần tử nhỏ nhất có thể.
    Ví dụ 1:
  • Input: list_input = [ 4,7,9,5,0,10], int_input = 8
  • Output: list_output = [9]
    Ví dụ 2:
  • Input: list_input = [ 4,3,5] , int_input = 6
  • Output: list_output = [3,4]
    2 bài mới thấy trên Facebook.
    Với bài 1 thì em giải như sau
from string import punctuation
s = 'a.b,c@d'
s = list(s)
specialchar = set(punctuation)
for i in range(len(s) // 2):
    if {s[i], s[-(i + 1)]} - specialchar == {s[i], s[-(i + 1)]}:
        s[i], s[-(i + 1)] = s[-(i + 1)], s[i]
s = ''.join(s)

Còn bài 2 thì em chưa biết làm như thế nào :joy:

1 Like
#2

Tập con có liên tiếp không ấy nhỉ, nếu liên tiếp thì chặt nhị phân thôi =)) còn nếu không thì QHĐ…

#3

2 câu này phỏng vấn :smile: Không cần liên tiếp

#4

Đời ngang trái thế :’( QHĐ thôi :frowning:
[spoiler]Vẫn là nhìn thấy như thế, nhưng chưa nghĩ ra nên làm gì tiếp theo :joy:[/spoiler]

Còn có 1 cách tham lam, sort tăng tất cả các phần tử rồi chặt nhị phân :v đề bảo không liên tiếp mà :v triển thôi, nhưng sợ sai :’( không có test case để thử nhỉ :v

Cái ví dụ 2 hơi sai nhỉ, list_output phải là [4, 3] chứ :v

#5

Em thì mù tịt không biết thuật toán là cái gì mặc dù mấy lần cũng ráng học mà mãi không vô :smile: gặp mấy bài này cũng bật ngữa

1 Like
#6

Cố lên =)) học mấy cái đơn giản trước, kiểu như thuật toán tìm kiếm, backtrack rồi dần phát triển lên =))

#8

E vẫn ngu ngơ không biết code nó thế nào :open_mouth:

#9

Ko đọc kĩ đề là tập con nhỏ nhất :smiley:

1 Like
#10

Ý nghĩ đầu tiên của mình khi đọc bài 2 là sắp xếp lại chuỗi đầu vào rồi tìm từ đuôi lên. Nếu số cuối cùng mà nhỏ hơn thì tính tổng 2 số cuối cùng. Nếu tổng 2 số cuối cùng mà nhỏ hơn int_input thì tính tổng 3 số cuối cùng…
Nếu tổng n số lớn hơn thì tìm khối n số nhỏ nhất lơn hơn int_input
Nếu tổng tất cả các số nhỏ hơn int_input thì trả về null

1 Like
#11

Nhìn sơ qua thì có 2 trưởng hợp nhỉ.
1 là trong list có số > int_input
2 là các số trong list đều < int_input
Còn trưởng hợp nào nữa ko ?
TH1 thì chọn số nào bé nhất trong số >int_input.
TH2 thì sắp xếp tăng dần rồi cộng các phần tử trong list

#12

Em lượm Facebook thì nó chỉ ngắn gọn thế thôi

#13

đọc cái thuật toán knapsack gì đó rồi chế biến thêm

2 Likes
#14

Hix bài này phải xé nó ra thành bài nhỏ hơn, Tìm tất cả các tập con của list_input???, làm được cái này thì như xong được 80%…hix hix hix
c1of7+c2of7+c3of7+c4of7+c5of7+c6of7=.
bài này thuộc thể loại vét cạn, !!!

1 Like
#15

Em làm bài 1 cách này. Các bác xem giúp e có được không ạ

# Khai bao bang chu cai
chu_cai = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
# Nhap vao chuoi ki tu
stri = raw_input("Nhap vao cac ki tu can sap xep : ")
# Tach chuoi ki tu thanh mang?
stri_list = list(stri)
print " Chuoi~ ki tu nhap vao la`:"
print stri_list
print "Chung ta se sap xep lai nhe !"
raw_input("Nhan phim bat ki de tiep tuc!")
# Tach mang? thanh cac mang rieng de sap xep
# n1 la mang cac chu~ (theo thu tu ban dau)
# n2 la mang cac ki tu dac biet ( theo thu tu ban dau)
# n3 la mang cac chu~ ko tach roi`
n1 =[]
n2 =[]
n3 =[]
n = []
# k la phan tu chen` them vao`
k = 0
for check_ki_tu in stri_list :
	if check_ki_tu in chu_cai :
		n1.append(check_ki_tu)
		n2.append(k)
	else :
		n2.append(check_ki_tu)
		n1.append(k)

for check_ki_tu in stri_list:
	if check_ki_tu in chu_cai:
		n3.append(check_ki_tu)

i = 0
l = len(n3)
while i < len(n1):
	if n1[i] in chu_cai:
		n.append(n3[l-1])
		l = l-1
	else :
		n.append(n2[i])
	i = i + 1

print " Cac ki tu ban dau la` :" ,stri
print "Cac ki tu sap xep lai la` : ", ''.join(n)
#16

Còn bài 2 thì em làm như này,các bác xem giúp e có ok không ạ

print " Nhap vao hang tu. Go~ 'Done' de ket thuc"
mang_dau_vao = []
while True:
	hang_tu = raw_input(">")
	if hang_tu != "Done":
		mang_dau_vao.append(int(hang_tu))
	else :
		break
print " Cac hang tu da nhap vao la :", mang_dau_vao

print "Nhap vao so ha.ng kiem tra :"
k = int(raw_input(">"))

tong_cac_so = 0
mang_dau_ra = []
while tong_cac_so < k :
	so_lon_nhat = max(mang_dau_vao)
	mang_dau_ra.append(so_lon_nhat)
	i = 0
	while i < len(mang_dau_vao):
		if mang_dau_vao[i] == max(mang_dau_vao):
			mang_dau_vao.pop(i)
			break
		else :
			i = i + 1
	for so_hang in mang_dau_ra:
		tong_cac_so = tong_cac_so + so_hang
print "Ma?ng con thoa man~ la`:", mang_dau_ra
print " Do dai ma?ng con la`:" , len(mang_dau_ra)
#17

Câu 2 nhé:

def list_subset(m_elt, n):
    """Trả về tất cả xâu nhị phân độ dài 2**n có m_elt '1'
    """
    for j in range(2 ** n):
        b = bin(j)[2:]
        if b.count("1") == m_elt:
            yield "".join(['0'] * (n - len(b))) + b


def smaller_subset(list_integer, n):
    sorted_list = sorted(list_integer)[::-1]
    len_list = len(list_integer)
    for i in range(len_list):
        for subset in list_subset(i, len_list):
            l = [sorted_list[e] for e in range(len_list) if subset[e] == "1"]
            if sum(l)>n:
                return l
    return []


print(smaller_subset([4, 7, 9, 5, 0, 10], 8))
[9]
print(smaller_subset([4, 3, 5], 6))
[4, 3]

Câu 1 có vẻ sai nhé, lời giải trên thì các kí tự đối diện kí tự đặc biệt không bị đổi chỗ, ví dụ “abcd@ef”
lời giải Grak_T
“fecd@ba”
trong khi tui hiểu đề thì kết quả phải là
fedc@ba

1 Like
#18 
using System;
using System.Collections.Generic;
using System.Linq;

int[] Bai2(int[] list_input, int int_input)
{
    if (list_input == null)
        return null;//Cái này để chống lỗi, nếu thằng nào nhập mảng null thì không sort được.
    Array.Sort(list_input);//Sort lại để dễ tìm dãy nhỏ nhất
    int OutputLength = 0;//Biến này sẽ lưu kích thước của mảng output
    var TempList = new List<int>();//Biến này sẽ đóng vai trò mảng output
    while (TempList.Sum() <= int_input)
    {
        TempList.Clear();
        OutputLength += 1;
        if (OutputLength > list_input.Length)
            return null;//Nếu như cả dãy cộng lại cũng không đủ lớn thì trả về null
        for (int i = 1; i <= OutputLength; i += 1)
        TempList.Add(list_input[list_input.Length - i]);//Nếu không thì cộng dãy lớn nhất có độ dài bằng OutputLength lại để xem có lớn hơn int_input không.
    }
    TempList.Clear();
    int Position;
    for (Position = 0; Position < OutputLength; Position += 1)
        TempList.Add(list_input[Position]);//Đưa các số đầu tiên trong dãy vào list.
    while (TempList.Sum() <= int_input)
    {
        TempList.RemoveAt(0);
        TempList.Add(list_input[Position]);//Nếu chưa đủ lớn thì xoá số nhỏ nhất rồi thêm số tiếp theo trong dãy ban đầu
        Position += 1;//Vị trí của số tiếp theo
    }
    return TempList.ToArray();
}
#19

chết chưa đọc đến python =))

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