Boo-BKing.

题目描述

给定一个字符串和一个整数 k，你需要对从字符串开头算起的每个 2k 个字符的前k个字符进行反转。如果剩余少于 k 个字符，则将剩余的所有全部反转。如果有小于 2k 但大于或等于 k 个字符，则反转前 k 个字符，并将剩余的字符保持原样。

1
2
3

样例
输入: s = "abcdefg", k = 2
输出: "bacdfeg"

要求

该字符串只包含小写的英文字母。
给定字符串的长度和 k 在[1, 10000]范围内。

算法

(模拟) O(n)
循环枚举每 2k 个字母的开头位置。

时间复杂度

每个字母最多仅被遍历一次，故时间复杂度为 O(n)。

python code

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        l = 0
        mid = k
        r = 2 * k
        res = ''
        while len(res) < len(s):
            res += s[l:mid][::-1] + s[mid:r]
            l = 2 * k + l
            mid = mid + 2 * k
            r = r + 2 * k
        return res

题目描述

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

示例 1：

输入：
[[0,0,0],
 [0,1,0],
 [0,0,0]]

输出：
[[0,0,0],
 [0,1,0],
 [0,0,0]]
示例 2：

输入：
[[0,0,0],
 [0,1,0],
 [1,1,1]]

输出：
[[0,0,0],
 [0,1,0],
 [1,2,1]]

提示：

给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。

算法

(宽度优先搜索) O(nm)
定义一个队列，初始时将所有 0 元素的坐标进队；定义答案数组 res，0 元素位置的值为 0，其余为 -1。
对这个队列开始进行宽度优先搜索，每次扩展上下左右四个方向，若发现新的位置在 dis 中值为 -1，则更新新位置的答案为当前位置答案加 1。

时间复杂度

宽度优先搜索每个位置仅被遍历一次，故时间复杂度为 O(nm)。

空间复杂度

需要额外的空间存放队列和每个点的距离，故空间复杂度为 O(nm)。

python code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        if not matrix or not matrix[0]: return matrix
        m = len(matrix)
        n = len(matrix[0])
        res = [[-1]*n for _ in range(m)]
        q = []
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    res[i][j] = 0
                    q.append([i,j])
        dx = [-1,0,1,0]
        dy = [0,1,0,-1]
        while q:
            tmp = q.pop(0)
            for i in range(4):
                x = dx[i] + tmp[0]
                y = dy[i] + tmp[1]
                if 0 <= x < m and 0 <= y < n and res[x][y] == -1:
                    res[x][y] = res[tmp[0]][tmp[1]] + 1
                    q.append([x,y])
        return res 

MySQL学习笔记（Day003：升级/参数/连接/权限）

一. 数据库升级

####1. 环境说明：

一般说来，MySQL数据库的二进制数据文件，也就是my.cnf中的配置项datadir所在的位置，和我们MySQL应用程序安装的位置，是分开的，仅仅通过配置项告诉MySQL，数据库的数据存在datadir这个目录下。当程序和数据分离以后，方便我们对数据库应用程序做版本的升级或者回退。

MySQL学习笔记（Day004：权限拾遗/Role模拟/Workbench/体系结构）

###一. 权限拾遗

1. GRANT与创建用户

1
2
3
4
5
6

mysql> grant select on sys.* to 'perf'@'127.0.0.1' identified by '123';
Query OK, 0 rows affected, 1 warning (0.01 sec) -- 这里有一个warning

mysql> show warnings;
-- 输入warning的Message如下：
-- Using GRANT for creating new user is deprecated and will be removed in future release. Create new user with CREATE USER statement.

MySQL学习笔记（Day001-002：介绍和安装）

###一.MySQL版本选择

1. MySQL5.6以后的版本，推荐使用官方版本。
2. Percona：在5.6版本以后，MySQL将Percon之前优化集成到官方版本中;
3. MariaDB：无INNODB;且核心代码较老
4. MySQL在5.6以后不断重构源码，安装包越来越大，功能和性能在持续改进

MySQL学习笔记（Day018：磁盘）

一. iostat

MySQL学习笔记（Day005：slow_log/generic_log/audit/存储引擎一）

一. 慢查询日志进阶

1. 相关参数：

• slow_query_log
  • 是否开启慢查询日志
• slow_query_log_file
  • 慢查询日志文件名, 在my.cnf我们已经定义为slow.log，默认是 机器名-slow.log

MySQL学习笔记（Day006：存储引擎二/多实例安装）

一. MyISAM存储引擎(下)

1. MyISAM还在使用的原因

• 历史原因，需要逐步替换
• 部分如User，DB等系统表(MyISAM引擎)，可以直接拷贝，比较方便
• 性能好，或者存储小不是MyISAM的优点，也不是存在的原因

MySQL学习笔记（Day008：数据类型）

一. INT类型

1. INT类型的分类

• TINYINT
  • 存储空间 ： 1 字节
  • 取值范围
    • 有符号(signed) ： [-128, 127]
    • 无符号(unsigned) ：[0, 255]

MySQL学习笔记（Day007：多实例下/SSL）

一. 多实例安装 – 多版本

1. [mysqld_multi]标签

• [mysqld_multi] 是否需要配置
  从操作演示来看，在my.cnf(老师给的模板配置)上直接配置[mysqld1]、[mysqld2]等实例标签，而不配置[mysqld_multi],使用mysqld_multi start 1也是可以启动数据库实例的，但是没有mysqld_safe的守护进程。所以该标签需要配置