Fork me on GitHub

ARTS(13)

Posted on | Edited on | In | Views:

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
45
46


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 Kafka 和 Apache 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-------------