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

Violet_7

Senior Member
Talk is cheap, show me code.

Với lại ko có sequence hay subarray gì cả. Tôi vẫn ko hiểu sao thím cứ nhắc tới subarray, hay thím ko hiểu rõ đề thế.
thím bảo dãy perfect là dãy như thế nào
VD có mảng [256, 2, 4, 3, 9, 16]
  • dãy liên tiếp thì nó chứa các số liên tiếp thỏa mãn đề bài -> [2, 4] hoặc [3, 9]
  • dãy ko cần các số liên tiếp mà chỉ cần index tăng thì sẽ là dãy [2, 4, 16]
  • Còn tập hợp ko cần đúng index tăng thì là [2, 4, 16, 256]
  • Căn bản cái từ 'dãy' có nhiều kiểu dãy, thím đưa đúng 1 vd nên em cx chưa hiểu thím bảo là dãy nào.
 

Fire Of Heart

M.I.A
tayto
thím bảo dãy perfect là dãy như thế nào
VD có mảng [256, 2, 4, 3, 9, 16]
  • dãy liên tiếp thì nó chứa các số liên tiếp thỏa mãn đề bài -> [2, 4] hoặc [3, 9]
  • dãy ko cần các số liên tiếp mà chỉ cần index tăng thì sẽ là dãy [2, 4, 16]
  • Còn tập hợp ko cần đúng index tăng thì là [2, 4, 16, 256]
  • Căn bản cái từ 'dãy' có nhiều kiểu dãy, thím đưa đúng 1 vd nên em cx chưa hiểu thím bảo là dãy nào.

Chắc mình giải thích ko rõ đề.
Thím có thể mua ko cần theo thứ tự input, nhưng các bao gạo thím mua nó phải thành 1 dãy theo yêu cầu, là bao sau sẽ có trọng lượng bằng bình phương bao trc
 

Fire Of Heart

M.I.A
tayto
theo đề thì mua gạo, tức có thể chọn bao gạo không theo tứ tự đúng không? Như vậy thì expected output của cái này [25, 4, 2, 16, 5] sẽ là 3? Như vậy sẽ là trường hợp sub-array như thím @Violet_7 mô tả.

Đây là code của tôi, độ phức tạp O(nlogn). Edge case thì tôi nghĩ có 4 loại:
  • mảng có các số 0 => nghe ko thực tế lắm
  • mảng có các số 1 => thực tế.
  • tràn số => bình phương số cũ lên nó thành số âm.
  • số lượng bao gạo có cùng giá trị ảnh hưởng đến chuỗi chính phương => chưa nghĩ ra test case nào, mà hình như số lượng bao gạo sẽ ko ảnh hưởng. Nhưng thôi cứ dùng dictionary thay vì set cho chắc cú.

C#:
using System;
using System.Collections.Generic;

public class MuaGao
{
    static void Main()
    {
        var sol = new Solution();
        Console.WriteLine(sol.solve(new uint[] {25,4,2,16,5})); // expected 3
        Console.WriteLine(sol.solve(new uint[] {1,1,25,4,2,16,5,1,1,1})); // expected 5
        Console.WriteLine(sol.solve(new uint[] {46343, 2147673649})); // expected 2
    }
}

public class Solution
{
    public uint solve(uint[] nums)
    {
        var q = new PriorityQueue<uint, uint>();
        var dict = new Dictionary<uint, uint>();
        foreach (var num in nums)
        {
            if (!dict.ContainsKey(num))
            {
                dict.Add(num, 1);
                q.Enqueue(num, num);
            }
            else
            {
                dict[num]++;
            }
        }

        uint max = 0;
        while (q.Count > 0)
        {
            uint num = q.Dequeue(), count = 0;
            while (dict.ContainsKey(num) && dict[num] > 0)
            {
                dict[num]--;
                count++;
                num = num*num;
            }
            max = Math.Max(max, count);
        }

        return max;
    }
}

Testcase thứ 2 của thím output vẫn là 3 chứ nhỉ.
Vì chỉ có dãy 2 4 16 là dài nhất
 

tdat00

Đã tốn tiền
Testcase thứ 2 của thím output vẫn là 3 chứ nhỉ.
Vì chỉ có dãy 2 4 16 là dài nhất

Oh vậy ra cái edge case mua 5 bao số 1 không được tính. Tôi cứ tưởng là vẫn tính cơ.

Sent from Samsung SM-A528B using vozFApp
 

Violet_7

Senior Member
Chắc mình giải thích ko rõ đề.
Thím có thể mua ko cần theo thứ tự input, nhưng các bao gạo thím mua nó phải thành 1 dãy theo yêu cầu, là bao sau sẽ có trọng lượng bằng bình phương bao trc
Nếu vậy là tập hợp các túi xong sort tập hợp đó phải thỏa mãn đễ bài
  • Thế thì dùng hash map thôi, thím check hộ em code này sai case nào ko, solution này dành cho cân nặng mỗi túi > 1,
  • nếu có Th túi = 1 thì tính riêng nữa, mà > 1 cho nó dễ
  • Ý tưởng thì vì cân nặng mỗi túi max 10^6 nên dùng map luôn, for(i: 1-> 10^3) map[i ^2] += map. Map đại diện cho số tui nhiều nhất kết thúc tại i


int maxBags(vector<int>& arr) {
int MAX = 1e6, result = 0;
unordered_map<int, int> map;
for(auto& num : arr) {
map[num] = 1;
}

for(int i = 1; i <= sqrt(MAX); i++) {
int next = pow(i, 2);
if(map[next] == 0)
continue;
map[next] += map [i..];
result = max(result, map[pow(i, 2)]);
}
return result;
}
 

Fire Of Heart

M.I.A
tayto
Oh vậy ra cái edge case mua 5 bao số 1 không được tính. Tôi cứ tưởng là vẫn tính cơ.

Sent from Samsung SM-A528B using vozFApp

À để bổ sung thêm:
Phải có ít nhất 2 loại khác nhau nhé.
Còn ví dụ nếu bao gạo = 1 -> thì mua bao nhiêu túi nó ko quan trọng, vì chỉ có 1 loại trọng lượng 1.
Input đảm bảo các bao có trọng lượng luôn khác nhau. Số lượng từng loại là vô hạn
 

Fire Of Heart

M.I.A
tayto
Nếu vậy là tập hợp các túi xong sort tập hợp đó phải thỏa mãn đễ bài
  • Thế thì dùng hash map thôi, thím check hộ em code này sai case nào ko, solution này dành cho cân nặng mỗi túi > 1,
  • nếu có Th túi = 1 thì tính riêng nữa, mà > 1 cho nó dễ
  • Ý tưởng thì vì cân nặng mỗi túi max 10^6 nên dùng map luôn, for(i: 1-> 10^3) map[i ^2] += map. Map đại diện cho số tui nhiều nhất kết thúc tại i


int maxBags(vector<int>& arr) {
int MAX = 1e6, result = 0;
unordered_map<int, int> map;
for(auto& num : arr) {
map[num] = 1;
}

for(int i = 1; i <= sqrt(MAX); i++) {
int next = pow(i, 2);
if(map[next] == 0)
continue;
map[next] += map [i..];
result = max(result, map[pow(i, 2)]);
}
return result;
}

Nếu sort là nlogn đúng ko? Vậy muốn o(n) thì sao?

Nếu 10^6 ^2 có bị tràn số ko?
 

Fire Of Heart

M.I.A
tayto
Sort ở đây là counting sort đó thím max vào có 10^6 nên dùng counting sort luôn. Thím nhìn kĩ solotion đó


Sort ở đây là counting sort đó thím max vào có 10^6 nên dùng counting sort luôn. Thím nhìn kĩ solotion đó

Đoạn code của thím sort chỗ nào vậy? Nếu vậy thím phải cài đặt thêm phần sort đó vô.
Còn ko thím chỉ bảo dùng sort thì default là n log n
 

Fire Of Heart

M.I.A
tayto
thím bảo dãy perfect là dãy như thế nào
VD có mảng [256, 2, 4, 3, 9, 16]
  • dãy liên tiếp thì nó chứa các số liên tiếp thỏa mãn đề bài -> [2, 4] hoặc [3, 9]
  • dãy ko cần các số liên tiếp mà chỉ cần index tăng thì sẽ là dãy [2, 4, 16]
  • Còn tập hợp ko cần đúng index tăng thì là [2, 4, 16, 256]
  • Căn bản cái từ 'dãy' có nhiều kiểu dãy, thím đưa đúng 1 vd nên em cx chưa hiểu thím bảo là dãy nào.

Ko cần đúng index nhé.
Như case này là output = 4 , vì mảng có thể dài nhất là 2. 4 16 256
 

Violet_7

Senior Member
Đoạn code của thím sort chỗ nào vậy? Nếu vậy thím phải cài đặt thêm phần sort đó vô.
Còn ko thím chỉ bảo dùng sort thì default là n log n
Counting sort có j mà phải cài đặt. Dùng map để đánh dấu những số trong mảng rồi duyệt từ 1 đến 10^3, map = false nghĩa là số i ko trong mảng thì continue, true thì map[i^2 ] += map[i.] nếu i^2 cx trong mảng. Counting sort là thế, sẽ duyệt đc các số bé nhất nhất trong mảng chứ cần j build hàm làm j.
 

Fire Of Heart

M.I.A
tayto
Counting sort có j mà phải cài đặt. Dùng map để đánh dấu những số trong mảng rồi duyệt từ 1 đến 10^3, map = false nghĩa là số i ko trong mảng thì continue, true thì map[i^2 ] += map[i.] nếu i^2 cx trong mảng. Counting sort là thế, sẽ duyệt đc các số bé nhất nhất trong mảng chứ cần j build hàm làm j.
Uh ok hiểu rồi.
Vì ban đầu thím nói dùng sort nên tôi tưởng thím sort trc rồi mới xử lý.

Btw vậy vẫn ko tối ưu nhé, giả sử array có 5 phần tử thôi thím vẫn phải duyệt 10^6 lần.
Tối ưu hơn đi
 

Violet_7

Senior Member
Uh ok hiểu rồi.
Vì ban đầu thím nói dùng sort nên tôi tưởng thím sort trc rồi mới xử lý.

Btw vậy vẫn ko tối ưu nhé, giả sử array có 5 phần tử thôi thím vẫn phải duyệt 10^6 lần.
Tối ưu hơn đi
Thực ra time sẽ là o(size mảng) + o(sqrt(max value)), duyệt 10^3 thôi. Vì size array 10^5 ms dùng cách này, còn size nhỏ thì sort bình thường là được. Còn tối ưu hơn nữa thì chịu. Căn bản chỉ quan tâm cái worst case thôi
 

Fire Of Heart

M.I.A
tayto
Thực ra time sẽ là o(size mảng) + o(sqrt(max value)), duyệt 10^3 thôi. Vì size array 10^5 ms dùng cách này, còn size nhỏ thì sort bình thường là được. Còn tối ưu hơn nữa thì chịu. Căn bản chỉ quan tâm cái worst case thôi

Uh nói chung là chưa tối ưu lắm, làm đúng thì o(n) thôi
 
yếu quá đc có 77%.


Screen Shot 2022-07-02 at 14.13.55.png


Python:
class Solution:
    def maxArea(self, h: int, w: int, horizontalCuts: List[int], verticalCuts: List[int]) -> int:
        M = 1000000007

        horizontalCuts = [0, *horizontalCuts, h]
        verticalCuts = [0, *verticalCuts, w]
        
        horizontalCuts.sort()
        verticalCuts.sort()
        
        max_horizontal_edge = max(horizontalCuts[i] - horizontalCuts[i-1]
                for i in range(1, len(horizontalCuts)))

        max_vertical_edge = max(verticalCuts[i] - verticalCuts[i-1]
                for i in range(1, len(verticalCuts)))
        
        
        return ((max_horizontal_edge % M) * (max_vertical_edge % M)) % M
 
Last edited:

Venjsen

Senior Member
Có bài này cho anh em thử :)

Đi siêu thị mua gạo, có 1 dãy các túi gạo với trọng lượng khác nhau. Bạn muốn mua 1 dãy perfect sao cho cứ túi này thì bằng bình phương trọng lượng túi trước. Tìm dãy dài nhất có thể

Ví dụ: Input: 3 9 2 4 16
Dãy nhiều các thím có thể mua dc là 2 4 16 -> output = 3

Ràng buộc: Input array size = n < 10^5
trọng lượng túi gạo < 10^6

Ko có link đâu, nên các thím tự tạo test case cho pass corner case nhé :)
TC cho pow(x,n) là O(n) nhưng n=2 nên tương đương O(1).
Đại loại là dựa vào giới hạn để giải, với 2 thì 2^20>1e6, với 3 là 3^15>1e6,... vì vậy tối đa 1 dãy chỉ có vài phần tử (tối đa là 5) (trừ mấy case đại loại dãy chứa 1, đề không cho cận dưới nên mặc định dãy nguyên dương vậy).
C++:
int solve(vector<int>&arr){
    int MAXN=1e6;
    int n=arr.size();
    vector<int>have(MAXN+5,0);
    for(auto x:arr) have[x]=1;
    int ans=0;
    int cnt1=0;
    for(int i=0;i<n;i++){
        int num=arr[i];
        if(arr[i]==1){
            cnt1++;
            continue;
        }
        int count=1;
        for(int j=2;j<=5;j++){
            num=pow(num,2);
            if(num>MAXN) break;
            if(!have[num]) break;
            count++;
        }
        ans=max(ans,count);
    }
    return max(ans,cnt1);
}
 
Last edited:
Top