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

Blue Amethyst

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é :)
Em thử sức thử phát :)

Java:
[QUOTE]
private static int solve(int[] bags)
{
    if (bags.length == 0)
    {
        return 0;
    }

    Set<Integer> set = new HashSet<>();
    for (int bag : bags)
    {
        set.add(bag);
    }

    int max = 1;
    for (int bag : bags)
    {
        int count = 1;
        if (set.contains(bag))
        {
            set.remove(bag);
            int weight = bag;
            while (set.remove((int)Math.sqrt(weight)))
            {
                ++count;
                weight = (int)Math.sqrt(weight);
            }
            weight = bag;
            while (set.remove((int)Math.pow(weight, 2)))
            {
                ++count;
                weight = (int)Math.pow(weight, 2);
            }
            max = Math.max(max, count);
        }
    }
    return max;
}
Format kì thế nhỉ :oops:
 
Last edited by a moderator:

Blue Amethyst

Senior Member
ý tưởng ổn rồi đấy, mà hàm Math.pow kia của java nó có handle tràn số ko nhỉ?

Mà có vẻ ko đúng lắm, chỗ này
Java:
while (set.remove((int)Math.sqrt(weight)))
Chỗ này ban nãy post xong em cũng hơi ngờ ngợ :beat_brick: vậy thì trước điều kiện này của while nên có thêm một điều kiện check liệu nó có phải là square root của perfect square hay không :cry:
 

trinity

Senior Member
bài này làm theo cách LIS chắc vẫn ổn :D
C++:
void solve() {
    int n;
    cin >> n;
    vector<int> bags(n);
    for (int &d : bags) {
        cin >> d;
    }

    vector<int> len(n, 1), back(n, -1);
    int maxlen = 1, k = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (bags[j] * bags[j] == bags[i]) {
                if (len[i] < len[j] + 1) {
                    len[i] = len[j] + 1;
                    back[i] = j;
                }

                if (len[i] > maxlen) {
                    maxlen = len[i];
                    k = i;
                }
            }
        }
    }

    cout << maxlen << endl;
    vector<int> ans;
    while (k != -1) {
        ans.push_back(bags[k]);
        k = back[k];
    }

    for (int i = ans.size() - 1; i >= 0; i--) {
        cout << ans[i] << " ";
    }
    cout << endl;
}
 
Last edited:

Fire Of Heart

M.I.A
tayto
Chỗ này ban nãy post xong em cũng hơi ngờ ngợ :beat_brick: vậy thì trước điều kiện này của while nên có thêm một điều kiện check liệu nó có phải là square root của perfect square hay không :cry:

uhm, cơ bản là cứ lấy căn xong, rồi lại bình phương cái căn đó lên, nếu bằng số trước đó thì xử lý tiếp.
 

GircoBoy

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é :)
Em đọc không kĩ đề tưởng có thể có túi trọng lượng bằng nhau, lúc đó lại phải xét corner case 1^2 = 1 nữa :whistle:
 

Violet_7

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é :)
Nếu là subarray thì dễ quá, còn nếu là sequence thì là khá giống câu dạy con tăng dài nhất. Time Ở(n^2)
Mà vì số sau đúng bằng bình phương số trước nên có thể dùng hash map cho từng số vs dãy [2, 1, 4, 5, 8].
Tạo map của số i là chuỗi còn dài nhất cho dãy kết thúc số i. Xét từng số, nếu ko phải số chính phương thì continue, nếu là số chính phương thì map[nums] = max[map[nums], map[sqrt(nums)] + 1)

Cáse đặc biệt: tạo th cho số đầu tiên nữa vì số đầu tiên trong dãy con có thể k phải số chính phương

Số 1 chính phương của nó vẫn là số 1

Time sẽ là 0(n)
 
Last edited:

ngx3009

Senior Member
Bác chỉnh lại khúc này xíu là đc
Java:
if (max_appear < current_appear){
    // Khi có một phần tử mới nhiều lần xuất hiện hơn thì cần phải xoá tất cả
    // các phần tử cũ trong mảng kết quả (do chúng có ít lần xuất hiện hơn).
    answer.clear();
   
    answer.add(nums[i]);
    answer = nums[i];
} else if (max_appear == current_appear){
    answer.add(nums[i]);
}
Mà bài này không cần 2 vòng for lồng nhau vậy đâu, bác có thể sắp xếp lại mảng để làm thì dễ hơn nhiều.
em vừa thử sort rồi dùng 1 for rồi k được bác ạ, vẫn phải cầnthêm 1 loop bên ngoài để khi thay đổi giá trị thì gán cái current_appear = 1, bác thử làm 1 loop với dãy int[] nums = {2,3,1,4,1,2,1,5,5,5}; xem
Code khi dùng sort của em đây
Java:
import java.util.ArrayList;
import java.util.Arrays;

public class FindMostAppear2 {
    public static ArrayList<Integer> findMostAppear2(int[] nums){
        int max_appear = 0;

        ArrayList<Integer> answer = new ArrayList<Integer>();
        Arrays.sort(nums); // 1 1 1 2 2 3 4 5 5 5
        int i = 0;
        while (i < nums.length) {
            int current_appear = 1;
            // tính từng số lần lặp của từng khối 111, 22, 3, 4, 555
            while (i + 1 < nums.length && nums[i] == nums[i + 1]) {
                current_appear++;
                i++;
            }
            if (max_appear < current_appear){
                max_appear = current_appear;
                // nếu current_appear > max_appear thì gán max = current,
                //và lúc này do cập nhật lại max mới nên phải xóa mảng đi
                answer.clear();
                answer.add(nums[i]);
            } else if (max_appear == current_appear){
                answer.add(nums[i]);
            }
            i++;
        }
        return answer;
    }
    public static void main(String[] args) {
        int[] nums = {2,3,1,4,1,2,1,5,5,5};
        for (int i = 0 ; i < findMostAppear2(nums).size(); i++){
            System.out.print(findMostAppear2(nums).get(i) + " ");
        }
        System.out.println("");
    }
}
 

GircoBoy

Senior Member
em vừa thử sort rồi dùng 1 for rồi k được bác ạ, vẫn phải cầnthêm 1 loop bên ngoài để khi thay đổi giá trị thì gán cái current_appear = 1, bác thử làm 1 loop với dãy int[] nums = {2,3,1,4,1,2,1,5,5,5}; xem
Code khi dùng sort của em đây
Java:
import java.util.ArrayList;
import java.util.Arrays;

public class FindMostAppear2 {
    public static ArrayList<Integer> findMostAppear2(int[] nums){
        int max_appear = 0;

        ArrayList<Integer> answer = new ArrayList<Integer>();
        Arrays.sort(nums); // 1 1 1 2 2 3 4 5 5 5
        int i = 0;
        while (i < nums.length) {
            int current_appear = 1;
            // tính từng số lần lặp của từng khối 111, 22, 3, 4, 555
            while (i + 1 < nums.length && nums[i] == nums[i + 1]) {
                current_appear++;
                i++;
            }
            if (max_appear < current_appear){
                max_appear = current_appear;
                // nếu current_appear > max_appear thì gán max = current,
                //và lúc này do cập nhật lại max mới nên phải xóa mảng đi
                answer.clear();
                answer.add(nums[i]);
            } else if (max_appear == current_appear){
                answer.add(nums[i]);
            }
            i++;
        }
        return answer;
    }
    public static void main(String[] args) {
        int[] nums = {2,3,1,4,1,2,1,5,5,5};
        for (int i = 0 ; i < findMostAppear2(nums).size(); i++){
            System.out.print(findMostAppear2(nums).get(i) + " ");
        }
        System.out.println("");
    }
}
2 vòng for nhưng vẫn là O(N) đó bác, nếu bác muốn sửa lại 1 vòng for cho đẹp hơn thì
Java:
int i = 0;
int current_appear = 1;
while (i < nums.length) {
    if (i + 1 < nums.length && nums[i] == nums[i + 1]) {
        current_appear++;
        i++;
        continue;
    }
    if (max_appear < current_appear){
        max_appear = current_appear;
        // nếu current_appear > max_appear thì gán max = current,
        //và lúc này do cập nhật lại max mới nên phải xóa mảng đi
        answer.clear();
        answer.add(nums[i]);
    } else if (max_appear == current_appear){
        answer.add(nums[i]);
    }
    // reset current_appear
    current_appear = 1;
    i++;
}
 

ngx3009

Senior Member
2 vòng for nhưng vẫn là O(N) đó bác, nếu bác muốn sửa lại 1 vòng for cho đẹp hơn thì
Java:
int i = 0;
int current_appear = 1;
while (i < nums.length) {
    if (i + 1 < nums.length && nums[i] == nums[i + 1]) {
        current_appear++;
        i++;
        continue;
    }
    if (max_appear < current_appear){
        max_appear = current_appear;
        // nếu current_appear > max_appear thì gán max = current,
        //và lúc này do cập nhật lại max mới nên phải xóa mảng đi
        answer.clear();
        answer.add(nums[i]);
    } else if (max_appear == current_appear){
        answer.add(nums[i]);
    }
    // reset current_appear
    current_appear = 1;
    i++;
}
cái đoạn if + continue cũng thành while bác nhỉ
 

Fire Of Heart

M.I.A
tayto
Nếu là subarray thì dễ quá, còn nếu là sequence thì là khá giống câu dạy con tăng dài nhất. Time Ở(n^2)
Mà vì số sau đúng bằng bình phương số trước nên có thể dùng hash map cho từng số vs dãy [2, 1, 4, 5, 8].
Tạo map của số i là chuỗi còn dài nhất cho dãy kết thúc số i. Xét từng số, nếu ko phải số chính phương thì continue, nếu là số chính phương thì map[nums] = max[map[nums], map[sqrt(nums)] + 1)

Cáse đặc biệt: tạo th cho số đầu tiên nữa vì số đầu tiên trong dãy con có thể k phải số chính phương

Số 1 chính phương của nó vẫn là số 1

Time sẽ là 0(n)

Thím hiểu sai đề rồi, có thể mình ko nói rõ.
Ví dụ: 2 3 9 16 4 thì thím tính sao
 

Violet_7

Senior Member
Thím hiểu sai đề rồi, có thể mình ko nói rõ.
Ví dụ: 2 3 9 16 4 thì thím tính sao

đầu tiên map[2] = 1, map[3] = 1, ...
xét từng số một:
map[2] vẫn bằng 1 vì 2 ko là số chính phương
map[3] vẫn bằng 1
map[9] = max(map[9], map[3] + 1) = 2
map[16] = max(map[16], map[4] + 1) = 1
map[4] = max(map[4], map[2] + 1) = 2
  • cái này sequence, còn subarray thì dễ quá
  • còn nếu nói là tập con thì sort thôi
 

GircoBoy

Senior Member
Hôm nay là 1 bài Medium: cho 1 cái bánh hình chữ nhật, sau đó cắt cái bánh theo chiều ngang hoặc chiều dọc bằng một số nhát cắt khác nhau, khi đó cái bánh sẽ bị phân thành nhiều phần nhỏ hơn, tính diện tích phần lớn nhất.

Cách làm của mình
Để tính diện tích phần lớn nhất, ta cần tìm chiều ngang lớn nhất và chiều dọc lớn nhất, nhận thấy chiều ngang và chiều dọc ko phụ thuộc nhau nên 2 cái này có thể tìm riêng biệt.

Để tìm chiều ngang lớn nhất khá đơn giản, ta chỉ cần sort lại mảng horizontalCuts, khi đó maxHorizontal sẽ bằng max(khoảng cách giữa 2 giá trị liền kề trong mảng). Cần lưu ý phải xét cả khoảng cách từ 0 -> giá trị nhỏ nhất và từ giá trị lớn nhất -> w. Cách làm của mình là push thêm 0 với w vào mảng horizontalCuts rồi sort lại tính cho dễ :)

Với chiều dọc làm tương tự, khi đó ans = maxHorizontal * maxVertical.
 

tdat00

Đã tốn tiền
Bài sáng nay đơn giản nhỉ. Vụ lấy kết quả mod 10^9 + 7 các thím có cách nào khác ngoài cách đổi số sang int64 không? Kiểu như a*b % c = (a % c)*(b % c) * ... ấy?

À rồi, a*b % c = ((a % c)*(b % c)) % c nhưng trong bài này c lớn quá nên (a % c) * (b % c) cũng bị tràn số luôn rồi => phải cast qua int64 mới được.

  • Sort 2 mảng horizontal với vertical lại để tính khoảng cách giữa các nhát cắt.
  • Tìm ra khoảng cách vertical và horizontal lớn nhất. Nhân lại là ra kết quả.
  • Độ fuck tạp O(mlogm + nlogn) với m, n là độ dài 2 mảng.

C#:
public class Solution {
    public int MaxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
        Array.Sort(horizontalCuts);
        Array.Sort(verticalCuts);
       
        int maxH = Math.Max(horizontalCuts[0], h - horizontalCuts[horizontalCuts.Length - 1]);
        int maxW = Math.Max(verticalCuts[0], w - verticalCuts[verticalCuts.Length - 1]);
        for (var i = 1; i < horizontalCuts.Length; i++)
        {
            maxH = Math.Max(maxH, horizontalCuts[i] - horizontalCuts[i-1]);
        }
        for (var i = 1; i < verticalCuts.Length; i++)
        {
            maxW = Math.Max(maxW, verticalCuts[i] - verticalCuts[i-1]);
        }
       
        return (int)(((long)maxH*(long)maxW) % 1000_000_007);
    }
}
 
Last edited:

Fire Of Heart

M.I.A
tayto
đầu tiên map[2] = 1, map[3] = 1, ...
xét từng số một:
map[2] vẫn bằng 1 vì 2 ko là số chính phương
map[3] vẫn bằng 1
map[9] = max(map[9], map[3] + 1) = 2
map[16] = max(map[16], map[4] + 1) = 1
map[4] = max(map[4], map[2] + 1) = 2
  • cái này sequence, còn subarray thì dễ quá
  • còn nếu nói là tập con thì sort thôi

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ế.
 

tdat00

Đã tốn tiền
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ế.

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;
    }
}
 
Top