Fork me on GitHub

ARTS 第三周

What’s ARTS?
A:Algorithm 每周至少做一个leetcode的算法题
R:Review 阅读并点评至少一遍英文技术文章
T:Tip 学习至少一个技术技巧
S:Share 分享一篇有观点和思考的技术文章

1. Algorithm

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串s,在s中找出最长回文子串。你可以假设s的最大长度为s。

 这道题难度为Medium,有很多种解法,自己刚开始想到的是使用暴力法去暴力破解,不过这种方法的时间复杂度太高,先枚举所有子串,对每个子串进行判断是否为回文,此种方法的时间复杂度为O(n^3),在网上看到有人用动态规划的方法,遂学习了下动态规划,关于动态规划——想单独写一篇文章记录下,就不在这里介绍了。代码如下

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
string longestPalindrome(string s)
{
if (!s.size())
return "";
int len = s.size();
int left = 0,right = 0;
bool dp[len][len];
dp[0][0] = true;
for (int i = 1;i<len;++i) {
dp[i][i] = true;
dp[i][i-1] = true;
}
for (int i = 2;i <= len;++i) {
for (int j = 0;j <= len-i;++j) {
if (s[j]==s[len-i-1] && dp[j+1][j+i-2]) {
dp[j][i+j-1] = true;
if (right-left+1 < i) {
left = j;
right = j+i-1
}
}
}
}
return s.substr(left,right-left+1);
}

2. Review

 先上链接Tutorial For Dynamic programming
 该文章讲解了Dynamic programming(动态规划),分别举例说明了DP的两种形式

 There are two ways of doing this.
 1.) Top-Down : Start solving the given problem by breaking it down. If you see that the problem has been solved already, then just return the saved answer. If it has not been solved, solve it and save the answer. This is usually easy to think of and very intuitive. This is referred to as Memoization.
 2.) Bottom-Up : Analyze the problem and see the order in which the sub-problems are solved and start solving from the trivial subproblem, up towards the given problem. In this process, it is guaranteed that the subproblems are solved before solving the problem. This is referred to as Dynamic Programming.

2.1 Memoization

 第一种自顶向下的方法,通过分解来解决给定的问题。如果你发现问题已经解决,就只需要返回已保存的答案,如果尚未解决,请解决并保存答案。这种方法被称为Memoization(备忘录法)。

 Recursion uses the top-down approach to solve the problem i.e. It begin with core(main) problem then breaks it into subproblems and solve these subproblems similarily. In this approach same subproblem can occur multiple times and consume more CPU cycle ,hence increase the time complexity. Whereas in Dynamic programming same subproblem will not be solved multiple times but the prior result will be used to optimise the solution. eg. In fibonacci series

 自顶向上的方法通常使用递归求解,即它从核心(主要)问题开始,然后将其分解为子问题并解决这些类似的子问题。在这种方法中,相同的子问题可能会多次出现并消耗更多的CPU周期,因此这种解决方法增加时间复杂度

2.2 Dynamic Programming

 第二种自底向上的方法,分析问题并查看子问题被解决的顺序,并从子问题开始解决问题,在此过程中,保证在解决问题之前解决子问题,这就是所谓的动态规划。
 关于动态规划会在另一篇博客中详细的介绍、记录一下。

2.3 Remark

 这篇文章详细的介绍了动态规划的概念,并通过三个问题一一讲解了Memoization和DP这两种解决方法的区别,总的来说是一篇非常不错很适合像我这种之前都不知道DP的人,一看就能懂就会的文章。值得mark

3. Tips

最近有使用到docker,在这里简单说下docker一些基础的操作命令

  1. docker pull 从镜像仓库拉取指定镜像
  2. docker images 查看本地所有镜像
  3. docker rmi 删除本地一个或多个镜像
  4. docker ps 查看正在运行的容器
  5. docker ps -a 查看所有容器
  6. docker run 运行容器,通常使用-it以交互模式运行容器
  7. docker top 查看容器中运行的进程信息
  8. docker start/stop/restart 对容器的操作
  9. docker rm 删除一个容器或多个容器

4. Share

分享的还是跟动态规划有关,这个使用漫画的形式,非常详细的介绍了动态规划,几乎纯小白一看就能懂的文章 文章链接

您的赞赏是对我最大的支持,谢谢!