thảo luận Leetcode mỗi ngày

  • Người tạo chủ đề Người tạo chủ đề _Gia_Cat_Luong_
  • Ngày bắt đầu Ngày bắt đầu
Trạng thái
Không mở để trả lời thêm.
Mắt Xích Yếu đã nói:
Xem tệp đính kèm 2791166 Xem tệp đính kèm 2791168
4gmOAMB.png
nghiệt ngã quá mà how ?
Nhấp để mở rộng...
Thì lấy all rights là ra 4 thôi
 
ý tưởng: duplicate s ->ss
Java: 
class Solution {
    public int takeCharacters(String s, int k) {
        if (k == 0)
            return 0;
        String ss = s + s;
        int n = ss.length();
        int[] freq = new int[3];
        int l = 0;
        int res = Integer.MAX_VALUE;
        for (int r = 0; r < n; r++) {
            int c = ss.charAt(r) - 'a';
            freq[c]++;
            while (r - l >= n / 2) {
                freq[ss.charAt(l) - 'a']--;
                l++;
            }
            if (freq[0] >= k && freq[1] >= k && freq[2] >= k) {
                if (r >= n /2-1) {
                    while (freq[0] >= k && freq[1] >= k && freq[2] >= k) {
                        if (r == n - 1 || (r < n - 1 && l < n / 2)) {
                            res = Math.min(res, r - l + 1);
                        }
                        freq[ss.charAt(l) - 'a']--;
                        l++;
                    }
                   
                }else{
                    res = Math.min(res, r - l + 1);
                }
               
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}
 
C++: 
class Solution {

public:

    int takeCharacters(string s, int k) {

        vector<int> map(3,0);

        for(int i=0; i<s.size(); i++){

            map[s - 'a']++;

        }

        int l = 0;

        int r = s.size();

        int res = -1;

        while(l <= r){

            int mid = (l + r)/2;

            vector<int> mapWindow(3,0);

            for(int i=0; i<mid; i++){

                mapWindow[s - 'a']++;

            }

            if(map[0] - mapWindow[0] >= k && map[1] - mapWindow[1] >= k && map[2] - mapWindow[2] >= k){

                res = s.size() - mid;

                l = mid + 1;

                continue;

            }

            int start = 0;

            int end = mid - 1;

            while(end < s.size() - 1){

                end++;

                mapWindow[s[start] - 'a']--;

                mapWindow[s[end] - 'a']++;

                start++;

                if(map[0] - mapWindow[0] >= k && map[1] - mapWindow[1] >= k && map[2] - mapWindow[2] >= k){

                    res = s.size() - mid;

                    l = mid + 1;

                break;

                }

            }

            if(!(map[0] - mapWindow[0] >= k && map[1] - mapWindow[1] >= k && map[2] - mapWindow[2] >= k)){

                r = mid - 1;

            }

        }

        return res;

        

    }

};
cài đặt sliding window lỏ quá có bác nào có pattern cho em học lỏm :adore:
 
Python: 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        if k == 0:
            return 0

        cnt = Counter(s)
        if cnt['a'] < k or cnt['b'] < k or cnt['c'] < k:
            return -1

        ss = s + s
        
        def f(m):
            c = defaultdict(int)

            start = len(s) - m
            for i in range(len(s) - m, len(s) + m):
                c[ss[i]] += 1
                if i - start >= m:
                    c[ss[i-m]] -= 1
                if c['a'] >= k and c['b'] >=k and c['c'] >= k:
                    return True
            
            return False

        l = 1
        r = len(s)

        while l < r:
            m = l + (r-l)//2

            if f(m):
                r = m
            else:
                l = m + 1
        
        return l
 
sliding window nông dân
C#: 
public class Solution
{
    public int TakeCharacters(string s, int k)
    {
        var total = new int[3];
        foreach (char c in s)
        {
            total[c - 'a']++;
        }

        if (total.Any(a => a < k))
        {
            return -1;
        }


        int l = 0, r = 0;
        int res = s.Length;
        while (l < res)
        {
            if (r < s.Length && total[s[r] - 'a'] > k)
            {
                total[s[r++] - 'a']--;
            }
            else
            {
                res = Math.Min(total.Sum(), res);
                total[s[l++] - 'a']++;
            }
        }

        return res;
    }
}
 
freedom.9 đã nói:
Python: 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        n = len(s)
        a, b, c = 0, 0, 0
        countLeft = [[0]*3 for _ in range(len(s) + 1)]
        countRight = [[0]*3 for _ in range(len(s) + 1)]
        for i in range(len(s)):
            if s[i] == 'a':
                a += 1
            if s[i] == 'b':
                b += 1
            if s[i] == 'c':
                c += 1
            countLeft[i + 1] = [a, b, c]

        a, b, c = 0, 0, 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == 'a':
                a += 1
            if s[i] == 'b':
                b += 1
            if s[i] == 'c':
                c += 1
        
            countRight[n - i] = [a, b, c]

        def bisearch(minute):
            for i in range(0, minute + 1):
                if countLeft[i][0] + countRight[minute - i][0] >= k and countLeft[i][1] + countRight[minute - i][1] >= k and countLeft[i][2] + countRight[minute - i][2] >= k:
                    return True
            
            return False

        ans = -1
        left = 0
        right = n
        while left <= right:
            mid = left + (right - left)//2
            if bisearch(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        return ans

Python: 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        count = [0]*3
        for char in s:
            count[ord(char) - ord('a')] += 1
        for i in range(3):
            count[i] -= k
            if count[i] < 0:
                return -1
               
        current = [0]*3
        left = 0
        n = len(s)
        ans = inf
        for right in range(n):
            current[ord(s[right]) - ord('a')] += 1
            while current[0] > count[0] or current[1] > count[1] or current[2] > count[2]:
                current[ord(s[left]) - ord('a')] -= 1
                left += 1
            ans = min(n - (right - left + 1), ans)
        return ans
Nhấp để mở rộng...
bài này chạy bin search thì ko khác gì BF, giả sử nếu interview thật thì chắc cũng ko được accept đâu bác nhỉ?
 
noobdev đã nói:
bài này chạy bin search thì ko khác gì BF, giả sử nếu interview thật thì chắc cũng ko được accept đâu bác nhỉ?
Nhấp để mở rộng...
Mình nghĩ vẫn accept như thường thôi, nói rõ time complexity là đc fen.
Chủ yếu là approach ra vấn đề như nào thôi chứ code binary search để nó accepted cũng ko đơn giản.
 
 
Thấy mọi người làm O(N) nên cũng nghĩ cách O(N) :big_smile:
Python: 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        n = len(s)
        ss = s + s
        c = defaultdict(int)
        start = 0
        res = float("inf")

        for i, ch in enumerate(ss):
            c[ch] += 1
            
            while c['a'] >= k and c['b'] >=k and c['c'] >= k and i >= n - 1 and start <= n:
                res = min(res, i - start + 1)
                c[ss[start]] -= 1
                start += 1
            
        
        return res if res <= n else -1
 
freedom.9 đã nói:
Python: 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        n = len(s)
        a, b, c = 0, 0, 0
        countLeft = [[0]*3 for _ in range(len(s) + 1)]
        countRight = [[0]*3 for _ in range(len(s) + 1)]
        for i in range(len(s)):
            if s[i] == 'a':
                a += 1
            if s[i] == 'b':
                b += 1
            if s[i] == 'c':
                c += 1
            countLeft[i + 1] = [a, b, c]

        a, b, c = 0, 0, 0
        for i in range(len(s) - 1, -1, -1):
            if s[i] == 'a':
                a += 1
            if s[i] == 'b':
                b += 1
            if s[i] == 'c':
                c += 1
        
            countRight[n - i] = [a, b, c]

        def bisearch(minute):
            for i in range(0, minute + 1):
                if countLeft[i][0] + countRight[minute - i][0] >= k and countLeft[i][1] + countRight[minute - i][1] >= k and countLeft[i][2] + countRight[minute - i][2] >= k:
                    return True
            
            return False

        ans = -1
        left = 0
        right = n
        while left <= right:
            mid = left + (right - left)//2
            if bisearch(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        return ans

Python: 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        count = [0]*3
        for char in s:
            count[ord(char) - ord('a')] += 1
        for i in range(3):
            count[i] -= k
            if count[i] < 0:
                return -1
               
        current = [0]*3
        left = 0
        n = len(s)
        ans = inf
        for right in range(n):
            current[ord(s[right]) - ord('a')] += 1
            while current[0] > count[0] or current[1] > count[1] or current[2] > count[2]:
                current[ord(s[left]) - ord('a')] -= 1
                left += 1
            ans = min(n - (right - left + 1), ans)
        return ans
Nhấp để mở rộng...
đọc code O(N) của bác khó hiểu thế nhỉ, count[0] là đã trừ bỏ k, xong mình so sánh current[0] > count[0] và lại lấy n - (right - left + 1) là sao bác
 
C++: 
func takeCharacters(s string, k int) int {
    target := [3]int{}

    for i := range s {
        switch s[i] {
        case 'a':
            target[0]++
        case 'b':
            target[1]++
        case 'c':
            target[2]++
        }
    }

    for i, count := range target {
        if count-k < 0 {
            return -1
        }
        target[i] = count - k
    }

    window := [3]int{}
    out := len(s)
    l := 0

    for r := 0; r < len(s); r++ {
        switch s[r] {
        case 'a':
            window[0]++
        case 'b':
            window[1]++
        case 'c':
            window[2]++
        }

        for window[0] > target[0] || window[1] > target[1] || window[2] > target[2] {
            switch s[l] {
            case 'a':
                window[0]--
            case 'b':
                window[1]--
            case 'c':
                window[2]--
            }
            l++
        }

        out = min(out, len(s)-(r-l+1))
    }

    return out
}
 
freedom.9 đã nói:
Nay chạy mấy bài medium ôn luyện code đỡ lỏ cuối tuần làm contest chứ xài clone thi ko có động lực gì, ae nhào vô ăn ít cơm thêm Medium

Mấy bài này hay phết đa dạng topic :ah:
Nhấp để mở rộng...
Python: 
class Solution:
    def minimizeXor(self, num1: int, num2: int) -> int:
        num1_32bit = list(format(num1, '032b'))
        total = num2.bit_count()
        res = ['0'] * 32

        for i, c in enumerate(num1_32bit):
            if c == '1' and total > 0:
                total -= 1
                res[i] = '1'
 

        for c, i in list(zip(res, range(32)))[::-1]:
            if total > 0 and c == '0':
                total -= 1
                res[i] = '1'
            
            if total == 0:
                break
            
        
        binary_string = ''.join(res)

        # Convert the binary string to a base-10 integer
        base_10_value = int(binary_string, 2)

        return base_10_value
 
Tinh Hoa Đông Lào đã nói:
đọc code O(N) của bác khó hiểu thế nhỉ, count[0] là đã trừ bỏ k, xong mình so sánh current[0] > count[0] và lại lấy n - (right - left + 1) là sao bác
Nhấp để mở rộng...
Ví dụ a b c là tổng của 'a' 'b' 'c' trong dãy thì để thỏa mãn đủ số k cần thiết thì cần 1 windows có at most a - k, b- k, c-k nên dùng sliding windows để tìm cái windows phù hợp thôi fence

via theNEXTvoz for iPhone
 
Sửa lần cuối:
Python: 
class Solution:
    def takeCharacters(self, s: str, k: int) -> int:
        if k == 0:
            return 0

        n = len(s)
       
        count = {}
        enough = 0
        for c in s:
            if c not in count:
                count[c] = 0
            count[c] += 1

            if count[c] == k:
                enough += 1

        if enough != 3:
            return -1

        l = 0
        res = 1000000
        for r in range(n):
            count[s[r]] -= 1

            while count[s[r]] < k and l <= r:
                count[s[l]] += 1
                l += 1

            res = min(res, n - (r - l + 1))

        return res
 
Trạng thái
Không mở để trả lời thêm.
AD · 970×250

Chủ đề tương tự

Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
2K
dattenmoi
D
megume
thảo luận Hôm nay, buổi bình minh của AI robot đã đến
Trả lời
4
Lượt xem
1K
Toc Hong
Toc Hong
Lộc Tục
(Dịch) Cuộc điều tra của CBC/Radio-Canada tiết lộ công ty Việt Nam nhắm vào người Canada bằng tin giả AI để kiếm lời
2
Trả lời
30
Lượt xem
5K
dukeng995
dukeng995
Ti Amo
[Dịch] Công ty Việt Nam dùng tin giả do AI tạo ra để kiếm tiền — nhắm vào độc giả Canada
Trả lời
0
Lượt xem
1K
Ti Amo
Ti Amo
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
907
giayasics
giayasics
AD · 300×600

Thống kê chủ đề

Ngày tạo
_Gia_Cat_Luong_,
Người trả lời cuối
Vipluckystar,
Trả lời
17.755
Lượt xem
1.215.382
AD · 300×600

Chia sẻ trang này

AD · 300×600
Quay lại
Lên đầu trang