Violet_7
Member
đúng r, mình dùng bitmask cho nó tiện luôn
thảo luận Leetcode mỗi ngày
- Người tạo chủ đề _Gia_Cat_Luong_
- Ngày bắt đầu
- Trạng thái
Lập Trình Viên Số Khổ
Senior Member
Sau nhiều lần submit để tăng %
)cơ mà phải dùng 2 cái defaultdict hơi tù, ai mn improve như nào vậy
Lập Trình Viên Số Khổ
Senior Member
https://leetcode.com/problems/maximum-rows-covered-by-columns/
Code theo C++ của 1 đứa thì code C++ của nó 100%
còn code python của mình <50%, sao python code theo C++ mà lại chậm vậy trời
https://leetcode.com/submissions/detail/791159601/
def next_popcount(n):
c = (n & -n)
r = n + c
return (((r ^ n) >> 2) // c) | r
ai biết tại sao 3 dòng này lại có chuyển đến cái mask tiếp theo ko vậy
à đây rùi https://www.slideshare.net/gkumar007/bits-next-higher-presentation
Sửa lần cuối:
kyo_pyro
Senior Member
Đang nói về C++ mà bro, bên C++ mặc định dùng deque làm container.
Còn java thì mấy cái kia là interface thôi, implement thế nào nó không nói rõ, chắc vẫn dùng deque thôi chứ dùng vector chậm vãi ra
Lập Trình Viên Số Khổ
Senior Member
- ưu tiên vị trí node trên cao trước
- nếu cùng hàng (level) thì xếp theo giá trị từ bé đến lớn
kyo_pyro
Senior Member
Không đọc kĩ đề, tự gạch
Aristides
Senior Member
stack bên java kế thừa từ class vector, mà vector chỉ là bản synchronized của ArrayList nên chậm hơn arraylist lẫn arraydeque, bù lại thì được thread safe
ArrayDeque thì chắc implement kiểu ring buffer, mỗi tội ArrayDeque thì không synchronized
kyo_pyro
Senior Member
Thì lúc construct object anh new cái gì thì cái underlying structure của nó là cái đó đó, chứ đều là interface làm sao so sánh tốc độ đượcinterface bên java chỉ có declare method chứ không có implement, không hiểu chỗ này của anh lắm
stack bên java kế thừa từ class vector, mà vector chỉ là bản synchronized của ArrayList nên chậm hơn arraylist lẫn arraydeque, bù lại thì được thread safe
ArrayDeque thì chắc implement kiểu ring buffer, mỗi tội ArrayDeque thì không synchronized
Aristides
Senior Member
Với cả, Stack synchronized thì chắc chắn chậm hơn ArrayDeque không sync rồi
kyo_pyro
Senior Member
Tôi chỉ biết cơ bản là ngôn ngữ nào nó cũng cho phép mình customize cái container cho stack để phù hợp với nhu cầu còn detail bên java như nào tôi ko nắmthì anh Stack là Linear array, còn arrayDeque cũng là array nhưng là array dạng vòng "Ring Buffer"
Với cả, Stack synchronized thì chắc chắn chậm hơn ArrayDeque không sync rồi
Lập Trình Viên Số Khổ
Senior Member
dangson
Đã tốn tiền
Bài nay chưa nghĩ cách nào 1 dòng được. T.T
Python:
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
level = [root] if root else []
while level:
yield (node.val for node in level)
level = list(chain.from_iterable(node.children for node in level))
return
Sửa lần cuối:
Cong_Go_De_Su
Senior Member
Dạo này toàn mấy bài tựa tựa nhau ko vậy 
Mã:
import scala.util.chaining._
import scala.language.implicitConversions
object Solution {
def levelOrder(root: Node): List[List[Int]] = {
def travel(node: Node, level: Int = 0, result: Map[Int, List[Int]] = Map()): Map[Int, List[Int]] = {
if (node == null) {
result
} else {
result.updatedWith(level) {
case Some(l) => Some(node.value :: l)
case _ => Some(node.value :: Nil)
}.pipe {
res => node.children.foldRight(res) {
(c, r) => travel(c, level + 1, r)
}
}
}
}
travel(root)
.toList
.sortBy(_._1)
.map(_._2)
}
}
Sửa lần cuối:
MH0602
Member
Dùng BFS cơ bản thôi
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> result;
if (root == nullptr) return result;
queue<Node*> q;
q.push(root);
int size;
Node* node;
while (!q.empty()) {
size = q.size();
vector<int> layer;
for (int i = 0; i< size; i++) {
node = q.front();
q.pop();
layer.push_back(node->val);
for (Node* n: node->children) {
q.push(n);
}
}
result.emplace_back(layer);
}
return result;
}
vector<vector<int>> result;
if (root == nullptr) return result;
queue<Node*> q;
q.push(root);
int size;
Node* node;
while (!q.empty()) {
size = q.size();
vector<int> layer;
for (int i = 0; i< size; i++) {
node = q.front();
q.pop();
layer.push_back(node->val);
for (Node* n: node->children) {
q.push(n);
}
}
result.emplace_back(layer);
}
return result;
}
Kân team v3
Senior Member
chỗ này
result.emplace_back(layer); cần gọi result.emplace_back(std::move(layer)) nha, nếu ko move thì nó truyền layer vào hàm emplace_back như là 1 lvalue, khi forward tới cho hàm ctor của vector<int> nó sẽ gọi copy ctor chứ ko phải move ctor 
move(layer) thì nó sẽ truyền layer dưới dạng rvalue, forward tới ctor của vector<int> sẽ gọi đúng move ctorhttps://godbolt.org/z/nneszKG43
gọi
v.emplace_back(a) nó gọi copy ctor, v.emplace_back(std::move(b)) mới gọi đúng move ctor nha
giờ viết thử cái tracer này mới thấy nếu ko để
noexcept ở move ctor và move assignment thì std::vector nó gọi copy ctor cho mỗi lần resize 
Sửa lần cuối:
thuyduong2007
Member
Bác kân nói chuẩn rồi.chỗ nàyresult.emplace_back(layer);cần gọiresult.emplace_back(std::move(layer))nha, nếu ko move thì nó truyềnlayervào hàmemplace_backnhư là 1 lvalue, khi forward tới cho hàm ctor củavector<int>nó sẽ gọi copy ctor chứ ko phải move ctortruyềnmove(layer)thì nó sẽ truyềnlayerdưới dạng rvalue, forward tới ctor củavector<int>sẽ gọi đúng move ctor
https://godbolt.org/z/nneszKG43
gọiv.emplace_back(a)nó gọi copy ctor,v.emplace_back(std::move(b))mới gọi đúng move ctor nha
Xem tệp đính kèm 1363320
giờ viết thử cái tracer này mới thấy nếu ko đểnoexceptở move ctor và move assignment thìstd::vectornó gọi copy ctor cho mỗi lần resizetrình dịch gì ngu học vậy
Mà chỗ emplace_back đối với code ntn thì dùng push_back cũng đc, dùng emplace_back ntn thì đâu có tận dụng đc gì đâu. Còn tốt hơn nữa thì tăng size của result lên 1, reserve cho result.back() bằng size của q, sau đó push thẳng vào result.back()
quyquaquyet.tx
Junior Member
rất hay
Kân team v3
Senior Member
tận dụng được chứ, copy cái
layer ví dụ phải gán 100 phần tử thì tốn kém hơn là move 1 pointer với 2 size_t chứ 
new 1 cái mảng mới, đã new 1 lần cho cái layer rồi còn phải new 1 lần nữa cho cái mảng trong result thì hơi phí. Move thẳng cái layer vào result luôn khỏi cần new 1 mảng mới làm gì.mấy tay dev C++ keo kiệt bần tiện lắm
new phát nào thì phải giảm phát đó
MH0602
Member
em cảm ơn bác, hồi đó em xem cha cherno bảo dùng emplace_back để khỏi copy thì em tưởng nó đã bao gồm std::move luôn rồitận dụng được chứ, copy cáilayerví dụ phải gán 100 phần tử thì tốn kém hơn là move 1 pointer với 2 size_t chứmà phần lớn là phảinew1 cái mảng mới, đãnew1 lần cho cáilayerrồi còn phảinew1 lần nữa cho cái mảng trongresultthì hơi phí. Move thẳng cáilayervàoresultluôn khỏi cầnnew1 mảng mới làm gì.
mấy tay dev C++ keo kiệt bần tiện lắmgiảm đượcnewphát nào thì phải giảm phát đó
mà sao lên đến ver 3 rồi thế này
firefox_nxh
Đã tốn tiền
Mới thành thục DFS nên dùng cho đỡ nghĩ, may vẫn qua
Học thêm được dùng set của python để lọc duplicate đỡ tốn time
Học thêm được dùng set của python để lọc duplicate đỡ tốn time
Mã:
class Solution:
def levelOrder(self, root: 'Node') -> List[List[int]]:
if root is None:
return []
visited = [root]
stack = [root]
ans = {0: [root.val]}
while len(stack) > 0:
node = stack[-1]
# print(node, node.val, len(stack), [x.val for x in visited])
if node.children is not None:
remains = set(node.children) - set(visited)
remains = [x for x in node.children if x in remains]
if len(remains) > 0:
for n in remains:
print(n.val)
if n not in visited:
stack.append(n)
visited.append(n)
# print(n.val)
if len(stack) not in ans:
ans[len(stack)] = [n.val]
else:
ans[len(stack)] += [n.val]
break
else:
stack.pop()
else:
stack.pop()
# print('pop')
# time.sleep(0.5)
return list(ans.values())- Trạng thái
Chủ đề tương tự
