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

Bonapart · Mar 26, 2023

Đọc đề làm liên tưởng ngay đến bài quái quỷ này https://leetcode.com/problems/find-the-duplicate-number nên làm theo kiểu giống vậy

Time: O(n)
Space: O(n)
Use tortoise and hare's algorithm to detect cycles and count the node in each cycle.

Python:

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        self.visited = set()
        self.edges = edges
        n = len(edges)
       
        maxCycle = -1
        for node in range(n):
            if node in self.visited:
                continue
               
            maxCycle = max(maxCycle, self.findCycle(node))
           
        return maxCycle
   
    def findCycle(self, node):
        slow = node
        fast = node
       
        cycle = False
        visited = set()
        visited.add(slow)
        while self.edges[fast] != -1 and self.edges[self.edges[fast]] != -1:
            slow = self.edges[slow]
            fast = self.edges[self.edges[fast]]
            visited.add(slow)
            visited.add(fast)
           
            if slow in self.visited or fast in self.visited:
                break
           
            if slow == fast:
                cycle = True
                break
       
        if not cycle:
            for node in visited:
                self.visited.add(node)
               
            return -1
       
        slow = node
        while slow != fast:
            slow = self.edges[slow]
            fast = self.edges[fast]
            visited.add(fast)
           
        count = 1
        curr = self.edges[slow]
        while curr != slow:
            curr = self.edges[curr]
            count += 1
           
        for node in visited:
            self.visited.add(node)
           
        return count

Mình có hướng làm giống thím mà vẫn đang bị TLE ở test case gần cuối :3

Shinedo9820 · Mar 27, 2023

Mình thấy câu này ở mức medium thôi. Chia sẻ chút về cách làm của mình:

1. Lặp qua các node trong graph, nếu nó đã được duyệt thì bỏ qua.
2. Nếu node chưa được duyệt thì men theo node cha và:
- Đánh dấu đã duyệt cho các node.
- Đánh thứ tự duyệt (th) cho các node.
- Đánh dấu node bắt đầu (nstart) cho các node.
3. Trong quá trình đi theo node cha nếu gặp được node đã duyệt (dnode) thì so sánh với node hiện tại (cnode) xem là node bắt đầu (nstart) có giống nhau không.
- Nếu giống thì lưu kết quả lại: res = th(dnode) - th(cnode) + 1
4. Trả về kết quả res lớn nhất.

Code:

func longestCycle(edges []int) int {
    visitedAtCount := make([]int, len(edges))
    visitedAtIndex := make([]int, len(edges))
    res := -1

    for i, _ := range edges {
        if visitedAtCount[i] > 0 {
            continue
        }

        count := 0
        prev_i := i
        _i := edges[i]

        for _i != -1 && visitedAtCount[_i] == 0 {
            count = count + 1
            visitedAtCount[_i] = count
            visitedAtIndex[_i] = i
            prev_i = _i
            _i = edges[_i]
        }

        if _i == -1 || visitedAtIndex[prev_i] != visitedAtIndex[_i] {
            continue
        }

        cres := visitedAtCount[prev_i] - visitedAtCount[_i] + 1
        if cres > 0 && cres > res {
            res = cres
        }
    }

    return res
}

nchhnchh · Mar 27, 2023

Python:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = []
        for i in range(m):
            dp.append([])
            for j in range(n):
                dp[-1].append(0)
        
        dp[0][0] = grid[0][0]

        for i in range(1, m):
            dp[i][0] = dp[i-1][0] + grid[i][0]
        for j in range(1, n):
            dp[0][j] = dp[0][j-1] + grid[0][j]
        

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
        
        return dp[m-1][n-1]

Symbiosis · Mar 27, 2023

Time: O(n * m)
Space: O(n * m)

Using standard DP, either bottom-up or top down, the idea is that the min cost to reach a cell (i, j) is either the min cost of reaching its left (i, j-1) or its top (i-1, j) + its own cost

minCosts[(i, j)] = min(minCosts[(i-1, j)], minCosts[(i, j-1)]) + grid[(i,j)]

Python:

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int: 
        n = len(grid)
        m = len(grid[0])
      
        minCosts = {}
        for row in range(n):
            for col in range(m):
                topCost = float('inf')
                leftCost = float('inf')
                if row > 0:
                    topCost = minCosts[(row-1, col)]
                  
                if col > 0:
                    leftCost = minCosts[(row, col-1)]
                  
                if topCost == float('inf') and leftCost == float('inf'):
                    topCost = 0
              
                minCosts[(row, col)] = min(topCost, leftCost) + grid[row][col]
 
        return minCosts[(n-1, m-1)]

Symbiosis · Mar 27, 2023

Bonapart said:
Mình có hướng làm giống thím mà vẫn đang bị TLE ở test case gần cuối :3

Hehe, tui cũng bị TLE ở lần submit đầu tiên do tính chưa kỹ cái visited làm time complexity trở thành O(n^2), sửa chút là nó pass. Ban đầu tui tính lờ mờ làm topological sorting (nhưng ko nhớ rõ giải thuật) nên nghĩ chút lại thử theo kiểu rùa và thỏ.

Bài hôm qua có thể xem như một câu hỏi interview khá tốt: có thể tiếp cận với những giải thuật khác nhau, độ khó tương đối để làm xong trong thời gian trung bình 30p (nếu biết cách làm).

anoldvozer1710.v2 · Mar 27, 2023

JavaScript:

function minPathSum(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const dp = Array.from({length: m}, e => Array(n).fill(0));
    dp[0][0] = grid[0][0]

    for (let i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + grid[i][0]
    }

    for (let j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + grid[0][j]
    }
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1])
        }
    }

    return dp[m-1][n-1];
};

NahSama · Mar 27, 2023

Code:

class Solution {
    public int minPathSum(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];
        dp[0][0] = grid[0][0];

        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++){
                if (row == 0 && col == 0) continue;
                if (row == 0) {
                    dp[row][col] = grid[row][col] + dp[row][col - 1];
                    continue;
                }

                if (col == 0) {
                    dp[row][col] = grid[row][col] + dp[row - 1][col];;
                    continue;
                }

                dp[row][col] = Math.min(dp[row][col - 1], dp[row - 1][col]) + grid[row][col];
            }
        }

        return dp[grid.length - 1][grid[0].length - 1];
    }
}

thanbaiks · Mar 27, 2023

JavaScript:

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minPathSum = function(grid) {
    const m = grid.length,
          n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (!i && !j) {
                continue;
            }

            grid[i][j] += Math.min(
                i > 0 ? grid[i-1][j] : +Infinity,
                j > 0 ? grid[i][j-1] : +Infinity,
            )
        }
    }
    
    return grid[m-1][n-1];
};

Shinedo9820 · Mar 27, 2023

Cách rút gọn nhất của mình

Code:

int minPathSum(int** grid, int m, int* n) {
    for (int i = 0; i < m; i++)
        for (int j = 0; j < (*n); j++)
            if(i == 0 && j == 0) continue;
            else if(i > 0 && j == 0)
                grid[i][j] += grid[i-1][j];
            else if(j > 0 && i == 0)
                grid[i][j] += grid[i][j-1];
            else if(grid[i-1][j] > grid[i][j-1])
                grid[i][j] += grid[i][j-1];
            else
                grid[i][j] += grid[i-1][j];
    return grid[m-1][(*n)-1];
}

dark_matter · Mar 27, 2023

Java:

class Solution {
    int[][] min;
    public int minPathSum(int[][] grid) {
        int height = grid.length;
        int width = grid[0].length;
        min = new int[height][width];
        min[0][0] = grid[0][0];

        for(int i = 0; i < height; i++) {
            for(int j = 0; j < width; j++) {
                if (i > 0 && j > 0) {
                    min[i][j] = Math.min(min[i-1][j], min[i][j-1]) + grid[i][j];
                }
                else if (i > 0) {
                    min[i][j] = min[i-1][j] + grid[i][j];
                }
                else if (j > 0) {
                    min[i][j] = min[i][j-1] + grid[i][j];
                }
            }
        }


        return min[height-1][width-1];
    }
}

NahSama · Mar 28, 2023

Tuan nay chac toan dp

Code:

class Solution {
    public int mincostTickets(int[] days, int[] costs) {
        int[] dp = new int[366];
        boolean[] isTraveling = new boolean[366];
        for (int day : days) {
            isTraveling[day] = true;
        }
        for (int i = 1; i <= 365; i++) {
            if (!isTraveling[i]) {
                dp[i] = dp[i-1];
                continue;
            }
            int min7 = i - 7 >= 0 ? dp[i - 7] : 0;
            int min30 = i - 30 >= 0 ? dp[i - 30] : 0;
            int min = Math.min(dp[i - 1] + costs[0], min7 + costs[1]);
            min = Math.min(min, min30 + costs[2]);
            dp[i] = min;
        }
      
        return dp[days[days.length - 1]];
    }
}

anoldvozer1710.v2 · Mar 28, 2023

JavaScript:

function mincostTickets(days: number[], costs: number[]): number {
    const maxDay = days[days.length -1];
    let dp = new Array( maxDay + 1).fill(0);
    const set: Set<number> = new Set();
    for (const day of days) {
        set.add(day);
    }

    for (let i = 1; i < dp.length; i++) {
        if (set.has(i)) {
            dp[i] = Math.min(dp[Math.max(i-1, 0)] + costs[0], dp[Math.max(i-7, 0)] + costs[1], dp[Math.max(i-30, 0)] + costs[2])
        } else {
            dp[i] = dp[i-1];
        }
    }

    return dp[dp.length - 1]


};

afatnan · Mar 28, 2023

C++:

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int dp[days.back() + 1];
        memset(dp, 0, sizeof(dp));
        dp[days[0]] = min(costs[0], min(costs[1], costs[2]));
        for(int i = 1; i < days.size(); ++i){
            int cur = days[i], pas = days[i - 1];
            for(int j = pas + 1; j < cur; ++j) dp[j] = dp[pas];
            dp[cur] = min(dp[cur - 1] + costs[0], min(dp[max(0, cur - 7)] + costs[1], dp[max(0, cur - 30)] + costs[2]));
        }
        return dp[days.back()];
    }
};

Symbiosis · Mar 28, 2023

Time: O(n)
Space: O(1) as two queues can never have more than 7 and 30 elements

Idea: DP https://leetcode.com/problems/minimum-cost-for-tickets/discuss/226659/Two-DP-solutions-with-pictures

Python:

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:
        cost = 0
        
        queue7 = deque([])
        queue30 = deque([])
        
        for day in days:
            while len(queue7) > 0 and (queue7[0][0] + 7) <= day:
                queue7.popleft()
            while len(queue30) > 0 and (queue30[0][0] + 30) <= day:
                queue30.popleft()
            
            queue7.append((day, cost + costs[1]))
            queue30.append((day, cost + costs[2]))
            
            cost = min(cost + costs[0], queue7[0][1], queue30[0][1])
        
        return cost

Shinedo9820 · Mar 29, 2023

Mới học giải thuật chưa ôn kỹ kiến thức, gặp bài này lú cả buổi

Code:

func min(a int, b int, c int) int {
    if a > b {
        a, b = b, a
    }
    if a > c {
        a, c = c, a
    }
    return a
}

func mincostTickets(days []int, costs []int) int {
    n := len(days)

    // return calCost(days, costs, n-1)

    res := make([]int, 3)
    res[0] = min(costs[0], costs[1], costs[2])

    for i := 1; i < n; i++ {
        var (
            pwind  int = -1
            pmind  int = -1
            pwcost int = 0
            pmcost int = 0
        )

        for j := i - 1; j >= 0; j-- {
            if days[i]-days[j]+1 > 7 && pwind == -1 {
                pwind = j
            }
            if days[i]-days[j]+1 > 30 && pmind == -1 {
                pmind = j
            }
        }

        if pwind >= 0 {
            pwcost = res[pwind]
        }

        if pmind >= 0 {
            pmcost = res[pmind]
        }

        res[i] = min(
            costs[0]+res[i-1],
            costs[1]+pwcost,
            costs[2]+pmcost,
        )
    }

    return res[n-1]
}

callmemark · Mar 29, 2023

DP is coming

Python:

class Solution:
    def mincostTickets(self, days: List[int], costs: List[int]) -> int:

        @lru_cache(None)
        def dp(i, end_date):
            if i == len(days):
                return 0
            if end_date > days[i]:
                return dp(i+1, end_date)
            else:
                return min(
                    costs[0] + dp(i+1, days[i] + 1),
                    costs[1] + dp(i+1, days[i] + 7),
                    costs[2] + dp(i+1, days[i] + 30)
                )
        
        return dp(0, 0

anoldvozer1710.v2 · Mar 29, 2023

Bài này đã từng làm từ trước. Không nghĩ là hard

JavaScript:

function maxSatisfaction(satisfaction: number[]): number {
    satisfaction = satisfaction.sort((a,b) => a-b);
        let ans = 0, total = 0, length = satisfaction.length;
        for (let i = length - 1; i >= 0 && satisfaction[i] > -total; i--) {
            total += satisfaction[i];
            ans += total;
        }
        return ans

};

Bonapart · Mar 29, 2023

Không nghĩ bài này đến mức hard

Java:

fun maxSatisfaction(satisfaction: IntArray): Int {
        satisfaction.sort()
        var result = 0
        var suffixSum = 0
        for (i in satisfaction.indices) {
            result += satisfaction[i] * (i + 1)
            suffixSum += satisfaction[i]
        }
        for (s in satisfaction) {
            result = maxOf(result, result - suffixSum)
            suffixSum -= s
        }
        return result
    }

NahSama · Mar 29, 2023

Code:

class Solution {
    public int maxSatisfaction(int[] satisfaction) {
        Arrays.sort(satisfaction);
        
        int prevSum = 0;
        int total = 0;
        int max = 0;
        
        for (int i = satisfaction.length - 1; i >= 0; i--) {
            prevSum += satisfaction[i];
            total += prevSum;
            max = Math.max(max, total);
        }
        
        return max;
    }
}

seastar · Mar 29, 2023

29/03: Bài này từng làm rồi, viết lại 1 dòng, 8-)

Python:

return reduce(lambda acc, x: [sum(acc) + x if acc[1] + x > 0 else acc[0], acc[1] + x], sorted(satisfaction, reverse=True), [0, 0])[0]

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

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Senior Member

Senior Member

Member

Similar threads

Share this page