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

Java: 
class Solution {
    public int partitionString(String s) {
        char[] c = s.toCharArray();

        Map<Character, Integer> map = new HashMap<>();
        int left = 0;
        int ans = 0;
        for (int i = 0; i< c.length; i++) {
            if (map.getOrDefault(c[i], -1) >= left) {
                left = i;
                ans++;
            }
            map.put(c[i], i);
        }

        ans++;
        return ans;
    }
}
 
Greedy

Python: 
class Solution:
    def partitionString(self, s: str) -> int:
        i = 0
        split = 1
        temp = set()
        while i < len(s):
            if s[i] not in temp:
                temp.add(s[i])
            else:
                temp = set()
                temp.add(s[i])
                split += 1
            i += 1
        return split
 
hôm này bài dễ
Java: 
class Solution {
    public int partitionString(String s) {
        int cnt = 0;
        Set<Integer> map = new HashSet<>();
        for(int i = 0; i < s.length(); i++) {
            int cur = s.charAt(i);
            if(map.contains(cur)) {
                cnt++;
                map.clear();
            }
            map.add(cur);
        }
        if(!map.isEmpty()) {
            cnt++;
        }
        return cnt;
    }
}
 
Đơn giản nhất là dùng Set thôi
JavaScript: 
function partitionString(s: string): number {
    let ans = 1;
    let set: Set<string> = new Set();
    set.add(s[0]);
    for (let i = 1; i < s.length; i++) {
        if (set.has(s[i])) {
            ans++;
            set.clear();
        }
        set.add(s[i])
    }
    return ans;
};
 
Ông nội này cục súc thật, cơ mà lại chạy nhanh nhất mới sợ chứ :))

1680582160916.png
 
Last edited:
Shinedo9820 said:
Ông nội này cục súc thật, cơ mà lại chạy nhanh nhất mới sợ chứ :))

View attachment 1758019
Click to expand...
tại sao cách ý lại nhanh hơn set được nhỉ, hơi có vấn đề:


vì check 1 phần tử trong string if i not in ss tui nghĩ nó chiếm O(N)
Python: 
class Solution:
    def partitionString(self, s: str) -> int:
        res = 0
        d = set()
       
        for c in s:
            if c in d:
                res += 1
                d = set()
            d.add(c)
                   
        return res + 1
 
JavaScript: 
/**
 * @param {string} s
 * @return {number}
 */
var partitionString = function(s) {
    const n = s.length;
    const h = {};
    let ans = 1, j = 0;

    for (let i = 0; i < n; i++) {
        const ch = s[i];
        if (h[ch] >= j) {
            ans++;
            j = i;
        }
        h[ch] = i;
    }

    return ans;
};
 
code dưới cùng là của mình vì muốn làm cho giống ví dụ nhưng báo lỗi vì nums không đổi(đã thử nums = temp):beat_brick:, code thứ 2 từ dưới lên là kham khảo Solution vậy là list trong python có thể edit trực tiếp trong function được hả mấy bác.
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums be k, to get accepted, you need to do the following things:
  • Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
  • Return k.
Custom Judge:
The judge will test your solution with the following code:
Code: 
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

Example:
Code: 
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Python: 
def removeDuplicates(self, nums: List[int]) -> int:
        nums_dict = {}
        x = 0

        for i in nums:
          if i in nums_dict:
            nums_dict[i] += 1
          else:
            nums_dict[i] = 1
            nums[x] = i
            x += 1
        else:
          return len(nums_dict)
Python: 
def removeDuplicates(nums: list[int]) -> int:
    temp = []

    for num in nums:
        if num not in temp:
            temp.append(num)
    else:
        unique = len(temp)
        temp += ["_"] * (len(nums) - len(temp))

    return unique
 
Last edited:
hoang_nam.1993 said:
code dưới cùng là của mình vì muốn làm cho giống ví dụ nhưng báo lỗi vì nums không đổi(đã thử nums = temp):beat_brick:, code thứ 2 từ lên là kham khảo Solution vậy là list trong python có thể edit trực tiếp trong function được hả mấy bác.
Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums be k, to get accepted, you need to do the following things:
  • Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
  • Return k.
Custom Judge:
The judge will test your solution with the following code:
Code: 
int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

Example:
Code: 
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).
Python: 
def removeDuplicates(self, nums: List[int]) -> int:
        nums_dict = {}
        x = 0

        for i in nums:
          if i in nums_dict:
            nums_dict[i] += 1
          else:
            nums_dict[i] = 1
            nums[x] = i
            x += 1
        else:
          return len(nums_dict)
Python: 
def removeDuplicates(nums: list[int]) -> int:
    temp = []

    for num in nums:
        if num not in temp:
            temp.append(num)
    else:
        unique = len(temp)
        temp += ["_"] * (len(nums) - len(temp))

    return unique
Click to expand...
y la cai function nay duoc call co tac dung thay doi cai list input, cai return la cai index

code thứ 2 từ lên là kham khảo Solution vậy là list trong python có thể edit trực tiếp trong function được hả mấy bác.
Click to expand...
do cai nay dang pass the value of reference toi cai list => thay doi cai list trong function thi no cung thay doi luon cai list ma thang ben ngoai dang refer toi (tai vi no la cung mot cai list)
 
Bài hôm nay hay phết ấy. Tưởng đang tuần BS nên mò mẫm BS trước rồi mới nghĩ ra PrefixSum:byebye:
JavaScript: 
function minimizeArrayValue(nums: number[]): number {
    let ans = 0, l = 0, r = 1e9
    const check = (m: number): boolean => {
        let tmp = 0;
        for (const num of nums) {
            if (num > m) {
                const d = num - m;
                if (d > tmp) return false;
                tmp-= d
            } else {
                tmp+= m - num
            }
        }
        return true
    }

    while (l <= r) {
        const m = l + Math.floor((r-l) / 2);
        if (check(m)) {
            r = m - 1;
            ans = m
        } else {
            l = m + 1;
        }
    }
    return ans;


};
JavaScript: 
function minimizeArrayValue(nums: number[]): number {
    let ans = 0, ps = 0;
    for (let i = 0; i < nums.length; i++) {
        ps+= nums[i];
        ans = Math.max(ans, Math.ceil(ps/(i+1)))
    }
    return ans;
};
 
Python: 
class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        n = len(nums)
        stack = [[nums[n-1], 1]]
        for i in range(n-1, 0, -1):
            if nums[i-1] <= math.ceil(stack[0][0]/stack[0][1]):
                stack[0][0] += nums[i-1]
                stack[0][1] += 1
            else:
                while len(stack) > 1 and stack[0][0] / stack[0][1] <= stack[1][0] / stack[1][1]:
                    stack[0][0] += stack[1][0]
                    stack[0][1] += stack[1][1]
                    stack.pop(1)
                stack.insert(0, [nums[i-1], 1])
        res = stack.pop(0)
        while len(stack) > 0:
            si = stack.pop(0)
            if res[0]/res[1] <= si[0]/si[1]:
                res[0] += si[0]
                res[1] += si[1]
            else:
                break
        return math.ceil(res[0]/res[1])
 
Aristides said:
TrMT7Oq.png
bài này chịu thua

Đọc đề éo hiểu nó viết mẹ gì
Click to expand...
nums = [3,7,1,6] -> max tại i = 1 -> giảm tại 1, tăng tại 0
nums = [4,6,1,6] -> max tại i = 3 -> giảm tại 3, tăng tại 2
nums = [4,6,2,5] -> max tại i = 1 -> giảm tại 1, tăng tại 0
nums = [5,5,2,5]. Đến lúc này không còn tìm cách nào tạo ra 1 dãy số mới có max nhỏ hơn 5 được -> Đáp án là 5.
-> Đề bài là: Từ dãy số ban đầu, biến đổi dãy số theo quy định của đề bài để tìm ra 1 maximum element mới trong dãy số, có giá trị nhỏ hơn maximum hiện tại. Khi không thể tìm được maximum mới -> kết thúc. Như ví dụ trên là 7 -> 6 -> 5.
 
JavaScript: 
var minimizeArrayValue = function(nums) {
    const n = nums.length;
    let ans = 0, sum = 0;

    for (let i = 0; i < n; i++) {
        sum += nums[i];
        ans = Math.max(
            ans,
            Math.ceil(sum / (i + 1)),
        );
    }

    return ans;
};
 
Aristides said:
TrMT7Oq.png
bài này chịu thua

Đọc đề éo hiểu nó viết mẹ gì
Click to expand...
Cho mảng nums. Cho 1 operator: chọn 1 cặp index cạnh nhau, tăng số bên trái lên 1 và giảm số bên phải đi 1. Cho thực hiện operator này bao nhiêu lần cũng được, tìm giá trị tối thiểu của MAX(nums)
Tip: Operator này có thể mở rộng ra là chọn 1 cặp index bất kỳ, có thể tăng bên trái & giảm bên phải bao nhiêu cũng được miễn số >= 0
 
Java: 
class Solution {
    public int closedIsland(int[][] grid) {
        int maxRow = grid.length;
        int maxCol = grid[0].length;
        int ans = 0;
        boolean[][] visited = new boolean[maxRow][maxCol];
        for (int row = 0; row < maxRow; row++){
            for (int col = 0; col < maxCol; col++) {
                if (visited[row][col]) continue;
                if (grid[row][col] == 1) {
                    visited[row][col] = true;
                    continue;
                }
                if (check(row, col, grid, visited)) {
                    ans++;
                }
            }
        }

        return ans;
    }

    boolean check(int row, int col, int[][] grid, boolean[][] visited) {
        int maxRow = grid.length;
        int maxCol = grid[0].length;
        Queue<Integer> q = new LinkedList<>();
        q.add(row * 1000 + col);
        visited[row][col] = true;
        boolean ans = true;
        int[][] directions = new int[][]{{1, 0}, {-1, 0}, {0,1},{0,-1}};
        while(!q.isEmpty()){
            int num = q.poll();
            int curRow = num/1000;
            int curCol = num % 1000;
            if (curRow == 0 || curRow == maxRow - 1) {
                ans = false;
            }
            if (curCol == 0 || curCol == maxCol - 1) {
                ans = false;
            }
            for (int[] d : directions){
                int newRow = curRow + d[0];
                int newCol = curCol + d[1];
                if (newRow < 0 || newRow > maxRow - 1) continue;
                if (newCol < 0 || newCol > maxCol - 1) continue;
                if (visited[newRow][newCol]) continue;
                visited[newRow][newCol] = true;
                if (grid[newRow][newCol] == 0) q.add(newRow * 1000 + newCol);
            }
        }
        return ans;
    }
}
 
JavaScript: 
/**
 * @param {number[][]} grid
 * @return {number}
 */
var closedIsland = function(grid) {
    const m = grid.length, n = grid[0].length;
    const dirs = [[-1, 0], [1, 0], [0, 1], [0, -1]];
    let ans = 0;

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            let closed = true;
            if (grid[i][j] === 0) {
                const q = new Queue();
                q.push([i, j]);
                grid[i][j] = -1;
                while (!q.isEmpty()) {
                    const next = q.pop();
                    for (const [ii, jj] of dirs.map(d => [next[0] + d[0], next[1] + d[1]])) {
                        if (ii < 0 || ii >= m || jj < 0 || jj >= n) {
                            closed = false;
                        } else if (grid[ii][jj] === 0){
                            grid[ii][jj] = -1;
                            q.push([ii, jj]);
                        }
                    }
                }

                ans += closed ? 1 : 0;
            }
        }
    }

    return ans;
};
 
C++: 
class Solution {
private:
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, 1, 0, -1};
    int rows, cols;
    bool closed;
    void dfs(vector<vector<int>>& grid, int i, int j){       
        for(int k = 0; k < 4; ++k){
            int ni = i + dx[k], nj = j + dy[k];
            if(ni < 0 || nj < 0 || ni >= rows || nj >= cols || grid[ni][nj])
                continue;
            if(ni == 0 || nj == 0 || ni == rows - 1 || nj == cols - 1)
                closed = false;
            grid[ni][nj] = 1;
            dfs(grid, ni, nj);
        }
    }
public:
    int closedIsland(vector<vector<int>>& grid) {
        rows = grid.size(), cols = grid[0].size();
        int res = 0;
        for(int i = 0; i < rows; ++i){
            for(int j = 0; j < cols; ++j){
                if(grid[i][j] == 1) continue;
                grid[i][j] = 1;
                closed = true;
                if(i == 0 || j == 0 || i == rows - 1 || j == cols - 1)
                    closed = false;
                dfs(grid, i, j);
                res += closed;
            }
        }
        return res;
    }
};
 
Đang luyện theo LC Explore Cards nên múa thử Union Find :shame:

n is number of cells (rows * cols)
Time: O(n + n * alpha(n))
Space: O(n)

Use Union Find data structure to find the number of connected components then excluding ones on the borders.

Python: 
class UnionFind:
    def __init__(self, n):
        self.roots = [node for node in range(n)]
        self.ranks = [1 for _ in range(n)]
        self.count = n
    
    def find(self, node):
        if self.roots[node] == node:
            return node
        
        self.roots[node] = self.find(self.roots[node])
        
        return self.roots[node]
    
    def union(self, node1, node2):
        root1 = self.find(node1)
        root2 = self.find(node2)
        
        if root1 != root2:
            if self.ranks[root1] > self.ranks[root2]:
                self.roots[root2] = root1
            elif self.ranks[root2] > self.ranks[root1]:
                self.roots[root1] = root2
            else:
                self.roots[root2] = root1
                self.ranks[root1] += 1
                
            self.count -= 1
    
class Solution:
    def closedIsland(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        
        mapp = {}
        count = 0
        for row in range(n):
            for col in range(m):
                if grid[row][col] == 0:
                    mapp[(row, col)] = count
                    count += 1
                    
        uf = UnionFind(count)
        
        dirs = [(1, 0), (0, 1)]
        for row in range(n):
            for col in range(m):
                if grid[row][col] == 1:
                    continue
                    
                node = mapp[(row, col)]
                    
                for bottom, right in dirs:
                    xRow = row + bottom
                    xCol = col + right
                    
                    if xRow >= n or xCol >= m:
                        continue
                    
                    if grid[xRow][xCol] == 1:
                        continue
                    
                    neigh = mapp[(xRow, xCol)]
                    
                    uf.union(node, neigh)
      
        excluded = set()
        for row, col in mapp:
            node = mapp[(row, col)]
            
            if row == 0 or row == n - 1 or col == 0 or col == m - 1:
                excluded.add(uf.find(node))
            
        return uf.count - len(excluded)
 

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
92
nhbin
nhbin
Duy1122
thảo luận [Database] Hiệu Suất Phân Trang Xâu Trong SQL Database
Replies
6
Views
627
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
160
domino123
domino123
T
thảo luận PIXELVERSE kèo hot đào trên tele dự kiến list b
Replies
16
Views
428
truonggiang!
T

Share this page

Back
Top