thảo luận [Học Tập] Topic thuật toán

vanfsn said:
Đúng là chỉ có 1 test case!

Java: 
class MinStack {

    List<Integer> stack;
   
    public MinStack() {
        stack = new ArrayList<>();
    }
   
    public void push(int x) {
        stack.add(x);
    }
   
    public void pop() {
        stack.remove(stack.size() - 1);
    }
   
    public int top() {
        return stack.get(stack.size() - 1);
    }
   
    public int getMin() {
        return Collections.min(stack);
    }
}
Click to expand...
Cái này linear time O(n) nha bác
 
talaai1312_ver2 said:
Sao thằng này có mỗi 1 test case à ta
C#: 
public class MinStack {

    List<int> stack;
    /** initialize your data structure here. */
    public MinStack() {
       stack  = new List<int>();
    }
   
    public void Push(int x) {
        stack.Add(x);
    }
   
    public void Pop() {
        stack.RemoveAt(stack.Count - 1);
    }
   
    public int Top() {
        return stack[stack.Count - 1];
    }
   
    public int GetMin() {
        return stack.Min();
    }
}
Click to expand...
GetMin của bác này cũng O(n) rồi nha
 
Ưng quá tối làm
[IamNormal] said:
Xin chào mọi người, vì mục tiêu hướng tới lương 5k 6k nên em lập thread này.
Mỗi ngày làm tối thiểu một bài trên Leetcode, ai có solution hay thì post lên cho mọi người tham khảo, ai không làm được có thể hỏi mọi người.
Mục đích chính để luyện cấu trúc dữ liệu và giải thuật :matrix:

Ai có problems hay thì post lên em sẽ tổng hợp ở #1 :big_smile:

Bài 1: [Easy] Min Stack
Click to expand...


via nextVOZ for iPhone
 
Hover said:
Mấy bác trên giải kiểu gì vậy nhỉ? O(1) tất cả các thao tác mà dùng Collections.min với List.min.



Đọc chưa hiểu hàm push của bác này lắm. Add vào stack số x mà cái min lại biến đổi như này?
min_.push_back(min_.back())
Click to expand...
Giả sử bác push theo thứ tự sau
[5, 5, 3, 3, 6, 1, 1]
Thì min_ phải là
[5, 5, 3, 3, 3, 1, 1]

Min_.back() trả giá trị nhỏ nhất hiện tại, nếu x nhỏ hơn min_.back() thì push x vào min_, không thì phải push(min_.back()) để size của 2 vector bằng nhau.
 
chaungoan said:
Giả sử bác push theo thứ tự sau
[5, 5, 3, 3, 6, 1, 1]
Thì min_ phải là
[5, 5, 3, 3, 3, 1, 1]

Min_.back() trả giá trị nhỏ nhất hiện tại, nếu x nhỏ hơn min_.back() thì push x vào min_, không thì phải push(min_.back()) để size của 2 vector bằng nhau.
Click to expand...

Đã hiểu cách của bác mà hơi ảo, bác chỉ cần push những index min vào thôi :D.
 
chaungoan said:
Chưa hiểu ý bác lắm. Dùng stack cần gì index bác? Đâu bác viết pseudo code mình coi
Click to expand...

Giả sử bác push theo thứ tự sau
[5, 7, 2, 3, 6, 1, 1]
Thì cái stack min sẽ push index của những cái min thôi:
[0, 2, 5, 6]

Lúc pop thì check cái index top có bằng cái top của min không thôi, nếu không thì không làm gì, nếu có thì pop cả ở min.
 
bài này xài sẵn cái min của python + list, submit tán loạn => 888ms xong hơn được có 11% nx ng submit lên, siêu chậm :v
Mình toàn lậm built-in python function :'((((
 
B2:[Easy] - Longest palindrome
Bài này đánh tag easy nhưng mình mất tận 6 lần submit mới đúng vì nghĩ hướng giải chưa hoàn chỉnh + test hay. speed <62%. mem <12.5% (hashTable lưu nặng ghê)
Hóng các bác chia sẻ idea nhanh hơn.
 
Last edited:
Hover said:
Giả sử bác push theo thứ tự sau
[5, 7, 2, 3, 6, 1, 1]
Thì cái stack min sẽ push index của những cái min thôi:
[0, 2, 5, 6]

Lúc pop thì check cái index top có bằng cái top của min không thôi, nếu không thì không làm gì, nếu có thì pop cả ở min.
Click to expand...
Vậy là bác check if cả push và pop nữa? Rồi lúc gọi min() thì phải lấy index nữa.
 
BadCoder said:
B2:[Easy] - Longest palindrome
Bài này đánh tag easy nhưng mình mất tận 6 lần submit mới đúng vì nghĩ hướng giải chưa hoàn chỉnh + test hay. speed <62%. mem <12.5% (hashTable lưu nặng ghê)
Hóng các bác chia sẻ idea nhanh hơn.
Click to expand...
bài này xử lí cơ bản thôi, đâu cần hash :)

C++: 
class Solution {
public:
    int longestPalindrome(string s) {
        int a[256] = {0};
        for (int i = 0; i < s.size(); ++i) a[s[i]]++;
        int ans = 0;
        for (int i = 0; i < 256; ++i) ans += a[i] / 2 * 2;
        for (int i = 0; i < 256; ++i) if (a[i] & 1) { ans += 1; break; }
        return ans;
    }
};
 
Last edited:
Python: 
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        hashTB = {}
        for c in s:
            if c in hashTB:
                hashTB[c] += 1
            else:
                hashTB[c] = 1
        even = 0
        odd = 0
        for value in hashTB.values():
            if value >= 2 and value % 2 == 0:
                even += value
            if value >=3 and value % 2 == 1:
                odd += (value-1)
        return min(even+odd+1,len(s))
chả bù cho cái hướng của em
 

Similar threads

Zuytori
Tiếp nhận đơn xin khai thác 'kho báu' 3 tấn vàng dưới lòng sông ở Bình Thuận
Replies
8
Views
476
yokitonara
Y
Nobitadiradivo
Phê duyệt gần 14.000 tỷ đầu tư tuyến đường nối cao tốc Biên Hòa – Vũng Tàu
Replies
4
Views
369
TraChanhMuoiMe
TraChanhMuoiMe
BaryonicLord
Tính toán kịch bản đánh thuế tiêu thụ đặc biệt, đảo ngược xu hướng tiêu thụ đồ uống có đường
2 3
Replies
47
Views
3K
Cún Xjnh
Cún Xjnh
sankhaukich
Nước cống đen kịt xả ra vịnh Hạ Long
4 5 6
Replies
103
Views
8K
Han sara
Han sara
N
thắc mắc Tìm phim trộm vàng
Replies
2
Views
112
nottelling
N

Share this page

Back
Top