“This is the 10th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

preface

This past weekend, I participated in the Biweekly Contest 70. I only made three questions. I was really ashamed. This is the third question in the Biweekly Contest 70. The difficulty Medium is actually examining BFS. As long as you clear your mind, you can basically do it.

describe

You are given a 0-indexed 2D integer array grid of size m x n that represents a map of the items in a shop. The integers in the grid represent the following:

  • 0 represents a wall that you cannot pass through.
  • 1 represents an empty cell that you can freely move to and from.
  • All other positive integers represent the price of an item in that cell. You may also freely move to and from these item cells.

It takes 1 step to travel between adjacent grid cells.You are also given integer arrays pricing and start where pricing = [low, high] and start = [row, col] indicates that you start at the position (row, col) and are interested only in items with a price in the range of [low, high] . You are further given an integer k.

You are interested in the positions of the k highest-ranked items whose prices are within the given price range. The rank is determined by the first of these criteria that is different:

  • Distance, defined as the length of the shortest path from the start (shorter distance has a higher rank).
  • Price (lower price has a higher rank, but it must be in the price range).
  • The row number (smaller row number has a higher rank).
  • The column number (smaller column number has a higher rank).

Return the k highest-ranked items within the price range sorted by their rank (highest to lowest). If there are fewer than k reachable items within the price range, return all of them.

Example 1:

Input: the grid = [,2,0,1 [1],,3,0,1 [1], [0,2,5,1]], pricing = (2, 5), start = (0, 0), k = 3 Output: [[0, 1], [1, 1], [2, 1]] Explanation: You start at (0,0). With a price range of [2,5], we can take items from (0,1), (2,1) and (2,2). The ranks of these items are: - (0,1) with distance 1 - (1,1) with distance 2 - (2,1) with distance 3 - (2,2) The 3 highest ranked items in the price range are (0,1), (1,1), and (2,1).Copy the code

Note:

m == grid.length n == grid[i].length 1 <= m, n <= 10^5 1 <= m * n <= 10^5 0 <= grid[i][j] <= 10^5 pricing.length == 2 2 <= low <= high <= 10^5 start.length == 2 0 <=  row <= m - 1 0 <= col <= n - 1 grid[row][col] > 0 1 <= k <= m * nCopy the code

parsing

Given a 2-d integer array grid with 0 index m x n, it represents a map of goods in a store. Integers in the grid represent the following:

  • Zero is the wall you can’t walk through
  • 1 represents an empty cell that can be moved freely
  • Other positive integers represent the price of items in the cell, and people can move in and out of these item cells freely.

It takes 1 step to move between adjacent grid cells. Pricing = [low, high], start = [row, col], pricing = [low, high], col = [row, col] And it’s only interested in pricing the product, and it gives you an integer k at the end. Let’s return the positions of the k highest-ranked items within a given price range, or less, all. Ranking is determined by the higher priority of the following four criteria:

  • Distance, defined as the length from the starting point to the shortest path (shorter distance, higher grade)
  • Price (The lower the price, the higher the ranking, but must be within the price range)
  • Line number (the smaller the line number, the higher the rank)
  • Column number (the smaller the column number, the higher the rank)

This question is very close to our daily life. We can also use this question to calculate our shopping position in the supermarket. Of course, you can consider the criteria according to your own. BFS = BFS = BFS

[grid[0]][start[1]], start[0], start[1]], start[0], start[1]]; At the same time, a collection visted is defined to store the locations that have been passed, so as to ensure that there will be no repeated shopping. If the location at the beginning is within the range of the intended price, we will add its location to the result result. If k is 1, result can be directly returned.

Then when the stack is not empty, I do the while loop. I don’t add the distance to the stack element, because the stack traversal is based on the distance. This is based on the BFS feature, starting from the start position, I use BFS to search for the next position. You can think of it as an item at the same distance on a similar contour line. We use the TMP list to store information about all items in the stack that are about to move to the next location. These items in TMP are all the same distance apart. Then sort TMP. The smaller the three elements are, the higher the priority is, so you can use the built-in sort function to sort them directly. Then iterate through the sorted TMP, add its position to result as long as the price is within the intended price. If there are already k results, return it directly.

After the end of the while loop, it indicates that there are less than K intended products that can be selected, and all the results can be returned directly.

This is the original code that I thought of at the beginning, so I posted it directly, and the idea is all of the above, the code is a bit messy, but it can be optimized, the time complexity is O(n), the space complexity is O(n).

answer

class Solution(object): def highestRankedKItems(self, grid, pricing, start, k): """ :type grid: List[List[int]] :type pricing: List[int] :type start: List[int] :type k: int :rtype: List [the List [int]] "" "M = len (grid) N = len (grid [0]) L = pricing [0] R = pricing [1] dirs = [[- 1, 0], [0, 1], [0, 1], [1, 0]] visted = set() visted.add((start[0], start[1])) stack = [[grid[start[0]][start[1]], start[0], start[1]]] result = [] if L<=grid[start[0]][start[1]]<=R: result.append([start[0],start[1]]) if len(result) == k: return result while stack: tmp = [] num = len(stack) while num! =0: p, x, y = stack.pop(0) for d in dirs: t_x = x + d[0] t_y = y + d[1] if t_x<0 or t_x>=M or t_y<0 or t_y>=N: continue if (t_x, t_y) in visted: continue if grid[t_x][t_y] == 0: continue visted.add((t_x, t_y)) tmp.append([grid[t_x][t_y], t_x, t_y]) num -= 1 tmp.sort() stack.extend(tmp) for item in tmp: if L<=item[0]<=R: result.append([item[1], item[2]]) if len(result) == k: return result return resultCopy the code

The results

Runtime: 3284 ms, Faster than 100.00% of Python online submissions for K Highest Ranked Items Within a Price Range. Memory Usage: The linked list for K Highest Ranked Items Within a Price Range.Copy the code

The original link

Leetcode.com/contest/biw…

Your support is my biggest motivation