全部标签
写点什么
开源云计算行业资讯玩转写作平台算法Python人工智能区块链Linux前端个人成长面试架构师编程企业动态新基建敏捷安全读书笔记高效工作团队管理创业活动专区生涯规划知识管理运维产品经理 查看更多

ARTS 打卡 第 29 周

用户头像
引花眠
关注
发布于: 2021 年 01 月 31 日

ARTS 简介

Algorithm 是一道算法题，Review 是读一篇英文文章，Technique/Tips 是分享一个小技术，Share 是分享一个观点。


Algorithm

力扣（LeetCode）76. 最小覆盖子串


给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。


示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"输出："BANC"示例 2：
输入：s = "a", t = "a"输出："a" 
提示：
1 <= s.length, t.length <= 105s 和 t 由英文字母组成

复制代码


解题思路：如果你看过算法小抄，就可以得出这是一个可以用滑动窗口解决的问题，而滑动窗口的解题思路就是用双指针，在合适的时候增大或缩小窗口空间。以下是滑动窗口的解题模板:


//该模板来自[labuladong的算法小抄](https://book.douban.com/subject/35252621/)public void slidingWindow(String s, String t) {        Map<Character, Integer> need = new HashMap<>();//统计每个需要判断的字符数量        Map<Character, Integer> window = new HashMap<>();//在窗口中每个满足条件的各个字符的数量        for (int i = 0, len = t.length(); i < len; i++) {            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);        }        int lenOfS = s.length();        int left = 0;        int right = 0;//[left,right)表示窗口的大小        int valid = 0;        int start = 0;        int len = Integer.MAX_VALUE;        while (right < lenOfS) {            //d是将要加入窗口的字符            char c = s.charAt(right);            //右移窗口            right++;            // 更新窗口中的数据            //...            //判断是否要收缩窗口            while (window need shrink) {                //d是将要移除窗口的字符                char d = s.charAt(left);                //左移窗口                left++;                //进行窗口类数据的更新            }        }
    }
复制代码


根据该模板，我们可以思考对于当前问题：


  1. 当 right 增加时，我们应该判断需要更新哪些数据

  2. 什么条件下我们应该缩小 left

  3. 缩小 left 之后，应该更新哪些数据

  4. 我们需要的结果是在缩小窗口时候更新，还是在扩大时更新


class Solution {    public String minWindow(String s, String t) {        Map<Character, Integer> need = new HashMap<>();        Map<Character, Integer> window = new HashMap<>();        for (int i = 0, len = t.length(); i < len; i++) {            need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);        }        int lenOfS = s.length();        int left = 0;        int right = 0;        int valid = 0;        int start = 0;        int len = Integer.MAX_VALUE;        while (right < lenOfS) {            char c = s.charAt(right);            right++;            if (need.containsKey(c)) {                window.put(c, window.getOrDefault(c, 0) + 1);                if (window.get(c).equals(need.get(c))) {                    valid++;                }            }            while (valid == need.size()) {                if (right - left < len) {                    start = left;                    len = right - left;                }                char d = s.charAt(left);                left++;                if (need.containsKey(d)) {                    if (window.get(d).equals(need.get(d))) {                        valid--;                    }                    window.put(d, window.get(d) - 1);                }            }        }        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);    }
}
复制代码


ps:参考资料


  1. 《剑指Offer：名企面试官精讲典型编程题（第2版）》

  2. labuladong 的算法小抄

  3. labuladong的算法小抄-实体书


Review

学习-微服务架构模式系列，网站地址是：https://microservices.io 微服务架构-Pattern: Domain-specific protocol 这篇文章的主要介绍了微服务架构下的通信模式：领域专用协议 背景：使用微服务架构，服务需要处理客户端的请求，可能需要多个客户端协作才能处理。所以需要跨服务通信。


解决方法，使用领域专有协议：


  1. 电子邮件协议，如 SMTP 和 IMAP

  2. 媒体流协议，如 RTMP、HLS 和 HDS


ps:《微服务架构设计模式》


Tips

记录我对于 Linux 的学习，网络管理的命令：


ps:“~” 表示为 home 目录，“.” 则是表示目前所在的目录，“…” 则表示当前目录的上一层目录 -h 用人类可读的格式展示(G（千兆字节），M（兆字节）,K（千字节）)，大部分命令有这个参数


top

top 用来监控 Linux 系统状况，比如 cpu、内存的使用等 用法： top [选项] 常用选项： 选项：


  1. -d 秒数：指定 top 命令每隔几秒更新。默认是 3 秒；

  2. -b 使用批处理模式输出。一般和"-n"选项合用，用于把 top 命令重定向到文件中；

  3. -n 次数：指定 top 命令执行的次数。一般和"-"选项合用；

  4. -p 进程 PID：仅查看指定 ID 的进程；

  5. -s 使 top 命令在安全模式中运行，避免在交互模式中出现错误；

  6. -u 用户名：只监听某个用户的进程；


在 top 命令的显示窗口中，还可以使用如下按键，进行一下交互操作：


  1. ? 或 h：显示交互模式的帮助；

  2. P：按照 CPU 的使用率排序，默认就是此选项；

  3. M：按照内存的使用率排序；

  4. N：按照 PID 排序；

  5. T：按照 CPU 的累积运算时间排序，也就是按照 TIME+ 项排序；

  6. k：按照 PID 给予某个进程一个信号。一般用于中止某个进程，信号 9 是强制中止的信号；

  7. r：按照 PID 给某个进程重设优先级（Nice）值；

  8. q：退出 top 命令；


以下时 top 命令的输出：


top - 20:42:01 up 4 days,  3:52,  3 users,  load average: 0.93, 1.26, 1.45任务: 315 total,   1 running, 312 sleeping,   0 stopped,   2 zombie%Cpu(s): 19.0 us,  5.6 sy,  0.0 ni, 72.8 id,  1.5 wa,  0.9 hi,  0.2 si,  0.0 stMiB Mem :  48128.1 total,  27592.0 free,  15048.8 used,   5487.2 buff/cacheMiB Swap:  32768.0 total,  30745.9 free,   2022.1 used.  31456.8 avail Mem
 进程号 USER      PR  NI    VIRT    RES    SHR    %CPU  %MEM     TIME+ COMMAND   1127 shaozuo   20   0 4827944 443792  76156 S  39.2   0.9 475:58.44 gnome-shell 143752 shaozuo   20   0    9.8g   1.0g 267732 S  12.3   2.2 274:39.21 chromium 493576 root      20   0       0      0      0 D  10.6   0.0   2:45.31 kworker/u8:3+events_unbound 342062 shaozuo   20   0  688556  98992  50172 S   5.0   0.2  52:39.91 chromium   1008 shaozuo   20   0  747660 148920  99328 S   4.0   0.3 135:37.79 Xorg   1427 shaozuo   20   0 1797292 132428  27772 S   3.0   0.3  17:03.96 variety 207946 shaozuo   20   0  962768  50996  29456 S   3.0   0.1   0:22.57 konsole 143603 shaozuo   20   0 3336320 807332  99196 S   2.3   1.6 209:43.42 chromium   2158 shaozuo   20   0  880248 257032 122552 S   2.0   0.5 119:11.19 chrome   2238 shaozuo   20   0 4606540  69296  40880 S   1.7   0.1  56:23.75 chrome   9637 shaozuo   20   0 4022072 360788 120844 S   1.7   0.7  86:25.07 firefox 143671 shaozuo   20   0 4732044  68084  40912 S   1.7   0.1  44:32.86 chromium   1021 shaozuo   20   0  480672  35192   4304 S   1.3   0.1   6:02.04 ibus-daemon 407636 shaozuo   20   0  105.6g   4.0g 113604 S   1.3   8.6  34:00.23 java 449984 shaozuo   20   0 4843976 618216  36124 S   1.0   1.3   1:39.73 java  84939 shaozuo   20   0 3060240 147000 113136 S   0.7   0.3   3:44.31 wpsoffice 336077 shaozuo   20   0 1199716 388972 107140 S   0.7   0.8  58:05.96 electron 490714 shaozuo   20   0   81.9g  88344  71776 S   0.7   0.2   0:04.66 WebKitWebProces
复制代码


1～5 行显示的系统整体信息:


  1. 第一行显示内容与 uptime 一样

  2. 第二行为进程信息任务: 315 total 系统中的进程总数 1 running 正在运行的进程数 312 sleeping 睡眠的进程数 0 stopped 正在停止的进程数 2 zombie 僵尸进程数。如果不是 0，则需要手工检查僵尸进程

  3. 第三行为 CPU 信息 19.0 us, 5.6 sy, 0.0 ni, 72.8 id, 1.5 wa, 0.9 hi, 0.2 si, 0.0 st%Cpu(s): 19.0 us 用户模式占用的 CPU 百分比 5.6 sy 系统模式占用的 CPU 百分比 0.0 ni 改变过优先级的用户进程占用的 CPU 百分比 72.8 id 空闲 CPU 占用的 CPU 百分比 1.5 wa 等待输入/输出的进程占用的 CPU 百分比 0.9 hi 硬中断请求服务占用的 CPU 百分比 0.2 si 软中断请求服务占用的 CPU 百分比 0.0 st st（steal time）意为虚拟时间百分比，就是当有虚拟机时，虚拟 CPU 等待实际 CPU 的时间百分比

  4. 第四行为物理内存信息 单位 MiB48128.1 total 物理内存的总量 27592.0 free 空闲的物理内存数量 15048.8 used 已使用的物理内存数量 5487.2 buff/cache 作为缓冲的内存数量

  5. 第五行为交换分区（swap）信息 单位 MiB32768.0 total 交换分区的总大小 30745.9 free 空闲交换分区的大小 2022.1 used. 已经使用的交换分区的大小 31456.8 avail Mem 可使用的交换分区大小


从第 6 行开始，显示的是系统中进程的信息：


  1. PID 进程的 ID。

  2. USER 该进程所属的用户。

  3. PR 优先级，数值越小优先级越高。

  4. NI 优先级，数值越小、优先级越高。

  5. VIRT 该进程使用的虚拟内存的大小，单位为 KB。

  6. RES 该进程使用的物理内存的大小，单位为 KB。

  7. SHR 共享内存大小，单位为 KB。

  8. S 进程状态。

  9. %CPU 该进程占用 CPU 的百分比。

  10. %MEM 该进程占用内存的百分比。

  11. TIME+ 该进程共占用的 CPU 时间。

  12. COMMAND 进程的命令名。


这只是默认显示的信息，top 可显示的信息还有很多，可以使用快捷键切换。 还可以使用htop，可以说是 top 的增强版本。


Share

最近在极客时间报名了训练营，时间有点不充分，后期会补上的。 先把很早之前的博客文章分享一下密码技术学习


划线
评论
复制
发布于: 2021 年 01 月 31 日阅读数: 27

版权声明: 本文为 InfoQ 作者【引花眠】的原创文章。

原文链接:【http://xie.infoq.cn/article/9608a1f059b4dabefac320658】。

本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。

微服务ARTS 打卡计划
用户头像

引花眠

关注

还未添加个人签名 2018.06.11 加入

还未添加个人简介

评论

发布
暂无评论
Copyright © 2021, Geekbang Technology Ltd. All rights reserved. 极客邦控股（北京）有限公司 | 京 ICP 备 16027448 号 - 5京公网安备京公网安备 11010502039052号
ARTS打卡 第29周