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

sondaica22 said:
Nghĩ mãi chẳng ra, đọc solution của mấy bác cũng chẳng hiểu nốt, cứu :eek:
Click to expand...
dp đơn giản thì sẽ tạo mảng lưu optimal solution tại idx i trên arr có độ dài n. Rồi tại index i duyệt từ 0 đến i xem thằng nào lớn nhất rồi +1 là ra dp tại đó.
dp = max(dp[0]...dp[i - 1]) + 1
Click to expand...

Khổ nỗi O(n^2) lận nên bị dính TLE, thì có cách nào giảm complexity xuống không nhỉ? :p
Thay vì lưu mảng dp length n thì giờ giảm kích thước lại còn 26 thôi, mỗi element lưu giá trị dài nhất có thể và kết thúc bằng char đó. Trong mảng 26 đó chọn ra thằng thỏa mãn k và lớn nhất. + nó thêm 1 là cái cần tìm đó.
 
billy_don said:
dp đơn giản thì sẽ tạo mảng lưu optimal solution tại idx i trên arr có độ dài n. Rồi tại index i duyệt từ 0 đến i xem thằng nào lớn nhất rồi +1 là ra dp tại đó.


Khổ nỗi O(n^2) lận nên bị dính TLE, thì có cách nào giảm complexity xuống không nhỉ? :p
Thay vì lưu mảng dp length n thì giờ giảm kích thước lại còn 26 thôi, mỗi element lưu giá trị dài nhất có thể và kết thúc bằng s. Trong mảng 26 đó chọn ra thằng thỏa mãn k và lớn nhất. + nó thêm 1 là cái cần tìm đó.
Click to expand...
e làm dp[length n] đây thì nàm sao
osCpCsi.png
có TLE đâu
 
Last edited:
LmaoSuVuong said:
for(int i =1 ;i<c.length;i++){
for(int j=0;j<=k;j++){
Click to expand...
1714023963250.png

mà TLE là do complexity đâu phải do space đâu, complexity của fen vẫn là O(n) thôi.
TLE của mình đây.

Java: 
class Solution {
    public int longestIdealString(String s, int k) {
        int[] dp = new int[s.length()];
        int ans = 0;
        
        for (int i = 0; i < s.length(); i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                int diff = (int) s.charAt(i) - s.charAt(j);
                
                if (Math.abs(diff) <= k) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            ans = Math.max(ans, dp[i]);
        }

        return ans;
    }
}
 
Code: 
use std::cmp;

impl Solution {
    pub fn longest_ideal_string(s: String, k: i32) -> i32 {
        let bytes = s.as_bytes();
        let n = bytes.len();

        if n == 1 {
            return 1;
        }

        let mut dp = vec![vec![0; n]; 26];
        dp[(bytes[0] - b'a') as usize][0] = 1;

        for i in 1..n {
            let char = bytes[i];
            let c = (char - b'a') as usize;

            for j in 0..26 {
                let d = (cmp::max(c, j) - cmp::min(c, j)) as i32;

                if d <= k {
                    dp[c][i] = cmp::max(dp[j][i - 1] + 1, dp[c][i]);
                }

                if j != c {
                    dp[j][i] = dp[j][i - 1];
                }
            }
        }

        dp.into_iter().map(|row| row.into_iter().max().unwrap()).collect::<Vec<i32>>().into_iter().max().unwrap()
    }
}
 
billy_don said:
dp đơn giản thì sẽ tạo mảng lưu optimal solution tại idx i trên arr có độ dài n. Rồi tại index i duyệt từ 0 đến i xem thằng nào lớn nhất rồi +1 là ra dp tại đó.


Khổ nỗi O(n^2) lận nên bị dính TLE, thì có cách nào giảm complexity xuống không nhỉ? :p
Thay vì lưu mảng dp length n thì giờ giảm kích thước lại còn 26 thôi, mỗi element lưu giá trị dài nhất có thể và kết thúc bằng char đó. Trong mảng 26 đó chọn ra thằng thỏa mãn k và lớn nhất. + nó thêm 1 là cái cần tìm đó.
Click to expand...
Bác giải thích dễ hiểu ghê, mình vẫn còn yếu DP lắm :eek:
Đọc cái hiểu luôn. Nhưng kể ra để mà suy nghĩ được từ simple DP cho tới khâu dùng DP 26 kí tự cũng là một quá trình, mình suy nghĩ cả ngày chắc cũng không ra..
 
Last edited:
Java: 
class Solution {
    public int longestIdealString(String s, int k) {
        int[] cnt = new int[26];
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            int minIndex = Math.max(0, s.charAt(i) - 'a' - k);
            int maxIndex = Math.min(25, s.charAt(i) - 'a' + k);
            int temp = 1;
            for (int index = minIndex; index <= maxIndex; index++) {
                temp = Math.max(cnt[index] + 1, temp);
            }
            cnt[s.charAt(i) - 'a'] = temp;
            res = Math.max(res, cnt[s.charAt(i) - 'a']);
        }
        return res;
    }
}
TOxIXtu.gif
bài nay được
 
sondaica22 said:
Bác giải thích dễ hiểu ghê, mình vẫn còn yếu DP lắm :eek:
Đọc cái hiểu luôn. Nhưng kể ra để mà suy nghĩ được từ simple DP cho tới khâu dùng DP 26 kí tự cũng là một quá trình, mình suy nghĩ cả ngày chắc cũng không ra..
Click to expand...
Luyện hết cái này là cũng tạm ổn nè
leetcode.com

Dynamic Programming - Study Plan - LeetCode

10 Essential DP Patterns
leetcode.com
 
Java: 
class Solution {
    public int longestIdealString(String s, int k) {
        int[] dp = new int[27];
        int ans = 0;
        for (char c : s.toCharArray()) {
            int max = 0;
            int left = Math.max(((c - 'a') - k), 0);
            int right = Math.min(((c - 'a') + k), 26);
            for (int j = left; j <= right; j++) {
                max = Math.max(max, dp[j]);
            }
            dp[c - 'a'] = max + 1;
        }
        for (int idx : dp) {
            ans = Math.max(idx, ans);
        }
        return ans;
    }
}
 
Ban đầu xài list bị MLE. Nhìn log thấy map thế là beat 63%. Mới làm DP chua phết :burn_joss_stick:
Python: 
class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        map = {ord(s[0]) : 1}
        for c in s[1:]:
            o = ord(c)
            maxc = map.get(o, 0)
            for key, v in map.items():
                if abs(key - o) <= k:
                    tmp = v + 1
                    if tmp > maxc:
                        maxc = tmp
            map[o] = max(maxc, 1)
            # print(map)
        return max([v for v in map.values()])
 
C++: 
class Solution {
public:
    int longestIdealString(string const& s, int k) {
        int arr[26] = {}; // store for max subsequence so far
        for (char c : s) {
            int mx = 0; // max subsequence so far
            int idx = c - 'a';
            for (int i = max(0, idx - k); i < min(26, idx + k + 1); ++i)
                mx = max(mx, arr[i]);
            arr[idx] = max(mx, arr[idx]) + 1;
        }
        return *max_element(begin(arr), end(arr));
    }
};
 
mới sáng đọc đề là thấy giống Longest Increased Subsequence nên nghĩ dễ, tạo cái array dp có n phần tử ( n: length(s)), với mỗi dp = số phần tử của subsequence bắt đầu từ s. Làm thế éo nào lại ra TLE. Xong mới vào đây lén học đc cách là chỉ tạo mảng dp có 26 phần tử. Thế là học đc thêm một cách mới của dp :'( code lại thì beat 63% runtime

Python: 
class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        numbers = [ord(character) for character in s]
        print(numbers)
        dp = [0] * 26
        for i in range(len(s)-1,-1,-1):
            min_value  = max(0,numbers[i]-ord('a')-k)
            max_value  = min(25,numbers[i]-ord('a')+k)
            dp[numbers[i]-ord('a')] = max(dp[min_value:max_value+1])+1
        return max(dp)
 
Vấn đề với người mới giải là chưa tính toán được time complexity. Đề cho constrain 10^5 mà giải như Lis thì chắc chắn sẽ TLE vì time complexity sẽ là O(n^2) nên cách giải đó lúc implement sẽ ko chính xác.
Nói chung là kinh nghiệm để tìm cách giải phù hợp thôi.
Nhìn vào constrains thì nhiều lúc sẽ nhìn ra được cách giải luôn là nên xài algorithm gì.

via theNEXTvoz for iPhone
 
Tuần này toàn db, 2 contests cuối tuần toàn dp chắc chết
C++: 
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        vector<vector<int>> dp(n, vector<int>(m, INT_MAX));
        for(int i = 0; i < m;i+=1){
            dp[0][i] = grid[0][i];
        }
        for(int i = 1; i < n;i+=1){
            for(int j = 0; j < m;j+=1){
                for(int k = 0; k < m;k+=1){
                    if(j != k){
                        dp[i][j] = min(dp[i][j], dp[i - 1][k] + grid[i][j]);
                    }
                }
            }
        }

        return *min_element(begin(dp[n - 1]), end(dp[n - 1]));
    }
};
 
Code: 
import numpy as np

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if n == 1:
            return grid[0][0]
       
        dp = [0] * n
       
        for row in grid:
            # get two smallest number in dp
            np_dp = np.array(dp)
            ind = np_dp.argsort()[0:2]

            smallest_dp = dp[ind[0]]
            second_smallest_dp = dp[ind[1]]

            for i in range (n):
                if i == ind[0]:
                    dp[i] = row[i] + second_smallest_dp
                else:
                    dp[i] = row[i] + smallest_dp
       
        return min(dp)
 
Python: 
class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:

        m, n = len(grid), len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        MAX_VAL = 10**9+7

        for i in range(m):
            for j in range(n):
                chosen = MAX_VAL
                if i - 1 >= 0:
                    for k in range(n):
                        if k == j:
                            continue
                        chosen = min(chosen, dp[i-1][k])
                else:
                    chosen = 0
                
                if chosen == MAX_VAL:
                    chosen = 0
                dp[i][j] = chosen + grid[i][j]

        return min(dp[m-1])
bài hôm nay đọc ko kỹ đề submit sai 1 lần :beat_shot:
 

Similar threads

hatayquelua
thắc mắc Cần kiến thức gì để được nhận thực tập Dev
2 3
Replies
40
Views
1K
thapnhat111
thapnhat111
L
kiến thức 100 ngày tự học CNTT (AI&Data)
Replies
5
Views
368
vieethang
V
Build Back Better
  • Locked
Bỡn cợt cô giáo lớn tuổi trên TikTok, giới trẻ đang làm gì vậy?
6 7 8
Replies
154
Views
9K
Wind.G
Wind.G
trustnetvn
thảo luận Ríp tồ: Cho các Fan cuồng BTC, ETH
Replies
0
Views
92
trustnetvn
trustnetvn
T
thắc mắc Làm thế nào để tự động hóa việc thiết lập môi trường dev khi khởi động Windows?
Replies
15
Views
795
shazam
shazam

Share this page

Back
Top