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

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.

Cái này mình lưu ít memory hơn bác. Hơn nữa bác đổi sang lưu thẳng value cũng được, vậy lúc pop thì check value thôi. Đoạn pop thêm if nhưng đoạn push mất cái else, memory thì lưu ít hơn nên cá nhân em nghĩ cách này tốt hơn.
 
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

Cách này của bác không đúng vì đâu phải lúc nào cũng cộng 1, mà sao phải có cái min nhỉ?
 
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.

Python:
class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0

        appear = [0] * 256
        for char in s:
            i = ord(char)
            appear[i] = appear[i] + 1

        ans = 0
        rest = 0
        for i in appear:
            ans += i - i % 2
            rest += i % 2
        if rest > 0:
            return ans + 1
        else:
            return ans

bài này để ý tí là thấy ngay
brick.png
thấy thím nói làm hashtable gắt quá :shame:

Python tốt nhưng đây là lập trình thi đấu. Ít ai xài Python.

cái trang leetcode này để luyện code phỏng vấn thôi thím, competitive thì thường dùng codeforces. Hồi cấp 3 em cũng luyện competitve, code bằng C++. Giờ dùng python thấy thọt quá tại dùng C++ nhiều cái nó yêu cầu rõ ràng, chặt chẽ mà cái thằng python này
lay.gif
nên giờ luyện code bằng python thôi. Ai thích code ngôn ngữ gì thì code ạ. Tự đánh giá độ phức tạp thuật toán được mà
brick.png
.
 
Last edited:
Cách này của bác không đúng vì đâu phải lúc nào cũng cộng 1, mà sao phải có cái min nhỉ?
Đúng như bác nói, không nên auto cộng 1 vô, em gặp test sai, sửa nên nó loạn xì quần, ý tưởng là đếm số lần xuất hiện của các phần tử, phần tử nào > 2 thì được phép đưa vào xâu đối xứng vì cứ đưa 1 ký tự vào đầu và vào cuối xâu, hay nói cách khác xâu có dạng a***-***a:
" -" là 1 ký tự hoặc có thể là ko điền gì cả.
- phần tử > 2 và chia hết cho 2 -> auto chấp thuận, đưa hết vào
- phần tử > 2 nhưng lẻ, -> chỉ có thể lấy x-1 ký tự (đưa số chẵn ký tự vào xâu đối xứng)
và cuối cùng cộng 1 vì chỉ lấy 1 ký tự chèn vào chính giữa xâu vẫn đảm bảo nó đối xứng
-
Lý do cộng một hết vào tất cả các trường hợp là vì bạn đầu không cộng, sai test case này xong kiểu đối phó với test có dạng 'aabbbcccddd':
"civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth"
Còn lý do lấy min là sai test này:
"tattarrattat"
-> t:6, a:4,r:2 2 : Chính vì em lúc nào cũng cộng 1 nên có thể có case mọi ký tự đều chẵn pass hết nó lại lớn hơn số ký tự của xâu.
:'(
 
bài này xử lí cơ bản thôi, đâu cần hash :)
C++:
int a[256] = {0};
for (int i = 0; i < s.size(); ++i) a[s[i]]++;
Bác cho em hỏi xíu về đếm số lần xuất hiệncủa ký tự trong chuỗi. Em phải dùng 2 vòng lặp lồng nhau. Còn như của bác là chỗ
Code:
a[s[i]]++
là sao vậy, bác giải thích giúp em được ko? s(i) là char mà sao dùng a(index char) được nhỉ?
 
Last edited:
Bác cho em hỏi xíu về đếm số lần xuất hiệncủa ký tự trong chuỗi. Em phải dùng 2 vòng lặp lồng nhau. Còn như của bác là chỗ
Code:
a[s[i]]++
là sao vậy, bác giải thích giúp em được ko? s(i) là char mà sao dùng a(index char) được nhỉ?
char trong c++ nó là một số nguyên thôi bác nên dùng mảng đếm được.
 
Chào các bác em có bài lập trình nghĩ mãi không ra. Có bác nào hứng thú nghĩ cách với em ạ. Em cám ơn!
1598099790972.png
 
Chào các bác em có bài lập trình nghĩ mãi không ra. Có bác nào hứng thú nghĩ cách với em ạ. Em cám ơn! View attachment 163068

Duyệt 1 lần thôi mà fen

1111 000 1 0 111 11111

flip = false;

If (next == 1)
{
temp +=1
CompareAndAssign
}
else {
flip ? { CompareAndAssign ; temp = 0; } : { temp +=1; CompareAndAssign, !flip }
}
 
Last edited:
Theo ý kiến của 1 thanh niên 5-6 năm rồi chưa đụng vào lập trình lại
Thì cứ tạo 2 biến để xác định vị trí bit 0 thứ 1 và bit 0 thứ 2 thôi. zerost, zerond
Đếm từ đầu tới bit 0 thứ 2 (zerond != 0), so sánh và gắn max, zerost = zerond, zerond = 0, count = zerond - zerost . Cứ đếm tới cuối thôi
 
Tạo 1 array chứa độ dài các chuỗi bit 1 liên tiếp. Sau đó tính max của tổng 2 số liên tiếp trong array đó. KQ là max+1.
 
Duyệt 1 lần thôi mà fen

1111 000 1 0 111 11111

flip = false;

If (next == 1)
{
temp +=1
CompareAndAssign
}
else {
flip ? { CompareAndAssign ; temp = 0; } : { temp +=1; CompareAndAssign, !flip }
}
Bác rảnh không giải thích giùm em với ạ. Ngu quá. :cry::cry:
 
bài này có thể giải theo cách thô sơ 2 vòng lặp. Còn cách tối ưu thì hình như sử dụng bfs hay dfs gì đó, quên mịa rồi :beat_brick:
 
Back
Top