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

function jump(nums: number[]): number {
  const l = nums.length
  let arr = Array(l).fill(Infinity)
  arr[0] = 0;
  for (let i = 0; i < l - 1; i++) {
    for (let j = 1; j <= nums[i]; j++) {
      if(i + j >= l) break;
      arr[i + j] = Math.min(arr[i + j], arr[i] + 1)
    }
  }
  return arr[l - 1]
};

public class Solution {
    public long DistinctNames(string[] ideas) {
        long res = 0;
        var dict = new Dictionary<char, List<string>>();
        foreach (var idea in ideas)
        {
            if (!dict.ContainsKey(idea[0]))
                dict.Add(idea[0], new List<string>{ idea.Substring(1) });
            else
                dict[idea[0]].Add(idea.Substring(1));
        }

        for (int i = 0; i < dict.Keys.Count - 1; i++)
        {
            for (int j = i + 1; j < dict.Keys.Count; j++)
            {
                var numberOfDuplicate = dict[dict.Keys.ElementAt(i)].Intersect(dict[dict.Keys.ElementAt(j)]).Count();
                res += 2 * (dict[dict.Keys.ElementAt(i)].Count - numberOfDuplicate) *
                       (dict[dict.Keys.ElementAt(j)].Count - numberOfDuplicate);
            }
            
        }
        return res;
    }
}

class Solution:
    def distinctNames(self, ideas: List[str]) -> int:
        d=defaultdict(set)
        for s in ideas:
            d[ord(s[0])-ord('a')].add(s[1:])
        res=0
        for i in range(26):
            for j in range(i+1,26):
                k=len(d[i]&d[j])
                res+=(len(d[i])-k)*(len(d[j])-k)*2
        return res

function distinctNames(ideas: string[]): number {
    const set: Set<string>[] = [];
    for (let i = 0; i < 26; i++) {
        set[i] = new Set();
    }
    for (const idea of ideas) {
        set[idea.charCodeAt(0) - 'a'.charCodeAt(0)].add(idea.substring(1));
    }

    let res = 0;
    for (let i = 0; i < 25; i++) {
        for (let j = i + 1; j < 26; j++) {
            let countDup = 0;
            for (const key of set[i]) {
                if (set[j].has(key)) {
                    countDup++;
                }
            }
            res += 2 * (set[i].size - countDup) * (set[j].size - countDup);
        }
    }

    return res;
};

public class Solution {
    public int MaxDistance(int[][] grid) {
        var row = grid.Length;
        var col = grid[0].Length;
        var visited = new bool[row, col];
        var queue = new Queue<Tuple<int, int, int>>();
        for (int rowIndex = 0; rowIndex < row; rowIndex++)
        for (int colIndex = 0; colIndex < col; colIndex++)
        {
            if (grid[rowIndex][colIndex] == 1)
            {
                queue.Enqueue(new Tuple<int, int, int>(rowIndex, colIndex, 0));
                visited[rowIndex, colIndex] = true;
            }
        }
        if (queue.Count == 0 || queue.Count == row * col) return -1;
        var directions = new[]
        {
            new int[] { 0, 1 },
            new [] {1,0},
            new int[] {-1,0},
            new int[] {0,-1}
        };
        var result = 0;
        while (queue.Any())
        {
            var item = queue.Dequeue();
            result = Math.Max(item.Item3, result);
            foreach (var direction in directions)
            {
                var nextRow = item.Item1 + direction[0];
                var nexCol = item.Item2 + direction[1];
                if (nextRow >= 0 && nextRow < row && nexCol >= 0 && nexCol < col && grid[nextRow][nexCol] == 0)
                {
                    queue.Enqueue(new Tuple<int, int, int>(nextRow, nexCol, item.Item3 + 1));
                    grid[nextRow][nexCol] = -1;
                }
            }
        }
        return result;
    }
}

fun maxDistance(grid: Array<IntArray>): Int {
        val n = grid.size
        if (n == 1) return -1
        val dx = intArrayOf(0, 1, 0, -1)
        val dy = intArrayOf(1, 0, -1, 0)
        val queue = LinkedList<IntArray>()
        for (i in grid.indices) {
            for (j in grid[i].indices) {
                if (grid[i][j] == 1) {
                    queue.offer(intArrayOf(i, j))
                }
            }
        }
        if (queue.size == n * n) return -1

        var distance = 0
        while (queue.isNotEmpty()) {
            distance++
            for (i in 1..queue.size) {
                val cell = queue.poll()
                for (k in 0..3) {
                    val x = cell[0] + dx[k]
                    val y = cell[1] + dy[k]
                    if (x in 0 until n && y in 0 until n && grid[x][y] == 0) {
                        grid[x][y] = distance
                        queue.offer(intArrayOf(x, y))
                    }
                }
            }
        }
        return distance - 1
    }

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    const n = grid.length;
    const moves = [[-1, 0], [1, 0], [0, -1], [0, 1]];
    const map = Array(n).fill().map(() => Array(n).fill());
    const q = new Queue();
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                map[i][j] = 0;
                q.enqueue([i, j]);
            }
        }
    }

    let ans = -1;
    while (!q.isEmpty()) {
        const [i, j] = q.dequeue();
        for (const [ii, jj] of moves.map(it => [i + it[0], j + it[1]])) {
            if (ii >= 0 && ii < n && jj >= 0 && jj < n && map[ii][jj] === undefined) {
                map[ii][jj] = map[i][j] + 1;
                ans = Math.max(ans, map[ii][jj]);
                q.enqueue([ii, jj]);
            }
        }
    }

    return ans;
};

/**
 * @param {number[][]} grid
 * @return {number}
 */
var maxDistance = function(grid) {
    var dic = Array(grid.length).fill(0).map(x => Array(grid.length).fill(-1))
    var x = [-1,0,0,1], y=[0,-1,1,0], q = [], sum=0
    for (let i=0; i<grid.length; i++)
        for (let j=0; j<grid.length; j++)
            if (grid[i][j] === 1) {
                dic[i][j] = 0
                q.push([i,j])
                sum++
            }
    if (q.length === 0 || sum===grid.length**2)
        return -1
    let a,b, max=0
    while (q.length > 0 ){
        [a,b]= q.shift()
        if (max < dic[a][b])
            max=dic[a][b]
        for(let k=0; k<4;k++)
            if (dic[a+x[k]]!=undefined && dic[a+x[k]][b+y[k]] != undefined && dic[a+x[k]][b+y[k]] === -1){
                q.push([a+x[k],b+y[k]])
                dic[a+x[k]][b+y[k]] = dic[a][b]+1
            }
    }
    return max
};

function maxDistance(grid: number[][]): number {
const n = grid.length;
  if (n === 0) {
    return -1;
  }
  let q = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        q.push([i, j]);
      }
    }
  }
  if (q.length === 0 || q.length === n * n) {
    return -1;
  }

  const dirs = { rigth: [0, 1], left: [0, -1], dow: [1, 0], up: [-1, 0] };

  const move = (dir, xy, grid, newQ) => {
    let [dx, dy] = dir;
    let a = xy[0] + dx;
    let b = xy[1] + dy;
    if (a >= 0 && a < n && b >= 0 && b < n && grid[a][b] === 0) {
      grid[a][b] = 1;
      newQ.push([a, b]);
    }
  };

  let dist = 0;
  while (q.length > 0) {
    let newQ = [];
    for (let i = 0; i < q.length; i++) {
      let [x, y] = q[i];
      move(dirs.rigth, q[i], grid, newQ);
      move(dirs.left, q[i], grid, newQ);
      move(dirs.dow, q[i], grid, newQ);
      move(dirs.up, q[i], grid, newQ);
    }
    q = newQ;
    dist++;
  }
  return dist - 1;
};

class Solution {
    class Data {
        int row;
        int col;
        int dis;
        public Data(int row, int col, int dis){
            this.row = row;
            this.col = col;
            this.dis = dis;
        }  
    }
    public int maxDistance(int[][] grid) {
        int n = grid.length;
        int max = 0;
        Queue<Data> queue = new LinkedList<>();
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == 1) queue.add(new Data(row, col, 0));
            }        
        }

        int[][] dirs = new int[][]{{-1,0}, {1, 0}, {0, 1}, {0, -1}};

        while(!queue.isEmpty()) {
            Queue<Data> nextQueue = new LinkedList<>();
            while(!queue.isEmpty()) {
                Data node = queue.poll();
                max = Math.max(max, node.dis);
                for(int[] dir : dirs) {
                    int newRow = node.row + dir[0];
                    int newCol = node.col + dir[1];
                    if (newRow >= 0 && newRow <n
                    && newCol >=0 && newCol <n) {
                        if(grid[newRow][newCol] == 0) {
                            grid[newRow][newCol] = 1;
                            nextQueue.add(new Data(newRow, newCol, node.dis + 1));
                        }
                    }
                }
            }
            queue = nextQueue;
        }
        return max > 0 ? max : -1;
    }
}