_Gia_Cat_Luong_
Senior Member
K hiểu đề fen ơi ? Sort theo gì đây, mỗi phần tử phải xuất hiện 1 lần rồi mới xuất hiện lại hả ?
thảo luận [Học Tập] Topic thuật toán
- Người tạo chủ đề unknowpc90
- Ngày bắt đầu
KimSoHyunGoddness
Member
Đúng rồi bác. Sort theo kiểu liên tiếp nhau ấy.
Bài tập này em tự nghĩ ra để nâng cao trình độ mà xong cái ko giải được luôn
_Gia_Cat_Luong_
Senior Member
Nếu value trong input thấp thì bài này dùng count sort là được.Đúng rồi bác. Sort theo kiểu liên tiếp nhau ấy.
Xem tệp đính kèm 708750
Xem tệp đính kèm 708761
Bài tập này em tự nghĩ ra để nâng cao trình độ mà xong cái ko giải được luôn
Nếu value trong input cao thì chắc là kết hợp nhiều cách sort chăng, nhưng về cơ bản vẫn là dùng count sort.
Hoặc là chuyển mảng input về dạng [3,2,1,2,3,4] => [(0,3),(0,2),(0,1),(1,2),(1,3),(0,4)]
Giá trị đầu tiên là thứ tự xuất hiện giữa các duplication của phần tử đó trong mảng, giá trị thứ 2 chính là phần tử đó. Cái này có thể làm O(n) bằng Hashmap.
Sau đó gọi hàm sort bình thường trên tuple => [(0,1),(0,2),(0,3),(0,4), (1,2),(1,3)] => map lại lấy value thứ 2 thôi [1,2,3,4,2,3].
KimSoHyunGoddness
Member
À bác cho em hỏi cái này 1 chút là. VỚi các bài toán giải bằng vòng lặp thì đều có thể giải bằng đệ quy. Vậy thì có ngược lại ko ? Tất cả bài toán giải bằng đệ quy đều giải được với vòng lặp.
Kân team
Member
được.
"giả lập" đệ quy cứ thay bằng 1 cái stack là xong. Bản chất đệ quy cũng chỉ là 1 cái stack chứ có mọe gì đâu
tu_do_quan_diem
Senior Member
Đệ quy = recursionĐệ quy là Recursion hả các fen ?
Quy hoạch động = dynamic programming
Giải thuật tham lam = greedy algorithm
Chục năm rồi tôi vẫn nhớ các từ tiếng Việt căn bản
minhgiang_hipvoz
Junior Member
các bác hay học thuật toán ở đâu
vexliva
Member
À thanks, mà tôi chỉ nhớ đc thuật toán "vét cạn" thôi mỗi lần thấy từ đó là liên tưởng tới ........ "không còn giọt nào"Đệ quy = recursion
Quy hoạch động = dynamic programming
Giải thuật tham lam = greedy algorithm
Chục năm rồi tôi vẫn nhớ các từ tiếng Việt căn bản
Sửa lần cuối:
thuyduong2007
Member
Được nha. Đệ quy nó hoạt động dựa vào call stack. Mình hoàn toàn có thể dùng 1 cái stack để giải quyết bài toán thay vì gọi đệ quy.Ví dụ như bài này: https://leetcode.com/problems/binary-tree-inorder-traversal/
Mình sẽ giải bằng cả 2 cách cho bạn nhé.
C++:
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
//return inorderTraversalRecursive(root);
return inorderTraversalNotRecursive(root);
}
vector<int> inorderTraversalRecursive(TreeNode* root){
if (root != NULL){
vector<int> result(inorderTraversal(root->left));
result.push_back(root->val);
vector<int> right(inorderTraversal(root->right));
result.insert(result.end(), right.begin(), right.end());
return result;
} else return {};
}
vector<int> inorderTraversalNotRecursive(TreeNode* root){
if (root == NULL) return {};
stack<TreeNode*> myStack;
myStack.push(root);
vector<int> result;
while (!myStack.empty()){
if (myStack.top()->left != NULL){
TreeNode* left = myStack.top()->left;
myStack.top()->left = NULL;
myStack.push(left);
} else {
TreeNode* node = myStack.top();
result.push_back(node->val);
myStack.pop();
if (node->right != NULL){
myStack.push(node->right);
}
}
}
return result;
}
};
Yêu em Thu Nga CN12 ptit
Senior Member
Quy hoạch động có trick nào không các bác? Ngoài ngồi code mòm tay lòi trĩ thì thành pro, mới động vào 1 2 ngày mà thấy chẳng update thêm tí kiến thức nào 
thuyduong2007
Member
Có nhé. Trick là cứ làm nhiều là sẽ quen thôi.Quy hoạch động có trick nào không các bác? Ngoài ngồi code mòm tay lòi trĩ thì thành pro, mới động vào 1 2 ngày mà thấy chẳng update thêm tí kiến thức nào
Yêu em Thu Nga CN12 ptit
Senior Member
hẹn bác 1 tháng sau em quay lạiCó nhé. Trick là cứ làm nhiều là sẽ quen thôi.
yuyuko1996
Senior Member
tui không biết giải đúng k nhưng idea là v
- B1: tạo 1 mảng 2 chiều (mục đích là để đưa tất cả các phần tử không trùng lặp vào từng mảng riêng biệt)
- B2: Kiểm tra nếu phần tử i không trùng lặp với bất kì phần tử nào trong mảng => đưa vào mảng đó. Nếu không tìm thấy thì push 1 mảng mới chứa phần tử i vào mảng 2 chiều.
- B3: Sort từng mảng không trùng lặp đã tách
- B4: concat lại
[email protected]
Senior Member
https://www.topcoder.com/thrive/articles/Dynamic Programming: From Novice to AdvancedQuy hoạch động có trick nào không các bác? Ngoài ngồi code mòm tay lòi trĩ thì thành pro, mới động vào 1 2 ngày mà thấy chẳng update thêm tí kiến thức nào
có cách là làm nhiều thôi.
_Gia_Cat_Luong_
Senior Member
Chuyên mục mỗi ngày một leetcode.
Khá buồn là từ hôm nay thì mình sẽ bận nhiều nên đành stop serie này. Hằng ngày mình vẫn dành chút tgian làm LC, nhưng k có thời gian share lên cho mọi người nữa. Hy vọng mọi người vẫn giữ tinh thần học tập cao như thời gian vừa qua. Mình vẫn tàu ngầm voz nên thỉnh thoảng có gì hay vẫn sẽ chém gió cùng mn. Chúc các fen thành công. Tạm biệt.
Khá buồn là từ hôm nay thì mình sẽ bận nhiều nên đành stop serie này. Hằng ngày mình vẫn dành chút tgian làm LC, nhưng k có thời gian share lên cho mọi người nữa. Hy vọng mọi người vẫn giữ tinh thần học tập cao như thời gian vừa qua. Mình vẫn tàu ngầm voz nên thỉnh thoảng có gì hay vẫn sẽ chém gió cùng mn. Chúc các fen thành công. Tạm biệt.
KimSoHyunGoddness
Member
huhuhu. Bác đi rồi ai giúp em làm bài đây
Coffe_Bên_Lề
Senior Member
Thím cứ làm bài đi rồi post lên đây cho mọi người cùng chộp giậthuhuhu. Bác đi rồi ai giúp em làm bài đây
em là em thích nhìn mục lời giải lắm
Yêu em Thu Nga CN12 ptit
Senior Member
Check hộp với bác, làm trên leetcode bài đực bài cái quáThử suy nghĩ bth trước nếu k dùng DP thì fen sẽ giải ntn ?
Sau đó, fen nhận thấy cách làm brute-force sẽ phải giải đi giải lại các bài toán con
Tìm cách lưu lại các bài toán con đó để improve performance ?
Cuối cùng là nghĩ cách làm bottom up cho nó đậm chất DP
Cố lên mai fen. Tui có list các bài DP cho beginner, nếu fen cần thì hộp tui gửi cho.
Chủ đề tương tự
