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.
Con mẹ mấy thằng dev Stripe bóp dái ẩn mẹ cái zipcode đi éo checkout đc, quả này đền nhấc người :canny:
Đang oncall dính cái p0 cay thật :too_sad:

via theNEXTvoz for iPhone
 
Mã: 
class MyCalendarTwo {
    private calendar: number[][];
    private booked: number[][];
    constructor() {
        this.calendar = [];
        this.booked = [];
    }
    
    book(start: number, end: number): boolean {
        for (const [s, e] of this.booked) {
            if (s < end && start < e) return false;
        }
        for (const [s, e] of this.calendar) {
            if (s < end && start < e) {
                this.booked.push([Math.max(s, start), Math.min(e, end)]);
            }
        }
        this.calendar.push([start, end]);
        return true;
    }
}
 
mai chắc My Calendar III, mấy bài dạng này dùng Line Sweep giải đc hết :rap:
Mà ngại viết :go:
JavaScript: 
class MyCalendarTwo {
    overlaps: number[][];
    books: number[][];
    constructor() {
        this.overlaps = [];
        this.books = [];
    }

    book(start: number, end: number): boolean {
        for (const [a, b] of this.overlaps) {
            if (start < b && end > a) return false;
        }
        for (const [a, b] of this.books) {
            if (start < b && end > a) {
                this.overlaps.push([Math.max(start, a), Math.min(end, b)])
            }
        }
        this.books.push([start, end])
        return true;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * var obj = new MyCalendarTwo()
 * var param_1 = obj.book(start,end)
 */
 
Python: 
from sortedcontainers import SortedDict
class MyCalendarTwo:
    # def __init__(self):
    #     self.meetings = []
    #     self.overlaps = []
    # def book(self, start: int, end: int) -> bool:
    #     for s,e in self.overlaps:
    #         if not (end <= s or start >= e):
    #             return False 
    #     for s,e in self.meetings:
    #         if not (end <= s or start >= e):
    #             self.overlaps.append((max(start, s), min(e, end)))
                
    #     self.meetings.append((start,end))
    #     return True
    # Approach 2 : Line Swap
    def __init__(self):
        self.meetings = SortedDict()
        self.max_count = 2
    def book(self, start: int, end: int) -> bool:
        self.meetings[start] = self.meetings.get(start, 0) + 1
        self.meetings[end] = self.meetings.get(end,0) - 1
        count = 0
        for i in self.meetings.values():
            count += i
            if count > self.max_count:
                self.meetings[start] -= 1
                self.meetings[end] += 1
                if self.meetings[start] == 0:
                    del self.meetings[start]
                if self.meetings[end] == 0:
                    del self.meetings[end]
                return False
        
        return True
 
Java: 
class MyCalendarTwo {

    TreeMap<Integer, Integer> calendars;
    int maxBooking = 2;

    public MyCalendarTwo() {
        calendars = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        calendars.put(start, calendars.getOrDefault(start, 0) + 1);
        calendars.put(end, calendars.getOrDefault(end, 0) - 1);
        int prefixSum = 0;
        for (Map.Entry<Integer, Integer> calendar : calendars.entrySet()) {
            prefixSum += calendar.getValue();
            if (prefixSum > maxBooking) {
                calendars.put(start, calendars.get(start) - 1);
                calendars.put(end, calendars.get(end) + 1);
                if (calendars.get(start) == 0) {
                    calendars.remove(start);
                }
                return false;
            }
        }
        return true;
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */
 
Python: 
class MyCalendarTwo:
    def __init__(self):
        self.overlapsed = []
        self.calendars = []

    def book(self, start: int, end: int) -> bool:
        for s, e in self.overlapsed:
            if not (start >= e or end <= s):
                return False

        for s, e in self.calendars:
            if start >= e or end <= s:
                continue

            self.overlapsed.append([max(s, start), min(e, end)])

        self.calendars.append([start, end])
        return True
          
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)

# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)
 
Python: 
from sortedcontainers import SortedList
class MyCalendarTwo:
    def __init__(self):
        self.items = SortedList()
        self.dict = defaultdict(int)

    def book(self, start: int, end: int) -> bool:
        self.dict[start] += 1
        self.dict[end] -= 1
        if start not in self.items:
            self.items.add(start)
        
        if end not in self.items:
            self.items.add(end)

        count = 0
        for num in self.items:
            count += self.dict[num]
            if count > 2:
                self.dict[start] -= 1
                self.dict[end] += 1
                if self.dict[start] == 0:
                    self.items.remove(start)
                if self.dict[end] == 0:
                    self.items.remove(end)
                return False

        return True
          
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)

# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)
 
hiếu thứ tha đã nói:
mình kết bạn học chung nha
Nhấp để mở rộng...
Set kèo thôi
yAua8od.png
 
gia nhập đường đua
C++: 
class MyCalendarTwo {
public:
    map<int, int> calendar;
    bool book(int start, int end) {
        calendar[start] += 1;
        calendar[end] -= 1;
        int booked = 0;
        for (auto it = calendar.begin(); it != calendar.end(); it++) {
            booked += it->second;
            if (booked >= 3) {
                calendar[start]--;
                calendar[end]++;
                return false;
            }
        }
        return true;
    }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */
C++: 
class MyCalendarThree {
public:
    map<int, int> calendar;

    MyCalendarThree() {
        
    }
    
    int book(int startTime, int endTime) {
        int booked = 0;
        int result = 0;
        calendar[startTime]++;
        calendar[endTime]--;
        for (auto it = calendar.begin(); it != calendar.end(); it++) {
            booked += it->second;
            // if (it->first >= startTime && it->first <= endTime) {
            //     result = max(result, booked);
            // }
            result = max(result, booked);
        }
        return result;
    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(startTime,endTime);
 */
 
hoangi19 đã nói:
gia nhập đường đua
C++: 
class MyCalendarTwo {
public:
    map<int, int> calendar;
    bool book(int start, int end) {
        calendar[start] += 1;
        calendar[end] -= 1;
        int booked = 0;
        for (auto it = calendar.begin(); it != calendar.end(); it++) {
            booked += it->second;
            if (booked >= 3) {
                calendar[start]--;
                calendar[end]++;
                return false;
            }
        }
        return true;
    }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */
C++: 
class MyCalendarThree {
public:
    map<int, int> calendar;

    MyCalendarThree() {
       
    }
   
    int book(int startTime, int endTime) {
        int booked = 0;
        int result = 0;
        calendar[startTime]++;
        calendar[endTime]--;
        for (auto it = calendar.begin(); it != calendar.end(); it++) {
            booked += it->second;
            // if (it->first >= startTime && it->first <= endTime) {
            //     result = max(result, booked);
            // }
            result = max(result, booked);
        }
        return result;
    }
};

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * MyCalendarThree* obj = new MyCalendarThree();
 * int param_1 = obj->book(startTime,endTime);
 */
Nhấp để mở rộng...
gia nhập ké
Java: 
class MyCalendarTwo {
    TreeMap<Integer, Integer> counts;
    int threashHold;
    public MyCalendarTwo() {
        threashHold = 2;
        counts = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        int count = 0;
        counts.put(start, counts.getOrDefault(start, 0) + 1);
        counts.put(end, counts.getOrDefault(end, 0) - 1);

        for (int x: counts.keySet()) {
            count += counts.get(x);

            if (count > threashHold) {
                counts.put(start, counts.get(start) - 1);
                counts.put(end, counts.get(end) + 1);

                if (counts.get(start) == 0) counts.remove(start);
                if (counts.get(end) == 0) counts.remove(end);

                return false;
            }
        }

        return true;
    }
}
 
Dùng Sweep line chạy chậm quá, dùng merge inverval cho nhanh mặc dù code hơi dài với dễ sai, :ah:
1727423383223.png


C++: 
class MyCalendarTwo {
public:
    MyCalendarTwo() {
        
    }
    
    bool book(int start, int end) {
        auto it = counter.lower_bound(end);
        
        // check
        for (auto it1 = it; it1 != counter.begin(); ) {
            it1 = prev(it1);
            auto [cur_end, cur_count] = it1->second;
            if (cur_end > start && cur_count > 1) return false;
            if (cur_end <= start) break;
        }
        
        // add
        for (auto it2 = it; start < end && it2 != counter.begin(); ) {
            it2 = prev(it2);
            auto &cur_start = it2->first;
            auto &[cur_end, cur_count] = it2->second;
            if (cur_end <= start) {
                counter.emplace(start, make_pair(end, 1));
                end = start;
                break;
            }
            
            if (cur_end > end) {
                counter.emplace(end, make_pair(cur_end, cur_count));
                cur_end = end;
            }
            
            if (end > cur_end) {
                counter.emplace(cur_end, make_pair(end, 1));
                end = cur_end;
            }
            
            if (start > cur_start) {
                counter.emplace(start, make_pair(end, cur_count + 1));
                end = start;
                break;
            } else {
                cur_count += 1;
                end = cur_start;
            }
        }
        
        if (start < end) {
            counter.emplace(start, make_pair(end, 1));
        }
        
        return true;
    }
private:
    map<int, pair<int, int>> counter;
};

C++: 
class MyCalendarThree {
public:
    MyCalendarThree() {
        
    }
    
    int book(int start, int end) {
        auto it = counter.lower_bound(end);
        
        int cur = 1;

        for (auto it2 = it; start < end && it2 != counter.begin(); ) {
            it2 = prev(it2);
            auto &cur_start = it2->first;
            auto &[cur_end, cur_count] = it2->second;
            if (cur_end <= start) {
                counter.emplace(start, make_pair(end, 1));
                end = start;
                break;
            }
            
            if (cur_end > end) {
                counter.emplace(end, make_pair(cur_end, cur_count));
                cur_end = end;
            }
            
            if (end > cur_end) {
                counter.emplace(cur_end, make_pair(end, 1));
                end = cur_end;
            }
            
            cur = max(cur, cur_count + 1);
            
            if (start > cur_start) {
                counter.emplace(start, make_pair(end, cur_count + 1));
                end = start;
                break;
            } else {
                cur_count += 1;
                end = cur_start;
            }
        }
        
        if (start < end) {
            counter.emplace(start, make_pair(end, 1));
        }
        
        k_ = max(k_, cur);
        return k_;
    }
private:
    map<int, pair<int, int>> counter;
    int k_;
};
 
sao code kiểu này lại ko pass ta, khó hiểu quá đi mất
yBBewst.png

Java: 
class MyCalendarTwo {
    private TreeMap<Integer, Integer> singleBooked;
    private TreeMap<Integer, Integer> doubleBooked;
    public MyCalendarTwo() {
        singleBooked = new TreeMap<>();
        doubleBooked = new TreeMap<>();
        singleBooked.put(-1,0);
        singleBooked.put((int) Math.pow(10,9), (int) Math.pow(10,9)+1);
        doubleBooked.put(-1,0);
        doubleBooked.put((int) Math.pow(10,9), (int) Math.pow(10,9)+1);
    }

    public boolean book(int start, int end) {
        int low = doubleBooked.floorKey(start);
        int high = doubleBooked.ceilingKey(start);
        if(start<doubleBooked.get(low)|| end>high)
            return false;
        low = singleBooked.floorKey(start);
        high = singleBooked.ceilingKey(start);
        if(start<singleBooked.get(low)||end>high){
            if(start<singleBooked.get(low))
                doubleBooked.put(Math.max(start,low),
                                Math.min(end,singleBooked.get(low)));
            if(end>high)
                doubleBooked.put(Math.max(start,high),
                                Math.min(end,singleBooked.get(high)));
        }
        singleBooked.put(start,end);
        return true;   
        
    }
}
 
Người quan sát cô đơn đã nói:
sao code kiểu này lại ko pass ta, khó hiểu quá đi mất
yBBewst.png

Java: 
class MyCalendarTwo {
    private TreeMap<Integer, Integer> singleBooked;
    private TreeMap<Integer, Integer> doubleBooked;
    public MyCalendarTwo() {
        singleBooked = new TreeMap<>();
        doubleBooked = new TreeMap<>();
        singleBooked.put(-1,0);
        singleBooked.put((int) Math.pow(10,9), (int) Math.pow(10,9)+1);
        doubleBooked.put(-1,0);
        doubleBooked.put((int) Math.pow(10,9), (int) Math.pow(10,9)+1);
    }

    public boolean book(int start, int end) {
        int low = doubleBooked.floorKey(start);
        int high = doubleBooked.ceilingKey(start);
        if(start<doubleBooked.get(low)|| end>high)
            return false;
        low = singleBooked.floorKey(start);
        high = singleBooked.ceilingKey(start);
        if(start<singleBooked.get(low)||end>high){
            if(start<singleBooked.get(low))
                doubleBooked.put(Math.max(start,low),
                                Math.min(end,singleBooked.get(low)));
            if(end>high)
                doubleBooked.put(Math.max(start,high),
                                Math.min(end,singleBooked.get(high)));
        }
        singleBooked.put(start,end);
        return true;
     
    }
}
Nhấp để mở rộng...
theo rule mới này thì intersections vẫn được maintain trong tree nên intersections interval có thể xuất hiện ở bất cứ đâu nơi mà start của nó bé hơn start đang xét ấy, nên code của bn chưa đúng ấy, ý kiến của Nhi là vậy.
Nếu chỉ xét 1 2 điểm thôi hk ăn thua đâu. Phải quét hết tree, mà làm vậy thì thui merge interval cho lẹ pn ak
 
Sửa lần cuối:
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
918
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.683
AD · 300×600

Chia sẻ trang này

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