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

Violet_7 said:
Python: 
class Solution:
    def mincostToHireWorkers(self, qualities: List[int], wages: List[int], k: int) -> float:
        def sort_by_wage_per_quality(quality_and_wage):
            quality, wage = quality_and_wage
            return wage / quality

        quality_and_wages = list(zip(qualities, wages))
        quality_and_wages.sort(key=sort_by_wage_per_quality)

        quality_heap = []
        quality_heap_sum = 0
        min_money = float('inf')

        for quality, wage in quality_and_wages:
            heapq.heappush(quality_heap, -quality)
            quality_heap_sum += quality

            if len(quality_heap) > k:
                quality_heap_sum += heapq.heappop(quality_heap)

            if len(quality_heap) == k:
                min_money = min(min_money, quality_heap_sum * wage / quality)

        return min_money
Click to expand...
Thấy anh em bảo hard nên thôi dzậy cho nhanh :shame:
 
Python: 
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        heap = []
        n = len(arr)
        for i in range(n - 1):
            heapq.heappush(heap, (arr[i] / arr[n - 1], i, n - 1))
        
        result = []
        while True:
            fraction, i, j = heapq.heappop(heap)
            k -= 1
            if k == 0:
                result = [arr[i], arr[j]]
                break
            if j > i + 1:
                heapq.heappush(heap, (arr[i] / arr[j - 1], i, j - 1))

        return result

Python: 
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        n = len(quality)
        result = 10 ** 9 + 7
        heap = []
        total_quality = 0

        proportion = [(w / q, q) for w, q in zip(wage,quality)]
        proportion.sort(key=lambda x: x[0])

        for i in range(n):
            heapq.heappush(heap, -proportion[i][1])       
            total_quality += proportion[i][1]

            if len(heap) > k:
                total_quality += heapq.heappop(heap)
            
            if len(heap) == k:
                result = min(result, total_quality * proportion[i][0])
        
        return result

Python: 
class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        result = []
        for i in range(n - 2):
            result.append([])
            for j in range(n - 2):
                maxLocal = max(grid[i1][j1] for j1 in range(j, j + 3) for i1 in range(i, i + 3))
                result[-1].append(maxLocal)
        
        return result
 
Bài dễ, giới hạn thấp thì cứ brute force.
Để đây đã, tối ưu chắc làm thêm sliding window hoặc heap
PS: Vừa search qua thì phép toán này gọi là max pooling, sử dụng trong convolution network rất nhiều.
C++: 
    vector<vector<int>> largestLocal(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> ret(n -2, vector<int>(n-2));
        for(int i = 0; i < n - 2; ++i) {
            for(int j = 0; j < n -2; ++j) {
                for(int l = i; l < i+3; l++) {
                    for(int k = j; k < j+3; k++) {
                        ret[i][j] = max(ret[i][j], grid[l][k]);
                    }
                }
            }
        }
        return ret;
    }
 
Last edited:
Làm lẹ rồi vô contest cúng rank nào. :whistle:
C#: 
public class Solution
{
    public int[][] LargestLocal(int[][] grid)
    {
        int rows = grid.Length;
        int cols = grid[0].Length;
        int[][] result = new int[rows - 2][];

        int resultRow = 0;
        for (int row = 1; row < rows - 1; row++)
        {
            int resultCol = 0;
            int[] rowVals = new int[cols - 2];
            for (int col = 1; col < cols - 1; col++)
            {
                rowVals[resultCol] = Max(grid, row, col);
                resultCol++;
                result[resultRow] = rowVals;
            }

            resultRow++;
        }

        return result;
    }

    private int Max(int[][] grid, int row, int col)
    {
        int sRow = row - 1;
        int sCol = col - 1;
        int max = 0;
        for (int i = 0; i < 3; i++)
        {
            for (int j = 0; j < 3; j++)
            {
                max = Math.Max(max, grid[sRow + i][sCol + j]);
            }
        }

        return max;
    }
}
 
bài hôm nay làm r, vào submit thôi
Java: 
class Solution {
    public int[][] largestLocal(int[][] grid) {
        int  n = grid.length;
        int[][] maxLocal = new int [n-2][n-2];
        for(int i=0;i<n-2;i++){
            for(int j=0;j<n-2;j++){
                int max=-1;
                for(int a=0;a:love:;a++){
                    for(int b=0;b:love:;b++){
                        max =Math.max(max,grid[i+a][j+b]);
                    }
                }
                maxLocal[i][j]=max;
            }
        }
        return maxLocal;
    }
}
 
Code: 
class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        steps = [-1,0,1]
        maxLocal = []
        for i in range(1,len(grid)-1):
            rowMax = []
            for j in range(1,len(grid)-1):
                maxVal = -1
                for row in steps:
                    for col in steps:
                        if maxVal < grid[i + row][j + col] :
                            maxVal = grid[i + row][j + col]
                rowMax.append(maxVal)
            maxLocal.append(rowMax)
        return maxLocal
 
PHP: 
class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer[][]
     */
    function largestLocal($grid) {
        $gridMaxIndex = count($grid[0]) - 1;
        $result = [];

        // create new matrix with length = grid.length-2
        for ($row=0; $row<=$gridMaxIndex-2; $row++) { // new matrix rows
            for ($column=0; $column<=$gridMaxIndex-2; $column++) { // new matrix columns
                // find max in area 3x3 of grid
                $max = 0;
                for ($i=$row; $i<$row+3; $i++) {
                    for($j=$column; $j<$column+3; $j++) {
                        $max = max($max, $grid[$i][$j]);
                    }
                }
                $result[$row][$column] = $max; // matrix[i][j] is max value of grid 3x3 area
            }
        }
       
        // return new matrix
        return $result;
    }
}
 
JavaScript: 
var largestLocal = function(grid) {
    let n = grid.length;
    let res = new Array(n - 2).fill(0).map(a => new Array(n - 2).fill(0));
    for (let i = 1; i < n - 1; i++) {
        for (let j = 1; j < n - 1; j++) {
            res[i-1][j-1] = Math.max(
                                 grid[i][j],
                                 grid[i-1][j-1], grid[i+1][j+1], grid[i+1][j-1], grid[i-1][j+1],
                                 grid[i][j-1], grid[i][j+1], grid[i-1][j], grid[i+1][j]
                                 );
        }
    }

    return res;
};
 
Last edited:
nchhnchh said:
Python: 
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        heap = []
        n = len(arr)
        for i in range(n - 1):
            heapq.heappush(heap, (arr[i] / arr[n - 1], i, n - 1))
       
        result = []
        while True:
            fraction, i, j = heapq.heappop(heap)
            k -= 1
            if k == 0:
                result = [arr[i], arr[j]]
                break
            if j > i + 1:
                heapq.heappush(heap, (arr[i] / arr[j - 1], i, j - 1))

        return result

Python: 
class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        n = len(quality)
        result = 10 ** 9 + 7
        heap = []
        total_quality = 0

        proportion = [(w / q, q) for w, q in zip(wage,quality)]
        proportion.sort(key=lambda x: x[0])

        for i in range(n):
            heapq.heappush(heap, -proportion[i][1])      
            total_quality += proportion[i][1]

            if len(heap) > k:
                total_quality += heapq.heappop(heap)
           
            if len(heap) == k:
                result = min(result, total_quality * proportion[i][0])
       
        return result

Python: 
class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        result = []
        for i in range(n - 2):
            result.append([])
            for j in range(n - 2):
                maxLocal = max(grid[i1][j1] for j1 in range(j, j + 3) for i1 in range(i, i + 3))
                result[-1].append(maxLocal)
       
        return result
Click to expand...
Python: 
class Solution:
    def largestLocal(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        return [[max(grid[i][j],grid[i][j+1],grid[i][j+2],
                grid[i+1][j],grid[i+1][j+1],grid[i+1][j+2],
                grid[i+2][j],grid[i+2][j+1],grid[i+2][j+2]) for j in range(n - 2)] for i in range(n - 2)]
 
Java: 
class Solution {
    public int[][] largestLocal(int[][] grid) {
        int[][] res = new int[grid.length - 2][grid[0].length - 2];
        for (int i = 1; i < grid.length - 1; i++) {
            for (int j = 1; j < grid[0].length - 1; j++) {
                int max = 0;
                for (int k = -1; k <= 1; k++) {
                    for (int l = -1; l <= 1; l++) {
                        max = Math.max(grid[i + k][j + l], max);
                    }
                }
                res[i - 1][j - 1] = max;
            }
        }
        return res;
    }
}
 
JavaScript: 
function largestLocal(grid: number[][]): number[][] {
    const res: number[][] = [];
    const windowSize = 3;

    for (let row = 0; row < grid.length - 2; row++) {
        const resRow: number[] = [];
        for (let col = 0; col < grid[row].length - 2; col++) {
            let maxCell = 0;

            for (let i = row; i < row + windowSize; i++) {
                for (let j = col; j < col + windowSize; j++) {
                    maxCell = Math.max(maxCell, grid[i][j])
                }
            }
            resRow.push(maxCell);
        }
        res.push(resRow)
    }

    return res
};
 
Code: 
def largest_local(grid)
    n = grid.length
    ans = Array.new(n-2) {Array.new(n-2, -1)}
    (0..n-3).each do |i|
        (0..n-3).each do |j|
            ans[i][j] = (i..i+2).map { |a| (j..j+2).map { |b| grid[a][b] }.max }.max
        end
    end
    ans
end
 
Trí khôn của ta đây @LmaoSuVuong
fd80e89f23663dc95baacfdb1f9c6bb9.gif

Java: 
class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        int[][] ans = new int[n - 2][n - 2];

        for (int row = 0; row < n - 2; row++) {
            for (int col = 0; col < n - 2; col++) {
                ans[row][col] = maxFilter(row, col, grid);
            }
        }

        return ans;
    }

    private int maxFilter(int startRow, int startCol, int[][] grid) {
        int max = Integer.MIN_VALUE;

        for (int row = startRow; row < startRow + 3; row++) {
            for( int col = startCol; col < startCol + 3; col++) {
                max = Math.max(grid[row][col], max);
            }
        }

        return max;
    }
}
 
billy_don said:
Trí khôn của ta đây @LmaoSuVuong View attachment 2489123
Java: 
class Solution {
    public int[][] largestLocal(int[][] grid) {
        int n = grid.length;
        int[][] ans = new int[n - 2][n - 2];

        for (int row = 0; row < n - 2; row++) {
            for (int col = 0; col < n - 2; col++) {
                ans[row][col] = maxFilter(row, col, grid);
            }
        }

        return ans;
    }

    private int maxFilter(int startRow, int startCol, int[][] grid) {
        int max = Integer.MIN_VALUE;

        for (int row = startRow; row < startRow + 3; row++) {
            for( int col = startCol; col < startCol + 3; col++) {
                max = Math.max(grid[row][col], max);
            }
        }

        return max;
    }
}
Click to expand...
bài ez mà củng phải tag shao
s80uLz1.png
bao h ez giả cầy hẳng tag
 
C#: 
public class Solution {
    public int[][] LargestLocal(int[][] grid) {
        int[][] result = new int[grid.Length-2][];
        for(int i = 0; i<grid.Length-2; i++)
        {
            result[i] = new int[grid.Length-2];
            for(int j = 0; j<grid.Length-2; j++)
                result[i][j] = 0;
        }

        for(int i = 0; i<result.Length; i++)
            for(int j = 0; j<result.Length; j++)
            {
                for(int k = i; k <= i+2; k++)
                    for(int p = j; p <= j+2; p++)
                    {
                        if(grid[k][p] > result[i][j])
                            result[i][j] = grid[k][p];
                    }
            }
        return result;
    }
}
 
Last edited:
Ngày đầu xài leetcode, ấn tượng ban đầu là không có autocomplete với báo lỗi như hackerrank. Không biết trả tiền ngon hơn không, nghèo code chay xong run coi nó báo lỗi đâu rồi sửa.

Ý tưởng là tìm max theo cột có 3 items trước, xong tìm max theo row 3 items. Reuse được max theo cột 3 items.

Swift: 
    func largestLocal(_ grid: [[Int]]) -> [[Int]] {

        var maxGrid:[[Int]] = []

        for y in 0..<(grid.count-2) {
            var row:[Int] = []
            for x in 0..<grid.count {
                let maxNum = max(grid[y][x], grid[y+1][x], grid[y+2][x])
                row.append(maxNum)
            }
            maxGrid.append(row)
        }

        var results: [[Int]] = []
        for y in 0..<(grid.count-2) {
            var row:[Int] = []
            for x in 0..<(grid.count-2) {
                let maxNum = max(maxGrid[y][x], maxGrid[y][x+1], maxGrid[y][x+2])
                row.append(maxNum)
            }
            results.append(row)
        }
        return results
    }

Cái runtime này xạo lol v~, mỗi lần run kết quả lại khác.

Screenshot 2024-05-13 at 00.09.06.png
 
Code: 
def largest_local(grid)
  m = grid[0].length - 2
  res = []
  i = 0
  while i < m
    j = 0
    temp = []
    while j < m
      temp << [
        grid[i][j], grid[i][j + 1], grid[i][j + 2],
        grid[i + 1][j], grid[i + 1][j + 1], grid[i + 1][j + 2],
        grid[i + 2][j], grid[i + 2][j + 1], grid[i + 2][j + 2]
      ].max
      j += 1
    end
    res << temp
    i += 1
  end
  res
end

đợi vợ ngủ ra code :D
 
giun đất said:
Code: 
def largest_local(grid)
  m = grid[0].length - 2
  res = []
  i = 0
  while i < m
    j = 0
    temp = []
    while j < m
      temp << [
        grid[i][j], grid[i][j + 1], grid[i][j + 2],
        grid[i + 1][j], grid[i + 1][j + 1], grid[i + 1][j + 2],
        grid[i + 2][j], grid[i + 2][j + 1], grid[i + 2][j + 2]
      ].max
      j += 1
    end
    res << temp
    i += 1
  end
  res
end

đợi vợ ngủ ra code :D
Click to expand...
Nghe là biết dân có vợ liền, ngồi code tí là nó mè nheo anh ơi anh hỡi :beat_brick:
 

Similar threads

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

Share this page

Back
Top