JavaInterview JavaInterview
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)

『Java面试+Java学习』
首页
指南
分类
标签
归档
  • CSDN (opens new window)
  • 文档集合 (opens new window)
  • 系统架构 (opens new window)
  • 微信号 (opens new window)
  • 公众号 (opens new window)
  • 指南
  • 简历

  • Java

  • 面试

  • 算法

  • algorithm
  • leetcode
JavaInterview.cn
2022-09-05
目录

随机翻转矩阵Java

文章发布较早,内容可能过时,阅读注意甄别。

# 题目

给你一个 m x n 的二元矩阵 matrix ,且所有值被初始化为 0 。请你设计一个算法,随机选取一个满足 matrix[i][j] == 0 的下标 (i, j) ,并将它的值变为 1 。所有满足 matrix[i][j] == 0 的下标 (i, j) 被选取的概率应当均等。

尽量最少调用内置的随机函数,并且优化时间和空间复杂度。

实现 Solution 类:

  • Solution(int m, int n) 使用二元矩阵的大小 m 和 n 初始化该对象
  • int[] flip() 返回一个满足 matrix[i][j] == 0 的随机下标 [i, j] ,并将其对应格子中的值变为 1
  • void reset() 将矩阵中所有的值重置为 0

示例:

输入
["Solution", "flip", "flip", "flip", "reset", "flip"]
[[3, 1], [], [], [], [], []]
输出
[null, [1, 0], [2, 0], [0, 0], null, [2, 0]]

解释
Solution solution = new Solution(3, 1);
solution.flip();  // 返回 [1, 0],此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同
solution.flip();  // 返回 [2, 0],因为 [1,0] 已经返回过了,此时返回 [2,0] 和 [0,0] 的概率应当相同
solution.flip();  // 返回 [0, 0],根据前面已经返回过的下标,此时只能返回 [0,0]
solution.reset(); // 所有值都重置为 0 ,并可以再次选择下标返回
solution.flip();  // 返回 [2, 0],此时返回 [0,0]、[1,0] 和 [2,0] 的概率应当相同

提示:

  • 1 <= m, n <= 104
  • 每次调用flip 时,矩阵中至少存在一个值为 0 的格子。
  • 最多调用 1000 次 flip 和 reset 方法。

# 思路

Set sets;

# 解法


class Solution {
    Set<String> sets;
    int r;
    int c;
    public Solution(int n_rows, int n_cols) {
        sets = new HashSet<String>();
        r = n_rows;
        c = n_cols;
    }
    
    public int[] flip() {
        int rr = new Random().nextInt(r);
        int cc = new Random().nextInt(c);
        while(sets.contains(rr+","+cc)){
            rr = new Random().nextInt(r);
            cc = new Random().nextInt(c);
        }
        sets.add(rr+","+cc);
        return new int[]{rr,cc};
    }
    
    public void reset() {
        sets.clear();
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(m, n);
 * int[] param_1 = obj.flip();
 * obj.reset();
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# 总结

  • 分析出几种情况,然后分别对各个情况实现
微信 支付宝
最近更新
01
1637. 两点之间不包含任何点的最宽垂直区域 Java
06-26
02
1636. 按照频率将数组升序排序 Java
06-26
03
1638. 统计只差一个字符的子串数目 Java
06-26
更多文章>
Theme by Vdoing | Copyright © 2019-2025 JavaInterview.cn
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式