Bạn đang dùng trình duyệt đã lỗi thời. Trình duyệt có thể không hiển thị đúng trang web này hoặc các trang web khác. Bạn nên nâng cấp hoặc dùng một trình duyệt khác.
Nhìn vào đề bài thì sẽ thấy được, cứ mỗi 1 lần sẽ lấy số ở đầu hoặc số ở cuối, lặp đi lặp lại và sử dụng kết quả của thằng đứng trước -> Dấu hiệu của đệ quy.
Cái mình cần tính được là trong thời gian chạy đệ quy, sẽ có những hàm đệ quy đã được tính rồi nhưng vẫn phải tính lại -> tạo cache để lưu -> cache ở đây có thể là hashmap/array.
Với bài thế này thì dễ dàng nhìn được nếu độ dài array là số chẵn thì luôn luôn có thể thắng nên thêm cái điều kiện if(n % 2 === 0) return true;
JavaScript:
function PredictTheWinner(nums: number[]): boolean {
const n = nums.length;
if (n % 2 === 0 || n === 1) return true;
const memo = new Array(n).fill(0).map(e => Array(n).fill(-1))
const go = (l: number, r: number): number => {
if (memo[l][r] !== -1) return memo[l][r];
if (l === r) return nums[l]
const lScore = nums[l] - go(l + 1, r)
const rScore = nums[r] - go(l, r-1)
memo[l][r] = Math.max(lScore, rScore)
return memo[l][r]
}
return go(0, n-1) >= 0;
};
Mấy bài game theory, cờ kiếc này nọ có vẻ toàn là dùng DP hết
Vì thằng 1 luôn có thể chủ động chọn toàn các số ở vị trí lẻ, hoặc toàn các số ở vị trí chẵn
Nếu tổng lẻ < chẵn thì chọn chẵn, mà nếu tổng chẵn < lẻ thì chọn lẻ
Sau khi ngồi làm cái topic binary search bị cái low high hành cho ra bã mấy hôm nay thì mới mò lên đọc cách tìm boundary của 1 pro Leetcode mới biết cách tìm low high cho đúng với bài toán binary search, lên share cho anh em phát
Thường binary search sẽ có 2 trường hợp, left = 0, right = array.Length - 1, và bên trong while query thì sẽ xảy ra 2 trường hợp while(left < right) và while(left <= right). Và thường lúc làm sẽ bị confused là chọn boundary nào cho hợp lí với từng bài toán. Thì cách chọn là thế này
1) Chọn low < high khi ko muốn trả kết quả về sau khi thực hiện binary search. Lúc đấy bên trong sẽ là high = mid và low = mid + 1
2) Chọn low <= high khi kết quả search ở ngay trong lúc binary search. Lúc đấy high = mid -1 và low = mid -1
Ví dụ như 2 bài này https://leetcode.com/problems/koko-eating-bananas/submissions/
Nếu chọn low <= high thì edge case sẽ tùm lum vì kết quả cuối cùng nó phải được tính sau khi binary search xong. Nên chọn low < high
C#:
public class Solution {
public int MinEatingSpeed(int[] piles, int h)
{
int left = 1;
int right = piles.Max();
var res = right;
while (left < right)
{
int mid= (left + right) / 2;
int totalTime = 0;
foreach (int p in piles)
{
totalTime += (int)Math.Ceiling((double)p / mid);
}
if (totalTime <= h)
{
right = mid;
}
else
{
left = mid + 1 ;
}
}
return left;
}
}
public class Solution {
public int SingleNonDuplicate(int[] nums) {
var left = 0;
var right = nums.Length - 1;
while(left < right)
{
var mid = (left + right)/2;
if (mid % 2 == 1) mid--;
}
return -1;
}
}
Sau khi ngồi làm cái topic binary search bị cái low high hành cho ra bã mấy hôm nay thì mới mò lên đọc cách tìm boundary của 1 pro Leetcode mới biết cách tìm low high cho đúng với bài toán binary search, lên share cho anh em phát
Thường binary search sẽ có 2 trường hợp, left = 0, right = array.Length - 1, và bên trong while query thì sẽ xảy ra 2 trường hợp while(left < right) và while(left <= right). Và thường lúc làm sẽ bị confused là chọn boundary nào cho hợp lí với từng bài toán. Thì cách chọn là thế này
1) Chọn low < high khi ko muốn trả kết quả về sau khi thực hiện binary search. Lúc đấy bên trong sẽ là high = mid và low = mid -1
2) Chọn low <= high khi kết quả search ở ngay trong lúc binary search. Lúc đấy high = mid -1 và low = mid -1
Ví dụ như 2 bài này https://leetcode.com/problems/koko-eating-bananas/submissions/
Nếu chọn low <= high thì edge case sẽ tùm lum vì kết quả cuối cùng nó phải được tính sau khi binary search xong. Nên chọn low < high
C#:
public class Solution {
public int MinEatingSpeed(int[] piles, int h)
{
int left = 1;
int right = piles.Max();
var res = right;
while (left < right)
{
int mid= (left + right) / 2;
int totalTime = 0;
foreach (int p in piles)
{
totalTime += (int)Math.Ceiling((double)p / mid);
}
if (totalTime <= h)
{
right = mid;
}
else
{
left = mid + 1 ;
}
}
return left;
}
}
public class Solution {
public int SingleNonDuplicate(int[] nums) {
var left = 0;
var right = nums.Length - 1;
while(left < right)
{
var mid = (left + right)/2;
if (mid % 2 == 1) mid--;
}
return -1;
}
}
Sau khi ngồi làm cái topic binary search bị cái low high hành cho ra bã mấy hôm nay thì mới mò lên đọc cách tìm boundary của 1 pro Leetcode mới biết cách tìm low high cho đúng với bài toán binary search, lên share cho anh em phát
Thường binary search sẽ có 2 trường hợp, left = 0, right = array.Length - 1, và bên trong while query thì sẽ xảy ra 2 trường hợp while(left < right) và while(left <= right). Và thường lúc làm sẽ bị confused là chọn boundary nào cho hợp lí với từng bài toán. Thì cách chọn là thế này
1) Chọn low < high khi ko muốn trả kết quả về sau khi thực hiện binary search. Lúc đấy bên trong sẽ là high = mid và low = mid -1
2) Chọn low <= high khi kết quả search ở ngay trong lúc binary search. Lúc đấy high = mid -1 và low = mid -1
Ví dụ như 2 bài này https://leetcode.com/problems/koko-eating-bananas/submissions/
Nếu chọn low <= high thì edge case sẽ tùm lum vì kết quả cuối cùng nó phải được tính sau khi binary search xong. Nên chọn low < high
C#:
public class Solution {
public int MinEatingSpeed(int[] piles, int h)
{
int left = 1;
int right = piles.Max();
var res = right;
while (left < right)
{
int mid= (left + right) / 2;
int totalTime = 0;
foreach (int p in piles)
{
totalTime += (int)Math.Ceiling((double)p / mid);
}
if (totalTime <= h)
{
right = mid;
}
else
{
left = mid + 1 ;
}
}
return left;
}
}
public class Solution {
public int SingleNonDuplicate(int[] nums) {
var left = 0;
var right = nums.Length - 1;
while(left < right)
{
var mid = (left + right)/2;
if (mid % 2 == 1) mid--;
}
return -1;
}
}
BS kiểu low <= high lấy mid làm ans làm bình thường thôi, nó là cách general và bug free nhất mà bác.
Python:
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l = 1
r = sum(piles)
ans = 0
while l <= r:
m = (l + r) >> 1
if h >= sum((pile + m - 1)// m for pile in piles):
ans = m
r = m - 1
else:
l = m + 1
return ans
Sau khi ngồi làm cái topic binary search bị cái low high hành cho ra bã mấy hôm nay thì mới mò lên đọc cách tìm boundary của 1 pro Leetcode mới biết cách tìm low high cho đúng với bài toán binary search, lên share cho anh em phát
Thường binary search sẽ có 2 trường hợp, left = 0, right = array.Length - 1, và bên trong while query thì sẽ xảy ra 2 trường hợp while(left < right) và while(left <= right). Và thường lúc làm sẽ bị confused là chọn boundary nào cho hợp lí với từng bài toán. Thì cách chọn là thế này
1) Chọn low < high khi ko muốn trả kết quả về sau khi thực hiện binary search. Lúc đấy bên trong sẽ là high = mid và low = mid -1
2) Chọn low <= high khi kết quả search ở ngay trong lúc binary search. Lúc đấy high = mid -1 và low = mid -1
Ví dụ như 2 bài này https://leetcode.com/problems/koko-eating-bananas/submissions/
Nếu chọn low <= high thì edge case sẽ tùm lum vì kết quả cuối cùng nó phải được tính sau khi binary search xong. Nên chọn low < high
C#:
public class Solution {
public int MinEatingSpeed(int[] piles, int h)
{
int left = 1;
int right = piles.Max();
var res = right;
while (left < right)
{
int mid= (left + right) / 2;
int totalTime = 0;
foreach (int p in piles)
{
totalTime += (int)Math.Ceiling((double)p / mid);
}
if (totalTime <= h)
{
right = mid;
}
else
{
left = mid + 1 ;
}
}
return left;
}
}
public class Solution {
public int SingleNonDuplicate(int[] nums) {
var left = 0;
var right = nums.Length - 1;
while(left < right)
{
var mid = (left + right)/2;
if (mid % 2 == 1) mid--;
}
return -1;
}
}
em bổ sung một chút thông tin có thể hữu ích
Những bài tìm kiếm nhị phân với số thực thì có thể dùng epsilon để kiểm tra điều kiện thoát vòng lặp, hoặc nếu lười thì có thể dùng for tầm 90 lần là sẽ được kết quả tương đối chính xác (giả sử lo thấp nhất là 0 và hi cao nhất là 1e18, lúc này dif ban đầu của ta sẽ là dif = hi - lo = 1e18, sau mỗi vòng lặp thì dif sẽ giảm đi một nửa, sau 90 vòng lặp thì dif chắc chắn nhỏ hơn 1e-9, độ chênh lệch chặt nhất có thể của một bài mình từng thấy, có thể kiểm tra 1e18 / (2 ^ 90) = 8.0779357e-10 < 1e-9.
Cái template này có mấy bài giải ko ra đâu thím, em gặp trong mấy hôm nay tu luyện rồi. Nên mới phải đi tìm chân kinh
Nếu bài toán mà tìm ra giá trị ngay ở trong while thì dùng low < high kiểu gì cũng ăn edge cases nên BS ko có template cụ thể mà phải chọn cách nào hợp lí nhất để 1 phát ăn ngay.
BS kiểu low <= high lấy mid làm ans làm bình thường thôi, nó là cách general và bug free nhất mà bác.
Python:
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l = 1
r = sum(piles)
ans = 0
while l <= r:
m = (l + r) >> 1
if h >= sum((pile + m - 1)// m for pile in piles):
ans = m
r = m - 1
else:
l = m + 1
return ans
Mình ko hiểu sao bài này viết như này convert qua C# ko pass được hết test case nha bác, mình ngồi loay hoay cả buổi sau phải chuyển về low < high mới pass
Sau khi ngồi làm cái topic binary search bị cái low high hành cho ra bã mấy hôm nay thì mới mò lên đọc cách tìm boundary của 1 pro Leetcode mới biết cách tìm low high cho đúng với bài toán binary search, lên share cho anh em phát
Thường binary search sẽ có 2 trường hợp, left = 0, right = array.Length - 1, và bên trong while query thì sẽ xảy ra 2 trường hợp while(left < right) và while(left <= right). Và thường lúc làm sẽ bị confused là chọn boundary nào cho hợp lí với từng bài toán. Thì cách chọn là thế này
1) Chọn low < high khi ko muốn trả kết quả về sau khi thực hiện binary search. Lúc đấy bên trong sẽ là high = mid và low = mid -1
2) Chọn low <= high khi kết quả search ở ngay trong lúc binary search. Lúc đấy high = mid -1 và low = mid -1
Ví dụ như 2 bài này https://leetcode.com/problems/koko-eating-bananas/submissions/
Nếu chọn low <= high thì edge case sẽ tùm lum vì kết quả cuối cùng nó phải được tính sau khi binary search xong. Nên chọn low < high
C#:
public class Solution {
public int MinEatingSpeed(int[] piles, int h)
{
int left = 1;
int right = piles.Max();
var res = right;
while (left < right)
{
int mid= (left + right) / 2;
int totalTime = 0;
foreach (int p in piles)
{
totalTime += (int)Math.Ceiling((double)p / mid);
}
if (totalTime <= h)
{
right = mid;
}
else
{
left = mid + 1 ;
}
}
return left;
}
}
public class Solution {
public int SingleNonDuplicate(int[] nums) {
var left = 0;
var right = nums.Length - 1;
while(left < right)
{
var mid = (left + right)/2;
if (mid % 2 == 1) mid--;
}
return -1;
}
}
Sau khi ngồi làm cái topic binary search bị cái low high hành cho ra bã mấy hôm nay thì mới mò lên đọc cách tìm boundary của 1 pro Leetcode mới biết cách tìm low high cho đúng với bài toán binary search, lên share cho anh em phát
Thường binary search sẽ có 2 trường hợp, left = 0, right = array.Length - 1, và bên trong while query thì sẽ xảy ra 2 trường hợp while(left < right) và while(left <= right). Và thường lúc làm sẽ bị confused là chọn boundary nào cho hợp lí với từng bài toán. Thì cách chọn là thế này
1) Chọn low < high khi ko muốn trả kết quả về sau khi thực hiện binary search. Lúc đấy bên trong sẽ là high = mid và low = mid + 1
2) Chọn low <= high khi kết quả search ở ngay trong lúc binary search. Lúc đấy high = mid -1 và low = mid -1
Ví dụ như 2 bài này https://leetcode.com/problems/koko-eating-bananas/submissions/
Nếu chọn low <= high thì edge case sẽ tùm lum vì kết quả cuối cùng nó phải được tính sau khi binary search xong. Nên chọn low < high
C#:
public class Solution {
public int MinEatingSpeed(int[] piles, int h)
{
int left = 1;
int right = piles.Max();
var res = right;
while (left < right)
{
int mid= (left + right) / 2;
int totalTime = 0;
foreach (int p in piles)
{
totalTime += (int)Math.Ceiling((double)p / mid);
}
if (totalTime <= h)
{
right = mid;
}
else
{
left = mid + 1 ;
}
}
return left;
}
}
public class Solution {
public int SingleNonDuplicate(int[] nums) {
var left = 0;
var right = nums.Length - 1;
while(left < right)
{
var mid = (left + right)/2;
if (mid % 2 == 1) mid--;
}
return -1;
}
}
Cái template này có mấy bài giải ko ra đâu thím, em gặp trong mấy hôm nay tu luyện rồi. Nên mới phải đi tìm chân kinh
Nếu bài toán mà tìm ra giá trị ngay ở trong while thì dùng low < high kiểu gì cũng ăn edge cases nên BS ko có template cụ thể mà phải chọn cách nào hợp lí nhất để 1 phát ăn ngay.
Cũng ko hẳn đâu thím ơi, nó chỉ là 2 cách implementation khác nhau thôi. Cơ bản chênh lệch 2 cái là ko đáng kể.
low <= high: khi thím muốn return ngay ở trong vòng lặp
low < high: kết lúc vòng lặp trước đã, rồi tính kết quả dựa trên giá trị low-high.
2 cái nó chỉ là implementation khác nhau nhưng kết quả thì ko thay đổi đâu thím.
Ví dụ như bài Koko này em thấy vẫn viết theo được kiểu đó thôi. Em nghĩ là do cái hàm feasible của thím viết thế nào thôi
Thím thử gửi cho em cái bài nào mà template này fail để e quẩy thử xem kk.
C#:
public class Solution {
private bool feasible(int[] piles, int m, int h) {
int total = 0;
foreach (int pile in piles) {
total+= (pile + m - 1) / m;
}
return total <=h;
}
public int MinEatingSpeed(int[] piles, int h) {
int l = 1, r = piles.Max();
while (l < r) {
int m = l + (r - l) / 2;
if (feasible(piles,m, h)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
}
mà đang viết JS/TS sang ngôn ngữ khác viết ngượng tay vãi, data type lỗi toè loe
Vẫn giải đc mà thím ơi, ví dụ như bài Koko này em thấy vẫn viết theo được kiểu đó thôi. Em nghĩ là do cái hàm feasible của thím viết thế nào thôi
Thím thử gửi cho em cái bài nào mà template này fail để e quẩy thử xem kk.
C#:
public class Solution {
private bool feasible(int[] piles, int m, int h) {
int total = 0;
foreach (int pile in piles) {
total+= (pile + m - 1) / m;
}
return total <=h;
}
public int MinEatingSpeed(int[] piles, int h) {
int l = 1, r = piles.Max();
while (l < r) {
int m = l + (r - l) / 2;
if (feasible(piles,m, h)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
}
mà đang viết JS/TS sang ngôn ngữ khác viết ngượng tay vãi, data type lỗi toè loe
https://leetcode.com/problems/time-based-key-value-store/description/
Bác thử giải bài này với template kia xem. Xưa giờ mình toàn xài c# để kiếm ăn thôi nên lúc nào cũng giải bằng C#
Hôm qua bài koko này xem NeetCode nó viết solution này thì pass test case mà mình convert qua C# lại chỉ pass 124/125
Python:
View on Github
class Solution:
def minEatingSpeed(self, piles: List[int], h: int) -> int:
l, r = 1, max(piles)
res = max(piles)
while l <= r:
k = (l + r) // 2
totalTime = 0
for p in piles:
totalTime += math.ceil(p / k)
if totalTime <= h:
res = min(res, k)
r = k - 1
else:
l = k + 1
return res
