thảo luận [Học Tập] Topic thuật toán
- Người tạo chủ đề unknowpc90
- Ngày bắt đầu
amolad
Senior Member
có gì thì post lên, nói thế ai biết mà trl
Quy hoạch động muốn thông thạo thì phải làm thật nhiều. Làm nhiều sẽ có được cái sense... rồi gặp dạng bài, phán đoán strategy rồi đi theo hướng đó.
Đôi khi lạc đề thì hỏi thằng interview xem m thấy hướng đi thế này có ổn ko, nếu nó bảo cứ tiếp tục thì ko sao.
Còn ko nó sẽ gợi ý cái hướng để đi cho đúng hướng. btw mình thấy đúng hướng hay ko ko quan trọng.
Quan trọng là đánh giá cách suy nghĩ, tìm lời giải của ứng viên.
Đôi khi lạc đề thì hỏi thằng interview xem m thấy hướng đi thế này có ổn ko, nếu nó bảo cứ tiếp tục thì ko sao.
Còn ko nó sẽ gợi ý cái hướng để đi cho đúng hướng. btw mình thấy đúng hướng hay ko ko quan trọng.
Quan trọng là đánh giá cách suy nghĩ, tìm lời giải của ứng viên.
chubedan
Member
à, tại cũng có mấy cái thuật toán như tìm đường đi euler, đồ thị hamilton ấy bác
tại đây có nhiều thuật toán tìm đường đi lắm nên em nói chung là môn lý thuyết đồ thị luôn
Yêu em Thu Nga CN12 ptit
Senior Member
nay có bác @_Gia_Cat_Luong_ đưa cho mấy bài nhập môn DP, mấy bài easy thì làm hết trước đó rồi, 2 bài medium thì 1 bài làm rồi 1 bài chưa. Cơ mà cứ code lại rồi đăng lên luôn
https://leetcode.com/problems/count-square-submatrices-with-all-ones/
Bài này giống giống cái bài tìm hình vuông có diện tích lớn nhất trong ma trận nhị phân hôm qua đã ngồi xem hướng dẫn trên youtube nên code ngon
https://leetcode.com/problems/count-sorted-vowel-strings/submissions/
Sau 2 3 ngày học thì cũng học được tí tư duy DP, biết nháp và phán đoán phương hướng chút chút
https://leetcode.com/problems/count-square-submatrices-with-all-ones/
Bài này giống giống cái bài tìm hình vuông có diện tích lớn nhất trong ma trận nhị phân hôm qua đã ngồi xem hướng dẫn trên youtube nên code ngon
C++:
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int n=matrix.size();
int m=matrix[0].size();
vector<vector<int>>dp(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(matrix[i-1][j-1] == 1){
dp[i][j] = 1 + min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans+=dp[i][j];
}
}
return ans;
}
};
Mã:
class Solution {
public:
int countVowelStrings(int n) {
vector<vector<int>>dp(n,vector<int>(5,0));
for(int i=0;i<5;i++){
dp[0][i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<5;j++){
for(int k=0;k<=j;k++){
dp[i][j]+=dp[i-1][k];
}
}
}
int ans=0;
for(int i=0;i<5;i++){
ans+=dp[n-1][i];
}
return ans;
}
};
Yêu em Thu Nga CN12 ptit
Senior Member
Đã rõ, code đến chết thôi bác, vì FAANG
. Tự cảm thấy mình học còn chểnh mảng nên từ mai sẽ try hard hơn
amolad
Senior Member
KimSoHyunGoddness
Member
Em tham cách giải bài này và thấy họ giải như thế này. Nhưng có chỗ em ko hiểu là
Với input vô là [20, 100, 10, 12, 5, 13] thì 3 con số hợp đk khi log ra là 5 12 13
Nhưng nhìn vào đề bài thì thấy vị trí của 5 12 13 đâu có phù hợp với điều kiện num < num[j] < num[k]. Tại mảng input vô thì là 12 5 13.
KO biết có bác nào giải thích cho em hiểu chỗ này với được ko
_Gia_Cat_Luong_
Senior Member
Thì chứngg tỏ fen giải sai rồi chứ sao. Đáp án đúng phải là 10 12 13.
vexliva
Member
st là tiệm cận dưới, fen tưởng tượng là cái log ra nó ko phải là 3 số cần tìm mà st = 5 nghĩa là trước nó có 1 số lớn hơn 5 nhưng bé hơn thứ nhì và số thứ 3 (max). Với cách làm như vậy thì fen ko cần biết chính xác 3 số nhưng fen biết có tồn tại 3 số đó, và nó làm vậy để Big O chỉ là O(n) thôi
Sửa lần cuối:
KimSoHyunGoddness
Member
Thấy trong comment giải thích là nó ghi là số tìm số bé nhất, sau đó là số bé thứ nhì mà
KimSoHyunGoddness
Member
Vẫn chưa hiểu lắm bác. Giải thích thêm xí được ko
vexliva
Member
Éc, nghĩ từ từ cũng ra mà, thôi được giờ num = 10 thì 10 là nhỏ nhất nên 10 là st, 100 là nd, num = 12 thì 12 là nd, khi có nd thì ta biết chắc rằng ở phía trước nó luôn có 1 số nhỏ hơn nd ( là số 10 ), và giờ chỉ cần tìm số tiếp theo mà lớn hơn nd là xong và khi num = 13 cái mà giờ lớn hơn nd thì ta đã xác định dc 3 số là : số luôn luôn nhỏ hơn nd ở phía trước ,nd, num = 13
KimSoHyunGoddness
Member
Sau 1 hồi suy nghĩ thì em hiểu bài toán như nàyÉc, nghĩ từ từ cũng ra mà, thôi được giờ num = 10 thì 10 là nhỏ nhất nên 10 là st, 100 là nd, num = 12 thì 12 là nd, khi có nd thì ta biết chắc rằng ở phía trước nó luôn có 1 số nhỏ hơn nd ( là số 10 ), và giờ chỉ cần tìm số tiếp theo mà lớn hơn nd là xong và khi num = 13 cái mà giờ lớn hơn nd thì ta đã xác định dc 3 số là : số luôn luôn nhỏ hơn nd ở phía trước ,nd, num = 13
Yêu em Thu Nga CN12 ptit
Senior Member
C++:
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int n=nums.size();
vector<int>dp(n,0);
int res=1;
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(nums[i]>nums[j]) dp[i]=max(dp[i],dp[j]);
}
dp[i]+=1;
res=max(res,dp[i]);
}
if(res>=3) return true;
else return false;
}
};cải tiến, chỉ cần dp=3 thì break, vẫn TLE;
C++:
class Solution {
public:
int LIS(vector<int>& nums) {
vector<int> res;
for(int i=0; i<nums.size(); i++) {
auto it = lower_bound(res.begin(), res.end(), nums[i]);
if(it==res.end()) res.push_back(nums[i]);
else *it = nums[i];
}
return res.size();
}
bool increasingTriplet(vector<int>& nums) {
int res=0;
res=LIS(nums);
if(res>=3) return true;
return false;
}
};vexliva
Member
Đúng rồi fen st là số bé nhất, nd là bé nhì, nhưng mà cứ iterate tuần tự rồi gán cái nào st cái nào nd thôi không cần biết trước cái nào bé nhất cái nào bé nhì .Khi tìm dc nd thì ta biết chắc chắc trước nó có 1 số bé hơn nó ( st ), và khi iterate tới số lớn hơn nd thì bam return true thôi
Sửa lần cuối:
Fireknight
Member
Mấy thím cho em hỏi học thuật toán ngoài phòng vấn ra thì ra làm có áp dụng nhiều không ạ.
KimSoHyunGoddness
Member
Mình đi làm được 2 exp và trả lời với bạn dựa trên kinh nghiệm cá nhân là CÓ nhưng rất ÍT.
Với công việc hiện tại của mình, mình chỉ áp dụng thuật toán nói chung và kỹ thuật cá nhân nói riêng vào công việc khi và chỉ khi mình đụng tới phần export file excel với hơn 100k dòng thì lúc đó mình mới dùng. VÌ nếu ko dùng vài kỹ thuật vào chỗ này thì server bị tràn ram, ko xử lý nỗi.
Còn ngoài ra thì hầu như ko cần. Lâu lâu mình giải được các bài toán hay hay thì mình xem rồi áp dụng vô project hiện tại. Vậy thôi
Fireknight
Member
Cảm ơn thím
KimSoHyunGoddness
Member
Với cá nhân mình cảm nhận là các cty top tier nó tuyển LTV biết và hiểu thuật toán ko phải là nó thực sự cần thuật toán đâu. Mà là vì những người LTV biết thuật toán họ điều có 1 điểm chung đó là sự chăm chỉ. Nhưng trong cái topic này cũng vậy thôi. Toàn những người chăm chỉ giải 1 toán, nghiên cứu những kiến thức mới, học thêm cái hay. Thời gian rảnh thì lôi thuật toán ra giải để ko bị lãng phí time.
Mà mấy đức tính đó thì chỉ có những LTV biết thuật toán mới có được. Nên mình nghĩ đó chính là lý do vì sao top tier nó tuyển LTV giỏi thuật toán.
Bác @_Gia_Cat_Luong_ là 1 ví dụ điển hình nè. Chắc bác ấy giờ vào được Axon màu vàng rồi ấy chứ. Nên ko còn time chia sẻ với anh em nữa
Chủ đề tương tự
