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??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.
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??
Thế thì đi cày dạo chứ toptier sao vô nổiCó. 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 OS
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)
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]
.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);
}
}
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)
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.Ở vòng lặp for thứ 2 có thể giới hạn chỉ cần lặp đến sqrt(i), giảm được xuống còn O(n^1.5).
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
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.
sum += count[x] * count[y] * (1 + (x != y))
https://voz.vn/t/leetcode-moi-ngay.568742/post-18474170cá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ủ.
# 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 node
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
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