thảo luận Leetcode mỗi ngày

1680425252046.png
mng giúp em với em sai ở chỗ nào vậy sub toàn wa :angry::angry:
C++: 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
   int t;
   cin >> t;
   while (t--)
   {
      int n;
      cin >> n;
      int a[n];
      for (int &x : a)
         cin >> x;
      stack<int> idx, hei;
      idx.push(0);
      hei.push(a[0]);
      ll res = 0;
      for (int i = 1; i < n; i++)
      {
         if (hei.top() > a[i])
         {
            int idxTmp;
            while (idx.size() && hei.size() && hei.top() > a[i])
            {
               res = max(res, 1LL * hei.top() * (i - idx.top()));
               hei.pop();
               idxTmp = idx.top();
               idx.pop();
            }
            hei.push(a[i]);
            idx.push(idxTmp);
         }
         else
         {
            hei.push(a[i]);
            idx.push(i);
         }
      }
      res = max(res, 1LL * hei.top());
      int idx1 = idx.top();
      hei.pop();
      idx.pop();
      while (hei.size() && idx.size())
      {
         int hei2 = hei.top();
         int idx2 = idx.top();
         res = max(res, 1LL * hei2 * (idx1 - idx2 + 1));
         hei.pop();
         idx.pop();
      }
      cout << res << endl;
   }
}
}
 
tuần này chắc lại toàn Binary Search rồi
aKpaReA.gif

JavaScript: 
function successfulPairs(spells: number[], potions: number[], success: number): number[] {
    potions.sort((a, b) => a - b);
    const ans = Array(spells.length).fill(0), pL = potions.length, max = potions[pL - 1];
    const bs = (k: number): number => {
        let l = 0, h = potions.length;
        while (l < h) {
            const m = Math.floor((l + h) / 2);
            if (potions[m] < k) {
                l = m + 1
            } else {
                h = m
            }
        }
        return l
    }
    for (let i = 0; i < spells.length; i++) {
        const s = spells[i], min = Math.ceil(success / s);
        if (min > max) {
            ans[i] = 0;
            continue
        }
        ans[i] = pL - bs(min)
    }

    return ans
};
 
chiyeuemthoi said:
View attachment 1754444mng giúp em với em sai ở chỗ nào vậy sub toàn wa :angry::angry:
C++: 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
   int t;
   cin >> t;
   while (t--)
   {
      int n;
      cin >> n;
      int a[n];
      for (int &x : a)
         cin >> x;
      stack<int> idx, hei;
      idx.push(0);
      hei.push(a[0]);
      ll res = 0;
      for (int i = 1; i < n; i++)
      {
         if (hei.top() > a[i])
         {
            int idxTmp;
            while (idx.size() && hei.size() && hei.top() > a[i])
            {
               res = max(res, 1LL * hei.top() * (i - idx.top()));
               hei.pop();
               idxTmp = idx.top();
               idx.pop();
            }
            hei.push(a[i]);
            idx.push(idxTmp);
         }
         else
         {
            hei.push(a[i]);
            idx.push(i);
         }
      }
      res = max(res, 1LL * hei.top());
      int idx1 = idx.top();
      hei.pop();
      idx.pop();
      while (hei.size() && idx.size())
      {
         int hei2 = hei.top();
         int idx2 = idx.top();
         res = max(res, 1LL * hei2 * (idx1 - idx2 + 1));
         hei.pop();
         idx.pop();
      }
      cout << res << endl;
   }
}
}
Click to expand...
code gì loằng ngoằng thế

C++: 
for(ll i=1;i<=n;++i)
    {
        stack<ll>st;
        for(ll j=1;j<=m;++j)
        {
            ll temp=j;
            while(sz(st)&&pref[i][st.top()]>=pref[i][j])
            {
                temp=st.top();
                st.pop();
                res=max(res,(j-temp)*pref[i][temp]);
            }
            st.push(temp);
            pref[i][temp]=pref[i][j];
        }
        while(sz(st))
        {
            res=max(res,(m-st.top()+1)*pref[i][st.top()]);
            st.pop();
        }
}
i là testcase thứ i. Hơi lười viết lại
 
chiyeuemthoi said:
View attachment 1754444mng giúp em với em sai ở chỗ nào vậy sub toàn wa :angry::angry:
C++: 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
   int t;
   cin >> t;
   while (t--)
   {
      int n;
      cin >> n;
      int a[n];
      for (int &x : a)
         cin >> x;
      stack<int> idx, hei;
      idx.push(0);
      hei.push(a[0]);
      ll res = 0;
      for (int i = 1; i < n; i++)
      {
         if (hei.top() > a[i])
         {
            int idxTmp;
            while (idx.size() && hei.size() && hei.top() > a[i])
            {
               res = max(res, 1LL * hei.top() * (i - idx.top()));
               hei.pop();
               idxTmp = idx.top();
               idx.pop();
            }
            hei.push(a[i]);
            idx.push(idxTmp);
         }
         else
         {
            hei.push(a[i]);
            idx.push(i);
         }
      }
      res = max(res, 1LL * hei.top());
      int idx1 = idx.top();
      hei.pop();
      idx.pop();
      while (hei.size() && idx.size())
      {
         int hei2 = hei.top();
         int idx2 = idx.top();
         res = max(res, 1LL * hei2 * (idx1 - idx2 + 1));
         hei.pop();
         idx.pop();
      }
      cout << res << endl;
   }
}
}
Click to expand...
xin link đề bài với?
 
ziqqqq said:
code gì loằng ngoằng thế

C++: 
for(ll i=1;i<=n;++i)
    {
        stack<ll>st;
        for(ll j=1;j<=m;++j)
        {
            ll temp=j;
            while(sz(st)&&pref[i][st.top()]>=pref[i][j])
            {
                temp=st.top();
                st.pop();
                res=max(res,(j-temp)*pref[i][temp]);
            }
            st.push(temp);
            pref[i][temp]=pref[i][j];
        }
        while(sz(st))
        {
            res=max(res,(m-st.top()+1)*pref[i][st.top()]);
            st.pop();
        }
}
i là testcase thứ i. Hơi lười viết lại
Click to expand...
cái đoạn mảng pref là gì đấy bác k hiểu mảng này đâu ra :eek:
 
Java: 
fun successfulPairs(spells: IntArray, potions: IntArray, success: Long): IntArray {
        potions.sort()
        val result = IntArray(spells.size)

        fun binarySearch(value: Long): Int {
            var left = 0
            var right = potions.size - 1
            if (value > potions[right]) return 0
            while (left < right) {
                val mid = left + (right - left) / 2
                if (potions[mid] >= value) {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            return potions.size - left
        }
        
        for (i in spells.indices) {
            result[i] = binarySearch((success - 1) / spells[i] + 1)
        }
        return result
    }
 
chiyeuemthoi said:
ơ đề là mảng 1 chiều mà bác :oops:
Click to expand...
đây là đề bài khác nhưng mà cách làm giống thôi bác.Mà giải thích hơi khó hiểu sửa code cho nhanh

C++: 
        stack<ll>st;
        for(ll j=1;j<=m;++j)
        {
            ll temp=j;
            while(sz(st)&&pref[st.top()]>=pref[j])
            {
                temp=st.top();
                st.pop();
                res=max(res,(j-temp)*pref[temp]);
            }
            st.push(temp);
            pref[temp]=pref[j];
        }
        while(sz(st))
        {
            res=max(res,(m-st.top()+1)*pref[st.top()]);
            st.pop();
        }
 
TrMT7Oq.png
ghét nhất mấy bài làm việc với số lớn long như daily hôm nay


Java: 
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length;
        int[] result = new int[n];
        for(int i = 0; i < n; i++){
            result[i] = search(spells[i], success, potions);
        }
        return result;
    }
    public int search(long sp, long s, int[] p){
        int left = 0;
        int right = p.length - 1;
        int index = p.length;
        while(left <= right){
            int mid = left + (right - left) / 2;
            if((long)(p[mid] * sp) >= s){
                right = mid - 1;
                index = mid;
            }
            else{
                left = mid + 1;
            }
        }
        return p.length - index;
    }
}
 
Java ko có binary search à, toy khinh
BlYu2Cr.png

C++: 
struct Solution {
    vector<int> successfulPairs(vector<int>& ss, vector<int>& ps, double success) {
        sort(begin(ps), end(ps));
        for (int& k : ss) k = end(ps) - lower_bound(begin(ps), end(ps), success / k);
        return move(ss);
    }
};
 
Python: 
class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        l, r = 0, len(people) - 1
        cnt = 0
        while l <= r:
            if l == r:
                w = people[l]
            else:
                w = people[l] + people[r]
            if w <= limit:
                l += 1
                r -= 1
            else:
                r -= 1
            cnt += 1
        return cnt
 
Bài hard 1444. Number of Ways of Cutting a Pizza hôm bữa chưa làm xong ngâm tới giờ vẫn chưa hiểu tại sao mấy test case cuối lại sai, sáng nay tức mình thử convert sang Python thì lại được accept. Bác nào đi ngang qua có nhã hứng thì phân tích giúp em với nhé:
Code: 
import (
    "strconv"
    "strings"
)


func str(num int) string {
    return strconv.Itoa(num)
}


func dp(p []string, m, n, r, c, k int, cache map[string]int) int {
    var (
        i, j int
        a byte = byte('A')
    )


    if k == 0 {
        for i = r; i < m; i++ {
            for j = c; j < n; j++ {
                if p[i][j] == a {
                    return 1
                }
            }
        }
        return 0
    }


    // check cache
    key := str(k) + "-" + str(r) + "-" + str(c)
    if v, ok := cache[key]; ok {
        return v
    }


    var (
        res int
        checked bool
    )


    for i = r; i < m; i++ {
        if !checked {
            for j = c; j < n; j++ {
                if p[i][j] == a {
                    checked = true
                    break
                }
            }
        } else {
            res += dp(p, m, n, i, c, k-1, cache)
        }
    }
    checked = false
    for j = c; j < n; j++ {
        if !checked {
            for i = r; i < m; i++ {
                if p[i][j] == a {
                    checked = true
                    break
                }
            }
        } else {
            res += dp(p, m, n, r, j, k-1, cache)
        }
    }
  
    cache[key] = res
    return res
}
Code: 
def dp(p: List[str], m: int, n: int, r: int, c: int, k: int, cache: Dict[str, int]) -> int:
    if k == 0:
        for i in range(r, m):
            for j in range(c, n):
                if p[i][j] == "A":
                    return 1
        return 0

    key = str(k) + "-" + str(r) + "-" + str(c)
    if key in cache:
        return cache[key]

    res = 0
    checked = False

    for i in range(r, m):
        if not checked:
            for j in range(c, n):
                if p[i][j] == "A":
                    checked = True
                    break
        else:
            res += dp(p, m, n, i, c, k-1, cache)

    checked = False
    for j in range(c, n):
        if not checked:
            for i in range(r, m):
                if p[i][j] == "A":
                    checked = True
                    break
        else:
            res += dp(p, m, n, r, j, k-1, cache)

    cache[key] = res
    return res

class Solution:
    def ways(self, p: List[str], k: int) -> int:
        cache = {}
        m = len(p)
        n = len(p[0])
        return dp(p, m, n, 0, 0, k-1, cache) % (10**9+7)
1680485672502.png
 
Last edited:
Tuần này chắc toàn Sorting rồi
JavaScript: 
function numRescueBoats(people: number[], limit: number): number {
    let res = 0;
    people.sort((a,b) => a-b);
    let l = 0, r = people.length - 1;
    while (l <= r) {
        res++;
        if (people[l] + people[r] <= limit) l++;
        r--;
    }
    return res;
};
 
anoldvozer1710.v2 said:
Tuần này chắc toàn Sorting rồi
JavaScript: 
function numRescueBoats(people: number[], limit: number): number {
    let res = 0;
    people.sort((a,b) => a-b);
    let l = 0, r = people.length - 1;
    while (l <= r) {
        res++;
        if (people[l] + people[r] <= limit) l++;
        r--;
    }
    return res;
};
Click to expand...
Tuần này thấy toàn binary search bác ạ :D
 
Shinedo9820 said:
Bài hard 1444. Number of Ways of Cutting a Pizza hôm bữa chưa làm xong ngâm tới giờ vẫn chưa hiểu tại sao mấy test case cuối lại sai, sáng nay tức mình thử convert sang Python thì lại được accept. Bác nào đi ngang qua có nhã hứng thì phân tích giúp em với nhé:
Code: 
import (
    "strconv"
    "strings"
)


func str(num int) string {
    return strconv.Itoa(num)
}


func dp(p []string, m, n, r, c, k int, cache map[string]int) int {
    var (
        i, j int
        a byte = byte('A')
    )


    if k == 0 {
        for i = r; i < m; i++ {
            for j = c; j < n; j++ {
                if p[i][j] == a {
                    return 1
                }
            }
        }
        return 0
    }


    // check cache
    key := str(k) + "-" + str(r) + "-" + str(c)
    if v, ok := cache[key]; ok {
        return v
    }


    var (
        res int
        checked bool
    )


    for i = r; i < m; i++ {
        if !checked {
            for j = c; j < n; j++ {
                if p[i][j] == a {
                    checked = true
                    break
                }
            }
        } else {
            res += dp(p, m, n, i, c, k-1, cache)
        }
    }
    checked = false
    for j = c; j < n; j++ {
        if !checked {
            for i = r; i < m; i++ {
                if p[i][j] == a {
                    checked = true
                    break
                }
            }
        } else {
            res += dp(p, m, n, r, j, k-1, cache)
        }
    }
 
    cache[key] = res
    return res
}
Code: 
def dp(p: List[str], m: int, n: int, r: int, c: int, k: int, cache: Dict[str, int]) -> int:
    if k == 0:
        for i in range(r, m):
            for j in range(c, n):
                if p[i][j] == "A":
                    return 1
        return 0

    key = str(k) + "-" + str(r) + "-" + str(c)
    if key in cache:
        return cache[key]

    res = 0
    checked = False

    for i in range(r, m):
        if not checked:
            for j in range(c, n):
                if p[i][j] == "A":
                    checked = True
                    break
        else:
            res += dp(p, m, n, i, c, k-1, cache)

    checked = False
    for j in range(c, n):
        if not checked:
            for i in range(r, m):
                if p[i][j] == "A":
                    checked = True
                    break
        else:
            res += dp(p, m, n, r, j, k-1, cache)

    cache[key] = res
    return res

class Solution:
    def ways(self, p: List[str], k: int) -> int:
        cache = {}
        m = len(p)
        n = len(p[0])
        return dp(p, m, n, 0, 0, k-1, cache) % (10**9+7)
View attachment 1755483
Click to expand...
Chắc bị tràn số đó bác. Tại Python ko giới hạn số
 
Shinedo9820 said:
Bài hard 1444. Number of Ways of Cutting a Pizza hôm bữa chưa làm xong ngâm tới giờ vẫn chưa hiểu tại sao mấy test case cuối lại sai, sáng nay tức mình thử convert sang Python thì lại được accept. Bác nào đi ngang qua có nhã hứng thì phân tích giúp em với nhé:
Code: 
import (
    "strconv"
    "strings"
)


func str(num int) string {
    return strconv.Itoa(num)
}


func dp(p []string, m, n, r, c, k int, cache map[string]int) int {
    var (
        i, j int
        a byte = byte('A')
    )


    if k == 0 {
        for i = r; i < m; i++ {
            for j = c; j < n; j++ {
                if p[i][j] == a {
                    return 1
                }
            }
        }
        return 0
    }


    // check cache
    key := str(k) + "-" + str(r) + "-" + str(c)
    if v, ok := cache[key]; ok {
        return v
    }


    var (
        res int
        checked bool
    )


    for i = r; i < m; i++ {
        if !checked {
            for j = c; j < n; j++ {
                if p[i][j] == a {
                    checked = true
                    break
                }
            }
        } else {
            res += dp(p, m, n, i, c, k-1, cache)
        }
    }
    checked = false
    for j = c; j < n; j++ {
        if !checked {
            for i = r; i < m; i++ {
                if p[i][j] == a {
                    checked = true
                    break
                }
            }
        } else {
            res += dp(p, m, n, r, j, k-1, cache)
        }
    }
 
    cache[key] = res
    return res
}
Code: 
def dp(p: List[str], m: int, n: int, r: int, c: int, k: int, cache: Dict[str, int]) -> int:
    if k == 0:
        for i in range(r, m):
            for j in range(c, n):
                if p[i][j] == "A":
                    return 1
        return 0

    key = str(k) + "-" + str(r) + "-" + str(c)
    if key in cache:
        return cache[key]

    res = 0
    checked = False

    for i in range(r, m):
        if not checked:
            for j in range(c, n):
                if p[i][j] == "A":
                    checked = True
                    break
        else:
            res += dp(p, m, n, i, c, k-1, cache)

    checked = False
    for j in range(c, n):
        if not checked:
            for i in range(r, m):
                if p[i][j] == "A":
                    checked = True
                    break
        else:
            res += dp(p, m, n, r, j, k-1, cache)

    cache[key] = res
    return res

class Solution:
    def ways(self, p: List[str], k: int) -> int:
        cache = {}
        m = len(p)
        n = len(p[0])
        return dp(p, m, n, 0, 0, k-1, cache) % (10**9+7)
View attachment 1755483
Click to expand...
Nhìn sơ thì đoán bị tràn số. Phải chia lấy dư trước khi lưu vào cache
 
Các bác chia sẻ cách cải thiện kỹ năng giải bài leetcode với. Em toàn bí 30p-1h thì đi đọc solution và ráng hiểu solution đó. Nhưng mà ko thấy cải thiện được gì lắm, vẫn bí tiếp như thường

Ko biết hỏi ở thớt này có hợp lý ko, nếu sai mong các bác bỏ qua :love:
 

Similar threads

Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
614
heocon0123
heocon0123
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
155
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
16
Views
424
truonggiang!
T
@_shin
kiến thức PIXELVERSE kèo hot - inbox tele để lấy extension chạy auto đánh boss
Replies
0
Views
127
@_shin
@_shin
D
kiến thức Lộ trình tự học phát triển Website Fullstack - Fullstack Web Development
2
Replies
25
Views
2K
Kieft
Kieft

Share this page

Back
Top