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

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

内容情况 你会称它为 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]

Share

祝大家新年快乐,身体健康,万事如意!