ARTS 打卡 第 3 周

用户头像
引花眠
关注
发布于: 2020 年 06 月 10 日

ARTS简介

Algorithm 是一道算法题,Review 是读一篇英文文章,Technique/Tips 是分享一个小技术,Share 是分享一个观点。

Algorithm

Lecode-5 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"


力扣(LeetCode) 5.最长回文子串

解题思路:

  1. 如果使用暴力方法,找到字符串的所有子串,判断是否为回文字符串,粗略估算一下,大概会使用O(n^3)的时间复杂度(查找所有子串O(n^2),判断回文O(n))。不过使用暴力法,时间复杂度非常感人,所以我们思考能否使用其他方式,比如动态规划、回溯等。

  2. 这里考虑使用动态规划(关于动态规划的解释,建议阅读《算法导论》),使用动态规划最重要的是找到状态转换方程,回文很容易找到转换方程,

  3. 如果我们使用dp[i][j]来表示字符串 s 的第 i 到 j个字母组成的串是否为回文串,则

  4. 如果s[i]!=s[j],肯定不是回文字符串

  5. 如果s[i]==s[j],那么如果其子串也是回文,即dp[i+1][j-1]==true,则dp[i][j]也是回文。

  6. 做一些优化,如果只有一个字符,则肯定是回文字符串;如果有两个字符且字符相同,则是回文字符串;

class Solution {
public String longestPalindrome(String inputs) {
if (inputs == null || inputs.length() == 0) {
return "";
}
if (inputs.length() == 1 || (inputs.length() == 2 && inputs.charAt(0) == inputs.charAt(1))) {
return inputs;
}
int length = inputs.length();
boolean[][] dp = new boolean[length][length];
int begin = 0;
int maxLen = 1;
for (int j = 0; j < length; j++) {
dp[j][j] = true;
}
//这里需要注意,根据转换方程我们需要先判断dp[i+1][j-1],才能判断d[i][j]
//所以我们的执行顺序如下
for (int j = 0; j < length; j++) {
for (int i = 0; i < j; i++) {
if (inputs.charAt(i) == inputs.charAt(j)) {
if (i == j - 1) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
if (dp[i][j] && j - i + 1 > maxLen) {
begin = i;
maxLen = j - i + 1;
}
}
}
// System.out.println(Arrays.deepToString(dp));
return inputs.substring(begin, begin + maxLen);
}
}

Review

学习-微服务架构模式系列,网站地址是:https://microservices.io

微服务架构-Pattern: Decompose by business capability

这篇文章的主要介绍了分解模式:根据业务能力进行服务拆分:

当我们使用微服务的架构是,需要对整个应用进行分解,有多种分解的方式,这篇文章介绍的是根据业务能力进行分解。

分解服务的强制条件:

  1. 结构必须稳定

  2. 服务必须是高内聚的

  3. 松耦合的

  4. 可测试的

  5. 服务必须小,支撑团队小6-10

  6. 必须是自治的,与其他团队交互较少

在此种情况下,可以根据业务能力进行分解,企业的业务能力是业务能力是业务架构建模中的一个概念。它是一个企业为了创造价值而做的事情,比如:

  1. 将订单相关分解为订单服务

  2. 物流管理相关服务等等

这样的好处:

  1. 因为业务功能是稳定的,所以服务也相对稳定

  2. 使用业务划分团队时,团队较小,非常自治

Tips

记录我对于Linux的学习,从磁盘相关的命令开始:

ps:”~” 表示为 home 目录,”.” 则是表示目前所在的目录,”..” 则表示当前目录的上一层目录

-h 用人类可读的格式展示(G(千兆字节),M(兆字节),K(千字节)),大部分命令有这个参数

dir 命令用于显示指定工作目录下之内容

ls 用于显示指定工作目录下之内容(列出目前工作目录所含之文件及子目录)

常用的参数有:

  1. -l 除文件名称外,亦将文件型态、权限、拥有者、文件大小等资讯详细列出

  2. -a 显示所有文件及目录 (ls内定将文件名或目录名称开头为”.”的视为隐藏档,不会列出)

dirs(不是dir)显示当前目录栈中的所有记录(不带参数的dirs命令显示当前目录栈中的记录)

dir -al
total 104
dr-xr-xr-x. 22 root root 4096 Nov 25 2019 .
dr-xr-xr-x. 22 root root 4096 Nov 25 2019 ..
dr-xr-xr-x. 2 root root 4096 Sep 17 2019 bin
dr-xr-xr-x. 4 root root 4096 Apr 21 2016 boot
....
###
ls -al
total 104
dr-xr-xr-x. 22 root root 4096 Nov 25 2019 .
dr-xr-xr-x. 22 root root 4096 Nov 25 2019 ..
dr-xr-xr-x. 2 root root 4096 Sep 17 2019 bin
dr-xr-xr-x. 4 root root 4096 Apr 21 2016 boot
...
### 显示当前目录栈中的记录
dirs
/tmp

ps:关于ls与dir命令之间的关系,可以看这篇文章‘dir’和’ls’终端命令之间的区别?

Share

分享最近对计算机基础的复习,这次分享的是信息的表示与存储-浮点数的表示,可能会有不足之处,之后会根据理解继续修改。



发布于: 2020 年 06 月 10 日 阅读数: 44
用户头像

引花眠

关注

还未添加个人签名 2018.06.11 加入

还未添加个人简介

评论

发布
暂无评论
ARTS打卡 第3周