Fork me on GitHub

ARTS(13)

ARTS 第十三周

每周完成一个ARTS(也就是 Algorithm、Review、Tip、Share 简称ARTS):

  1. 每周至少做一个 leetcode 的算法题
  2. 阅读并点评至少一篇英文技术文章
  3. 学习至少一个技术技巧
  4. 分享一篇有观点和思考的技术文章。

Algorithm

力扣 519. 随机翻转矩阵

题中给出一个 n 行 n 列的二维矩阵 (n_rows,n_cols),且所有值被初始化为 0。要求编写一个 flip 函数,均匀随机的将矩阵中的 0 变为 1,并返回该值的位置下标 [row_id,col_id];同样编写一个 reset 函数,将所有的值都重新置为 0。尽量最少调用随机函数 Math.random(),并且优化时间和空间复杂度。

注意:

1.1 <= n_rows, n_cols <= 10000

  1. 0 <= row.id < n_rows 并且 0 <= col.id < n_cols

3.当矩阵中没有值为 0 时,不可以调用 flip 函数

4.调用 flip 和 reset 函数的次数加起来不会超过 1000 次

示例 1:

输入:
[“Solution”,”flip”,”flip”,”flip”,”flip”]
[[2,3],[],[],[],[]]
输出: [null,[0,1],[1,2],[1,0],[1,1]]
示例 2:

输入:
[“Solution”,”flip”,”flip”,”reset”,”flip”]
[[1,2],[],[],[],[]]
输出: [null,[0,0],[0,1],null,[0,0]]

执行结果:通过

显示详情 执行用时 :125 ms, 在所有 Java 提交中击败了100.00%的用户

内存消耗 :39 MB, 在所有 Java 提交中击败了100.00% 的用户

思路:

  1. 首先二维数组摊平成一维数组,使用以下方式转换: int x = result % n_rows; int y = result / n_rows;
  2. size 表示当前未被访问的数字个数,随机数从 0~size-1 之间产生,但随机数并不一定是最终的数字。
  3. 维护一个黑名单 map,若随机数已经存在于当前黑名单中,那么取出黑名单中的 value 代替此随机数。
  4. 此 value 讲道理应该不在黑名单中,若不幸还在黑名单里,那就以此 value 继续查找黑名单。
  5. 确定最终的数字后,就要往黑名单中添加当前的记录:最终的数字做 key,size 做 value,记录在黑名单中。
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
34
35
36
37
38
39
40
41
42
43
44


import java.util.HashMap;
import java.util.Map;


public class Solution {
int n_rows;
int n_cols;
int size;
Map<Integer, Integer> visitedMap;


public Solution(int n_rows, int n_cols) {
this.n_rows = n_rows;
this.n_cols = n_cols;
this.size = n_cols * n_rows;
this.visitedMap = new HashMap<>();
}

public int[] flip() {

int index = (int) (Math.random() * size);
--size;
int result = index;
while (visitedMap.containsKey(result)) {
result = visitedMap.get(result);
}
int x = result % n_rows;
int y = result / n_rows;
visitedMap.put(result, size); // K - V : 黑名单 - 白名单
int[] ret = new int[2];
ret[0] = x;
ret[1] = y;
return ret;

}

public void reset() {
this.size = n_cols * n_rows;
this.visitedMap = new HashMap<>();
}

}

Review

本周分享英文文章是:Data Streaming Made Easy With Apache KafkaApache Kafka With Scala Tutorial

解读:

  1. kafka 适用于微服务架构(也就是 MSA),主要原因就是消息队列的异步特性。producer 什么时候生产 topic 跟 consumer 什么时候消费 topic,是不存在time、task依赖的,也无需担心同步锁的问题。
  2. 消息中的数据其实就是字节数组,能够以任意形式存储。kafka 中的消息以 topic 数据结构存储,
  3. kafka 的 servers 集群称为 brokers,每个 broker 会存储一个或多个分区。
  4. producer 发布消息的过程是线程安全的,而且能够控制 message 进入哪个分区。
    1. 支持多个 server 发布同一个 topic。
  5. 无论 topic 被消费与否,kafka 都会保存消息到一定时间(时间可配置)。
  6. 运行 kafka 之前,还需要 zookeeper对 broker 进行管理,参考:为啥Kafka依赖Zookeeper

Tip

今天分享一个 很方便通过可视化的方式进行git 操作的软件——sourcetree,我觉得优点有这么几个:

  1. 图形化展示工作区、各分支、commit 等
  2. 所有 git 命令
  3. 能做简单的代码 diff
  4. 学习成本低,半天上手

Share

本周对本站之前的一篇 k8s 的文章进行了补充,加了不少干货,参考以下链接:

K8s 入门笔记

-------------The End-------------