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

Aristides · 3/9/22

Blue Amethyst đã nói:
Nếu bác muốn nhanh hơn thì như này: đổi Stack thành ArrayDeque và thay vì dùng stream + mapToInt thì bác tạo array rồi tự map qua luôn Vì Stack trong Java không nhanh bằng Array Deque đâu

P/s: em không rõ hàm numLength bác viết gì trong đó, nhưng nhanh gọn lẹ thì cứ lấy log(10) + 1 thôi

xài kiểu primitive array là viết lại arraylist cho kiểu int nguyên thủy như lão cân team làm đấy. Cách đấy khẩm dô quá, mặc dù nó hiệu quả thật (time complexity beats 96%) nên thôi bỏ

ArrayDeque với Stack với cái bài với số lượng phần tử ít thế này thì perfomance chả cải thiện gì mấy. Hiệu năng của cái bài này chủ yếu vẫn là do cái generics của cả 3 thằng Stack, ArrayList, ArrayDeque chỉ cast và instantiate wrapper class trên heap, phải chi viết lại class ArrayList xài kiểu int nguyên thủy trên stack như trên của cha cân team thì mới thấy khác bọt

Còn numsLength thì cứ loop hoặc cast qua string rồi dùng size chứ log base 10 tôi nhớ là chỉ chính xác với kiểu dữ liệu long hoặc float, int thì sẽ bị sai kết quả và thao tác mấy số kiểu floating point thì tùy compiler nó ra kết quả khác nữa

java chưa thử chứ C++ gặp hoài, nói chung nhức đầu

Blue Amethyst · 3/9/22

Aristides đã nói:
xài kiểu primitive array là viết lại arraylist cho kiểu int nguyên thủy như lão cân team làm đấy. Cách đấy khẩm dô quá, mặc dù nó hiệu quả thật (time complexity beats 96%) nên thôi bỏ

ArrayDeque với Stack với cái bài với số lượng phần tử ít thế này thì perfomance chả cải thiện gì mấy. Hiệu năng của cái bài này chủ yếu vẫn là do cái generics của cả 3 thằng Stack, ArrayList, ArrayDeque chỉ cast và instantiate wrapper class trên heap, phải chi viết lại class ArrayList xài kiểu int nguyên thủy trên stack như trên của cha cân team thì mới thấy khác bọt

Còn numsLength thì cứ loop hoặc cast qua string rồi dùng size chứ log tôi nhớ là chỉ chính xác với kiểu dữ liệu long hoặc float, int thì sẽ bị sai kết quả và thao tác mấy số kiểu floating point thì tùy compiler nó ra kết quả khác nữa

java chưa thử chứ C++ gặp hoài, nói chung nhức đầu

Bác cứ thử đi, chứ em đổi trên code bác thì thấy runtime nhanh hơn đó :byebye:

Stack so với ArrayDeque lúc nào chả chậm hơn, còn cái log thì vẫn chạy bình thường không thấy lỗi lầm gì :byebye:

thuyduong2007 · 3/9/22

BFS không cần xài queue, 1 phát ăn ngay,

.
Nay nhậu xỉn quá mà cũng ráng bò lên làm cho xong bài daily challenge với ae,

C++:

class Solution {
public:
    vector<int> numsSameConsecDiff(int n, int k) {
        vector<int> ret = {1,2,3,4,5,6,7,8,9};
        for (int i = 1; i < n; ++i) {
            vector<int> tmp;
            for (auto x : ret) {
                if (x%10 - k >= 0) {
                    tmp.push_back(x*10 - k + x%10);
                }
                if (k != 0 && x%10 + k <= 9) {
                    tmp.push_back(x*10 + k + x%10);
                }
            }
            tmp.swap(ret);
        }
        return ret;
    }
};

Aristides · 3/9/22

Blue Amethyst đã nói:
Bác cứ thử đi, chứ em đổi trên code bác thì thấy runtime nhanh hơn đó Stack so với ArrayDeque lúc nào chả chậm hơn, còn cái log thì vẫn chạy bình thường không thấy lỗi lầm gì

"không lỗi" của anh bạn đây:

Còn đây là xài ArrayDeque theo ý anh bạn:

tôi đã bảo rồi, Stack hay ArrayDeque cỡ này thì performance không khác mấy đâu. Cái quan trọng vẫn là việc Instantiate wrapper class trên heap kìa

Blue Amethyst · 3/9/22

Aristides đã nói:
"không lỗi" của anh bạn đây:

Xem tệp đính kèm 1360097

Còn đây là xài ArrayDeque theo ý anh bạn:

Xem tệp đính kèm 1360101

tôi đã bảo rồi, Stack hay ArrayDeque cỡ này thì performance không khác mấy đâu. Cái quan trọng vẫn là việc Instantiate wrapper class trên heap kìa

https://leetcode.com/submissions/detail/790418995/ :ops:

khác chưa bro :ops:

Aristides · 3/9/22

Blue Amethyst đã nói:
https://leetcode.com/submissions/detail/790418995/ khác chưa bro

Cái trên tôi có map trực tiếp với xài log10 đâu? :ops:

Đấng Tối Cao · 3/9/22

Aristides đã nói:
thì Integer là wrapper class mà. Bản chất nó là 1 object thì allocate trên heap rồi garbage collection đương nhiên chậm hơn kiểu primitive type trên stack rồi

Edit: nghe bảo Java đang có project Valhalla hay cái éo gì ấy tương tự hứa hẹn generics giờ cũng sẽ cast được primitive type, nhưng vẫn đảm bảo backward compatibility lẫn hiệu năng tốt chứ không phải kiểu syntactic sugar

nghe ảo ma vãi lẫn mùi bánh vẽ thoang thoảng đâu đây

Valhalla thì hình như đã có preview, không rõ lắm nhưng không nghĩ là bánh vẽ đâu. Mấy trùm Java nghiên cứu đâu cũng gần 10 năm rồi. Java hậu Valhalla sẽ là một cái gì đó khá là kinh vãi :oh:

Hệ thống kiểu dữ liệu của Java trước Valhalla

Hệ thống kiểu dữ liệu của Java sau Valhalla (có thêm value object và primitive object)

bribnt · 3/9/22

100%, 0ms:

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

Bí quyết là allocate bộ nhớ cho res và tmp ngay từ đầu, vì tối đa cũng chỉ có 9*2^8 phần tử.

Screenshot_20220903_230544_com.brave.browser.jpg

Cong_Go_De_Su · 3/9/22

Đấng Tối Cao đã nói:
Valhalla thì hình như đã có preview, không rõ lắm nhưng không nghĩ là bánh vẽ đâu. Mấy trùm Java nghiên cứu đâu cũng gần 10 năm rồi. Java hậu Valhalla sẽ là một cái gì đó khá là kinh vãi

Nói đơn giản thì giống struct của .net thì phải, ngày xưa phân ra primitive với box. Giờ đẻ ra cái này thế là dân tình có cái để hype

nhonlv · 3/9/22

sau một hồi bí vì cố nghĩ heuristic tìm digit phù hợp thì nhận ra bài này dùng đệ quy ngon ơ :v

Runtime: 143 ms, faster than 38.71% of C# online submissions for Numbers With Same Consecutive Differences.
Memory Usage: 35.4 MB, less than 70.97% of C# online submissions for Numbers With Same Consecutive Differences.

Aristides · 4/9/22

Thật ra theo như mấy lão trên StackOverFlow thì trước đây Java xém nữa có generics dành cho cả primitive type

Tuy nhiên, do cha đẻ của Java là James Gosling cùng đồng bọn do quá ham tiền.... à nhầm, do quá nôn nóng việc phát hành Java 1.0 trước thị trường web còn mới mẻ và béo bở hồi thập niên 90

thế nên Gosling và đồng bọn đã quyết định không add Generics vào. Và thế là Java 1.0 ra đời mà không có generics

Mãi sau này có thời gian phát triển thêm thì Java mới có Generics. Tuy nhiên, lần này Generics của Java phải có backward compatibility cho cả ver Java trước vốn không có generics, và bùm,

generics hiện nay chỉ support objects
https://stackoverflow.com/a/2721602

Đấng Tối Cao · 4/9/22

Aristides đã nói:
Thật ra theo như mấy lão trên StackOverFlow thì trước đây Java xém nữa có generics dành cho cả primitive type

Tuy nhiên, do cha đẻ của Java là James Gosling cùng đồng bọn do quá ham tiền.... à nhầm, do quá nôn nóng việc phát hành Java 1.0 trước thị trường web còn mới mẻ và béo bở hồi thập niên 90

thế nên Gosling và đồng bọn đã quyết định không add Generics vào. Và thế là Java 1.0 ra đời mà không có generics

Mãi sau này có thời gian phát triển thêm thì Java mới có Generics. Tuy nhiên, lần này Generics của Java phải có backward compatibility cho cả ver Java trước vốn không có generics, và bùm,

generics hiện nay chỉ support objects
https://stackoverflow.com/a/2721602

Nghe câu chuyện như bên Go, mà Go thì đâu có chịu áp lực phát hành đâu mà mãi đến giờ mới có generic :confused:

Nhưng cái hay là giờ Java vẫn fix lại được bằng Valhalla mới ảo :censored:

Vi diệu

Violet_7 · 4/9/22

4/9/2022:

Câu hard hôm nay có vẻ hơi dễ nhể.
.
- Ý tưởng khá straightforward, dfs để đánh tọa độ các node.
- nếu node cha có tọa độ (row, col) thì tọa độ node con trái (row + 1, col - 1) và node con phải (row + 1, col + 1)
- vì tọa độ cột có thể âm nên dùng cái hash map để lưu các cột
- gọi hash map là map trong đó map[col] là 1 array lưu các cặp, 1 cặp là {row của node đó, value của node đó), các node đó phải thuộc cột col
- trong c++: unordered_map<int, vector<pair<int, int>>> map;
- dfs rồi push từng node vào map
- tìm cái cột "leftmost" nhất rồi bruteforce thôi,với mỗi cái column thì sort xong push vào cái result
- ra đáp án
- time: O(nlogn)
- space: O(n)
Code: https://leetcode.com/submissions/detail/790854676/

Aristides · 4/9/22

Violet_7 đã nói:
4/9/2022:

Câu hard hôm nay có vẻ hơi dễ nhể

ý tưởng khá straightforward, dfs để đánh tọa độ các node

nếu node cha có tọa độ (row, col) thì tọa độ node con trái (row + 1, col - 1) và node con phải (row + 1, col + 1)

vì tọa độ cột có thể âm nên dùng cái hash map để lưu các cột

gọi hash map là map trong đó map[col] là 1 array lưu các cặp, 1 cặp là {row của node đó, value của node đó), các node đó phải thuộc cột col

trong c++: unordered_map<int, vector<pair<int, int>>> map;

dfs rồi push từng node vào map

tìm cái cột "leftmost" nhất rồi bruteforce thôi,với mỗi cái column thì sort xong push vào cái result

ra đáp án

time: O(nlogn)

space: O(n)

Code: https://leetcode.com/submissions/detail/790854676/

vui lòng nhét hướng dẫn vào spoil

Kân team v3 · 4/9/22

Violet_7 đã nói:
4/9/2022:

Câu hard hôm nay có vẻ hơi dễ nhể

ý tưởng khá straightforward, dfs để đánh tọa độ các node

nếu node cha có tọa độ (row, col) thì tọa độ node con trái (row + 1, col - 1) và node con phải (row + 1, col + 1)

vì tọa độ cột có thể âm nên dùng cái hash map để lưu các cột

gọi hash map là map trong đó map[col] là 1 array lưu các cặp, 1 cặp là {row của node đó, value của node đó), các node đó phải thuộc cột col

trong c++: unordered_map<int, vector<pair<int, int>>> map;

dfs rồi push từng node vào map

tìm cái cột "leftmost" nhất rồi bruteforce thôi,với mỗi cái column thì sort xong push vào cái result

ra đáp án

time: O(nlogn)

space: O(n)

Code: https://leetcode.com/submissions/detail/790854676/

vì đề chỉ cho có 1k node nên có thể xài mảng 2001 phần tử thay cho cái unordered_map

hình như mỗi cột chỉ có 2logn ~ O(logn) phần tử? Nếu thế thì sort mỗi cột chỉ mất O(loglogn), xài mảng 2001 phần tử thêm vào mỗi cột mất O(1) thì time chỉ có O(n loglogn)

https://leetcode.com/submissions/detail/790870881/ submit 4 lần 1 lần 3ms, 2 lần 4ms, 1 lần 11ms

ủa chết mọe mảng thường mà chứa vector thì vector đó có được khởi tạo ko

edit có gà thặc lâu ròi mà ko để ý

Violet_7 · 4/9/22

Aristides đã nói:
vui lòng nhét hướng dẫn vào spoil

ok đã nhét hướng dẫn vào spoil :whistle:

Violet_7 · 4/9/22

Kân team v3 đã nói:
vì đề chỉ cho có 1k node nên có thể xài mảng 2001 phần tử thay cho cái unordered_map

hình như mỗi cột chỉ có 2logn ~ O(logn) phần tử? Nếu thế thì sort mỗi cột chỉ mất O(loglogn), xài mảng 2001 phần tử thêm vào mỗi cột mất O(1) thì time chỉ có O(n loglogn)

https://leetcode.com/submissions/detail/790870881/ submit 4 lần 1 lần 3ms, 2 lần 4ms, 1 lần 11ms

ủa chết mọe mảng thường mà chứa vector thì vector đó có được khởi tạo ko

edit có gà thặc lâu ròi mà ko để ý

chắc xài đc mảng 2000 phần tử sẽ nhanh hơn
vẫn là O(nlogn) nha thím vd th này chẳng hạn
theo em chắc vẫn khởi tạo đc thôi

Kân team v3 · 4/9/22

Violet_7 đã nói:
chắc xài đc mảng 2000 phần tử sẽ nhanh hơn

vẫn là O(nlogn) nha thím vd th này chẳng hạnXem tệp đính kèm 1360543

theo em chắc vẫn khởi tạo đc thôi

ờm vẫn là O(n) phần tử mỗi cột

nick junior còi ko like được

Cong_Go_De_Su · 4/9/22

Hard mà làm ngắn hơn mấy bài med

Mã:

defmodule Solution do
  @spec vertical_traversal(nil | TreeNode.t()) :: list
  def vertical_traversal(root) do
    vertical_traversal(%{}, root, 0, 0)
    |> Enum.sort()
    |> Enum.map(fn {_, v} -> v |> Enum.sort() |> Enum.map(fn {_, v} -> v end) end)
  end

  defp vertical_traversal(map, node, row, col) do
    case node do
      nil ->
        map

      %TreeNode{val: v, left: l, right: r} ->
        Map.update(map, col, [{row, v}], fn elems -> [{row, v} | elems] end)
        |> vertical_traversal(l, row + 1, col - 1)
        |> vertical_traversal(r, row + 1, col + 1)
    end
  end
end

thuyduong2007 · 4/9/22

Sáng nay có ai làm contest k? nay oải quá không tham gia được. Chỉ làm mỗi daily challenge.
Ý tưởng là dùng dfs để tính ra được range min, max của vertical.
Rồi Traversal thêm lần nữa bằng bfs rồi lấy ra kết quả,

C++:

class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        if (root == NULL) return {};
       
        auto [start, end] = getMinMaxV(root, 0);
        vector<vector<int>> ret(end - start + 1);
        unordered_map<int, vector<TreeNode*>> vertical;
        vertical[0].push_back(root);
        while (!vertical.empty()) {
            unordered_map<int, vector<TreeNode*>> tmp;
            for (auto &[v, vec] : vertical) {
                sort(vec.begin(), vec.end(), [](auto a, auto b) {return a->val < b->val;});
                for (auto node : vec) {
                    ret[v-start].push_back(node->val);
                    if (node->left) tmp[v-1].push_back(node->left);
                    if (node->right) tmp[v+1].push_back(node->right);
                }
            }
            tmp.swap(vertical);
        }
        return ret;
    }
   
    pair<int, int> getMinMaxV(TreeNode* root, int v) {
        if (root == NULL) return {0,0};
        auto [l_min, l_max] = getMinMaxV(root->left, v-1);
        auto [r_min, r_max] = getMinMaxV(root->right,v+1);
        return {min(v, min(l_min, r_min)), max(v, max(l_max, r_max))};
    }
};

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

Senior Member

Senior Member

Member

Senior Member

Senior Member

Senior Member

Member

Đã tốn tiền

Senior Member

Junior Member

Senior Member

Member

Member

Senior Member

Senior Member

Member

Member

Senior Member

Senior Member

Member

Chủ đề tương tự

Thống kê chủ đề

Chia sẻ trang này