Nhằm giúp ace nâng cao kỹ năng, kiến thức lập trình, dễ dàng ghi nhớ và hiểu sâu hơn khi đã học lý thuyết về Stack tại series tự học cấu trúc dữ liệu và giải thuật của cafedev. Sau đây là các bài tập có full lời giải và hướng dẫn giải cực chi tiết cho ace trên nhiều ngôn ngữ lập trình khác nhau.
Bài 1: Kiểm tra xem hai cây nhị phân có giống nhau hay không
Viết một thuật toán hiệu quả để kiểm tra xem hai cây nhị phân có giống nhau hay không. tức là nếu chúng có cấu trúc giống nhau thì nội dung của chúng cũng giống nhau
Gợi ý: Ý tưởng là duyệt qua cả hai cây và so sánh giá trị tại nút gốc của chúng. Nếu giá trị khớp, chúng tôi kiểm tra đệ quy xem cây con bên trái của cây thứ nhất có giống với cây con bên trái của cây thứ hai và cây con bên phải của cây thứ nhất có trùng với cây con bên phải của cây thứ hai hay không. Nếu giá trị tại nút gốc của chúng khác nhau, cây vi phạm thuộc tính dữ liệu. Nếu tại bất kỳ thời điểm nào trong đệ quy, cây đầu tiên rỗng cây thứ hai không trống hoặc cây thứ hai rỗng cây thứ nhất không rỗng, các cây vi phạm thuộc tính cấu trúc và chúng không thể giống nhau.
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải theo đệ quy
1.2 Giải bằng vòng lặp
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải theo vòng lặp
Bài 2: Tìm tổ tiên của nút đã cho trong Cây nhị phân
Cho một cây nhị phân, hãy tìm tất cả tổ tiên của nút đã cho trong đó.
Ví dụ:
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
Tổ tiên của nút 9 là 7, 3 và 1
Tổ tiên của nút 6 là 3 và 1
Tổ tiên của nút 5 là 2 và 1
Gợi ý: Ý tưởng là đi ngang cây theo thứ tự và tìm kiếm nút đã cho trên cây. Nếu nút được tìm thấy, chúng tôi trả về true từ hàm. Vì vậy, đối với bất kỳ nút nào, nếu nút đã cho được tìm thấy trong cây con bên trái hoặc cây con bên phải của nó, thì nút hiện tại là tổ tiên của nó.
Bài giải theo đệ quy
Bài giải theo vòng lặp
Bài 3: Đảo ngược văn bản mà không đảo ngược các từ riêng lẻ
Cho một dòng văn bản, đảo ngược văn bản mà không đảo ngược các từ riêng lẻ.
Ví dụ: Input: Chúng tôi cung cấp tài liệu tốt để chuẩn bị cho Phỏng vấn Kỹ thuật CNTT
Output: chuẩn bị Phỏng vấn Kỹ thuật CNTT để cung cấp vật liệu tốt chúng ta
Gợi ý: Một giải pháp đơn giản là đẩy các từ riêng lẻ bắt đầu từ đầu văn bản vào một ngăn xếp. Cuối cùng, chúng tôi bật tất cả các từ từ ngăn xếp và lưu trữ chúng trở lại văn bản theo thứ tự LIFO. Độ phức tạp thời gian của giải pháp này là O (n) và không gian phụ được chương trình sử dụng là O (n) cho ngăn xếp.
Bài giải
Bài 4: Tìm dấu ngoặc đơn trùng lặp trong một biểu thức
Đưa ra một biểu thức cân bằng có thể chứa dấu ngoặc mở và đóng, hãy kiểm tra xem biểu thức có chứa bất kỳ dấu ngoặc đơn trùng lặp nào hay không.
Ví dụ:
Input: ((x+y))+z
Output: Trùm lặp () được tìm thấy trong biểu thức con ((x + y))
Input: (x+y)
Output: Không thấy trùng lặp ()
Input: ((x+y)+((z)))
Output: Trùng lặp () được tìm thấy trong biểu thức con ((z))
Gợi ý: Chúng ta có thể sử dụng một ngăn xếp để giải quyết vấn đề này. Ý tưởng là đi qua
- Nếu ký tự hiện tại trong biểu thức không phải là một dấu ngoặc đóng, thì chúng tôi đẩy ký tự vào ngăn xếp.
- Nếu ký tự hiện tại trong biểu thức là một dấu ngoặc đóng, chúng ta sẽ kiểm tra xem phần tử trên cùng trong ngăn xếp có phải là một dấu ngoặc mở hay không. Nếu nó đang mở ngoặc đơn, thì biểu thức con kết thúc ở ký tự hiện tại có dạng ((exp)), nếu không, chúng tôi tiếp tục xuất các ký tự từ ngăn xếp cho đến khi tìm thấy kết quả phù hợp cho hiện tại
Bài giải
Bài 5: Đánh giá biểu thức hậu tố đã cho
Viết code để đánh giá hiệu quả biểu thức postfix đã cho.
Ví dụ:
82 / sẽ đánh giá cho ra kết quả là 4 (8/2)
138*+ sẽ đánh giá cho ra kết quả là 25 (1+8*3)
545*+5/ sẽ đánh giá cho ra kết quả là 5 ((5+4*5)/5)
Gợi ý: Chúng ta có thể dễ dàng tính giá trị của biểu thức postfix bằng cách sử dụng ngăn xếp. Ý tưởng là duyệt biểu thức đã cho từ trái sang phải. Nếu ký tự hiện tại của biểu thức là một toán hạng, chúng tôi đẩy nó vào ngăn xếp khác nếu ký tự hiện tại là một toán tử, chúng tôi bật hai phần tử trên cùng từ ngăn xếp, đánh giá chúng bằng toán tử hiện tại và đẩy kết quả trở lại ngăn xếp. Khi tất cả các ký tự của biểu thức được xử lý, chúng ta sẽ chỉ còn lại một phần tử trong ngăn xếp chứa giá trị đánh giá.
Giải bài
Bài giải
Bài 6: Kiểm tra xem biểu thức đã cho có phải là biểu thức cân bằng hay không
Cho một chuỗi chứa dấu ngoặc nhọn mở và đóng, hãy kiểm tra xem nó có đại diện cho một biểu thức cân bằng hay không.
Ví dụ:
{[{} {}]} [()], {{} {}}, [] {} () là các biểu thức cân bằng.
{()} [), {(}) không cân bằng.
Gợi ý: Chúng ta có thể sử dụng một ngăn xếp để giải quyết vấn đề này. Chúng ta duyệt qua biểu thức đã cho và
- Nếu ký tự hiện tại trong biểu thức là một dấu ngoặc nhọn mở, chúng tôi đẩy nó vào ngăn xếp.
- Nếu ký tự hiện tại trong biểu thức là một dấu ngoặc nhọn đóng, chúng tôi bật một ký tự từ ngăn xếp và chúng tôi trả về false nếu ký tự được bật lên không giống với ký tự hiện tại hoặc nó không ghép nối với ký tự hiện tại của biểu thức. Ngoài ra, nếu ngăn xếp được tìm thấy là trống, điều đó có nghĩa là số lượng dấu ngoặc nhọn mở ít hơn số lượng dấu ngoặc nhọn đóng tại điểm đó, do đó biểu thức không thể được cân bằng.
Bài giải
Hướng dẫn cách xem và tải tài liệu từ trang cafedev tại đây.
Bài giải
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
