519. 随机翻转矩阵

日期:2022-9-11 16:31 | 标签: | 阅读:18

重点思路:

  1. 基于数组元素个数进行建模,降低二维矩阵复杂度。不过还原的时候需要注意
  2. 基于 JS 自带 random 函数随机值,值区间为 【0 ~ 未访问数值的总数】
  3. 基于 Map 记录区间内存在交换过的坐标

ps: 需要重点注意的是在交换前,需要判断是否已在 Map 中存在,这时的坐标为 Map 存有的坐标

/**
 * @param {number} m
 * @param {number} n
 */
var Solution = function(m, n) {
    this.m = m ;
    this.n = n;
    this.N = m * n;
    this.exchangeCacheMap = new Map();
};

/**
 * @return {number[]}
 */
Solution.prototype.flip = function() {
    if(this.N === 0){
        return null;
    }
    // 获取随机抽取的下标
    let randN = Math.floor(Math.random() * this.N);

    // 得到行列
    let row ,column;
    let hashedVal = this.exchangeCacheMap.get(randN);
    if(hashedVal){
        row =  Math.floor(hashedVal / this.n);
        column = hashedVal % this.n;
    }else{  
        row =  Math.floor(randN / this.n);
        column = randN % this.n;
    }

    // 交换下标
    if(randN !== this.N - 1){
        if(this.exchangeCacheMap.get(this.N - 1)){
            // 假如已经交换过,那么应该使用 Map 存储的交换过的序号
            this.exchangeCacheMap.set(randN, this.exchangeCacheMap.get(this.N - 1));
        }else{
            this.exchangeCacheMap.set(randN, this.N - 1);
        }
    }

    this.N -= 1;
    return [row, column];
};

/**
 * @return {void}
 */
Solution.prototype.reset = function() {
     this.N = this.m * this.n;
     this.exchangeCacheMap = new Map();
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(m, n)
 * var param_1 = obj.flip()
 * obj.reset()
 */

版权声明: 署名-非商业性使用-禁止演绎 4.0 国际(CC BY-NC-ND 4.0
Copyright ©2013-2022 | 粤ICP备14081691号 | yipeng手工打造 | 联系方式