Contest sáng nay C1 ez, C2 math, C3 làm kiểu straitforward cứ thêm số tiếp theo thì check với các số trong subarr trước đó.
Sao bài 3 tui bị sai test case này nhỉ:Contest sáng nay C1 ez, C2 math, C3 làm kiểu straitforward cứ thêm số tiếp theo thì check với các số trong subarr trước đó.
C4 cảm giác chỉ cần dùng heap push pop mô phỏng lại thôi mà còn 45p cx ko xong đc
https://leetcode.com/contest/weekly-contest-309/problems/meeting-rooms-iii/
Python:nums = [84139415, 693324769, 614626365, 497710833, 615598711, 264, 65552, 50331652, 1, 1048576, 16384, 544, 270532608, 151813349, 221976871, 678178917, 845710321, 751376227, 331656525, 739558112, 267703680] dp = [1 for _ in range(len(nums))] for i in range(1, len(dp)): flag = 0 for j in range(i-1, i - dp[i-1] - 1, -1): if nums[j] & nums[i] != 0: dp[i] = 1 flag = 1 break if flag == 0: dp[i] = dp[i-1] + 1 else: dp[i] = 1 for i in range(len(dp)): print(i, dp[i]) print(max(dp))
C2 math ntn vậy thím. T làm kiểu ngây thơ dùng đệ quy + memoi mà dùng python nên k chạy nổi xong bỏ luôn.Contest sáng nay C1 ez, C2 math, C3 làm kiểu straitforward cứ thêm số tiếp theo thì check với các số trong subarr trước đó.
C4 cảm giác chỉ cần dùng heap push pop mô phỏng lại thôi mà còn 45p cx ko xong đc
https://leetcode.com/contest/weekly-contest-309/problems/meeting-rooms-iii/
class Solution {
public List<List<Integer>> verticalTraversal(TreeNode root) {
ArrayList<Tuples> tmp = new ArrayList<>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
preorderTraversal(root, tmp, 0, 0);
Collections.sort(tmp);
ans.add(new ArrayList<>());
ans.get(0).add(tmp.get(0).val);
int prevX = tmp.get(0).x;
for(int i = 1; i < tmp.size(); i++)
{
if(tmp.get(i).x != prevX)
{
ans.add(new ArrayList<>());
ans.get(ans.size() - 1).add(tmp.get(i).val);
}
else
{
ans.get(ans.size() - 1).add(tmp.get(i).val);
}
prevX = tmp.get(i).x;
}
return ans;
}
public void preorderTraversal(TreeNode root, ArrayList<Tuples> tmp, int x, int y)
{
if(root == null)
{
return;
}
tmp.add(new Tuples(x, y, root.val));
preorderTraversal(root.left, tmp, x -1, y - 1);
preorderTraversal(root.right, tmp, x + 1, y - 1);
}
}
class Tuples implements Comparable<Tuples> {
public int x;
public int y;
public int val;
Tuples()
{
x = 0;
y = 0;
val = 0;
}
Tuples(int x, int y, int val)
{
this.x = x;
this.y = y;
this.val = val;
}
@Override
public int compareTo(Tuples o)
{
if(this.x == o.x)
{
if(this.y == o.y)
{
if(this.val == o.val)
{
return 0;
}
return (this.val < o.val) ? -1 : 1;
}
return (this.y > o.y) ? -1 : 1;
}
return (this.x < o.x) ? -1 : 1;
}
}Đọc kỹ đề bài đi,
.
class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
if (k + endPos - startPos) % 2 != 0:
return 0
positive = (k + endPos - startPos) // 2
negative = k - positive
if negative < 0:
return 0
def cnk(n, k):
M = 1000000007
f = [[0 for x in range(n-k + 1)] for _ in range(k + 1)]
for i in range(k + 1):
for j in range(n-k + 1):
if j == 0 or i == 0:
f[i][j] = 1
continue
f[i][j] = (f[i][j-1] % M + f[i-1][j] % M) % M
return f[k][n-k]
return cnk(positive + negative, positive)Gọi a,b là số bước right và left. Thì ta có a+b=k,a-b=endPos-startPos. Như vậy là tính đc a và b.
Có hàm factorial mà bác
for j in range(i-1, i - dp[i-1] - 1, -1):
if nums[j] & nums[i] != 0:
dp[i] = 1
flag = 1
breakclass Solution:
def longestNiceSubarray(self, nums: List[int]) -> int:
dp=[1]*len(nums)
res=1
for i in range(1,len(nums)):
for j in range(i-1,i-1-dp[i-1],-1):
if nums[i]&nums[j]==0:
dp[i]+=1
else:
break
res=max(dp[i],res)
return res
C4 giải kiểu trâu bò vẫn Accept: https://leetcode.com/submissions/detail/791109321/ Không có heap push pop gì hết, cứ loop hết các room thôi.Contest sáng nay C1 ez, C2 math, C3 làm kiểu straitforward cứ thêm số tiếp theo thì check với các số trong subarr trước đó.
C4 cảm giác chỉ cần dùng heap push pop mô phỏng lại thôi mà còn 45p cx ko xong đc
https://leetcode.com/contest/weekly-contest-309/problems/meeting-rooms-iii/
Bài này input bé tí chắc giải theo kiểu brute force thử tất cả các tổ hợp thôi nhỉ? Mình chưa nghĩ ra được cách nào hay hơn.
), tks fen
