thảo luận Leetcode mỗi ngày
- Thread starter _Gia_Cat_Luong_
- Start date
Bài hôm nay đúng là kinh điển.
Hồi xưa cách đây 8-10 năm giải được bải này thôi và lên ý tưởng để chạy nlogn là đã đỗ phỏng vấn Amazon vòng cuối và nhận offer rồi. Rồi phỏng vấn vòng đầu Google chỉ hỏi tìm vị trí xuất hiện đầu tiên của phần tử được cho trong mảng đã sắp xếp.
Giờ khác xưa nhiều quá, bài này chỉ còn là dạng medium dân tình luyện nát ra rồi. Mấy câu này hỏi ngay vòng đầu.
Thế mới biết dev giờ nhiều và thừa quá. Mấy bài leetcode lúc phỏng vấn càng ngày càng khó hơn vì các dev ngày càng nhiều và ngày càng hì hục hơn luyện mấy cái này để qua được vòng phỏng vấn.
Hồi xưa cách đây 8-10 năm giải được bải này thôi và lên ý tưởng để chạy nlogn là đã đỗ phỏng vấn Amazon vòng cuối và nhận offer rồi. Rồi phỏng vấn vòng đầu Google chỉ hỏi tìm vị trí xuất hiện đầu tiên của phần tử được cho trong mảng đã sắp xếp.
Giờ khác xưa nhiều quá, bài này chỉ còn là dạng medium dân tình luyện nát ra rồi. Mấy câu này hỏi ngay vòng đầu.
Thế mới biết dev giờ nhiều và thừa quá. Mấy bài leetcode lúc phỏng vấn càng ngày càng khó hơn vì các dev ngày càng nhiều và ngày càng hì hục hơn luyện mấy cái này để qua được vòng phỏng vấn.
the_gioi_that_dep
Junior Member
Vậy bác có nghĩ rồi một lúc nào đó người ta phải tìm ra một cách đánh giá nào đó thay thế bộ môn leetcode thân yêu này khi interview không bác??
hoangreal
Senior Member
Có. Dân giỏi ở Mỹ đang nhắm Quant. Bọn này thì Leetcode med-hard chỉ là vòng 1 chào hỏi nhau thôi, 5-6 vòng sau toàn Toán với ML / System Design / Network OSVậy bác có nghĩ rồi một lúc nào đó người ta phải tìm ra một cách đánh giá nào đó thay thế bộ môn leetcode thân yêu này khi interview không bác??
ngoctan_95
Senior Member
Thế thì đi cày dạo chứ toptier sao vô nổi
Arik97
Senior Member
Bài hnay 9/8: math + dp
Sort (arr) rồi duyệt từ bé đến lớn. Gọi N[num] là số lượng binary tree của phần tử num trong arr.
Có CT: N[num]=sum(N[a_i]*N[b_i]) , với các cặp a_i*b_i=num (a_i,b_i có thể bằng nhau)
Sort (arr) rồi duyệt từ bé đến lớn. Gọi N[num] là số lượng binary tree của phần tử num trong arr.
Có CT: N[num]=sum(N[a_i]*N[b_i]) , với các cặp a_i*b_i=num (a_i,b_i có thể bằng nhau)
Python:
class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
arr.sort()
n=len(arr)
h={}
for num in arr:
h[num]=1
for i in range(n):
for j in range(i):
if arr[i]%arr[j]==0:
k=arr[i]//arr[j]
if k in h:
h[arr[i]]+=h[arr[j]]*h[k]
return sum(h.values())%(10**9+7)Bài hôm nay tôi cũng sort arr trước để giảm số thao tác thừa. Sau đó với từng
arr[i] thì xem trước đó có 2 items nào mà arr[m]*arr[n]==arr[i] hay không. Nếu có thì số lượng tree tạo ra được từ root arr[i] sẽ là tích 2 kết quả của arr[m] và arr[n].https://leetcode.com/submissions/detail/768912658/
C#:
public class Solution {
public int NumFactoredBinaryTrees(int[] arr) {
Array.Sort(arr);
Dictionary<int, long> count = new ();
for (var i = 0; i < arr.Length; i++)
{
count.Add(arr[i], 1);
for (var j = 0; j < i; j++)
{
if (arr[i] % arr[j] == 0 && count.ContainsKey(arr[i]/arr[j]))
count[arr[i]] += count[arr[j]]*count[arr[i]/arr[j]] % 1_000_000_007;
}
}
long sum = 0;
foreach (var kvp in count)
{
//Console.WriteLine($"{kvp.Key}: {kvp.Value}");
sum += kvp.Value;
}
return (int)(sum % 1_000_000_007);
}
}
alpha_coder
Senior Member
Solution tương tự các bác ở trên O(N^2), góp vui code python 
Python:
class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
arr = sorted(arr)
n = len(arr)
res = 0
mod = 1e9 + 7
mapper = {val: idx for idx, val in enumerate(arr)}
dp = [1 for i in range(n)]
for i, val_p in enumerate(arr):
for j, val_l in enumerate(arr[:i]):
val_r = val_p // val_l
if val_p % val_l == 0 and val_r in mapper:
dp[i] = (dp[i] + dp[mapper[val_l]]*dp[mapper[val_r]]) % mod
res = (res + dp[i]) % mod
return int(res)
ngoctan_95
Senior Member
Bài nay hơi khoai, đã thử đệ quy mà thấy không ổn nên chuyển qua dynamic programming 
Java:
class Solution {
public int numFactoredBinaryTrees(int[] arr) {
int length = arr.length;
Arrays.sort(arr);
long whoopRes = 0;
long []deeperLength = new long[length];
long leepMaxNum = (long)1e9+7;
for( int i=0; i<length; i++ ){
long currentIndexingNumber = 1;
int left = 0;
int right = i-1;
while( left <= right ){
long mul2Ways = arr[left] * arr[right];
boolean shouldStopTrackingLeft = arr[left] <= ( arr[i]/2 );
boolean shouldStopTrackingRight = arr[right] <= ( arr[i]/2 );
boolean shouldFallDownContainerPoint = (arr[i] % leepMaxNum) - mul2Ways == 0;
if(shouldFallDownContainerPoint && shouldStopTrackingLeft && shouldStopTrackingRight){
int tempCheckToReset = 2;
if(arr[left] == arr[right])
{
tempCheckToReset = 1;
}
int delta = (( deeperLength[right] * deeperLength[left] ) % leepMaxNum ) * tempCheckToReset;
currentIndexingNumber = ( currentIndexingNumber + delta) % leepMaxNum;
right--;
left++;
}
else if ( mul2Ways > arr[i] ) {
right--;
} else {
left++;
}
}
deeperLength[i] = currentIndexingNumber;
whoopRes = ( whoopRes + currentIndexingNumber )%leepMaxNum;
}
return (int)whoopRes;
}
}Lúc đầu tôi cũng chỉ cho chạy đến sqrt, nhưng trong vòng lặp cần phải check thêm điều kiện nếu số đó là số chính phương thì phải bỏ bớt các tree đối xứng. Thấy code xấu quá nên bỏ qua luôn.
thuyduong2007
Member
Bài này dùng đệ quy + memoi dễ mà, 
Python:
class Solution:
def numFactoredBinaryTrees(self, arr: List[int]) -> int:
mySet = set(arr)
mod = int(1e9 + 7)
@cache
def countRoot(num : int) -> int :
ret = 1
for x in arr:
if num/x in mySet:
ret += countRoot(x)*countRoot(num/x)%mod
return ret
return sum(countRoot(num) for num in arr)%mod- Nếu là số chính phương: + bình phương count của root
- Nếu không phải số chính phương: + 2 lần tích của count của hai số. Bởi vì có thể build cây theo 2 cách.
Chỉ cần 1 lệnh cho cả hai trường hợp, khỏi cần check if else gì cả.
Code:
sum += count[x] * count[y] * (1 + (x != y))
Hóng hết mọi thứ
Senior Member
các cao thủ cho em hỏi cách mình học rồi luyện thuật toán trên leetcode chi tiết được không ạ, em thấy nó xếp tùm lum không biết bắt đầu như nào ạ.Cảm ơn các cao thủ.
_Gia_Cat_Luong_
Senior Member
https://voz.vn/t/leetcode-moi-ngay.568742/post-18474170
Thấy có nhiều ng hỏi vấn đề này nên mình sẽ pin lên #1 luôn.
alpha_coder
Senior Member
Bài hôm nay chia đôi + recursion, ez
Code:
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
return self.buildtree(nums, 0, len(nums))
def buildtree(self, nums, left, right):
if left == right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = self.buildtree(nums, left, mid)
node.right = self.buildtree(nums, mid+1, right)
return nodethuyduong2007
Member
Bài hôm nay 1 dòng là đủ 
Python:
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
return TreeNode(nums[len(nums)//2], self.sortedArrayToBST(nums[:len(nums)//2]), self.sortedArrayToBST(nums[len(nums)//2+1:])) if len(nums) > 0 else Nonealpha_coder
Senior Member
Thím nhận của em một lạyBài hôm nay 1 dòng là đủ
Python:class Solution: def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]: return TreeNode(nums[len(nums)//2], self.sortedArrayToBST(nums[:len(nums)//2]), self.sortedArrayToBST(nums[len(nums)//2+1:])) if len(nums) > 0 else None
Similar threads
