Lập Trình Viên Số Khổ
Senior Member
O(n) 10^4 làm gì k pass fenCái code này mà vẫn pass đc hả?
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
thuyduong2007
Member
T thấy nó sai logic mà. Thử chạy testcase này xem: [191,223]
Lập Trình Viên Số Khổ
Senior Member
Python:
class Solution:
def validUtf8(self, data: List[int]) -> bool:
arr = 0
for num in data:
if 0 <= num <= 127:
continue
elif num <= 191:
arr -= 1
else:
if arr != 0:
return False
elif num <= 223:
arr += 1
elif num <= 239:
arr += 2
elif num <= 247:
arr += 3
elif num > 247:
arr += inf
return arr == 0Code này thì sao fen
Sửa lần cuối:
Lập Trình Viên Số Khổ
Senior Member
à vẫn sai
)))
Cong_Go_De_Su
Senior Member
Đề cho sẵn cái table valid pattern của utf8 từ 1-4 bytes rồi, chỉ việc implement code check 4 cái pattern đó là xong . Chắc nhiều thanh niên viết code check n-bytes thật nên tạch edge cases, xong đọc solution rồi cho dislikestrict quá thì lại méo ai làm cho coi
mà bài hôm nay lại có solution, thấy giải đáp nhanh gọn, dễ hiểu
P/s: à tác giả solution cũng không quên nói: "The problem isn't that hard if you read the problem carefully"hay lắm, cho 1 dislike này
Aristides
Senior Member
Kân team v3
Senior Member
thấy đáp án toàn xài phép chia màNói chứ mấy vấn đề bit manipulate là một, raw pointer là hai, cstring là ba cái thứ khốn nạn nhất trong đời tôinhắc về bit manipulate cũng có bài này trên leetcode, medium, 11k dislike về việc implement toán tử phép chia: https://leetcode.com/problems/divide-two-integers/
https://leetcode.com/submissions/detail/798923067/ ac này có gì đâu
Aristides
Senior Member
thấy đáp án toàn xài phép chia màchắc ko có cách kiểm soát nên mới bị dis like
https://leetcode.com/submissions/detail/798923067/ ac này có gì đâu
Đề nó đã nói rõ: "divide two integers without using multiplication, division, and mod operator." mà
Cong_Go_De_Su
Senior Member
Làm dev application mà xài bit manipulate lúc review pull request chả bị chửi cho vuốt mặt ko kịp vì khả năng cao thằng tới sau ko hiểu thằng trước viết cái gì cả, và thằng viết code đó tuần sau nó cũng quên mất nó viết cái gì luônNói chứ mấy vấn đề bit manipulate là một, raw pointer là hai, cstring là ba cái thứ khốn nạn nhất trong đời tôinhắc về bit manipulate cũng có bài này trên leetcode, medium, 11k dislike về việc implement toán tử phép chia: https://leetcode.com/problems/divide-two-integers/
Kân team v3
Senior Member
làm dev mà ko hiểu bit manip thì khác gì ko phải dân dev
ta có q = n / d thì n = q * d, viết q thành dạng sum_i=0..31{c_i * 2^i}, ví dụ q = 11 thì viết thành 2^0 + 2^2 + 2^3 thì n = (2^0 + 2^2 + 2^3) * d thì chỉ cần tính d * 2^i vào cái mảng 32 phần tử rồi lấy n trừ là xong
cách cùi bắp này độ phức tạp là O(b^2) với b ở đây = 32 bit, b cố định thì có thể cho đó là O(1)
bài cũng hay, tương đương với viết quotient thành bit mà tại lũ LC ko thấy được cái hay thoynào, ai lại chơi thế
Đề nó đã nói rõ: "divide two integers without using multiplication, division, and mod operator." mà
ta có q = n / d thì n = q * d, viết q thành dạng sum_i=0..31{c_i * 2^i}, ví dụ q = 11 thì viết thành 2^0 + 2^2 + 2^3 thì n = (2^0 + 2^2 + 2^3) * d thì chỉ cần tính d * 2^i vào cái mảng 32 phần tử rồi lấy n trừ là xong
cách cùi bắp này độ phức tạp là O(b^2) với b ở đây = 32 bit, b cố định thì có thể cho đó là O(1)
Aristides
Senior Member
làm dev mà ko hiểu bit manip thì khác gì ko phải dân dev
bài cũng hay, tương đương với viết quotient thành bit mà tại lũ LC ko thấy được cái hay thoy
ta có q = n / d thì n = q * d, viết q thành dạng sum_i=0..31{c_i * 2^i}, ví dụ q = 11 thì viết thành 2^0 + 2^2 + 2^3 thì n = (2^0 + 2^2 + 2^3) * d thì chỉ cần tính d * 2^i vào cái mảng 32 phần tử rồi lấy n trừ là xong
cách cùi bắp này độ phức tạp là O(b^2) với b ở đây = 32 bit, b cố định thì có thể cho đó là O(1)
Kân team v3
Senior Member
nhân đâu, * 2^i xài left bit shiftvẫn phải xài multiplication
Aristides
Senior Member
Kân team v3
Senior Member
đang implement bug cái -2^31 tùm lumừ nhỉ
Thế accepted chưa bác?
thoy ý tưởng đúng được ròi
ế ac ròi này https://leetcode.com/submissions/detail/798953305/
ko có check >= mà check == ở dòng
if (q >= 2147483648ULL thằng UBSan nó gào thét ko cho qua
int q phải là uint64_t q luôn cho đúng vì 0 + 2^31 nó overflow thành -2^31 là UB, nhưng toy sửa lại submit nãy giờ ko ra 0ms
edit: code trên vẫn đúng vì https://en.cppreference.com/w/cpp/language/implicit_conversion#Integral_conversions 0 + 2^31 thì vì qi = 2^31 là uint64_t sẵn nên vế phải nó được promote thành uint64_t, được implicit cast về int32_t thì là implement defined chứ ko phải UB, vậy declare
int q vẫn đúng 
thoy thế lày được rồi: https://leetcode.com/submissions/detail/798957531/
vd q=11 thì qi = 2^0, 2^2, 2^3
db[i\] = d * 2^0, d * 2^2, d * 2^3
quá chình dẫn tới ý tưởng giải bài lày là toy đã biết phép chia thực chất chỉ là phép trừ nhiều lần thoy, n / d nghĩa là n - d - d - d - ... - d tới khi nào ko trừ được nữa, trừ bao nhiêu lần d thì đó là đáp án q. Tới đây toy viết vòng for thì bị TLE
<<= thì hiểu ngay là trừ gộp 2^i như cách tính nhanh a^b vậy. Từ đó mới thấy thực chất bài này cũng tương tự với bài output số q dưới dạng tổng 2^i thoy
Sửa lần cuối:
220914 - 1457. Pseudo-Palindromic Paths in a Binary Tree
Lại một bài bit manipulation nữa.
Để ý thấy:
==> Có thể lưu mảng counter chỉ bằng 9 bit, trong đó bit 0 = chẵn, 1 = lẻ. Dùng phép xor ^ thay cho phép cộng.
1 dòng
Lại một bài bit manipulation nữa.
Để ý thấy:
- Để check palindrome thì chỉ cần quan tâm đến chẵn / lẽ, không cần số lượng cụ thể
- Giá trị mỗi node chỉ là từ 1 -> 9
==> Có thể lưu mảng counter chỉ bằng 9 bit, trong đó bit 0 = chẵn, 1 = lẻ. Dùng phép xor ^ thay cho phép cộng.
C++:
class Solution {
public:
int pseudoPalindromicPaths (TreeNode* root, int cnt = 0) {
if (!root) return 0;
cnt ^= 1 << root->val;
if (!root->left & !root->right)
return __builtin_popcount(cnt) <= 1;
return pseudoPalindromicPaths(root->left, cnt) + pseudoPalindromicPaths(root->right, cnt);
}
};1 dòng
C++:
class Solution {
public:
int pseudoPalindromicPaths (TreeNode* root, int cnt = 0) {
return root ? cnt ^= 1 << root->val, pseudoPalindromicPaths(root->left, cnt) + pseudoPalindromicPaths(root->right, cnt) + (root->left == root->right & !(cnt & (cnt - 1))) : 0;
}
};
Sửa lần cuối:
Lập Trình Viên Số Khổ
Senior Member
Python:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def pseudoPalindromicPaths (self, root: Optional[TreeNode]) -> int:
d = defaultdict(int)
res = []
def check(d):
count_odd = 0
for key in d:
if d[key] % 2:
count_odd += 1
return count_odd < 2
def dfs(node):
d[node.val] += 1
if node.left:
dfs(node.left)
if node.right:
dfs(node.right)
if not node.left and not node.right:
if check(d):
res.append(d)
d[node.val] -= 1
dfs(root)
return len(res)Kân team v3
Senior Member
thặc kinh dị toy chỉ nghĩ ra mảng int tần suất 10 phần tử mà ko nghĩ ra chỉ cần mảng bool / 1 cái int là đủ
Cong_Go_De_Su
Senior Member
Sắp tới chuỗi ngày ôm cây như tháng trước rồi
Mã:
defmodule Solution do
def pseudo_palindromic_paths(root) do
palindrome_check(root, %{})
end
defp palindrome_check(%TreeNode{val: v, left: nil, right: nil}, map),
do: palindrome_check(Map.update(map, v, 1, &(&1 + 1)))
defp palindrome_check(%TreeNode{val: v, left: l, right: nil}, map),
do: palindrome_check(l, Map.update(map, v, 1, &(&1 + 1)))
defp palindrome_check(%TreeNode{val: v, left: nil, right: r}, map),
do: palindrome_check(r, Map.update(map, v, 1, &(&1 + 1)))
defp palindrome_check(%TreeNode{val: v, left: l, right: r}, map) do
palindrome_check(l, Map.update(map, v, 1, &(&1 + 1))) +
palindrome_check(r, Map.update(map, v, 1, &(&1 + 1)))
end
defp palindrome_check(map) do
map
|> Enum.reduce_while(_odd_count = 0, fn
{_, count}, 0 when rem(count, 2) == 1 -> {:cont, 1}
{_, count}, _ when rem(count, 2) == 1 -> {:halt, false}
_, odd_count -> {:cont, odd_count}
end)
|> (&if(&1 == false, do: 0, else: 1)).()
end
end
- Trạng thái
Chủ đề tương tự
