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

NahSama · Mar 19, 2023

Code:

class WordDictionary {
    TrieNode root;
   
    public WordDictionary() {
        root = new TrieNode();
    }
   
    public void addWord(String word) {
        root.add(word);
    }
   
    public boolean search(String word) {
        char[] ch = word.toCharArray();
        return search (ch, root, 0);
    }
   
    public boolean search(char[] chars, TrieNode node, int index) {
        if (index == chars.length) return node.isWord;
       
       
        if (chars[index] != '.'){
            return node.kids[chars[index] - 'a'] != null && search(chars, node.kids[chars[index] - 'a'], index + 1);
        } else {
            for (TrieNode kid : node.kids) {
                if (kid != null && search(chars, kid, index+1)) return true;
            }
            return false;
        }
    }
   
    class TrieNode {
        public boolean isWord;
        public TrieNode[] kids;
        public TrieNode() {
            this.kids = new TrieNode[26];
            isWord = false;
        }
       
        public void add(String s) {
            char[] chars = s.toCharArray();
            TrieNode curr = this;
           
            for (int i = 0; i < chars.length; i++) {
                if (curr.kids[chars[i] - 'a'] == null) {
                    curr.kids[chars[i] - 'a'] = new TrieNode();
                }
               
                curr = curr.kids[chars[i] - 'a'];
            }
            curr.isWord = true;
        }
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

thanbaiks · Mar 19, 2023

JavaScript:

class WordDictionary {
    root = {};

    addWord(word) {
        let node = this.root;
        for (const ch of word) {
            node[ch] ??= {};
            node = node[ch];
        }

        node.$ = true;
    }

    search(word) {
        let nodes = [this.root];
        for (const ch of word) {
            if (!nodes.length) {
                return false;
            }

            let next = [];
            if (ch === '.') {
                for (const node of nodes) {
                    next.push(...Object.values(node).filter(it => typeof it === 'object'));
                }
            } else {
                next.push(...nodes.map(it => it[ch]).filter(Boolean));
            }
            nodes = next;
        }


        return nodes.some(it => it.$);
    }
}

anoldvozer1710.v2 · Mar 19, 2023

JavaScript:

class TrieNode {
    children: Map<string, TrieNode>
    isWord: boolean
    constructor() {
        this.children = new Map();
        this.isWord = false;
    }

}

class WordDictionary {
    root: TrieNode
    constructor() {
        this.root = new TrieNode()
    }

    addWord(word: string): void {
        const add = (node: TrieNode, index: number) => {
            if (index === word.length) return node.isWord = true;
            if (!node.children.has(word[index])) {
                node.children.set(word[index], new TrieNode())
            };
            add(node.children.get(word[index]), index + 1);
        }
        add(this.root, 0);
    }

    search(word: string): boolean {
        const find = (node: TrieNode, index: number) => {
            if (index === word.length && node.isWord) return true;
            if (index === word.length) return false;

            if (word[index] === '.') {
                for (const [key, next] of node.children) {
                    if (find(next, index + 1)) return true;
                }
                return false;
            }
            if (!node.children.has(word[index])) return false;
            return find(node.children.get(word[index]), index + 1);
        }
        return find(this.root, 0);
    }
}

Aristides · Mar 19, 2023

bài này là sequel của bài 2 ngày trước thì phải

Java:

class WordDictionary {
    private Node root;
    public WordDictionary() {
        root = new Node();
    }
    
    public void addWord(String word) {
        Node ptr = root;
        for(char c : word.toCharArray()){
            if(ptr.containsKey(c) == false){
                ptr.put(c, new Node());
            }
            ptr = ptr.get(c);
        }
        ptr.setEnd(true);
    }
    
    public boolean search(String word) {
        return this.dfs(0, word, this.root);       
    }
    private boolean dfs(int i, String word, Node curr){
        if(curr == null){
            return false;
        }
        if(i == word.length()){
            return curr.isEnd();
        }
        char c = word.charAt(i);
        if(c == '.'){
            for(int j = 0; j < 26; j++){
                if(this.dfs(i + 1, word, curr.get((char)(j + 'a')))){
                    return true;
                }
            }
            return false;
        }
        else if(curr.containsKey(c)){
            return dfs(i + 1, word, curr.get(c));
        }
        return false;
    }
}
class Node {
    private Node[] child;
    private boolean end;
    public Node(){
        child = new Node[26];
        end = false;
    }
    public boolean containsKey(char c){
        return child[c - 'a'] != null;
    }
    public void put(char c, Node n){
        child[c - 'a'] = n;
    }
    public boolean isEnd(){
        return end;
    }
    public Node get(char c){
        return child[c - 'a'];
    }
    public void setEnd(boolean value){
        this.end = value;
    }
}
/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */

callmemark · Mar 20, 2023

Python:

 def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        for i, p in enumerate(flowerbed):
            if p == 0:
                prev_i = i - 1
                next_i = i + 1
                if prev_i >= 0 and next_i < len(flowerbed):
                    if flowerbed[prev_i] == 0 and flowerbed[next_i] == 0:
                        flowerbed[i] = 1
                        n -= 1
                elif prev_i >= 0:
                    if flowerbed[prev_i] == 0:
                        flowerbed[i] = 1
                        n -= 1
                elif next_i < len(flowerbed):
                    if flowerbed[next_i] == 0:
                        flowerbed[i] = 1
                        n -= 1
                else:
                    n -= 1
        
        return n <= 0

Symbiosis · Mar 20, 2023

Bài hôm nay giải nhanh bằng DP cơ bản, nhưng đọc LC solution thì greedy là đủ, nhưng lại ko có proof of correctness.

Tui nghĩ ko biết viết proof thì chắc ăn cứ DP mà táng thui

Time: O(n)
Space: O(n)

Python:

class Solution1:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        self.flowerbed = flowerbed
        self.size = len(flowerbed)
        self.n = n
        
        self.cache = defaultdict(int)
        self.possible = False
        
        self.dfs(0)
        
        return self.possible
        
    def dfs(self, idx):
        if idx == self.size:
            return 0
        
        if self.possible:
            return 0
        
        if idx in self.cache:
            return self.cache[idx]
        
        before = idx == 0 or self.flowerbed[idx-1] == 0
        after = idx == self.size - 1 or self.flowerbed[idx+1] == 0
        current = self.flowerbed[idx] == 0
        
        plantable = before and current and after
        
        res = 0
        if plantable:
            self.flowerbed[idx] = 1
            res = 1 + self.dfs(idx + 1)
            self.flowerbed[idx] = 0
        
        res = max(res, self.dfs(idx + 1))
        
        self.cache[idx] = res
        
        if res >= self.n:
            self.possible = True
        
        return res

bribnt · Mar 20, 2023

Symbiosis said:
Bài hôm nay giải nhanh bằng DP cơ bản, nhưng đọc LC solution thì greedy là đủ, nhưng lại ko có proof of correctness.

Tui nghĩ ko biết viết proof thì chắc ăn cứ DP mà táng thui

Làm chi mà phức tạp vậy.
Với bài này ta thấy nếu đặt được x hoa thì cũng có thể đặt được y < x hoa. Như vậy chỉ cần tìm cách đặt nhiều nhất có thể rồi so sánh với n.
Cách đếm là đếm riêng lẻ số cách đặt hoa giữa hai vị trí đã chiếm chỗ sẵn có có ban đầu, công thức là (d - 2) / 2. Để ý đầu / cuối nữa là được.

C++:

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int last1 = -2;
        for (int i = 0; i < flowerbed.size(); ++i) {
            if (flowerbed[i] == 1) {
                n -= max(0, (i - last1 - 2) / 2);
                last1 = i;
            }
        }
        return (n - max<int>(0, (flowerbed.size() - last1 - 1) / 2)) <= 0;
    }
};

NahSama · Mar 20, 2023

Dat hoa ngay neu tim duoc vi tri thoa dieu kien

Code:

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int cnt = 0;
        for(int i = 0; i < flowerbed.length; i++) {
            if (flowerbed[i] == 1) continue;
            int leftBound = i - 1;
            int rightBound = i + 1;
            boolean noLeft = true;
            boolean noRight = true;
            if (leftBound >= 0) {
                noLeft = false;
                if (flowerbed[leftBound] == 0) noLeft = true;
            }

            if (rightBound <= flowerbed.length - 1) {
                noRight = false;
                if (flowerbed[rightBound] == 0) noRight = true;
            }

            if (noLeft && noRight) {
                flowerbed[i] = 1;
                cnt++;
            }
        }

        return cnt >= n;

    }
}

Cyberpunker · Mar 20, 2023

Java:

class Solution {
  public boolean canPlaceFlowers(int[] flowerbed, int n) {
    int cnt = 0;
    for (int i = 0; i < flowerbed.length; ++i) {
      if ((i-1 < 0 || flowerbed[i-1] == 0)
          && flowerbed[i] == 0
          && (i+1 >= flowerbed.length || flowerbed[i+1] == 0)) {
        flowerbed[i] = 1;
        cnt++;
      }
    }
    return cnt >= n;
  }
}

NahSama · Mar 20, 2023

contest hom qua cau 3 kho hon cau 4 :censored:

con hom truoc thi t thay cau 2 kho hon cau 4, nhung ban t dung multiset gi do cua c++ lam max ngan

Code:

class Solution {
    public int beautifulSubsets(int[] nums, int k) {
        int n = nums.length;
     
        boolean[] dp = new boolean[(1 << n)];
     
        dp[0] = true;
        int ans = 0;
        for (int mask = 1; mask < (1 << n); mask++) {
            dp[mask] = true;
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) > 0) {
                    for (int j = 0; j < n; j++) {
                        if ((mask & (1 << j)) == 0) continue;
                        if (i == j) continue;
                        if (Math.abs(nums[i] - nums[j]) == k) {
                            dp[mask] = false;
                            break;
                        }
                    }
                 
                    dp[mask] = dp[mask] && dp[mask - (1 << i)];
                    ans += dp[mask] == true ? 1 : 0;
                    break;
                }
            }
        }
     
        return ans;
    }
}

Flow-chart · Mar 20, 2023

JavaScript:

var canPlaceFlowers = function (flowerbed, n) {
  for (let i = 0; i < flowerbed.length; i++) {
    if (!flowerbed[i] && !flowerbed[i - 1] && !flowerbed[i + 1]) {
      n--;
      flowerbed[i]  = 1
    }
  }
  return n <= 0
};

anoldvozer1710.v2 · Mar 20, 2023

Mình cũng không biết đây là giải theo p/p gì. Đơn giản dễ hiểu thôi :big_smile:

JavaScript:

function canPlaceFlowers(flowerbed: number[], n: number): boolean {
    let ans = 0;
    for (let i = 0; i < flowerbed.length; i++) {
        if (!flowerbed[i] && !flowerbed[i - 1] && !flowerbed[i + 1]) {
            ans++;
            flowerbed[i] = 1;
        }
    }
    return ans >= n;

}

seastar · Mar 20, 2023

anoldvozer1710.v2 said:
Mình cũng không biết đây là giải theo p/p gì. Đơn giản dễ hiểu thôi

JavaScript:

function canPlaceFlowers(flowerbed: number[], n: number): boolean { let ans = 0; for (let i = 0; i < flowerbed.length; i++) { if (!flowerbed[i] && !flowerbed[i - 1] && !flowerbed[i + 1]) { ans++; flowerbed[i] = 1; } } return ans >= n; }

Cái này là greedy. Mà code này access out of index rồi, sửa lại đi fen,

Solution của t đây. Code này k hay 1 chỗ là làm thay đổi input, mà lười nên làm vậy. Giống như @Spaghetti Code đã nói: ai kêu truyền tham chiếu vào làm chi, 8-)

C++:

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        for (int i = 0;  n > 0 && i < flowerbed.size(); ++i) {
            if (!flowerbed[i] && (i == 0 || !flowerbed[i-1]) && (i == flowerbed.size() - 1 || !flowerbed[i+1])) {
                --n;
                flowerbed[i] = 1;
            }
        }
        return n == 0;
    }
};

Edit: bổ sung cách k sửa input:

C++:

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        bool prev = false;
        for (int i = 0;  n > 0 && i < flowerbed.size(); ++i) {
            if (!flowerbed[i] && !prev && (i == flowerbed.size() - 1 || !flowerbed[i+1])) {
                --n;
                prev = true;
            } else prev = flowerbed[i];
        }
        return n == 0;
    }
};

thanbaiks · Mar 20, 2023

JavaScript:

var canPlaceFlowers = function(flowerbed, n) {
    let m = 0, s = -1;
    flowerbed.push(0, 1);
    for (let i = 0; i < flowerbed.length; i++) {
        if (flowerbed[i]) {
            m += Math.max(0, (i - s - 1) >> 1);
            s = i + 1;
        }
    }

    return m >= n;
};

callmemark · Mar 21, 2023

Brute force for life

Python:

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = []
        cnt = 0
        for n in nums:
            if n == 0:
                cnt += 1
            else:
                if cnt != 0:
                    ans.append(cnt)
                    cnt = 0
        if cnt != 0:
            ans.append(cnt)
            
        res = 0
        for v in ans:
            res += v*(v+1)/2
        return int(res)

Symbiosis · Mar 21, 2023

First attempt: Time O(n) Space O(n)

Python:

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        self.dp = {1: 1}
        
        started = False
        count = 0
        res = 0
        for num in nums:
            if num == 0:
                if started:
                    count += 1
                else:
                    started = True
                    count = 1
            else:
                if started:
                    res += self.calcSubarray(count)
                    count = 0
                    started = False
        
        if started:
            res += self.calcSubarray(count)
            
        return res
    
    def calcSubarray(self, n):
        if n in self.dp:
            return self.dp[n]
        
        res = n + self.calcSubarray(n-1)
        
        self.dp[n] = res
        
        return res

Second attempt (sau khi check LC solution) Time: O(n) Space: O(1)

Python:

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        started = False
        count = 0
        res = 0
        for num in nums:
            if num == 0:
                if started:
                    count += 1
                else:
                    started = True
                    count = 1
                res += count
            elif started:
                count = 0
                started = False
        
        return res

Also, quên luôn f(n) = n + n-1 + n-2 + ... + 1 = n x (n+1)/2 xưa học mathematical induction trả hết chữ nghĩa cho thầy cô rồi =((

anoldvozer1710.v2 · Mar 21, 2023

Chưa hiểu sao bài này medium

Khi dãy số 0 liên tiếp tăng thêm 1 phần tử, thì tổng số subarrays của dãy đó tăng đúng bằng độ dài dãy số

JavaScript:

function zeroFilledSubarray(nums: number[]): number {
    let ans = 0, count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === 0) {
            count++;
            ans+= count;
        } else {
            count = 0;
        }
    }
    return ans;
};

seastar · Mar 21, 2023

21/03: Bài này tầm easy thôi, 8-)

Python:

reduce(lambda acc, x: [acc[0], 0] if x else [sum(acc) + 1, acc[1] + 1], nums, [0,0])[0]

C++:

class Solution {
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        int count = 0;
        return accumulate(begin(nums), end(nums), 0LL, [&count](long long acc, int num) {
            count = num ? 0 : count + 1;
            return acc + count;
        });
    }
};

NahSama · Mar 21, 2023

Code:

class Solution {
    public long zeroFilledSubarray(int[] nums) {
        int cnt = nums[0] == 0 ? 1 : 0;
        long ans = nums[0] == 0 ? 1 : 0;
        int last = nums[0];
        for (int i = 1; i < nums.length; i++){
            if (nums[i] != 0) {
                last = nums[i];
                cnt = 0;
                continue;
            }

            if (nums[i] == 0) {
                if (last != nums[i]) {
                    last = nums[i];
                }
                cnt++;
                ans += cnt;
            }
        }

        return ans;
    }
}

NahSama · Mar 21, 2023

seastar said:
21/03: Bài này tầm easy thôi,

Python:

reduce(lambda acc, x: [acc[0], 0] if x else [sum(acc) + 1, acc[1] + 1], nums, [0,0])[0]

doc may bai medium ma AC > 50% thi la medium cui (Q2 contest) con AC thap thi la medium xin (Q3 Q4)

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

Senior Member

Senior Member

Senior Member

Senior Member

Junior Member

Senior Member

Đã tốn tiền

Senior Member

Junior Member

Senior Member

Junior Member

Senior Member

Member

Senior Member

Junior Member

Senior Member

Senior Member

Member

Senior Member

Senior Member

Similar threads

Share this page