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

Fire Of Heart said:
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é :)
Click to expand...
tui thấy Violet_7 giải đúng rùi, đây là phiên bản python

Python: 
from collections import defaultdict

def maxBags(arr):
    hm = defaultdict(int)

    for num in arr:
        hm[num] += 1

    result = 0
    for num in arr:
        if num > 1000:
            continue
        next = num ** 2
        if hm[next] == 0:
            continue
        hm[next] += hm[num]
        result = max(result, hm[next])

    return result
 
Fire Of Heart said:
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é :)
Click to expand...
Với mỗi k = a_i duyệt cho tới khi k = k * k không có trong mảng (có thể dùng map hoặc mảng 10^6). Mỗi bước duyệt vậy tính mm[a_i] += mm[k].

C++: 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    unordered_map<ll, int> mm;
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        mm[a[i]] = 1;
    }

    for (int i = 0; i < n; ++i) {
        if (!mm[a[i]]) continue;
        ll k = a[i];

        while (mm[k * k]) {
            k = k * k;
            mm[a[i]] += mm[k];
            mm[k] = 0;
        }

        ans = max(ans, mm[a[i]]);
    }

    cout << ans;

    return 0;
}
 
Lập Trình Viên Số Khổ said:
tui thấy Violet_7 giải đúng rùi, đây là phiên bản python

Python: 
from collections import defaultdict

def maxBags(arr):
    hm = defaultdict(int)

    for num in arr:
        hm[num] += 1

    result = 0
    for num in arr:
        if num > 1000:
            continue
        next = num ** 2
        if hm[next] == 0:
            continue
        hm[next] += hm[num]
        result = max(result, hm[next])

    return result
Click to expand...


Ko sai, nhưng ko tối ưu
 
Giải
cuc gach said:
Với mỗi k = a_i duyệt cho tới khi k = k * k không có trong mảng (có thể dùng map hoặc mảng 10^6). Mỗi bước duyệt vậy tính mm[a_i] += mm[k].

C++: 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    unordered_map<ll, int> mm;
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        mm[a[i]] = 1;
    }

    for (int i = 0; i < n; ++i) {
        if (!mm[a[i]]) continue;
        ll k = a[i];

        while (mm[k * k]) {
            k = k * k;
            mm[a[i]] += mm[k];
            mm[k] = 0;
        }

        ans = max(ans, mm[a[i]]);
    }

    cout << ans;

    return 0;
}
Click to expand...

Ý tưởng cũng gần đúng nhưng có vẻ sót case:
Thím thử input này: 16 4 2 3 9 có ra 3 ko
 
Nói idea bài trên nhá:
Ví dụ với input 2 4 16 3 9
Các thím để ý là có thể tách ra 2 chuỗi dài nhất 2 4 16 và 3 9

Vấn đề là thứ tự lộn xộn, giả sử a0 = 16.
Vậy mình sẽ đi 2 hướng:

  • hướng 1 bình phương 16, rồi cứ bình phương tới khi ko tồn tại trong mảng. Nếu tồn tại thì tăng count lên 1.
  • hướng 2: đi lui, lấy sqrt 16 = 4, check 4 có trong mảng ko.
  • Cứ mỗi lần check thì tăng count lên 1 đơn vị, lúc nào quay lại loôp thì reset count, trc đó so sánh với max để lưu lại giá trị lớn nhất
Nhưng sẽ có tình huống sqrt của nó là lẻ, ví dụ căn 2 của 8 chẳng hạn.
Cho nên cần check thêm 1 lượt bằng cách lấy bình phương lại xem có = 8 hay 16 ko.

Làm như vậy thì chỉ tốn O(n) thôi. Ko cần sort, có thể check tồn tại hay ko = cách dùng array hay map đều dc. Sau khi check 1 số xong thì remove ra khỏi map là dc.

Ngoài ra cần handle tình huống ^2 lên bị tràn số nên cần check tới 10^3 là dc

Có bạn kia code đúng hướng r nên mình ko code lại
 
Fire Of Heart said:
Nói idea bài trên nhá:
Ví dụ với input 2 4 16 3 9
Các thím để ý là có thể tách ra 2 chuỗi dài nhất 2 4 16 và 3 9

Vấn đề là thứ tự lộn xộn, giả sử a0 = 16.
Vậy mình sẽ đi 2 hướng:

  • hướng 1 bình phương 16, rồi cứ bình phương tới khi ko tồn tại trong mảng. Nếu tồn tại thì tăng count lên 1.
  • hướng 2: đi lui, lấy sqrt 16 = 4, check 4 có trong mảng ko.
  • Cứ mỗi lần check thì tăng count lên 1 đơn vị, lúc nào quay lại loôp thì reset count, trc đó so sánh với max để lưu lại giá trị lớn nhất
Nhưng sẽ có tình huống sqrt của nó là lẻ, ví dụ căn 2 của 8 chẳng hạn.
Cho nên cần check thêm 1 lượt bằng cách lấy bình phương lại xem có = 8 hay 16 ko.

Làm như vậy thì chỉ tốn O(n) thôi. Ko cần sort, có thể check tồn tại hay ko = cách dùng array hay map đều dc. Sau khi check 1 số xong thì remove ra khỏi map là dc.

Ngoài ra cần handle tình huống ^2 lên bị tràn số nên cần check tới 10^3 là dc

Có bạn kia code đúng hướng r nên mình ko code lại
Click to expand...
TC của sqrt không phải O(1) đâu. T nhớ là O(LogN). Nên cách này không hiệu quả hơn cách sort rồi nhân từ dưới lên đâu.
 
thuyduong2007 said:
TC của sqrt không phải O(1) đâu. T nhớ là O(LogN). Nên cách này không hiệu quả hơn cách sort rồi nhân từ dưới lên đâu.
Click to expand...


logn là khi tự implement theo kiểu binary, còn của std thì nó dùng thuật toán cài đặt sẵn của hardware thím nhé.

https://stackoverflow.com/questions/6884359/c-practical-computational-complexity-of-cmath-sqrt

For newer processors, the cost is less and is almost the same for DIV and for SQRT, e.g. for Sandy Bridge Intel CPU:
 
3/7/2022:
  • 1 câu medium khá quen thuộc
  • đọc cái đề khó hiểu vãi, lúc đầu làm 10 phút sai cái đề
  • Nhìn qua đề dễ dàng nhận thấy chúng ta chỉ cần quan tâm tới khoảng cách giữa 2 số liên tiếp trong mảng -> tưởng tượng 1 mảng chỉ gồm khoảng cách 2 số
  • Khá giống câu Longest incresing sequence, làm tương tự câu LIS thì time là O(N^2)
  • Nhưng time yêu cầu là O(n) nên phải làm cách khác
  • Key ở đây chính là dương âm
  • Ta có thể tạo 2 biến positiveLength là độ dài lớn nhất sequence có kết thúc ở diff(khoảng cách 2 số) dương và nagativeLength là độ dài lớn nhất sequence có kết thúc ở diff âm
  • Như vậy positiveLength và negativeLength trong mọi vị trí chỉ có thể hơn nhau 1 đơn vị
  • Duyệt từ đầu mảng đến cuối mảng
  • Ta có công thức QHĐ:
  • nếu diff > 0, positiveLength = max(2, negativeLength + 1) (2 là độ dài đầu tiên)
  • nếu diff < 0, negativeLength = max(2, positiveLength + 1);
  • Chú ý Trường hợp diff == 0 thì ko tính trong sequence
  • Time: O(n)
  • Space: O(1)
  • Sau khi làm lại thì mất 15 phút do cái bug code cũ :beat_brick::beat_brick:
Code: https://leetcode.com/submissions/detail/737002030/
Code sau khi optimize: https://leetcode.com/submissions/detail/737005318/
 
Bài sáng nay ban đầu tôi cũng nghĩ tương tự Longest Increasing Subsequence với 1 chút ít thay đổi, nhưng code hoài méo được nên suy nghĩ đơn giản lại, ai dè thấy ăn ngay cái O(n) luôn :beauty:

  • Duyệt hết cái mảng lần đầu để tính diff giữa các item trong mảng, và lưu các diff này vào 1 mảng tạm.
  • Lúc đầu chưa chú ý nên diff == 0 vẫn lưu vào mảng tạm luôn => xử lý hơi khó khăn. Về sau tôi thấy mình không cần quan tâm khi diff == 0 nên bỏ ra khỏi mảng tạm => xử lý đơn giản hơn.
  • Duyệt qua cái mảng tạm kia, thấy 2 items liền kề mà trái dấu nhau thì tăng kết quả thêm 1.
  • Time: O(n), Space: O(n). Nếu không dùng mảng tạm mà sửa trực tiếp mảng input thì cũng được O(1)

C#: 
public class Solution {
    public int WiggleMaxLength(int[] nums) {
        List<int> diff = new ();
        for (var i = 1; i < nums.Length; i++)
        {
            if (nums[i] != nums[i-1])
                diff.Add(nums[i] - nums[i-1]);
        }
       
        if (diff.Count == 0) // all items in nums are equal
            return 1;
       
        //Console.WriteLine(string.Join(',', diff));

        int len = 2; // nums contains a wiggle sequence of at least 2 items
        for (var i = 1; i < diff.Count; i++)
        {
            if (diff[i]*diff[i-1] < 0)
                len++;
        }
       
        return len;
    }
}
 
:love:
Do chỉ cần quan tâm tới phần tử liền kề trước nó thôi nên em chọn stack
Cần thỏa mãn 1 trong 2 điều kiện để push phần tử vào stack (i.e thỏa mãn điều kiện bài toán):
  • Stack rỗng (ban đầu)
  • Phần tử top của stack trái dấu với hiệu số 2 phần tử liên tiếp được xét tới

Kết quả cuối cùng là size của stack + 1

Java: 
class Solution {
    public int wiggleMaxLength(int[] nums) {
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < nums.length - 1; ++i)
        {
            int diff = nums[i + 1] - nums[i];
            if (diff == 0)
                continue;
            if (st.empty() || st.peek() * diff < 0)
                st.push(diff);
        }
        return st.size() + 1;
    }
}
 
Violet_7 said:
3/7/2022:
  • 1 câu medium khá quen thuộc
  • đọc cái đề khó hiểu vãi, lúc đầu làm 10 phút sai cái đề
  • Nhìn qua đề dễ dàng nhận thấy chúng ta chỉ cần quan tâm tới khoảng cách giữa 2 số liên tiếp trong mảng -> tưởng tượng 1 mảng chỉ gồm khoảng cách 2 số
  • Khá giống câu Longest incresing sequence, làm tương tự câu LIS thì time là O(N^2)
  • Nhưng time yêu cầu là O(n) nên phải làm cách khác
  • Key ở đây chính là dương âm
  • Ta có thể tạo 2 biến positiveLength là độ dài lớn nhất sequence có kết thúc ở diff(khoảng cách 2 số) dương và nagativeLength là độ dài lớn nhất sequence có kết thúc ở diff âm
  • Như vậy positiveLength và negativeLength trong mọi vị trí chỉ có thể hơn nhau 1 đơn vị
  • Duyệt từ đầu mảng đến cuối mảng
  • Ta có công thức QHĐ:
  • nếu diff > 0, positiveLength = max(2, negativeLength + 1) (2 là độ dài đầu tiên)
  • nếu diff < 0, negativeLength = max(2, positiveLength + 1);
  • Chú ý Trường hợp diff == 0 thì ko tính trong sequence
  • Time: O(n)
  • Space: O(1)
  • Sau khi làm lại thì mất 15 phút do cái bug code cũ :beat_brick::beat_brick:
Code: https://leetcode.com/submissions/detail/737002030/
Code sau khi optimize: https://leetcode.com/submissions/detail/737005318/
Click to expand...

Bác có thể giải thích rõ hơn tại sao chỉ cần so sánh diff a và a[i-1] là đủ không? Lỡ ra a[i-1] không thuộc vào 2 subsequence dài nhất thì sao?

Sent from HUAWEI DBY-W09 using vozFApp
 
bribnt said:
Bác có thể giải thích rõ hơn tại sao chỉ cần so sánh diff a và a[i-1] là đủ không? Lỡ ra a[i-1] không thuộc vào 2 subsequence dài nhất thì sao?

Sent from HUAWEI DBY-W09 using vozFApp
Click to expand...
a[i .] ko thuộc sequence khi a[i.] == a[i - 1] hoặc a[i.] - a[i - 1] cùng dấu với a[i + 1] - a[i.]. Lúc này lấy a[i.] hay a[i + 1] đều đc, cách tui sẽ lấy a[i + 1]. Còn chỉ cần diff thì cái đề bài nó nói rõ mà bác.
 
Violet_7 said:
a[i .] ko thuộc sequence khi a[i.] == a[i - 1] hoặc a[i.] - a[i - 1] cùng dấu với a[i + 1] - a[i.]. Lúc này lấy a[i.] hay a[i + 1] đều đc, cách tui sẽ lấy a[i + 1]. Còn chỉ cần diff thì cái đề bài nó nói rõ mà bác.
Click to expand...

Ý là tại sao lại so sánh a[i.] với a[i-1] để quyết định nó sẽ thuộc vào subsequence positive hay negative. Mà không phải là so sánh a[i.] với số khác.

Vẫn chưa có gì chứng minh rằng a[i-1] thuộc một subsequence nào đó, thì việc so sánh với nó có ảnh hưởng gì?

Sent from Xiaomi M2007J20CG using vozFApp
 
 
Violet_7 said:
3/7/2022:
  • 1 câu medium khá quen thuộc
  • đọc cái đề khó hiểu vãi, lúc đầu làm 10 phút sai cái đề
  • Nhìn qua đề dễ dàng nhận thấy chúng ta chỉ cần quan tâm tới khoảng cách giữa 2 số liên tiếp trong mảng -> tưởng tượng 1 mảng chỉ gồm khoảng cách 2 số
  • Khá giống câu Longest incresing sequence, làm tương tự câu LIS thì time là O(N^2)
  • Nhưng time yêu cầu là O(n) nên phải làm cách khác
  • Key ở đây chính là dương âm
  • Ta có thể tạo 2 biến positiveLength là độ dài lớn nhất sequence có kết thúc ở diff(khoảng cách 2 số) dương và nagativeLength là độ dài lớn nhất sequence có kết thúc ở diff âm
  • Như vậy positiveLength và negativeLength trong mọi vị trí chỉ có thể hơn nhau 1 đơn vị
  • Duyệt từ đầu mảng đến cuối mảng
  • Ta có công thức QHĐ:
  • nếu diff > 0, positiveLength = max(2, negativeLength + 1) (2 là độ dài đầu tiên)
  • nếu diff < 0, negativeLength = max(2, positiveLength + 1);
  • Chú ý Trường hợp diff == 0 thì ko tính trong sequence
  • Time: O(n)
  • Space: O(1)
  • Sau khi làm lại thì mất 15 phút do cái bug code cũ :beat_brick::beat_brick:
Code: https://leetcode.com/submissions/detail/737002030/
Code sau khi optimize: https://leetcode.com/submissions/detail/737005318/
Click to expand...
https://leetcode.com/submissions/detail/737388734/
bai nay suy nghi ra cach roi ma lam mat may tieng @@ bun
 
bribnt said:
Ý là tại sao lại so sánh a[i.] với a[i-1] để quyết định nó sẽ thuộc vào subsequence positive hay negative. Mà không phải là so sánh a[i.] với số khác.

Vẫn chưa có gì chứng minh rằng a[i-1] thuộc một subsequence nào đó, thì việc so sánh với nó có ảnh hưởng gì?

Sent from Xiaomi M2007J20CG using vozFApp
Click to expand...
gọi
dp_up[i.] là chiều dài lớn nhất của subsequence positive đạt được với kết thúc là a[i.]

dp_down[i.] là chiều dài lớn nhất của subsequence negative đạt được với kết thúc là a[i.]

với cách gọi này thì dp_up[i.] cũng là chiều dài lớn nhất của subsequence positive đạt được lấy từ dãy có chiều dài đến vị trí i (không cần kết thúc tại a[i.] ).

Chứng minh bằng phản chứng: ví dụ có subs positive có m số kết thúc tại j < i mà dãy subs positive kết thúc ở a[i.] được có n số với n < m.

m số là: x1, x2, ....x(m-1), xm
n số là: y1,y2,...y(n-1),yn = a[i.]
nếu yn > x(m-1) ta có dãy m số kết thúc tại x1, x2, ....x(m-1), yn = a[i.]
nếu yn<= x(m-1) suy ra y(n-1) < yn <= x(m-1) < x(m-2) ta có dãy: x1, x2, ....x(m-2), y(n-1), yn = a[i.]

2 dãy trên đều có số lượng là m > n (vô lí)
 
Last edited:

Similar threads

_Gia_Cat_Luong_
thảo luận [IELTS] Mỗi ngày 20p Reading / Listening
2 3
Replies
51
Views
1K
_Gia_Cat_Luong_
_Gia_Cat_Luong_
aquarius8
Phát card mỗi ngày
2 3
Replies
50
Views
3K
aquarius8
aquarius8
Masterchiefs
Toàn cầu thiệt hại 1.000 tỉ USD mỗi năm do người lao động trầm cảm
Replies
0
Views
78
Masterchiefs
Masterchiefs
RPG29
Cửa hàng phố lớn cài then, livestream bán hàng giả chốt nghìn đơn mỗi ngày
Replies
1
Views
156
waitforme
waitforme
Song Nguyen
thảo luận Game Triều Đại Tây Sơn
2 3
Replies
45
Views
2K
Song Nguyen
Song Nguyen

Share this page

Back
Top