thaygiao3
Senior Member
cảm giác đầu tiên khi làm đc 1 bài hard trên leetcode khá fun, https://leetcode.com/problems/frog-jump/, bài hard này chắc cx dễ thôi nhưng đối vs em thế là vui r, khoe tí thôi, đây là code của em
C++:
C++:
Đù sao code Cpp của fen nhìn màu mè đẹp thế. Dùng cái gì vậy fencảm giác đầu tiên khi làm đc 1 bài hard trên leetcode khá fun, https://leetcode.com/problems/frog-jump/, bài hard này chắc cx dễ thôi nhưng đối vs em thế là vui r, khoe tí thôi, đây là code của em
C++:
View attachment 909273
vs code ấy mà, chắc là theam one dark pro vs font fira codeĐù sao code Cpp của fen nhìn màu mè đẹp thế. Dùng cái gì vậy fen
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;
}
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;
}
};
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; } };
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
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?View attachment 925319
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 ạ
trong clip thì thằng đó bảo cái đầu linear time cái sau constant time thím2 đ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?
trong clip thì thằng đó bảo cái đầu linear time cái sau constant time thím
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.
phút thứ 50:57 nhé thím
à 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.
à vậy ra e nghe nhầm à. tks thím nhé
à 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ầmBật CC lên thím
View attachment 925319
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 ạ
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 ạ View attachment 934285
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ữaNà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