ARTS Week 19

Algorithm

给你一个字符串 s，找到 s 中最长的回文子串。例如输入：s = "babad"，输出："bab"

本题使用动态规划进行解决，动态规划的核心就在于找到状态转移方程。通过观察发现，回文串去掉首尾两个字符后，依然是回文串，即 dp[i][j] = dp[i+1][j-1] ^ (s[i] == s[j])，再加上只有一个或两个字符时作为初始条件，因此状态转移方程为：

dp[i][i] = true,

dp[i][i+1] = (s[i] == s[i+1]),

dp[i][j] = dp[i+1][j-1] ^ (s[i] == s[j]), j-i>1

根据状态转移方程，很容易写出代码，主要要记录下最长回文子串的开始索引和长度，以方便得到该回文子串。

class Solution {

    public String longestPalindrome(String s) {

        int length = s.length();

        if (length < 2) {

            return s;

        }

        int maxLength = 1;

        int begin = 0;

        boolean[][] dp = new boolean[length][length];

        for (int i = 0; i < length; i++) {

            dp[i][i] = true;

        }

        for (int right = 1; right < length; right++) {

            for (int left= 0; left < right; left++) {

                if (s.charAt(left) != s.charAt(right)) {

                    dp[left][right] = false;

                } else {

                    if (right - left < 3) {

                        dp[left][right] = true;

                    } else {

                        dp[left][right] = dp[left+1][right-1];

                    }

                }

                if (dp[left][right] == true && (right - left + 1 > maxLength)) {

                    maxLength = right - left + 1;

                    begin = left;

                }

            }

        }

        return s.substring(begin, begin+maxLength);

    }

}

Review

本周 Review 的英文文章为：不要怕，你的内存是够用的！

因为 Linux 系统中存在着磁盘缓存，其目的是为了让系统变得更快。当你需要更多的内存时，磁盘缓存会自动释放来满足应用或进程的需要。虽然你无法关闭，但是你想强制清除目前的缓存，可以运行 echo 3 | sudo tee /proc/sys/vm/drop_caches。

但是我们在使用 top 或 free 命令查看内存时，却经常发现内存都已经被使用了，但这实际上是因为 Linux 系统中的 free 和 available 和我们平时的概念有所不同，它们的对比表如下：

内容情况	你会称它为	Linux 系统会称它为
被应用所使用	Used	Used
被使用，但可以使得其可用	Free (or Available)	Used (or Available)
没有被使用	Free	Free

通过查看 free 命令显示结果中 available 这一列，你便可以得到现在系统中实际可用的内存。

$ free -m

                total        used        free      shared  buff/cache   available

  Mem:           1504        1491          13           0         855      792

  Swap:          2047           6        2041

最后作者给出了具体的何时需要担心内存情况的建议。当下面的情况发生时，你并不需要担心内存是否够用：

free 值接近了0
used 值接近了 total 值
available 值（或者free + buffers/cache的和）是足够的（占 total 20% 以上）
swap 那一行中 used 的值没有改变

下面是值得注意的真正低内存可用的警告信号：

available 值（或者free + buffers/cache的和）接近0
swap 那一行中 used 的值在增加或者波动
使用 dmesg | grep oom-killer 来查看 OutOfMemory-killer 是否在工作

Tip

Python 中一个二维数组按列计算每一列的平均值，需要使用 numpy 包，调用 numpy.average(data, axis=0) 语句来执行，当 axis=1 时则为按行计算均值，示例如下：

import numpy

data = [[1, 2], [3, 4]]

avg = numpy.average(data, axis=0)

print(avg) # [2, 3]

祝大家新年快乐，身体健康，万事如意！

巴特西

ARTS Week 19

Algorithm

Review

Tip

Share

最新文章

热门文章