JAVA - BSF Example

 Leetcode 1091

class Solution { class Point{ int x ; int y ; int steps; public Point(int x, int y , int steps){ this.x = x; this.y = y; this.steps = steps; } } public int shortestPathBinaryMatrix(int[][] grid) { //BFS //DFS //BFS -> Shortest path //DSA : Queue if(grid[0][0] != 0){ return -1; } int [][] moves = new int[][]{{0,-1} , {0,1} , {1,0}, {-1,0} , {-1,-1},{-1, 1},{1,1},{1,-1}}; Queue<Point> queue = new LinkedList<>(); queue.offer(new Point(0 , 0, 1)); grid[0][0] = 1; int newX = 0; int newY = 0; while(! queue.isEmpty()){ Point point = queue.poll(); if(point.x == grid.length -1 && point.y == grid[0].length-1){ return point.steps; } for(int i = 0 ;i<8 ; i++){ newX = point.x + moves[i][0]; newY = point.y + moves[i][1]; if( newX >=0 && newY >=0 && newX < grid.length && newY < grid[0].length && grid[newX][newY] == 0){ queue.offer(new Point(newX, newY , point.steps +1)); grid[newX][newY] = 1; } } } return -1; } } /** grid[i][i+1] = 0 -> grid[i][i-1] = 0 <- grid[i-1][i] = 0 A grid[i+1][i] = 0 V grid[i-1][i-1] = 0 <- A grid[i-1][i+1] = 0 <- V grid[i+1][i+1] = 0 -> V grid[i+1][i-1] = 0 -> A */

留言

發佈留言

此網誌的熱門文章

MAP - Sort with stream

 LEETCODE 1636 Given an array of integers   nums , sort the array in   increasing   order based on the frequency of the values. If multiple values have the same frequency, sort them in   decreasing   order. Return the  sorted array . Example 1: Input: nums = [1,1,2,2,2,3] Output: [3,1,1,2,2,2] Explanation: '3' has a frequency of 1, '1' has a frequency of 2, and '2' has a frequency of 3. Example 2: Input: nums = [2,3,1,3,2] Output: [1,3,3,2,2] Explanation: '2' and '3' both have a frequency of 2, so they are sorted in decreasing order. Example 3: Input: nums = [-1,1,-6,4,5,-6,1,4,1] Output: [5,-1,4,4,-6,-6,1,1,1] #1 class Solution { public int[] frequencySort(int[] nums) { return Arrays.stream(nums) .boxed() // boxing to wapped class .collect(Collectors.toMap(e-> e , e-> 1 , Integer::sum))//?? .entrySet() .stream() .sorted((e1,e2) -> e1.getValue().equals(e...
閱讀更多

JAVA - DSF Example

  class Solution { class Point { int x ; int y ; int steps ; public Point ( int x , int y , int steps ){ this . x = x; this . y = y; this . steps = steps; } } public int shortestPathBinaryMatrix ( int [][] grid ) { //BFS //DFS //BFS -> Shortest path //DSA : Queue if (grid[ 0 ][ 0 ] != 0 ){ return - 1 ; } int [][] moves = new int [][]{{ 0 ,- 1 } , { 0 , 1 } , { 1 , 0 }, {- 1 , 0 } , {- 1 ,- 1 },{- 1 , 1 },{ 1 , 1 },{ 1 ,- 1 }}; Stack < Point > queue = new Stack <>(); queue . push ( new Point ( 0 , 0 , 1 )); grid[ 0 ][ 0 ] = 1 ; int newX = 0 ; int newY = 0 ; while (! queue . isEmpty ()){ Point point = queue . pop (); if ( point . x == grid . length - 1 && point . y == grid[ 0 ]. length - 1 ){ ...
閱讀更多