本文共 2159 字,大约阅读时间需要 7 分钟。
You are given the number of rows n_rows
and number of columns n_cols
of a 2D binary matrix where all values are initially 0. Write a function flip
which chooses a 0 value , changes it to 1, and then returns the position [row.id, col.id]
of that value. Also, write a function reset
which sets all values back to 0. Try to minimize the number of calls to system's Math.random() and optimize the time and space complexity.
Note:
1 <= n_rows, n_cols <= 10000
0 <= row.id < n_rows
and 0 <= col.id < n_cols
flip
will not be called when the matrix has no 0 values left.flip
and reset
will not exceed 1000.Example 1:
Input: ["Solution","flip","flip","flip","flip"][[2,3],[],[],[],[]]Output: [null,[0,1],[1,2],[1,0],[1,1]]
Example 2:
Input: ["Solution","flip","flip","reset","flip"][[1,2],[],[],[],[]]Output: [null,[0,0],[0,1],null,[0,0]]
Explanation of Input Syntax:
The input is two lists: the subroutines called and their arguments. Solution
's constructor has two arguments, n_rows
and n_cols
. flip
and reset
have no arguments. Arguments are always wrapped with a list, even if there aren't any.
--------------------------------------------------------------------------------
思路很巧妙,有点类似于蓄水池抽样,写起来非常容易有bug
import randomclass Solution: def __init__(self, n_rows: int, n_cols: int): self.not_visited = {} #key对应的value还没被随出来过,key之前确实被随即过了 self.rows = n_rows self.cols = n_cols self.last = self.rows*self.cols - 1 def flip(self): if (self.last < 0): #bug3 return None x = random.randint(0, self.last) y = self.not_visited[x] if x in self.not_visited else x self.not_visited[x] = self.last if self.last not in self.not_visited else self.not_visited[self.last] #bug2: self.last之前可能名花有主了 self.last -= 1 return [y // self.cols, y % self.cols] #bug1: [y // self.rows, y % self.rows] def reset(self): self.not_visited.clear() self.last = self.rows*self.cols - 1# Your Solution object will be instantiated and called as such:obj = Solution(2, 2)print(obj.flip())print(obj.flip())print(obj.flip())print(obj.flip())print(obj.flip())obj.reset()
转载地址:http://stfoi.baihongyu.com/