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

JavaScript: 
function buildTree(inorder: number[], postorder: number[]): TreeNode | null {
    let map: Map<number, number> = new Map();
    for (let i = 0; i < inorder.length; i++) {
        map.set(inorder[i], i);
    }

    let build = function (start: number, end: number) {
        if (start > end) return null;
        const val = postorder.pop();
        const root = new TreeNode(val);
        root.right = build(map.get(val) + 1, end);
        root.left = build(start, map.get(val) - 1);
        return root;
    }

    return build(0, inorder.length - 1);
};
 
JavaScript: 
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    const ioi = {};
    inorder.forEach((v, idx) => ioi[v] = idx);

    const read = (instart, inend, poststart, postend) => {
        if (instart === inend) {
            return null;
        }

        const v = postorder[postend-1];
        const node = new TreeNode(v);
        const leftCount = ioi[v] - instart;
        const rightCount = inend - instart - leftCount - 1;
        node.left = read(instart, instart + leftCount, poststart, poststart + leftCount);
        node.right = read(instart + 1 + leftCount, instart + 1 + leftCount + rightCount, poststart + leftCount, poststart + leftCount + rightCount);

        return node;
    }

    return read(0, inorder.length, 0, inorder.length);
};
 
Code: 
fun buildTree(inorder: IntArray, postorder: IntArray): TreeNode? {
    if(inorder.isEmpty()) return null
    val rootVal = postorder.last()
    val indexOfRootNodeIO = inorder.indexOf(rootVal)
    val leftIO = inorder.copyOfRange(0, indexOfRootNodeIO)
    val leftPO = postorder.copyOfRange(0, indexOfRootNodeIO)
    val rightIO = inorder.copyOfRange(indexOfRootNodeIO + 1, inorder.size)
    val rightPO = postorder.copyOfRange(indexOfRootNodeIO, postorder.lastIndex)

    val root = TreeNode(rootVal)
    root.left = buildTree(leftIO, leftPO)
    root.right = buildTree(rightIO, rightPO)

    return root
}
 
Code: 
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        if (inorder.length == 1) return new TreeNode(postorder[0]);
        int rootVal = postorder[postorder.length - 1];
        int rootInorderIndex = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootVal) {
                rootInorderIndex = i;
                break;
            }
        }
        int[] LI = Arrays.copyOfRange(inorder, 0, rootInorderIndex); 
        int[] LP = Arrays.copyOfRange(postorder, 0, LI.length);
        int[] RI = Arrays.copyOfRange(inorder, rootInorderIndex + 1, inorder.length);
        int[] RP = Arrays.copyOfRange(postorder, LI.length, postorder.length - 1);

        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(LI, LP);
        root.right = buildTree(RI, RP);

        return root;
    }
}
 
1678969325361.png

bác nào cho em xin ý tưởng bài này với
eDEPIVR.gif
 
thì đi tới n chỉ có thể là từ n-1 đi lên bằng cách thêm 1 ký tự tốn X thời gian, hoặc từ n+1 đi xuống bằng cách loại 1 ký tự tốn Y thời gian, hoặc x2 số ký tự từ n/2 tốn Z thời gian, lấy min của 3 cái này thoy
WawmAwM.png

thêm T(0) = 0, T(số âm) = ko tính
osCpCsi.png



dp có lẽ code đơn giản hơn, nhưng mất công phải tìm cái maximum N' > N tại vì đi về N có thể phải đi từ N' xuống N. Vì N <= 100 nên cứ chọn N' = 128 là chắc cú. Vì sao là 128 thì do mỗi lần x2 tốn Z thời gian nên ví dụ nếu N=100 thì có thể chọn +1 tốn X được 1, x2 tốn Z được 2, x2 tốn Z được 4, x2 tốn Z được 8, ..., x2 tốn Z được 64, x2 tốn Z được 128, rồi -1 từ từ xuống 100 lại tốn 28Y, tổng X + 7Z + 28Y có thể là min, nên N' tối đa là 128. N' "động" cho từng trường hợp N thì nó là 2^ceil(log2(N))
pzGVwuf.png


ơ mà nếu đi n tăng từ từ mà nó thay đổi T(n-1) lại phải quay lại n-1 à :V chắc phải Dijkstra thoy
 
Last edited:
Spaghetti Code said:
thì đi tới n chỉ có thể là từ n-1 đi lên bằng cách thêm 1 ký tự tốn X thời gian, hoặc từ n+1 đi xuống bằng cách loại 1 ký tự tốn Y thời gian, hoặc x2 số ký tự từ n/2 tốn Z thời gian, lấy min của 3 cái này thoy
WawmAwM.png

thêm T(0) = 0, T(số âm) = ko tính
osCpCsi.png



dp có lẽ code đơn giản hơn, nhưng mất công phải tìm cái maximum N' > N tại vì đi về N có thể phải đi từ N' xuống N. Vì N <= 100 nên cứ chọn N' = 128 là chắc cú. Vì sao là 128 thì do mỗi lần x2 tốn Z thời gian nên ví dụ nếu N=100 thì có thể chọn +1 tốn X được 1, x2 tốn Z được 2, x2 tốn Z được 4, x2 tốn Z được 8, ..., x2 tốn Z được 64, x2 tốn Z được 128, rồi -1 từ từ xuống 100 lại tốn 28Y, tổng X + 7Z + 28Y có thể là min, nên N' tối đa là 128. N' "động" cho từng trường hợp N thì nó là 2^ceil(log2(N))
pzGVwuf.png


ơ mà nếu đi n tăng từ từ mà nó thay đổi T(n-1) lại phải quay lại n-1 à :V chắc phải Dijkstra thoy
Click to expand...
dijkstra thì đúng đấy, vì nó có đi lùi nên nhìn qua dp không được (để tìm i lại cần i+1). Cơ mà thực chất đi lùi từ i+1 về i là đi từ (i+1)/2 lên thêm cái delele+copy ((i+1)/2*2-1=i), nghĩa là đã tính rồi.
Công thức dp đây:
dp=min(dp[i-1]+insert,(i%2==0?dp[i/2]+copy:dp[(i+1)/2]+copy+delete))
2QMh0l8.png
 
Đảng viên Hanni said:
dijkstra thì đúng đấy, vì nó có đi lùi nên nhìn qua dp không được (để tìm i lại cần i+1). Cơ mà thực chất đi lùi từ i+1 về i là đi từ (i+1)/2 lên thêm cái delele+copy ((i+1)/2*2-1=i), nghĩa là đã tính rồi.
Công thức dp đây:
dp=min(dp[i-1]+insert,(i%2==0?dp[i/2]+copy:dp[(i+1)/2]+copy+delete))
2QMh0l8.png
Click to expand...
thặc khó hiểu thoy cứ Dijkstra cho lành
aVgiONl.png


để tránh cái vụ đi lùi phải tính lại thì có thể thấy vì X Y Z > 0 hết nên để đi lùi từ n+1 ít tốn thời gian hơn thì có thể nghĩ là n+1 phải là số chẵn, để x2 từ (n+1)/2 rồi lùi, vì nếu n+1 lẻ thì để có n+1 có thể đi từ n lên mà n lên rồi lùi lại thì tốn thêm X+Y vô ích. Nhưng mà n+1 cũng có thể lùi từ n+2 chẵn, vậy tới n+1 lẻ có thể là từ (n+2)/2*2 - 1
g8XXj8u.gif
tới đây toy bó tay thoy Dijkstra cho lành
aVgiONl.png


à phải chia ra 2 TH chẵn lẻ:

n lẻ = 2k + 1: min(T(2k) + X, T(k+1) + Z + Y)
đi từ n-1 lên hoặc đi từ n+1 xuống, ko có x2 vì n lẻ. Đi từ n+1 xuống để tránh vụ thay đổi n thì tính từ 2(k+1) - 1 là T(k+1) + Z + Y

n = 2k + 2: min(T(2k+1) + X, T(k+2) + Z + Y + Y, T(k+1) + Z)
đi từ n-1 lên hoặc đi từ n+1 xuống hoặc x2 lên. Đi từ n+1 xuống là 2k+3 xuống 1 thì đồng nghĩa với đi từ 2k+4 xuống trừ 2 lần nghĩa là T(k+2) + Z + Y + Y
DP kiểu lày khó thặc
0KSdPUp.png
 
Last edited:
Spaghetti Code said:
thặc khó hiểu thoy cứ Dijkstra cho lành
aVgiONl.png


để tránh cái vụ đi lùi phải tính lại thì có thể thấy vì X Y Z > 0 hết nên để đi lùi từ n+1 ít tốn thời gian hơn thì có thể nghĩ là n+1 phải là số chẵn, để x2 từ (n+1)/2 rồi lùi, vì nếu n+1 lẻ thì để có n+1 có thể đi từ n lên mà n lên rồi lùi lại thì tốn thêm X+Y vô ích. Nhưng mà n+1 cũng có thể lùi từ n+2 chẵn, vậy tới n+1 lẻ có thể là từ (n+2)/2*2 - 1
g8XXj8u.gif
tới đây toy bó tay thoy Dijkstra cho lành
aVgiONl.png


à phải chia ra 2 TH chẵn lẻ:

n lẻ = 2k + 1: min(T(2k) + X, T(k+1) + Z + Y)
đi từ n-1 lên hoặc đi từ n+1 xuống, ko có x2 vì n lẻ. Đi từ n+1 xuống để tránh vụ thay đổi n thì tính từ 2(k+1) - 1 là T(k+1) + Z + Y

n = 2k + 2: min(T(2k+1) + X, T(k+2) + Z + Y + Y, T(k+1) + Z)
đi từ n-1 lên hoặc đi từ n+1 xuống hoặc x2 lên. Đi từ n+1 xuống là 2k+3 xuống thì đi từ 2k+4 xuống trừ 2 lần nghĩa là T(k+2) + Z + Y + Y
DP kiểu lày khó thặc
0KSdPUp.png
Click to expand...

thế là dijkstra dễ hiêut hơn à bacd

Gửi từ Realme RMX3371 bằng vozFApp
 
chiyeuemthoi said:
View attachment 1721524
bác nào cho em xin ý tưởng bài này với
eDEPIVR.gif
Click to expand...
Bài này là dùng Dynamic Programming thì phải :LOL:
Không DP được, dính quả T từ T+1, chuyển qua BFS/Dijkstra :rolleyes: Trên LeetCode mấy ngày trước có bài tương tự.

Đơn giản thôi.
Tạo distance array d = new int [N+1]
Ban đầu set distance = INFINITY hết
d[1] = X
Tạo PriorityQueue, add {1, X} vào (1 là index, X là current min cost)
Mỗi lần poll ra index idx thì sẽ update distance và add tối đa 3 element mới cho insert/delete/copy (idx +1, idx -1 và idx * 2)
While loop break khi poll ra đúng index N hoặc queue empty (không xảy ra trường hợp empty queue trong bài này)
Output d[N] :LOL:
 
Last edited:
đầu tiên, tại vị trí i đang xét, chia mảng ra làm 2 phần. Từ 0 đến i-1 và từ i+1 đến n-1.
Giờ làm sao để 0->i-1 đi lên i+1->n-1? Không quan trọng quá trình, mà quan trọng thao tác cuối là gì, chắc chắn không phải delete, vì nếu delete là bước cuối thì không thể vượt qua i được, cũng không phải insert, vì nếu insert thì chỉ tối đa đến i thôi.
06wkMvn.png

ok vậy thao tác cuối là copy. Vậy tại sao ta chỉ quan tâm đến copy lên i+1? Vì sao không quan tâm i+3, i+5, i+7,...? (copy *2 luôn bằng chẵn vì vậy không có vụ i+2, i+4,... nhé). Ví dụ i+3, delete 2 lần về i+1, thì ở (i+3)/2, ta delete 1 lần là về (i+1)/2 rồi. Nói cách khác, thay vì phải delete x lần, ta chỉ cần quay về thao tác trước copy, delete x/2 lần. => Chỉ cần xét i+1.
9S282dK.png

Công thức dp ban đầu:
lẻ: dp=min(dp[i-1]+insert,dp[i+1]+delete)
chẵn: dp=min(dp[i-1]+insert,dp[i+1]+delete,dp[i/2]+copy)
(không thể qhđ)
tương đương:
lẻ: dp=min(dp[i-1]+insert,dp[(i+1)/2]+copy+delete)
chẵn: dp=min(dp[i-1]+insert,dp[i/2]+copy)
(có thể qhđ)
Spaghetti Code said:
thặc khó hiểu thoy cứ Dijkstra cho lành
aVgiONl.png


để tránh cái vụ đi lùi phải tính lại thì có thể thấy vì X Y Z > 0 hết nên để đi lùi từ n+1 ít tốn thời gian hơn thì có thể nghĩ là n+1 phải là số chẵn, để x2 từ (n+1)/2 rồi lùi, vì nếu n+1 lẻ thì để có n+1 có thể đi từ n lên mà n lên rồi lùi lại thì tốn thêm X+Y vô ích. Nhưng mà n+1 cũng có thể lùi từ n+2 chẵn, vậy tới n+1 lẻ có thể là từ (n+2)/2*2 - 1
g8XXj8u.gif
tới đây toy bó tay thoy Dijkstra cho lành
aVgiONl.png


à phải chia ra 2 TH chẵn lẻ:

n lẻ = 2k + 1: min(T(2k) + X, T(k+1) + Z + Y)
đi từ n-1 lên hoặc đi từ n+1 xuống, ko có x2 vì n lẻ. Đi từ n+1 xuống để tránh vụ thay đổi n thì tính từ 2(k+1) - 1 là T(k+1) + Z + Y

n = 2k + 2: min(T(2k+1) + X, T(k+2) + Z + Y + Y, T(k+1) + Z)
đi từ n-1 lên hoặc đi từ n+1 xuống hoặc x2 lên. Đi từ n+1 xuống là 2k+3 xuống 1 thì đồng nghĩa với đi từ 2k+4 xuống trừ 2 lần nghĩa là T(k+2) + Z + Y + Y
DP kiểu lày khó thặc
0KSdPUp.png
Click to expand...
 

Similar threads

nhbin
kiến thức Kèo Watch to earn 5p mỗi ngày $EVERY gọi vốn $60M từ A16Z, Coinbase, DragonFly
Replies
0
Views
102
nhbin
nhbin
Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
638
heocon0123
heocon0123
MasterchiefsReborn
Sinh viên than kiến tập mà làm việc không kịp ăn
2 3
Replies
47
Views
3K
OneThing
OneThing
domino123
kiến thức PixelTap by Pixelverse
Replies
0
Views
164
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
17
Views
445
truonggiang!
T

Share this page

Back
Top