KimSoHyunGoddness
Member
Đù sao code Cpp của fen nhìn màu mè đẹp thế. Dùng cái gì vậy fen
thảo luận [Học Tập] Topic thuật toán
- Người tạo chủ đề unknowpc90
- Ngày bắt đầu
thaygiao3
Senior Member
vs code ấy mà, chắc là theam one dark pro vs font fira code
Tuấn Mỏ
Senior Member
1 bài merge list khá hay, ae tham khảo
https://leetcode.com/problems/merge-k-sorted-lists/
Bài này dùng Min Heap để tối ưu
https://leetcode.com/problems/merge-k-sorted-lists/
Bài này dùng Min Heap để tối ưu
C++:
struct Comperator
{
bool operator()(ListNode* a, ListNode* b)
{
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* head = nullptr;
ListNode* cur = nullptr;
std::priority_queue<ListNode*, std::vector<ListNode*>, Comperator> minHeap;
for(auto& iter : lists)
{
if(!iter)
continue;
minHeap.push(iter);
}
while(!minHeap.empty())
{
ListNode* node = minHeap.top();
minHeap.pop();
if(node && node->next)
{
minHeap.push(node->next);
}
if(!head)
{
head = node;
}
else if(cur)
{
cur->next = node;
}
cur = node;
if(!node)
break;
}
return head;
}
Yêu em Thu Nga CN12 ptit
Senior Member
Nay ở nhà 1 mình húp mỳ đói mờ cả mắt. Ngồi từ 2 rưỡi sáng đến giờ mới implement hết 3 cái thuật string search: Boyer-Moore, KMP, Rabin-Karp, với được 1 bài hard trên leetcode (không biết làm, lúc đầu làm brute force chỉ pass 119/120 case, nhưng thấy họ ghi là xài KMP nên mới lọ mọ tìm cái để đọc đọc). Đọc hết VNOI, mấy web linh tinh các kiểu cũng không hiểu cái KMP. Xem 2 vid của anh Ấn Độ mất 30ph là thông não. Làm xong trời cũng sáng chạy vội sang quán húp bát cháo rồi về ngủ.
https://leetcode.com/problems/shortest-palindrome/
https://leetcode.com/problems/shortest-palindrome/
C++:
class Solution {
public:
string shortestPalindrome(string s) {
string New="";
New+=s;
New+='.';
reverse(s.begin(),s.end());
New+=s;
int length=0;
vector<int>LPS(New.size(),0);
for(int i=1;i<New.size();i++){
while(length>0&&New[length]!=New[i]) length=LPS[length-1];
if(New[length]==New[i]){
LPS[i]=++length;
}
else LPS[i]=0;
}
string res="";
res+=s.substr(0,s.size()-LPS[New.size()-1]);
reverse(s.begin(),s.end());
res+=s;
return res;
}
};
Bình Lê (Cổ cồn trắng)
Member
Cố lên mấy đứa
Thích Màu Hường
Member
Nay ở nhà 1 mình húp mỳ đói mờ cả mắt. Ngồi từ 2 rưỡi sáng đến giờ mới implement hết 3 cái thuật string search: Boyer-Moore, KMP, Rabin-Karp, với được 1 bài hard trên leetcode (không biết làm, lúc đầu làm brute force chỉ pass 119/120 case, nhưng thấy họ ghi là xài KMP nên mới lọ mọ tìm cái để đọc đọc). Đọc hết VNOI, mấy web linh tinh các kiểu cũng không hiểu cái KMP. Xem 2 vid của anh Ấn Độ mất 30ph là thông não. Làm xong trời cũng sáng chạy vội sang quán húp bát cháo rồi về ngủ.
https://leetcode.com/problems/shortest-palindrome/
C++:class Solution { public: string shortestPalindrome(string s) { string New=""; New+=s; New+='.'; reverse(s.begin(),s.end()); New+=s; int length=0; vector<int>LPS(New.size(),0); for(int i=1;i<New.size();i++){ while(length>0&&New[length]!=New[i]) length=LPS[length-1]; if(New[length]==New[i]){ LPS[i]=++length; } else LPS[i]=0; } string res=""; res+=s.substr(0,s.size()-LPS[New.size()-1]); reverse(s.begin(),s.end()); res+=s; return res; } };
Accepted solution, vét cạn thôi, ko phải tối ưu nhưng gọn
Python:
class Solution:
def shortestPalindrome(self, s: str) -> str:
shortest_ps = s
i = 1
while True:
half_length_ps = len(shortest_ps) // 2
if half_length_ps == 0 or shortest_ps[0:half_length_ps] == shortest_ps[-half_length_ps:][::-1]:
break
shortest_ps = s[-i:][::-1] + s
i += 1
return shortest_ps
Hoai cmn Linh
Member
em hơi ngu toán các thím thông não em sao cái ở trên là O(n) còn ở dưới là constant time vậy ạ
Giam Doc EVN
Đã tốn tiền
2 đoạn code chung mục đích tìm phần tử trong linked list giống nhau mà. Khác mỗi cái trên dùng recursion còn cái dưới dùng while. Cả 2 đều O(N) chứ sao O(1) đc?
Hoai cmn Linh
Member
trong clip thì thằng đó bảo cái đầu linear time cái sau constant time thím
Thích Màu Hường
Member
Sao mà constant time được, duyệt qua single linked list thì là O(n) rồi. Không thấy nó phụ thuộc hoàn toàn vào số phần tử của list đó sao. Post cái clip lên đây.
Hoai cmn Linh
Member
Sao mà constant time được, duyệt qua single linked list thì là O(n) rồi. Không thấy nó phụ thuộc hoàn toàn vào số phần tử của list đó sao. Post cái clip lên đây.
Thích Màu Hường
Member
Gạch phát.
Người ta nói là cả 2 cái đều là linear time complexity O(n). Còn cái dưới là constant space complexity vì ko có đệ quy nên ko phải lưu các lời gọi hàm, các biến như cái đệ quy.
Sửa lần cuối:
Hoai cmn Linh
Member
à vậy ra e nghe nhầm à. tks thím nhéGạch phát.
Người ta nói là cả 2 cái đều là linear time complexity O(n). Còn cái dưới là constant space complexity vì ko có đệ quy nên ko phải lưu các lời gọi hàm, các biến như cái đệ quy.
Thích Màu Hường
Member
Bật CC lên thím
Hoai cmn Linh
Member
à em nghe đc tiếng anh thím, chỉ có khúc này chắc do lo chú ý code quá nên nghe nhầm
dảk quá pepsi ơi
Senior Member
Mọi người cho em hỏi là thầy em có dạy về thuật toán và đây là sắp xếp nổi bọt nhưng em nhìn thì nếu quay ngang ra nó chả khác gì cái Selection Sort cả. không biết có phải em lú không ạ
Chắc là O(n) với O(1) về space chứ sao lại time được. Đoạn code trên dùng đệ quy, mỗi lần gọi hàm mới thì nó phải khởi tạo heap các kiểu nên tốn memory hơn.
Sent from Samsung SM-G973F using vozFApp
Này là selection sort rồi, mỗi step chọn ra giá trị min rồi swap về phía đầu mảng. Còn bubble sort đi đến đâu nó swap đến đấy.
Sent from Samsung SM-G973F using vozFApp
dảk quá pepsi ơi
Senior Member
Vậy là sai rồi đúng không ạ, vừa nãy em định hỏi lại thầy mà không biết giải thích bằng lời sao nữa
Seeder_Intel
Senior Member
Mình có 1 cái problem như hình, có runtime constraint nên không thể brute force được, các ae vào giúp đỡ. Mình cám ơn
Các ae lưu ý là 2 là winter chứ k phải summer
Các ae lưu ý là 2 là winter chứ k phải summer
Chủ đề tương tự
