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

thuyduong2007 · 11/9/22

Bài hôm nay t ngồi nghĩ cũng k ra. Đọc hint của @Violet_7 thì làm được ngay,

Lập Trình Viên Số Khổ · 11/9/22

Ai biết làm contest 310 C3 ko
loop 2 vòng TLE

https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/

Python:

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        visited = [0 for _ in range(len(intervals))]
        res = 0
       
        for i in range(len(intervals)):
           
            if visited[i] == 1:
                continue
               
            visited[i] = 1
            last = intervals[i][1]

            for j in range(i+1, len(intervals)):
                if visited[j] == 1:
                    continue
                   
                if intervals[j][0] > last:
                    visited[j] = 1
                    last = intervals[j][1]
                   
            res += 1
           
        return res

NudeDuck · 11/9/22

Tuần này câu cuối khó ghê :<

Lập Trình Viên Số Khổ đã nói:
Ai biết làm contest 310 C3 ko
loop 2 vòng TLE

https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/

Python:

class Solution: def minGroups(self, intervals: List[List[int]]) -> int: intervals.sort() visited = [0 for _ in range(len(intervals))] res = 0 for i in range(len(intervals)): if visited[i] == 1: continue visited[i] = 1 last = intervals[i][1] for j in range(i+1, len(intervals)): if visited[j] == 1: continue if intervals[j][0] > last: visited[j] = 1 last = intervals[j][1] res += 1 return res

Câu này thì ý tưởng là:
1. Sort interval theo thời gian end
2. Duy trì 1 danh sách các group và di chuyển i từ 0 đến n-1. Với mỗi interval thì tìm group thích hợp để nhét interval vào (group thích hợp là group có end lớn nhất có thể mà end đó vẫn bé hơn start của interval)
3. Code ^^

Java:

class Solution { public int minGroups(int[][] intervals) { TreeSet<Group> set=new TreeSet<>(new Comparator<Group>(){ public int compare(Group a, Group b){ if(a.end!=b.end) return a.end-b.end; return a.i-b.i; } }); Arrays.sort(intervals, new Comparator<int[]>(){ public int compare(int[] a, int[] b){ if(a[1]!=b[1]) return a[1]-b[1]; return a[0]-b[0]; } }); int n=intervals.length; int res=0; for(int i=0;i<n;i++){ Group dummy=new Group(intervals[i][0], -1); Group group=set.floor(dummy); if(group!=null){ set.remove(group); group.end=intervals[i][1]; group.i=i; } else{ group=new Group(intervals[i][1], i); res++; } set.add(group); } return res; } } class Group{ int end; int i; Group(int end, int i){ this.end=end; this.i=i; } }

sau_tim_thiep_hong · 11/9/22

Lập Trình Viên Số Khổ đã nói:
Ai biết làm contest 310 C3 ko
loop 2 vòng TLE

https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/

Python:

class Solution: def minGroups(self, intervals: List[List[int]]) -> int: intervals.sort() visited = [0 for _ in range(len(intervals))] res = 0 for i in range(len(intervals)): if visited[i] == 1: continue visited[i] = 1 last = intervals[i][1] for j in range(i+1, len(intervals)): if visited[j] == 1: continue if intervals[j][0] > last: visited[j] = 1 last = intervals[j][1] res += 1 return res

Dùng thêm heap cho đỡ comp time. Có ông làm được cả On

Python:

from heapq import *
class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        tmp=[]
        for l,r in sorted(intervals):
            if len(tmp)==0:
                heappush(tmp,r)
                continue
           
            if l <= tmp[0]:
                heappush(tmp,r)
            else:
                heappushpop(tmp,r)
        return len(tmp)

NudeDuck · 11/9/22

Bài cuối xài Segment Treeeee

( Thế thì chịuuuu

Violet_7 · 11/9/22

Hôm nay contest câu cuối 7 điểm khó vl. Làm 3 câu đầu có 30p mà câu cuối chịu

Lập Trình Viên Số Khổ · 11/9/22

sau_tim_thiep_hong đã nói:

Dùng thêm heap cho đỡ comp time. Có ông làm được cả On

Python:

from heapq import *
class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        tmp=[]
        for l,r in sorted(intervals):
            if len(tmp)==0:
                heappush(tmp,r)
                continue
          
            if l <= tmp[0]:
                heappush(tmp,r)
            else:
                heappushpop(tmp,r)
        return len(tmp)

hay dữ, mà tui sửa lại code chút cho nó ngắn :v

của @NudeDuck độ phức tạp bn vậy

NudeDuck · 11/9/22

Lập Trình Viên Số Khổ đã nói:
Xem tệp đính kèm 1374045

hay dữ, mà tui sửa lại code chút cho nó ngắn :v

của @NudeDuck độ phức tạp bn vậy

O(nlgn) ấy :LOL:

mà phức tạp lắm.
Tuần này thấy bài hằng ngày toàn bài hard là biết ngay cuối tuần contest khó

Lập Trình Viên Số Khổ · 11/9/22

sau_tim_thiep_hong đã nói:

Dùng thêm heap cho đỡ comp time. Có ông làm được cả On

Python:

from heapq import *
class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        tmp=[]
        for l,r in sorted(intervals):
            if len(tmp)==0:
                heappush(tmp,r)
                continue
       
            if l <= tmp[0]:
                heappush(tmp,r)
            else:
                heappushpop(tmp,r)
        return len(tmp)

sort nó đã ăn nlogn rùi, ô có link o(n) ko share tui phát. Mà ai biết tính độ phức tạp của các bài liên quan đến heap ko

ví dụ bài này thì độ phức tạp như nào

Python:

        intervals = [[1, 5], [1, 10], [2, 3], [5, 10], [6, 8]]
        pq = []
        for l, r in sorted(intervals):
            heappush(pq, r)
            if l > pq[0]:
                heappop(pq)

dynamic programming · 11/9/22

Bài hôm nay mình sắp xếp theo speed giảm dần, xử lý cái đoạn lấy < k engineers loằng ngoằng với lặp vc. Thấy ae sắp xếp theo efficiency chỉ cần lặp có 1 lần sau khi sort

https://leetcode.com/submissions/detail/796819407/

Sent from Samsung SM-J730G using vozFApp

bribnt · 11/9/22

Violet_7 đã nói:
Hôm nay contest câu cuối 7 điểm khó vl. Làm 3 câu đầu có 30p mà câu cuối chịu

NudeDuck đã nói:
Bài cuối xài Segment Treeeee ( Thế thì chịuuuu

Câu cuối code trâu bò O(nk) vẫn accept, mặc dù tốn đến 1.8s.
Ý tưởng:

Ý tưởng: Dùng map (end -> len) để lưu danh sách những sequence với kết thúc là end, độ dài len, để ý thấy trong các subsequence cùng kết thúc là end thì chỉ cần lưu cái có độ dài lớn nhất là đủ.
Với mỗi phần tử thì thử tìm cách nối nó với những subsequence hợp lệ đã có rồi cập nhật map.

Thuật toán: Loop qua các phần tử, tìm những subsequence trong khoảng từ a-k đến a-1

- Nếu không tìm thấy cái nào thì thêm sub mới độ dài là 1,

- Nếu tìm thấy nhiều sub thì tìm sub có len lớn nhất và nối vào, giả sử sub này có end là e0,

- Đồng thời, xóa hết tất cả các sub khác có độ dài từ e0+1 -> a-1 trong map. Lý do là vì những sub này không thể phát triển thành sub có độ dài max sau này nữa.

Cải tiến: Nếu sử dụng CTDL nào đó mà tìm nhanh được max len trong một khoảng của end thì có thể giảm độ phức tạp xuống. Segment tree có lẽ là lựa chọn hợp lý.

sau_tim_thiep_hong · 11/9/22

Lập Trình Viên Số Khổ đã nói:
sort nó đã ăn nlogn rùi, ô có link o(n) ko share tui phát. Mà ai biết tính độ phức tạp của các bài liên quan đến heap ko

ví dụ bài này thì độ phức tạp như nào

Python:

intervals = [[1, 5], [1, 10], [2, 3], [5, 10], [6, 8]] pq = [] for l, r in sorted(intervals): heappush(pq, r) if l > pq[0]: heappop(pq)

heap thì log(n) ông .
O(N) đây, chưa đọc thấy nó để title là vậy

)
https://leetcode.com/problems/divid...560080/Simplest-way-oror-Prefix-Sum-oror-O(n)

Cong_Go_De_Su · 11/9/22

Phải tự implement PQ, thặc là vl

Mã:

defmodule PoorManPq do
  defstruct data: nil, size: 0
  def new(), do: %PoorManPq{data: :gb_trees.empty(), size: 0}
  def size(%PoorManPq{size: s}), do: s
  def push(%PoorManPq{data: d, size: s}, key) do
    case :gb_trees.lookup(key, d) do
      :none -> %PoorManPq{data: :gb_trees.insert(key, 1, d), size: s + 1}
      {:value, count} -> %PoorManPq{data: :gb_trees.update(key, count + 1, d), size: s + 1}
    end
  end
  def pop(%PoorManPq{data: d, size: s} = pq) do
    cond do
      s == 0 ->
        {nil, pq}
      true ->
        case :gb_trees.smallest(d) do
          {v, 1} -> {v, %PoorManPq{data: :gb_trees.take_smallest(d) |> elem(2), size: s - 1}}
          {v, count} -> {v, %PoorManPq{data: :gb_trees.update(v, count - 1, d), size: s - 1}}
        end
    end
  end
end
defmodule Solution do
  @divisor 1_000_000_007
  def max_performance(_n, speed, efficiency, k) do
    Stream.zip(efficiency, speed)
    |> Enum.sort_by(fn {e, s} -> {-e, s} end)
    |> Enum.reduce({0, 0, PoorManPq.new()}, fn {e, s}, {result, speed_sum, pq} ->
      {speed_sum, pq} =
        if PoorManPq.size(pq) == k do
          {min_speed, pq} = PoorManPq.pop(pq)
          {speed_sum - min_speed + s, pq}
        else
          {speed_sum + s, pq}
        end
      {max(result, speed_sum * e), speed_sum, PoorManPq.push(pq, s)}
    end)
    |> elem(0)
    |> rem(@divisor)
  end
end

Aristides · 11/9/22

bài khó vãi nhái

Nhờ bác nào review giúp trư cái code này tại sao sai ở test case thứ 25 vậy?

Java:

class Solution {
    public int maxPerformance(int n, int[] speed, int[] efficiency, int k) {
        if(n <= 0 || k <= 0)
        {
            throw new IllegalArgumentException("ConstraintViolation!");
        }
        Tuples[] e = new Tuples[n];
        for(int i = 0; i < n; i++)
        {
            e[i] = new Tuples(speed[i], efficiency[i]);
        }
        Arrays.sort(e, Collections.reverseOrder());
        PriorityQueue<Integer> minSpeed = new PriorityQueue<>();
        minSpeed.add(e[0].first);
        int sumSpeed = e[0].first;
        int minEff = e[0].second;
        long ans = sumSpeed * minEff;
        for(int i = 1; i < n; i++)
        {
            sumSpeed += e[i].first;
            minEff = e[i].second;
            minSpeed.add(e[i].first);
            if(minSpeed.size() > k)
            {
                sumSpeed -= minSpeed.remove();
            }
            ans = Math.max(ans, sumSpeed * minEff);
        }
        return (int)(ans % (Math.pow(10, 9) + 7));
    }
}
class Tuples implements Comparable<Tuples>
{
    public int first;
    public int second;
    public Tuples()
    {
       first = 0;
       second = 0;
    }
    public Tuples(int first, int second)
    {
       this.first = first;
       this.second = second;
    }
    @Override
    public int compareTo(Tuples o)
    {
        if(this.second == o.second)
        {
           return 0;
        }
        return (this.second < o.second) ? -1 : 1;
    }
}

Aristides · 11/9/22

à mà chỗ remove kia sửa lại là poll

Voz bị gì không cho edit code

Kân team v3 · 11/9/22

Aristides đã nói:
if(minSpeed.size() > k)

trong pq chỉ có tối đa k-1 phần tử thoy chứ ko phải k phần tử vì dòng sumSpeed += e[i].first; là cộng thêm 1 phần tử ròi, trong pq mà có k phần tử thì hóa ra += thêm là k+1 phần tử

Aristides · 11/9/22

Kân team v3 đã nói:
trong pq chỉ có tối đa k-1 phần tử thoy chứ ko phải k phần tử vì dòng sumSpeed += e[i].first; là cộng thêm 1 phần tử ròi, trong pq mà có k phần tử thì hóa ra += thêm là k+1 phần tử

không phải đâu bác

Sửa cái data type của sumSpeed từ int sang long là OK ngay

mịa nãy phải clone về Intellij rồi debug thử mới ra. Do cái sumSpeed làint nên khi cộng lại tổng nó chỉ ởINT_MAX nên cái hàm Max() nó mặc định cast sang long cũng là INT_MAX luôn. Dò đến chỗ breakpoint hàm max mới phát hiện ra

Lập Trình Viên Số Khổ · 11/9/22

Python:

class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        pair = sorted(zip(efficiency, speed), key=lambda x: -x[0])
        sum_speed, perf = 0, 0
        speed_pq = []
        for curr_efficiency, curr_speed in pair:
            if len(speed_pq) == k:
                sum_speed -= heappop(speed_pq)
            heappush(speed_pq, curr_speed)
            sum_speed += curr_speed
            perf = max(perf, sum_speed * curr_efficiency)
        return perf % 1000000007

Aristides · 11/9/22

mà công nhận Python code vừa gọn vừa không phải quan tâm nhiều đến data type

thôi mai thử học python làm AI, ML, DL cho thượng đẳng chứ chiều giờ chỉ vì cái data type chết tiệt của chà và mà bực mình gì đâu

Kân team v3 · 11/9/22

Aristides đã nói:
không phải đâu bác

Sửa cái data type của sumSpeed từ int sang long là OK ngay

mịa nãy phải clone về Intellij rồi debug thử mới ra. Do cái sumSpeed làint nên khi cộng lại tổng nó chỉ ởINT_MAX nên cái hàm Max() nó mặc định cast sang long cũng là INT_MAX luôn. Dò đến chỗ breakpoint hàm max mới phát hiện ra

Xem tệp đính kèm 1375087

ờm chỗ speedSum toy ko để ý

mà lạ vậy pq size là k vẫn đúng à

à chắc vì xét max sau khi -= nên vẫn đúng

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

Member

Senior Member

Junior Member

Member

Junior Member

Member

Senior Member

Junior Member

Senior Member

Junior Member

Đã tốn tiền

Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này