头像

西河二当家

复旦大学


访客:3646

离线:1天前



换到 Ubuntu18.4 后,除了驱动问题,等宽字体渲染问题也困扰了我好久。比如 acwing 代码块,leetcode 代码块,typora 代码块等都出现等宽字体不正常、未显示等宽字体等问题,如图:

bad_monospace.jpg

typora 我曾用修改 css 的方式解决了,但是 acwing 等网站上的代码块字体异常就没办法自己改了。

后来看了 一篇博客,按照该方式修复成功。我对作者某些手误的地方进行了修正,在此分享(作者未留联系方式,如果得到联系方式,我会及时征得作者同意)。

1 前置知识

首先我们常用字体主要有两类:中文字体和拉丁字体

而通常字体分为如下几类

  • 衬线字体(Serif),这种字体适合打印使用而不是液晶屏
  • 无衬线字体(Sans Serif),与Serif恰好相反
  • 等宽字体(Monospace或Mono),一般是程序员的最爱,一个中文等宽字体等于两个拉丁等宽字体

2 等宽字体修复

仔细研究后,问题原因其实是:这两个软件包是中文字体渲染包,但是编写者为了简洁直接将整个系统字体全部设为改字体(包括拉丁文字),部分软件有自己的字体设置优先级较高就没有收到影响,其它的就因为没有安装该字体所以出锅了…

所以我们的问题成功转化为给系统英文等宽字体一个更高的优先级来覆盖掉这两个软件包的修改

我用开发者模式观察了一下各大OJ的代码块字体加载设置,主要有Monaco,Consolas,Ubuntu Mono三个等宽字体是一定会加载的,但Ubuntu安装Consolas只可以安装一个叫做YaHei Consolas Hybrid YaHei Consolas Hybird Regular的字体,所以考虑使用Ubuntu Mono和Monaco(推荐使用Monaco,我的Ubuntu Mono好像亲测失败)

首先安装Monaco,在终端依次运行

$sudo mkdir /usr/share/fonts/Monaco
$sudo cp Monaco.ttf /usr/share/fonts/Monaco
$cd /usr/share/fonts/Monaco
$sudo mkfontscale && sudo mkfontdir && sudo fc-cache -fv

然后新建 ~/.fonts.conf,修改为(Monaco),这一步是添加这两个字体到系统的字体加载顺序中(这个文件是用户font配置文件)

<?xml version="1.0"?>
<!DOCTYPE fontconfig SYSTEM "fonts.dtd">
<fontconfig>
    <match>
        <test name="family"><string>sans-serif</string></test>
        <edit name="family" mode="prepend" binding="strong">
            <string>Monaco</string>
        </edit>
    </match>
    <match>
        <test name="family"><string>serif</string></test>
        <edit name="family" mode="prepend" binding="strong">
            <string>Monaco</string>
        </edit>
    </match>
    <match>
        <test name="family"><string>monospace</string></test>
        <edit name="family" mode="prepend" binding="strong">
            <string>Monaco</string>
        </edit>
    </match>
</fontconfig>

接下来还需要对系统的字体加载顺序进行修改,打开

$sudo vim /etc/fonts/conf.d/60-latin.conf

在每一个 <prefer> 后面添加 <family>Monaco</family>,给一个例子:

<alias>
    <family>serif</family>
    <prefer>
        <family>Monaco</family>

这样就可以了

3 字体渲染修复

打开 /etc/fonts/conf.avail/64-language-selector-prefer.conf,发现里面的代码JP(日语)优先度高于SC(中文),所以将每一个SC代码移动到优先级最高的位置

另外linux中文字体很多hint打开但默认中文字体是没有hint的,所以最好新建文件/etc/fonts/local.conf,修改为

<?xml version='1.0'?>
<!DOCTYPE fontconfig SYSTEM 'fonts.dtd'>
<fontconfig>
    <match target="font">
        <edit name="hintstyle" mode="assign">
            <const>hintnone</const>
        </edit>
    </match>
</fontconfig>

这样可以把所有字体的hint全部禁用



活动打卡代码 AcWing 90. 64位整数乘法

龟速乘

用模板因子 ( $a \times {2^i}$ ) 加法实现乘法,防止 long long 溢出($2^{63} - 1 \approx 9 \times 10^8$)

$$
\begin{aligned}a \times k &= a \times (k_0 \times 2^0 + k_1 \times 2^1 + k_2 \times 2^2 + … + k_m \times 2^m) \\ &= a \times {k_0 \times 2^0} + a \times {k_1 \times 2^1} + a \times {k_2 \times 2^2} + … \times a \times {k_m \times 2^m}\end{aligned}
$$

显然
$$
a \times {k_i \times 2^i} = \begin{cases}0 & k_i = 0 \\ a \times {2^i} & k_i = 1\end{cases}
$$

因此
$$
a \times k = \prod_{i \in \lbrace i |k_i=1 \rbrace} a \times {2^i}
$$

#include <iostream>

using namespace std;
using LL = long long;

// 求 a*k % p
LL tmu(LL a, LL k, LL p)
{
    LL res = 0;
    while (k)
    {
        if (k & 1) res = (res + a) % p;
        a = (a + a) % p;
        k >>= 1;
    }
    return res;
}

int main()
{
    LL a, b, p;
    cin >> a >> b >> p;
    cout << tmu(a, b, p) << endl;
    return 0;
}


活动打卡代码 AcWing 106. 动态中位数

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    int T;
    scanf("%d", &T);

    while (T --)
    {
        int idx, n;
        scanf("%d%d", &idx, &n);

        printf("%d %d\n", idx, n + 1 >> 1);

        priority_queue<int> down;
        priority_queue<int, vector<int>, greater<int>> up;

        int cnt = 0;
        for (int i = 1; i <= n; i ++)
        {
            int x;
            scanf("%d", &x);

            if (down.empty() || x <= down.top()) down.push(x);
            else up.push(x);

            if (down.size() > up.size() + 1) up.push(down.top()), down.pop();
            if (up.size() > down.size()) down.push(up.top()), up.pop();

            if (i % 2) {
                printf("%d ", down.top());
                if (++cnt % 10 == 0) puts("");
            }
        }
        if (cnt % 10) puts("");
    }

    return 0;
}


活动打卡代码 AcWing 105. 七夕祭

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

using LL = long long;

const int N = 1e5 + 10;

int row[N], col[N], s[N], c[N];


// x[i]: a[i] 给 a[i-1] 的糖果数
//
// a1 - x1 + x2 = avg
// a2 - x2 + x3 = avg
// a3 - x3 + x4 = avg
// ......
// an - xn + x1 = avg
//
// =>
//
// x1 = x1 - c1 = x1 - 0
// x2 = x1 - c2 = x1 - (a1 - avg)
// x3 = x1 - c3 = x1 - (a1 + a2 - 2*avg)
// ......
// xn = x1 - cn = x1 - (a1 + a2 + ... + a[n-1] - (n-1)*avg)

LL work(int n, int a[])
{
    for (int i = 1; i <= n; i ++) s[i] = s[i-1] + a[i];  // 求前缀和

    if (s[n] % n) return -1;

    int avg = s[n] / n;

    c[1] = 0;
    for (int i = 2; i <= n; i ++) c[i] = s[i-1] - (i - 1) * avg;

    sort(c + 1, c + n + 1);

    LL res = 0;
    for (int i = 1; i <= n; i ++) res += abs(c[i] - c[(n + 1) / 2]);

    return res;
}

int main()
{
    int n, m, cnt;
    scanf("%d%d%d", &n, &m, &cnt);

    while (cnt --)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        row[x] ++, col[y] ++;
    }

    LL r = work(n, row);
    LL c = work(m, col);

    if (r != -1 && c != -1) printf("both %lld\n", r + c);
    else if (r != -1) printf("row %lld\n", r);
    else if (c != -1) printf("column %lld\n", c);
    else printf("impossible\n");

    return 0;
}


活动打卡代码 LeetCode 15. 三数之和

题目

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

双指针算法。

nums[j] + nums[k] + nums[i] >= 0

对于有序数组,i固定,若j变大,为保证总和靠近0,则k应当变小。

为保证三元组不重复,对 ij 进行无重复枚举。

C++代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n; i ++)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1, k = n - 1; j < k; j ++)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= 0) k --;
                if (nums[i] + nums[j] + nums[k] == 0) 
                    res.push_back({nums[i], nums[j], nums[k]});
            }
        }
        return res;
    }
};


活动打卡代码 LeetCode 14. 最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

C++代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        int k = 0;
        bool flag = true;
        while (flag)
        {
            if (k >= strs[0].size()) break;
            char ch = strs[0][k];
            for (auto& str: strs)
                if (k >= str.size() || str[k] != ch)
                {
                    flag = false;
                    break;
                }

            if (flag) k ++;
        }
        return strs[0].substr(0, k);
    }
};



题目

罗马数字包含以下七种字符: IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。

示例 1:

输入: "III"
输出: 3

示例 2:

输入: "IV"
输出: 4

示例 3:

输入: "IX"
输出: 9

示例 4:

输入: "LVIII"
输出: 58
解释: L = 50, V = 5, III = 3.

示例 5:

输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

分析

按照个十百千位分别将阿拉伯数字映射为罗马数字。

1    2    3    4    5    6    7    8    9  
I    II   III  IV   V    VI   VII  VIII IX

10   20   30   40   50   60   70   80   90 
X    XX   XXX  XL   L    LX   LXX  LXXX XC

100  200  300  400  500  600  700  800  900
C    CC   CCC  CD   D    DC   DCC  DCCC CM

1000 2000 3000
M    MM   MMM

如果当前罗马字母对应的数字小于后面的,那就减去当前罗马字母对应数字,否则加上当前罗马字母对应数字。

C++代码

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> r2i;
        r2i['I'] = 1;
        r2i['V'] = 5;
        r2i['X'] = 10;
        r2i['L'] = 50;
        r2i['C'] = 100;
        r2i['D'] = 500;
        r2i['M'] = 1000;

        int res = 0;
        for (int i = 0; i < s.size(); i ++)
            if (i + 1 < s.size() && r2i[s[i]] < r2i[s[i + 1]])
                res -= r2i[s[i]];
            else
                res += r2i[s[i]];

        return res;
    }
};



题目

罗马数字包含以下七种字符: IVXLCDM

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

  • I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
  • X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
  • C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。

给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: "III"

示例 2:

输入: 4
输出: "IV"

示例 3:

输入: 9
输出: "IX"

示例 4:

输入: 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

分析

按照个十百千位分别将阿拉伯数字映射为罗马数字。

1    2    3    4    5    6    7    8    9  
I    II   III  IV   V    VI   VII  VIII IX

10   20   30   40   50   60   70   80   90 
X    XX   XXX  XL   L    LX   LXX  LXXX XC

100  200  300  400  500  600  700  800  900
C    CC   CCC  CD   D    DC   DCC  DCCC CM

1000 2000 3000
M    MM   MMM

记录几个特殊阿拉伯数字对应的罗马数字即可。

C++代码

class Solution {
public:
    string intToRoman(int num) {
        int values[] = {
            1000,
            900, 500, 400, 100,
            90, 50, 40, 10,
            9, 5, 4, 1
        };
        string reps[] = {
            "M",
            "CM", "D", "CD", "C",
            "XC", "L", "XL", "X",
            "IX", "V", "IV", "I"
        };

        string res;
        for (int i = 0; i <= 12; i ++)
            while (num >= values[i])
            {
                num -= values[i];
                res += reps[i];
            }
        return res;
    }
};



题目

给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

lc.11

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例:

输入:[1,8,6,2,5,4,8,3,7]
输出:49

分析

贪心:两个指针,最初指向两个端点。每轮比较两个指针所指的元素值,记录容积,并将值较小的指针向中间移动。

证明:

假设最优解为 (i, j),目标是证明我们的移动策略可以经历最优解。

最初指针在两端,那么按照我们的策略,必然有其中一个指针率先达到最优解的其中一个端点,不妨设指针1达到了左端点 i,此时指针2达到了k(k >j)。

那么只需要证明,从j+1到k,所有元素值都小于a[i]。

反证法:
假设存在某个位置 p 位于 j+1到k之间,使得 a[p] >= a[i],
那么此时容积为 a[i] * (p-i) > a[i] * (j - i) >= 最优解
矛盾。

因此,从j+1到k,所有元素值都小于a[i],按照我们的移动策略,此后会一直移动指针2,直到指针2指向a[j],即我们的策略达到了最优解。

C++代码

class Solution {
public:
    int maxArea(vector<int>& height) {
        int i = 0, j = height.size() - 1;
        int res = 0;
        while (i < j)
        {
            vol = (j - i) * min(height[i], height[j]);
            res = max(res, min(height[i], height[j]) * (j - i));
            if (height[i] < height[j]) i ++;
            else j --;
        }
        return res;
    }
};



题目

给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

’.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 ‘a’。因此,字符串 “aa” 可被视为 ‘a’ 重复了一次。

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: “.” 表示可匹配零个或多个(’‘)任意字符(’.’)。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

分析

状态表示f(i, j):
    集合: 所有s[1~i]和p[1~j]的匹配方案
    属性: 集合是否非空(是否存在一个合法方案)
状态计算:
    if (p[j] != '*')
        f(i,j) = (s[i]==p[j] || p[j]=='.') && f(i-1,j-1)
    else if (p[j] == '*')
        f(i,j) = f(i,j-2)                                   ||      // *表示 0 个字符
                 f(i-1,j-2) && match(s[i])                  ||      // *表示 1 个字符
                 f(i-2,j-2) && match(s[i]) && match(s[i-1]) ||      // *表示 1 个字符
                 ...
               = f[i][j-2] || f[i-1][j] & match(s[i])  // 简化后

p[j] == '*' 时,简化的推导过程如下

由
f[i][j] = f[i][j-2] || 
          f[i-1][j-2] && match(s[i]) || 
          f[i-2][j-2] && match(s[i]) && match(s[i-1]) || 
          ...
得
f[i-1][j] =             
          f[i-1][j-2] || 
          f[i-2][j-2] && match(s[i-1]) || 
          f[i-3][j-2] && match(s[i-1]) && match(s[i-2]) || 
          ...
那么
f[i][j] = f[i][j-2] || f[i-1][j] & match(s[i])

C++代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        // 让下标从 1 开始
        s = ' ' + s, p = ' ' + p;   
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
        // 初始状态
        f[0][0] = true;      // 两个空串自然匹配
        // f[+][0] = false;  // 目标串非空而模板串为空,必然不匹配 
        // 状态计算
        for (int i = 0; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                if (j + 1 <= m && p[j + 1] == '*')  // "a*"无法单独用, f[i][j]不用算了
                    continue;
                if (i && p[j] != '*') {  // 目标串为空却没有通配符时一定不匹配
                    f[i][j] = f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '.');
                } else if (p[j] == '*') {  // 有通配符就看之前是否匹配
                    f[i][j] = f[i][j - 2] || i && f[i - 1][j] && (s[i] == p[j - 1] || p[j - 1] == '.');
                }
            }

        return f[n][m];
    }
};