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

C++: 
class Solution {
    vector<vector<vector<int>>> dp;
    const int MOD = 1000000007;
    int dfs(vector<vector<int>> &pizza_count, int k, int x, int y) {
        if (k == 1) return pizza_count[x][y] > 0;
        if (pizza_count[x][y] < k) return 0;
        if (dp[x][y][k] != -1) return dp[x][y][k];
        int ans = 0;
        for (int i = x + 1; i < pizza_count.size(); ++i) {
            if (pizza_count[x][y] > pizza_count[i][y]) {
                ans += (dfs(pizza_count, k - 1, i, y) % MOD);
                ans %= MOD;
            }
        }

        for (int j = y + 1; j < pizza_count[0].size(); ++j) {
            if (pizza_count[x][y] > pizza_count[x][j]) {
                ans += dfs(pizza_count, k - 1, x, j) % MOD;
                ans %= MOD;
            }
        }
        dp[x][y][k] = ans % MOD;
        return ans % MOD;
    }

public:
    int ways(vector<string>& pizza, int k) {
        auto n = pizza.size(), m = pizza[0].size();
        vector<vector<int>> pizza_count(n, vector<int>(m, 0));
        dp = vector<vector<vector<int>>>(n + 1, vector<vector<int>>(m + 1, vector<int>(k + 1, -1)));
        for (int x = n - 1; x >= 0; --x) {
            for (int y = m - 1; y >= 0; --y) {
                int a = (x + 1 < n)?pizza_count[x + 1][y]:0;
                int b = (y + 1 < m)?pizza_count[x][y + 1]:0;
                int c = (x + 1 < n && y + 1 < m)?pizza_count[x + 1][y + 1]:0;
                pizza_count[x][y] = a + b - c + (pizza[x][y] == 'A');
            }
        }

        return dfs(pizza_count, k, 0, 0);
    }
};
 
Symbiosis said:
Đọ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
Click to expand...
Bài tìm 1 số bị lặp kia chỉ O(n) và Space O(1) thôi thím.
 
JavaScript: 
/**
 * @param {string[]} pizza
 * @param {number} k
 * @return {number}
 */
var ways = function(pizza, k) {
    const MOD = 1e9 + 7;
    const m = pizza.length;
    const n = pizza[0].length;
    const ac = Array(m).fill().map(() => Array(n).fill());
    const getApples = (r, c) => {
        if (r >= m || c >= n) {
            return 0;
        }

        if (ac[r][c] === undefined) {
            ac[r][c] =
                (pizza[r][c] === 'A' ? 1 : 0)
                + getApples(r + 1, c)
                + getApples(r, c + 1)
                - getApples(r + 1, c + 1)
        }

        return ac[r][c];
    };

    const cc = Array(m).fill().map(
        () => Array(n).fill().map(
            () => Array(k + 1).fill()
        )
    );
    const getCC = (r, c, z) => {
        if (cc[r][c][z] === undefined) {
            if (z === 1) {
                cc[r][c][z] = getApples(r, c) > 0 ? 1 : 0;
            } else {
                cc[r][c][z] = 0;
                for (let t = r + 1; t < m; t++) {
                    if (getApples(r, c) > getApples(t, c)) {
                        cc[r][c][z] += getCC(t, c, z - 1);
                        cc[r][c][z] %= MOD;
                    }
                }
                for (let t = c + 1; t < n; t++) {
                    if (getApples(r, c) > getApples(r, t)) {
                        cc[r][c][z] += getCC(r, t, z - 1);
                        cc[r][c][z] %= MOD;
                    }
                }
            }
        }

        return cc[r][c][z];
    };

    return getCC(0, 0, k);
};
 
Đỡ nát hơn bài hôm qua, hôm nay viết tới đoạn viết suffix sum, còn kẹt khúc recursion chưa giải ra đúng, thôi ko giải được thì...khi khác giải vậy, kiếm bài dễ hơn, miễn cưỡng ko hạnh phúc =((

vouu0102 said:
Bài tìm 1 số bị lặp kia chỉ O(n) và Space O(1) thôi thím.
Click to expand...

Đúng rồi bạn, mình chỉ nói là tương tự cách tiếp cận, cái giải của mình là cho bài https://leetcode.com/problems/longest-cycle-in-a-graph/ nó là graph nên tốn space O(n)
 
may quá vẫn nhớ để làm hehe, có badge tháng 3 rồi
hkNtitg.png

JavaScript: 
function ways(pizza: string[], k: number): number {
  let m = pizza.length, n = pizza[0].length, mod = 10 ** 9 + 7;
  let counts = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
  let memo = Array(m).fill(0).map(() => Array(n).fill(0).map(() => Array(k + 1).fill(-1)));
  for (let i = m - 1; i >= 0; i--) {
    for (let j = n - 1; j >= 0; j--) {
      let curr = pizza[i][j] === 'A' ? 1 : 0;
      counts[i][j] = counts[i][j + 1] + counts[i + 1][j] - counts[i + 1][j + 1] + curr;
    }
  }
  return dp(0, 0, k);
 
  function dp(i: number, j: number, k: number) {
    if (k === 1) return counts[i][j] > 0 ? 1 : 0;
    if (counts[i][j] === 0) return 0;
    if (memo[i][j][k] !== -1) return memo[i][j][k];
    
    let ans = 0;
    for (let newRow = i; newRow < m - 1; newRow++) {
      if (counts[newRow + 1][j] === counts[i][j]) continue;
      ans = (ans + dp(newRow + 1, j, k - 1)) % mod;
    }
    for (let newCol = j; newCol < n - 1; newCol++) {
      if (counts[i][newCol + 1] === counts[i][j]) continue;
      ans = (ans + dp(i, newCol + 1, k - 1)) % mod;
    }
    return memo[i][j][k] = ans;
  }
};
 
JavaScript: 
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let l = 0, h = nums.length;
    while (l < h) {
        const m = (l + h) >> 1;
        if (nums[m] < target) {
            l = m + 1;
        } else {
            h = m;
        }
    }

    return nums[l] === target ? l : -1;
};
 
vl sau 1 tuần khó nhai thì tuần này lại cho bài ez nhất
qZV215Z.png

JavaScript: 
function search(nums: number[], target: number): number {
        let left = 0, right = nums.length - 1;
        
        while (left <= right) {
            let mid = left + Math.floor((right - left) / 2);
            if (nums[mid] == target) {
                return mid;
            }
            else if (nums[mid] < target) {
                left = mid + 1;   
            }
            else {
                right = mid - 1;
            }
        }
        
        return -1;
};
 
Time: O(logn)
Space: O(1)

Python: 
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums) - 1
        
        while left < right:
            mid = left + (right - left) // 2
            
            if nums[mid] == target:
                return mid
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
                
        return left if nums[left] == target else -1
 
JavaScript: 
/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
var successfulPairs = function(spells, potions, success) {
    let ans = new Array(spells.length);
    potions.sort((u, v) => v - u);
    spells.map((v, idx) => [v, idx]).sort((u, v) => v[0] - u[0]).forEach(([v, i]) => {
        while (potions.length > 0 && potions[potions.length-1] * v < success) {
            potions.pop();
        }
        ans[i] = potions.length;
    });

    return ans;
};
 
Java: 
class Solution {
  public int[] successfulPairs(int[] s, int[] potions, long success) {
    Arrays.sort(potions);
    int[] ans = new int[s.length];
    int N = potions.length;
    for (int i = 0; i < s.length; ++i) {
      int l=0, r=N-1;
      while (l <= r) {
        int m = l+r >> 1;
        if (1L*s[i]*potions[m] >= success) r = m-1;
        else l = m+1;
      }
      ans[i] = N-1-r;
    }
    return ans;
  }
}
 
Python: 
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        return [len(potions) - bisect_left(potions, success/i) for i in  spells]
 
thanbaiks said:
JavaScript: 
/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
var successfulPairs = function(spells, potions, success) {
    let ans = new Array(spells.length);
    potions.sort((u, v) => v - u);
    spells.map((v, idx) => [v, idx]).sort((u, v) => v[0] - u[0]).forEach(([v, i]) => {
        while (potions.length > 0 && potions[potions.length-1] * v < success) {
            potions.pop();
        }
        ans[i] = potions.length;
    });

    return ans;
};
Click to expand...
O(N^2) js vẫn nhận nhỉ
 
Python: 
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n, m = len(spells), len(potions)
        potions.sort()
        pairs = []
        import bisect

        for s in spells:
            target = math.ceil(success / s)
            idx = bisect.bisect_left(potions, target)
            pairs.append(len(potions) - idx)
        return pairs
 
n is length of spells, m is length of potions
Time: O(mlogm + nlogm)
Space (excluding the output): depending on the sorting implementation O(1) -> O(m)

For every spell, we search for the minimum potion that can form a successful pair, then all potions equal to or larger than that minimum can also form successful pairs.

Python: 
class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        potions.sort()
        m = len(potions)
        return [m - bisect.bisect_left(potions, math.ceil(success / spell)) for spell in spells]
 
Java: 
class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int[] ans = new int[spells.length];

        int i = 0;
        for (int spell : spells) {
            ans[i] = bs(spell, potions, success);
            i++;
        }

        return ans;
    }

    public int bs(int spell, int[] potions, long success) {
        long minProduct = (long) spell * (long) potions[0];
        long maxProduct = (long) spell * (long) potions[potions.length - 1];
        if (minProduct >= success) return potions.length;
        if (maxProduct < success) return 0;

        int low = 0;
        int high = potions.length - 1;
        int res = high;
        while (low < high) {
            int mid = low + (high - low)/2;
            long prod = (long)spell * (long) potions[mid];
            if (prod >= success) {
                res = mid;
                high = mid;
            } else {
                low = mid + 1;
            }
        }

        return potions.length - res;
    }
}
 

Similar threads

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

Share this page

Back
Top