ARTS Week 19

Algorithm

本周的 LeetCode 题目为 5. 最长回文子串

给你一个字符串 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 和我们平时的概念有所不同，它们的对比表如下：

通过查看 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 numpydata = [[1, 2], [3, 4]]
avg = numpy.average(data, axis=0)
print(avg) # [2, 3]

Share

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