ARTS-week49

Algorithms

Find All Anagrams in a String
思路: 用哈希表分别记录p的字符个数和s中前p个字符串长度的字符个数，再进行比较，如果两者相同，则将0加入结果res中，之后开始遍历s中剩余的字符，右边加入一个新字符，左边就删除一个旧字符，再比较两个哈希表是否相同。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.empty()) {
            return {};
        }
        vector<int> res, m1(256, 0), m2(256, 0);
        for (int i = 0; i < p.size(); ++i) {
            ++m1[s[i]];
            ++m2[p[i]];
        }
        
        if (m1 == m2) res.push_back(0);
        
        for (int i = p.size(); i < s.size(); ++i) {
            ++m1[s[i]]; 
            --m1[s[i - p.size()]];
            if (m1 == m2) {
                res.push_back(i - p.size() + 1);
            }
        }
        return res;
    }
};

Arranging Coins
思路: 等差数列。

class Solution {
public:
    int arrangeCoins(int n) {
        if (n <= 0) {
            return 0;
        }
        return int((sqrt(8.0 * n + 1.0) - 1.0) / 2.0); 
    }
};

Review

本周阅读英文文章:
Hacking and social engineering with a 70% success rate

Tutorial: How to scale and rotate contours in OpenCV using Python

Technique

在极客时间的专栏《Python核心技术与实践》中学习到关于Python垃圾回收的知识点:

Python使用标记清除(mark-sweep)算法和分代收集(generational)算法来启用针对循环引用的自动垃圾回收。

1)不可达。先用图论来理解不可达的概念，对于一个有向图，如果从一个节点出发进行遍历，并标记其经过的所有节点；那么，在遍历结束后，所有没有被标记的节点，我们就称之为不可达节点。显而易见，这些节点的存在是没有任何意义的，自然的，我们就需要对它们进行垃圾回收。

2)标记清除算法。每次都遍历全图，对于Python而言是一种巨大的性能浪费。所以，在Python的垃圾回收实现中，mark-sweep使用双向链表维护了一个数据结构，并且只考虑容器类的对象(只有容器类对象才有可能产生循环引用)。

3)分代收集算法，则是另一个优化手段。Python将所有对象分为三代。刚刚创立的对象是第0代；经过一次垃圾回收后，依然存在的对象，便会依次从上一代挪到下一代。而每一代启动自动垃圾回收的阈值，则是可以单独指定的。当垃圾回收器中新增对象减去删除对象达到相应的阈值时，就会对这一代对象启动垃圾回收。

事实上，分代收集基于的思想是，新生的对象更有可能被垃圾回收，而存活更久的对象也有更高的概率继续存活。因此，通过这种做法，可以节约不少计算量，从而提高Python的性能。

记录本周踩的一个小坑:

给一台新机器装Ubuntu 18.04 Desktop，用rufus做的U盘启动，一直使用这个工具，十分好用，是Ubuntu官方文档中推荐的方式:
https://tutorials.ubuntu.com/tutorial/tutorial-create-a-usb-stick-on-windows#0

但是这次出现了问题，第一次进入了grub命令行，这十分的尬尴，重新刻录了一次后，可以进入安装选项界面，选择Install Ubuntu后报错/casper/vmlinuz: not found。和ISO镜像文件对比了一下，的确缺少文件。

想起rufus在写入之前弹出了检测到ISOHybrid镜像的提示说在引导遇到问题时，可以尝试以DD镜像模式写入，之前我一直选择的是以ISO镜像模式写入，更改为以DD镜像模式写入后，成功引导，完成安装。

查了一下，Manjaro在用户手册中推荐使用DD模式:

Rufus
For Windows users using USB media, Rufus is highly recommended.
Select the USB key to be used in the Device menu. Then, on the
line beginning with Boot selection, click on Select to select your down-
loaded disc image, and then Start. After doing so, select DD Image
in the window that appears.

突然对Manjaro产生了极大的兴趣，想装一个玩玩😮

Algorithms

Review

Technique

Share