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

  • Người tạo chủ đề Người tạo chủ đề Vipluckystar
  • Ngày bắt đầu Ngày bắt đầu
Python: 
class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        def isSquare(n: int) -> bool:
            return math.isqrt(n) ** 2 == n

        # pre compute the list for each number from 1->n
        squares = defaultdict(list[int])
        squares[0] = []
        for i in range(1, n + 1):
            squares[i] = copy.deepcopy(squares[i - 1])
            if isSquare(i):
                squares[i].append(i)
        # the optimal strategy: player try to have the next turn of the them the piles would have a square number of it
        # means each player will try to make the next turn not have a square number
        dp = [False] * (n + 1)
        for i in range(1, n + 1):
            if isSquare(i):
                dp[i] = True
                continue
            result = False
            for square in squares[i]:
                if not isSquare(i - square):
                    result = result or (not dp[i - square])
            dp[i] = result

        return dp[n]
Méo mó có còn hơn không :shame:
1786344204353.webp


Update: tối ưu bằng cách k pre computed nữa
Python: 
class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        def isSquare(n: int) -> bool:
            return math.isqrt(n) ** 2 == n

        # the optimal strategy: player try to have the next turn of the them the piles would have a square number of it
        # means each player will try to make the next turn not have a square number
        dp = [False] * (n + 1)
        for i in range(1, n + 1):
            if isSquare(i):
                dp[i] = True
                continue
            k = 1
            while k * k < i:
                if not isSquare(i - k * k) and not dp[i - k * k]:
                    dp[i] = True
                    break
                k += 1

        return dp[n]
1786359015350.webp
 
Sửa lần cuối:
bài này thấy dễ hơn bài hôm trước
Y9XGQJi.png

JavaScript: 
function winnerSquareGame(n: number): boolean {
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        let k = Math.floor(Math.sqrt(i));
        for (let j = k; j >= 1; j--) {
            if (!dp[i - j * j]) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n]
};
 
Python: 
class Solution:
    def missingInteger(self, nums: List[int]) -> int:
        sum_seq = nums[0]
        i = 1
        while i < len(nums) and nums[i] == nums[i - 1] + 1:
            sum_seq += nums[i]
            i += 1
        
        res = sum_seq
        set_nums = set(nums)
        while res in set_nums:
            res += 1
        
        return res
 
JavaScript: 
function missingInteger(nums: number[]): number {
    const set = new Set();
    for (let i = 0; i < nums.length; i++) {
        set.add(nums[i]);
    }
    let cur = nums[0]
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] === nums[i - 1] + 1) cur+= nums[i];
        else break;
    }
    for (let i = cur; i <= 2500; i++) {
        if (!set.has(i)) return i;
    }
    return -1;
};
 
Python: 
class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        # in the window, every element <= k, meaning that if a element inside the window freq > k, we need to minimize the window

        count = Counter()
        l, res = 0, 0

        for r in range(len(nums)):
            count[nums[r]] += 1
            while count[nums[r]] > k:
                count[nums[l]] -= 1
                l += 1
            res = max(res, r - l + 1)
        return res
 
JavaScript: 
function maxSubarrayLength(nums: number[], k: number): number {
    let count = 1, start =0, end = 0, map = new Map<number, number>();
    while(end < nums.length) {
        map.set(nums[end], (map.get(nums[end]) || 0) + 1);
        while(map.get(nums[end]) > k) {
            map.set(nums[start], map.get(nums[start]) - 1);
            start++;
        }
        count = Math.max(count, end - start + 1)
        end++
    }
    return count;
};
 
Python: 
class Solution:
    def maxSubarrayLength(self, nums: List[int], k: int) -> int:
        i, j = 0, 0
        max_dict = defaultdict(list[int])
        n = len(nums)
        res = 0
        count = 0
        while i < n and j < n:
            key = nums[j]
            max_dict[key].append(j)
            if max_dict[key][0] < i:
                max_dict[key] = [x for x in max_dict[key] if x >= i]
            if len(max_dict[key]) > k:
                i = max_dict[key][0] + 1
                max_dict[key] = max_dict[key][1:]
                count = j - i
            count += 1
            res = max(res, count)
            j += 1
       
        return res
 
Sửa lần cuối:
C++: 
class Solution {
    public:
        int maxSubarrayLength(const std::vector<int> &nums, const int &k) {
            const int n = nums.size();
            if (n == 1) return n;

            int a = 0, l = 0, r = 0;
            std::unordered_map<int, int> b;

            while (r < n) {
                if (b.find(nums[r]) == b.end()) {
                    b.emplace(nums[r], 1);
                }
                else if (b[nums[r]] < k) {
                    b[nums[r]]++;
                }
                else if (b[nums[r]] == k) {
                    while (nums[l] != nums[r]) {
                        b[nums[l]]--;
                        l++;
                    }
                    b[nums[l]]--;
                    l++;
                    b[nums[r]]++;
                }

                a = std::max(a, r - l + 1);
                r++;
            }
            return a;
        }
};
 
Bài 2 hôm trước nhưng với k = 2 lol
Python: 
class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        i, j = 0, 0
        max_dict = defaultdict(list[int])
        n = len(s)
        res = 0
        count = 0
        while i < n and j < n:
            key = s[j]
            max_dict[key].append(j)
            if max_dict[key][0] < i:
                max_dict[key] = [x for x in max_dict[key] if x >= i]
            if len(max_dict[key]) > 2:
                i = max_dict[key][0] + 1
                max_dict[key] = max_dict[key][1:]
                count = j - i
            count += 1
            res = max(res, count)
            j += 1
        
        return res
 
JavaScript: 
function maximumLengthSubstring(s: string, k = 2): number {
    let count = 1, start =0, end = 0, map = new Map<string, number>();
    while(end < s.length) {
        map.set(s[end], (map.get(s[end]) || 0) + 1);
        while(map.get(s[end]) > k) {
            map.set(s[start], map.get(s[start]) - 1);
            start++;
        }
        count = Math.max(count, end - start + 1)
        end++
    }
    return count;   
};
 
C-like: 
func maximumLengthSubstring(s string) int {
    var count [26]int
    left, right, res := 0, 0, 0
    for left <= right && right < len(s) {
        count[s[right] - 'a']++
        isValid := false
        for isValid == false {
            for _, c := range count {
                if c > 2 {
                    count[s[left] - 'a']--
                    left++
                    break
                }
                isValid = true
            }
        }
        if res < (right - left + 1) {
            res = right - left + 1
        }
        right++
    }
    return res
}


func maximumLengthSubstring(s string) int {
    var count [26]int
    left, right, res := 0, 0, 0
    for left <= right && right < len(s) {
        count[s[right] - 'a']++
        for count[s[right] - 'a'] > 2 {
            count[s[left] - 'a']--
            left++
        }
        res = max(res, right - left + 1)
        right++
    }
    return res
}
 
Sửa lần cuối:
C++: 
class Solution {
    public:
        int maximumLengthSubstring(const std::string &s) {
            const int n = s.size();
            int a = 0;
            int l = 0, r = 0;
            std::unordered_map<int, int> b;

            while (r < n) {
                if (b.find(s[r]) == b.end()) {
                    b[s[r]] = 1;
                }
                else if (b[s[r]] == 2) {
                    while (s[l] != s[r]) {
                        b[s[l]]--;
                        l++;
                    }
                    l++;
                }
                else b[s[r]]++;
                a = std::max(a, r - l + 1);
                r++;
            }
            return a;
        }
};
 
Python: 
class Solution:
    def longestSubsequence(self, nums: List[int]) -> int:
        n = len(nums)
        set_n = set(nums)
        if len(set_n) == 1:
            if 0 in set_n:
                return 0
        prod = functools.reduce(lambda x, y: x ^ y, nums[1:n], nums[0])
        return n if prod != 0 else n - 1
 
C++: 
class Solution {
    public:
        int longestSubsequence(std::vector<int> &nums) {
            int a = 0, b = 0;
            for (int &i: nums) {
                a ^= i;
                b |= i;
            }
            if (b == 0) return 0;
            return nums.size() - !a;
        }
};
 
Mã: 
func longestSubsequence(nums []int) int {
    xor:=0
    for _,num:=range nums{
        xor^=num
    }
    if xor !=0 {
        return len(nums)
    }
    for _,num:=nums{
        if xor^num !=0{
            return len(nums)-1
        }
    }
    return 0
}
 
Mấy anh cho em xin hỏi khi đi phỏng vấn thường ra những dạng thuật toán nào vậy ạ. Em đang tính nhảy công ty mà mấy công ty đầu em không chỗ nào phỏng vấn thuật toán hết nên lúc đó em không tìm hiểu.
 
k thoát khỏi được bruteforce :ROFLMAO:
Python: 
class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        # if they not equal then keep doing so and accumulate
        # if equal then spawn recursion to see which one return the bigger result and keep doing so
        # a 2D dp for storing sum from i to j
        n = len(stoneValue)
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(i, n):
                if j == i:
                    dp[i][j] = stoneValue[j]
                else:
                    dp[i][j] = dp[i][j - 1] + stoneValue[j]

        @cache
        def rec(l: int, r: int) -> int:
            # if take the left => r update to i
            # if take the right => l update to i + 1
            if l == r:
                return 0
            result = 0
            for i in range(l, r):
                left, right = dp[l][i], dp[i + 1][r]
                if left < right:
                    result = max(result, left + rec(l, i))
                elif right < left:
                    result = max(result, right + rec(i + 1, r))
                else:
                    result = max(result, left + rec(l, i), right + rec(i + 1, r))
            return result

        return rec(0, n - 1)
 
NgoaLong66 đã nói:
Mấy anh cho em xin hỏi khi đi phỏng vấn thường ra những dạng thuật toán nào vậy ạ. Em đang tính nhảy công ty mà mấy công ty đầu em không chỗ nào phỏng vấn thuật toán hết nên lúc đó em không tìm hiểu.
Nhấp để mở rộng...
chắc tuỳ gu interviewer th thím, cty hiện tại hồi pv cũng méo có hỏi algo nên sắp pv em cũng chả biết, mở leetcode ôn đại th
 
Bạn phải đăng nhập hoặc đăng ký để trả lời tại đây.

Chủ đề tương tự

saigon2026
thắc mắc Lập thread mới tiếp nối thread cũ có bị coi là vi phạm không?
Trả lời
3
Lượt xem
1K
shinichi Kudo1221
shinichi Kudo1221
P
Người trẻ ngủ 12 tiếng mỗi ngày: Liệu có phải bệnh?
2 3
Trả lời
41
Lượt xem
4K
Rheinmetall
Rheinmetall
Thach Sanh Mat Riu
Điều gì xảy ra nếu bạn uống nước chè xanh mỗi ngày?
2
Trả lời
22
Lượt xem
2K
dattenmoi
D
Gấu Ted
Độc giả ngày càng tin nhà báo hơn thương hiệu báo chí
Trả lời
10
Lượt xem
887
giayasics
giayasics
Claude_User
[THỬ THÁCH] 100 ngày giảm cân
6 7 8
Trả lời
158
Lượt xem
9K
sonomi102
sonomi102

Thống kê chủ đề

Ngày tạo
Vipluckystar,
Người trả lời cuối
Holo code dạo,
Trả lời
7.740
Lượt xem
455.998

Chia sẻ trang này

Quay lại
Lên đầu trang