ARTS打卡：第十三周

发表于 | 分类于 | 本文总阅读量 次

ARTS打卡：第十三周

每周完成一个ARTS：

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

Algorithm

48. Rotate Image(Medium)

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

大致题意

给一个 n×n 的2D矩阵，要求将这个矩阵顺时针旋转90°
注意： 需要原地旋转，意味着要直接修改输入的2D矩阵，不允许借助其他的矩阵来完成旋转。

解题思路

我们可以通过仔细观察 example 的示例，发现其中规律：

  1. n×n的2D矩阵是一个二维数据，旋转90°，相当于逐层旋转90°，如图所示：
    旋转
    1层和2层分别顺时针旋转90°。
  2. 单层旋转的时候，假设输入的2D矩阵是 a，那么顺时针旋转90°时，矩阵外层的四个角的元素值替换顺序为：a[x][x] -> a[x][y] -> a[y][y] -> a[x][x]（x 为起点下标，y为终点下标）。
    那么对于外层□来说，只需依次对上边元素进行旋转90°即可，所以我们可以推导出：a[x][x + offset] -> a[x + offset][y] -> a[y][y - offset] -> a[x][x + offset]，其中 offset 是偏移量，要满足 offset < 当前外层正方形的长度 - 1。
  3. 外层向内层递进的时候，边长度都减 2。

代码实现

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
/**
 * 核心思路：
 * n × n 的矩阵
 * 由最外层到最里层，一层层依次进行旋转。
 * <p>
 * 可以观察的规律是
 * 1. 每层递进时，矩阵边长度都 -2
 * 2. a[x][x + offset] -> a[x + offset][y] -> a[y][y - offset] -> a[x][x + offset] 其中 offset 是偏移量，要满足 offset < 当前矩阵边长度 -1
 *
 * @param matrix
 */
public void rotate(int[][] matrix) {
    int x = 0;
    int y = matrix.length - 1;
    int currLength = matrix.length;
    while (x < y) {
        int offset = 0;
        while (offset < currLength - 1) {
            int topLeft = matrix[x][x + offset];
            matrix[x][x + offset] = matrix[y - offset][x];
            int topRight = matrix[x + offset][y];
            matrix[x + offset][y] = topLeft;
            int bottomRight = matrix[y][y - offset];
            matrix[y][y - offset] = topRight;
            matrix[y - offset][x] = bottomRight;
            ++offset;
        }
        ++x;
        --y;
        currLength -= 2;
    }
}

运行结果与复杂度分析

结果：
Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Image.
Memory Usage: 36.1 MB, less than 99.73% of Java online submissions for Rotate Image.

复杂度分析：
时间复杂度：O(n²)
空间复杂度：O(n)

Review

本周阅读：

  1. 《Top 10 Methods for Java Arrays》
    文中列举了Java Array的十大方法。它们是stackoverflow中投票最多的问题。
  2. 《Why String is immutable in Java?》
    文中从内存，同步和数据结构的角度说明了 String 为什么设计为不可变的。
    拓展阅读：《JVM Run-Time Data Areas》
  3. Learn basics of Version Control & Git Commands in less than 10 minutes.
    作者在文中介绍了版本控制的概念、用途和术语以及一些基础的练习方式，并列举一些流行的版本控制系统。
    其中作者着重介绍了最流行的版本控制系统 Git，在文中列举了 Git 的基础命令，并写下了有关 Git 的简单使用教程。

这三篇文章都挺简单易懂的，感觉兴趣的小伙伴们，可以通过查看原文，了解更多详情。

Tip

本周分享有关 firewalld 的一些命令：

  1. firewalld的基本使用
    启动： systemctl start firewalld
    查看状态： systemctl status firewalld
    停止： systemctl disable firewalld
    禁用： systemctl stop firewalld
  2. systemctl是CentOS7的服务管理工具中主要的工具，它融合之前service和chkconfig的功能于一体。
    启动一个服务：systemctl start firewalld.service
    关闭一个服务：systemctl stop firewalld.service
    重启一个服务：systemctl restart firewalld.service
    显示一个服务的状态：systemctl status firewalld.service
    在开机时启用一个服务：systemctl enable firewalld.service
    在开机时禁用一个服务：systemctl disable firewalld.service
    查看服务是否开机启动：systemctl is-enabled firewalld.service
    查看已启动的服务列表：systemctl list-unit-files|grep enabled
    查看启动失败的服务列表：systemctl –failed
  3. 配置firewalld-cmd
    查看版本： firewall-cmd –version
    查看帮助： firewall-cmd –help
    显示状态： firewall-cmd –state
    查看所有打开的端口： firewall-cmd –zone=public –list-ports
    更新防火墙规则： firewall-cmd –reload
    查看区域信息: firewall-cmd –get-active-zones
    查看指定接口所属区域： firewall-cmd –get-zone-of-interface=eth0
    拒绝所有包：firewall-cmd –panic-on
    取消拒绝状态： firewall-cmd –panic-off
    查看是否拒绝： firewall-cmd –query-panic
  4. 开启端口
    添加: firewall-cmd –zone=public –add-port=80/tcp –permanent （–permanent永久生效，没有此参数重启后失效）
    重新载入: firewall-cmd –reload
    查看: firewall-cmd –zone=public –query-port=80/tcp
    删除: firewall-cmd –zone=public –remove-port=80/tcp –permanent

转自：CentOS7使用firewalld打开关闭防火墙与端口。

Share

本周分享耗子叔的一篇文章：《如何超过大多数人》。