免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

題目要求

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 uniformly at random, 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. 1 <= n_rows, n_cols <= 10000
2. 0 <= row.id < n_rows and 0 <= col.id < n_cols
3. flip will not be called when the matrix has no 0 values left.
4. the total number of calls to 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.

假設(shè)現(xiàn)在有一個(gè)n_rows行和n_columns列的矩陣，該矩陣中初始時(shí)每一個(gè)元素值均為0。調(diào)用flip方法時(shí)需要隨機(jī)選擇矩陣中一個(gè)值為0的格子并設(shè)置為1，返回格子的行列坐標(biāo)。reset方法會(huì)將矩陣重制為初始狀態(tài)。要求盡可能減少random方法的調(diào)用次數(shù)。

思路和代碼

其實(shí)最直觀的方法就是使用隨機(jī)數(shù)分別生成隨機(jī)的行和列，然后判斷該位置上的值是否為0。如果不為0，則繼續(xù)生成隨機(jī)行列，繼續(xù)判斷，直到找到為0的格子。

這里的第一個(gè)優(yōu)化就在于將二維數(shù)組進(jìn)行一維化的表示，即第i行第k列這個(gè)坐標(biāo)完全可以通過i*n_columns+k得出唯一的一個(gè)整數(shù)表示形式。我們只需要對(duì)n_rows*n_colums范圍內(nèi)生成一個(gè)隨機(jī)的整數(shù)并轉(zhuǎn)化為二維坐標(biāo)，可以直接將隨機(jī)方法的執(zhí)行次數(shù)減少一半。

那么接著的優(yōu)化思路其實(shí)可以很直觀的想到，如果我們可以保存一個(gè)還沒有遍歷到的下標(biāo)集合。每次以集合大小作為隨機(jī)數(shù)生成的邊界，再?gòu)募现幸瞥撾S機(jī)數(shù)，代表這一次翻了這個(gè)位置的格子。

但是直接用List來存儲(chǔ)這樣的一個(gè)結(jié)構(gòu)還是會(huì)有很嚴(yán)重的性能問題。假設(shè)是一個(gè)1000*1000的矩陣，則初始的List中需要存儲(chǔ)1000000個(gè)未被選中的格子，對(duì)于時(shí)間和空間來說都是不可接受的。那么有沒有辦法可以用另一種形式來記錄未翻牌的元素下標(biāo)？

前面已經(jīng)講了，二維數(shù)組的下標(biāo)是可以被轉(zhuǎn)化為一維數(shù)組下標(biāo)表示。我們可以想象這樣的一個(gè)場(chǎng)景，對(duì)于這個(gè)一維數(shù)組，每當(dāng)一個(gè)下標(biāo)被翻開，都將該下標(biāo)和位于當(dāng)前未被翻開的最后一個(gè)元素位置進(jìn)行交換。我們只需要記錄叫喚到前面的最后一個(gè)元素的新的位置即可。舉個(gè)例子，2*3的矩陣，可以翻開為一個(gè)長(zhǎng)度為6的一維矩陣，其元素分別為0,1,2,3,4,5。

第一次flip隨機(jī)生成下標(biāo)2，則我們將2和5進(jìn)行交換，并記錄2這個(gè)位置上新的元素5(2:5)
第二次flip隨機(jī)生成下標(biāo)1，則將1和4進(jìn)行叫喚，并記錄1這個(gè)位置上新的元素為4(2:5, 1:4)
第三次flip隨機(jī)生成下標(biāo)2，此時(shí)我們發(fā)現(xiàn)2上存的元素是5，因此返回5，經(jīng)記錄2上的新元素為3（2:3, 1:4)
。。。

這樣的話，當(dāng)隨機(jī)生成的下標(biāo)不在記錄中時(shí)，下標(biāo)上存儲(chǔ)的位置就是本身，否則就是交換過的位置。每次都要更新下標(biāo)上的元素為最后一個(gè)還未被翻開的下標(biāo)。

    Map<Integer, Integer> map;    Random                r;    int rowCount;    int columnCount;    int flipCount;    public Solution(int n_rows, int n_cols) {        map = new HashMap<>();        r = new Random();        rowCount = n_rows;        columnCount = n_cols;        flipCount = rowCount * columnCount;    }    public int[] flip() {        int randomIndex = r.nextInt(flipCount--);        int value = map.getOrDefault(randomIndex, randomIndex);        map.put(randomIndex, map.getOrDefault(flipCount, flipCount));        return new int[]{value/columnCount, value%columnCount};    }    public void reset() {        map.clear();        flipCount = rowCount * columnCount;    }