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

BigHeadCrew · 7/5/20

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

ah ừ. Mình tưởng thớt chỉ muốn luyện leetcode đi phỏng vấn thôi

talaai1312_ver2 · 7/5/20

Hover đã nói:
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.

chaungoan đã nói:
GetMin của bác này cũng O(n) rồi nha

Qua em đọc đề xong làm luôn ko để ý vụ big O

mấy bác xem ở đâu thế nhỉ hay là mỗi lần giải đều phải luôn để ý big O. Em không thấy nó ghi chú trong đề

Hover · 7/5/20

chaungoan đã nói:
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.

Hover · 7/5/20

BadCoder đã nói:

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ỉ?

[IamNormal] · 7/5/20

BadCoder đã nói:
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

thấy thím nói làm hashtable gắt quá :shame:

dangmt đã nói:
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

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à

.

[IamNormal] · 7/5/20

talaai1312_ver2 đã nói:
Qua em đọc đề xong làm luôn ko để ý vụ big O mấy bác xem ở đâu thế nhỉ hay là mỗi lần giải đều phải luôn để ý big O. Em không thấy nó ghi chú trong đề

http://vnoi.info/wiki/translate/topcoder/Computational-Complexity-Section-1
https://giaithuatlaptrinh.github.io/Phân-tích-thuật-toán/

BadCoder · 8/5/20

Hover đã nói:
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.
:'(

talaai1312_ver2 · 8/5/20

hts222 đã nói:
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ỗ

Mã:

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ỉ?

hts222 · 8/5/20

talaai1312_ver2 đã nó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ỗ

Mã:

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.

hadata · 22/8/20

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!

Đặt Vụ · 22/8/20

đếm độ dài các chuỗi bit 1, output là tổng độ dài 2 chuỗi lớn nhất + 1

hadata · 22/8/20

Thế thì chưa đúng bác ạ. VD trường hợp này: 11101101111

deptrainhatVOZ1999 · 22/8/20

vét máng nhé nhầm vét cạn

qkhanhpro · 22/8/20

hadata đã nói:
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! Xem tệp đính kèm 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 }
}

hadata · 22/8/20

qkhanhpro đã nói:
Duyệt 1 lần thôi mà fen

Là sao bác?

Saten Ruiko · 22/8/20

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

shampoo · 22/8/20

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.

hadata · 22/8/20

Cám ơn các bác, để em làm thử ạ!

hadata · 22/8/20

qkhanhpro đã nói:
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:

T.Dark · 22/8/20

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:

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

Junior Member

Senior Member

Member

Member

Senior Member

Senior Member

Member

Senior Member

Member

Junior Member

Senior Member

Junior Member

Member

Đã tốn tiền

Junior Member

Đã tốn tiền

Junior Member

Junior Member

Junior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này