Maxw的小站

Maxw学习记录

发表于 分类于

定时器与时间管理

时间的流逝对内核至关重要。大量内核函数是由时间驱动的，而非事件驱动¹。其中一些函数是周期性的，例如调度器运行队列的平衡或屏幕刷新。它们按照固定计划执行，比如每秒100次。内核还会在未来某个相对时间调度其他函数，例如延迟的磁盘I/O。举例来说，内核可能会调度一个500毫秒后执行的任务。最后，内核还必须管理系统运行时间以及当前日期和时间。

需注意相对时间与绝对时间的区别。调度一个5秒后发生的事件不需要绝对时间的概念——只需相对时间（例如，从现在起5秒后）。相反，管理当前时间不仅要求内核理解时间的流逝，还需要掌握某种绝对时间度量。这两个概念对时间管理都至关重要。

此外，处理周期性事件与内核调度未来特定时间点事件的方式在实现上有所不同。周期性事件（比如每10毫秒一次）由系统定时器驱动。系统定时器是一种可编程硬件，能够以固定频率发出中断。该定时器的中断处理程序（称为定时器中断）负责更新系统时间并执行周期性工作。系统定时器及其定时器中断是Linux的核心，也是本章的重点内容。

本章的另一个重点是动态定时器，这种机制用于调度在指定时间间隔后仅执行一次的事件。例如，软盘设备驱动程序使用定时器在指定空闲时间后关闭软盘驱动器电机。内核可以动态创建和销毁定时器。本章将探讨动态定时器的内核实现，以及可供代码调用的相关接口。

¹ 更准确地说，时间驱动事件也属于事件驱动——这里的事件即指时间的流逝。但在本章中，我们特别强调时间驱动事件，因为其在内核中出现的频率及重要性尤为突出。

内核的时间概念

显然，计算机对时间的理解有些抽象。实际上，内核必须与系统硬件协同工作来理解和管理时间。硬件提供了一个系统定时器，内核借助它来度量时间的流逝。该系统定时器基于电子时钟源运行，例如数字时钟或处理器频率。系统定时器会按照预设频率（称为节拍率）触发（通常称为"命中"或"弹出"）。当系统定时器触发时，它会发出一个中断，内核通过特定的中断处理程序来处理该中断。

由于内核知晓预设的节拍率，它就能计算出任意两次连续定时器中断之间的时间间隔。这个周期称为一个"节拍"，相当于 1/(节拍率) 秒。这正是内核追踪实际时间和系统运行时间的方式。

实际时间（即一天中的具体时刻）对用户空间应用程序至关重要。内核之所以要追踪实际时间，根本原因在于内核控制着定时器中断。一系列系统调用向用户空间提供日期和时间信息。系统运行时间（即系统启动后的相对时间）对内核空间和用户空间都很有用。大量代码必须感知时间的流逝。两次运行时间读数（当前值与过去值）之间的差值，就是这种相对性的简单度量。

定时器中断对操作系统的管理至关重要。大量内核功能的生灭都与时间流逝紧密相关。定时器中断定期执行的部分工作包括：

  • 更新系统运行时间
  • 更新实际时间
  • 在SMP系统上，确保调度器运行队列处于平衡状态，若不平衡则进行平衡调整（如第4章"进程调度"所述）
  • 运行所有已到期的动态定时器
  • 更新资源使用情况和处理器时间统计信息

其中部分工作会在每次定时器中断时执行——也就是说，这些工作以节拍率的频率执行。而其他函数则定期执行，但仅在第n次定时器中断时才触发。也就是说，这些函数以节拍率的某个分数频率执行。在"定时器中断处理程序"一节中，我们将详细探讨该中断处理程序。

节拍率：HZ

系统定时器的频率（即节拍率）是在系统启动时，基于一个静态的预处理器定义 HZ 来设定的。对于每个受支持的体系结构，HZ 的值都不同。在某些受支持的体系结构中，它甚至在不同的机器类型之间也存在差异。

内核在 <asm/param.h> 头文件中定义了该值。节拍率的频率为 HZ 赫兹，周期为 1/HZ 秒。例如，在默认情况下，x86 架构将 HZ 定义为 100。因此，i386 上的定时器中断频率为 100Hz，即每秒发生 100 次（每百分之一秒一次，也就是每 10 毫秒一次）。HZ 的其他常见值还有 250 和 1000，分别对应 4 毫秒和 1 毫秒的周期。

在编写内核代码时，切勿假定 HZ 具有任何特定值。如今这已不是一个常见的错误，因为许多体系结构的节拍率各不相同。然而，在过去，Alpha 是唯一节拍率不等于 100Hz 的架构，经常会看到代码错误地硬编码了值 100，而实际上本应使用 HZ 值。后文将展示在内核代码中使用 HZ 的示例。

定时器中断的频率至关重要。正如您所看到的，定时器中断执行大量工作。实际上，内核的整个时间概念都源于系统定时器的周期性。选择合适的值，就像经营一段成功的关系，全在于权衡妥协。

理想的 HZ 值

从 Linux 的最初版本开始，i386 架构的定时器中断频率一直是 100 Hz。然而，在 2.5 开发系列期间，频率被提升到了 1000 Hz，并且（像这类事情一样）引起了争议。尽管频率后来又回到了 100 Hz，但它现在是一个配置选项，允许用户编译具有自定义 HZ 值的内核。由于系统的许多部分都依赖于定时器中断，改变其频率会对系统产生显著影响。当然，选择较大或较小的 HZ 值各有优缺点。

提高节拍率意味着定时器中断运行得更频繁。因此，它执行的工作也会更频繁地发生。这带来以下好处：

  • 定时器中断具有更高的分辨率，因此所有定时事件也具有更高的分辨率。
  • 定时事件的准确性得到提高。

分辨率随着节拍率的提高而同比例提升。例如，当 HZ=100 时，定时器的粒度是 10 毫秒。换句话说，所有周期性事件都沿着定时器中断的 10 毫秒周期发生，无法保证更精细的精度(我们这里使用的是计算机领域的"精度"含义，而非科学上的。科学上的精度是对可重复性的统计度量。在计算机中，精度是指用于表示一个值的有效数字位数)。而当 HZ=1000 时，分辨率是 1 毫秒——精细了 10 倍。尽管内核代码可以创建具有 1 毫秒分辨率的定时器，但并不能保证在 HZ=100 时提供的精度足以在优于 10 毫秒间隔的任何时间点上执行定时器。

同样，准确性也以相同的方式提高。假设内核在随机时间启动定时器，由于定时器可能在任何时间到期，但仅在定时器中断发生时才会被执行，因此定时器的平均误差为定时器中断周期的一半。例如，对于 HZ=100，事件发生的时间平均会在期望时间的 +/- 5 毫秒范围内。因此，平均误差为 5 毫秒。对于 HZ=1000，平均误差降至 0.5 毫秒——提高了十倍。

提高 HZ 值（节拍率）的优势

更高的分辨率和准确性带来了多重优势：

  • 内核定时器以更精细的分辨率和更高的准确性执行。（这带来了大量改进，其中之一如下所述。）
  • 诸如 poll() 和 select() 这类可选择使用超时值的系统调用，能够以更高的精度执行。
  • 资源使用情况或系统运行时间等测量值，能以更精细的分辨率被记录。
  • 进程抢占的发生更加精确。

最显而易见的性能提升，来自于 poll() 和 select() 超时精度的改善。这种改进可能相当显著；一个重度使用这些系统调用的应用程序，可能会浪费大量时间等待定时器中断，而实际上超时时间早已到期。请记住，平均误差（即可能浪费的时间）是定时器中断周期的一半。

提高节拍率的另一个好处是进程抢占的准确性更高，从而降低了调度延迟。回顾第 4 章，定时器中断负责递减运行进程的时间片计数。当计数减至零时，会设置 need_resched 标志，并且内核会尽快运行调度器。现在假设一个给定的进程正在运行，其时间片剩余 2 毫秒。在 2 毫秒后，调度器应该抢占当前运行进程并开始执行一个新进程。但不幸的是，这个事件直到下一次定时器中断发生时才会被处理，而这可能不是在 2 毫秒之后。最坏的情况下，下一次定时器中断可能要在 1/HZ 秒之后才会到来！当 HZ=100 时，一个进程可能额外多运行近 10 毫秒。当然，这一切会达到平衡，公平性得以保持，因为所有任务在调度时都承受着相同的不精确度——但问题不在这里。问题的根源在于延迟抢占所产生的延迟。如果待调度的任务有对时间敏感的操作需要执行，例如重新填充音频缓冲区，那么这种延迟可能是不可接受的。将节拍率提高到 1000Hz，能将最坏情况下的调度超限降低到仅 1 毫秒，平均情况下的超限降低到仅 0.5 毫秒。

提高 HZ 值（节拍率）的劣势

既然提高节拍率有这么多好处，那它一定有某些缺点，否则最初就会设定为 1000Hz（甚至更高）。确实，存在一个主要问题：更高的节拍率意味着更频繁的定时器中断，也就意味着更高的开销，因为处理器必须花费更多时间来执行定时器中断处理程序。节拍率越高，处理器执行定时器中断所花费的时间就越多。这不仅导致可用于其他工作的处理器时间减少，还会更频繁地冲击处理器的缓存并增加功耗。

关于开销影响的问题存在争议。从 HZ=100 提高到 HZ=1000 显然会带来十倍的开销。然而，最初的开销究竟有多大呢？最终的共识是，至少在现代系统上，HZ=1000 并不会产生不可接受的开销，并且向 1000Hz 定时器的转变对性能的损害并不大。尽管如此，在 2.6 内核中，仍然可以在编译时为 HZ 设置不同的值（并非任意值，例如在x86上一般为100，500和1000）。

无节拍操作系统

您可能会问，操作系统是否真的需要一个固定的定时器中断？尽管这已成为 40 年来的常态，几乎所有通用操作系统都采用类似于本章所述的定时器中断，但 Linux 内核支持一个称为"无节拍操作"的选项。当内核构建时设置了 CONFIG_HZ 配置选项，系统会根据待处理的定时器动态地调度定时器中断。定时器中断不再是固定地每 1 毫秒触发一次，而是根据需要被动态地调度和重新调度。如果下一个定时器设定在 3 毫秒后触发，那么定时器中断就在 3 毫秒后触发。在此之后，如果没有工作需要处理的时间长达 50 毫秒，内核会将中断重新调度到 50 毫秒后再触发。

减少开销是受欢迎的，但真正的收益在于功耗的节省，尤其是在空闲系统上。在基于标准节拍的系统中，即使是在空闲期间，内核也需要处理定时器中断。而在无节拍系统中，空闲时刻不会被不必要的定时中断所打断，从而降低了系统功耗。无论空闲期是 200 毫秒还是 200 秒，长期累积的收益将转化为可观的节电效果。

jiffies变量

  • jiffies 是一个全局变量，记录自系统启动以来发生的时钟“滴答”（tick）数量。内核在启动时将其初始化为 0，并在每次定时器中断时将其加 1。
  • 由于每秒有 HZ 次定时器中断，所以每秒有 HZ 个 jiffies。系统运行时间（uptime）等于 jiffies / HZ（秒）。
  • 实际实现略有复杂：内核初始化 jiffies 为一个“特殊的初始值”（offset），使变量更频繁地溢出以便捕捉 bug；要取得真实值时要先减去这个偏移。

在内核中的声明与常用换算

  • jiffies 在头文件 <linux/jiffies.h> 中声明为： extern unsigned long volatile jiffies;
  • 把秒转换为 jiffies（ticks）： seconds * HZ
  • 把 jiffies 转换为秒： jiffies / HZ
  • 将秒换算为 ticks 更常见，例如设置未来某个时间点： unsigned long time_stamp = jiffies; /* now / unsigned long next_tick = jiffies + 1; / one tick from now / unsigned long later = jiffies + 5HZ; /* five seconds from now / unsigned long fraction = jiffies + HZ / 10; / a tenth of a second from now */
  • 一般只有与用户空间通信时才会把 ticks 换算为秒，内核内部通常不关心绝对时间。

jiffies 的内部表示与溢出问题

  • jiffies 一直定义为 unsigned long：在 32 位架构上是 32 位，在 64 位架构上是 64 位。
  • 示例溢出时间：若 HZ=100，32-bit jiffies 大约在 497 天后溢出；若 HZ=1000，则约在 49.7 天后溢出。
  • 如果在所有架构上都把 jiffies 存为 64 位（u64），对于合理的 HZ 值，jiffies 将几乎永远不会溢出。但出于性能和历史兼容性的考虑，开发者希望保留 jiffies 为 unsigned long。
  • 解决办法（linker magic）：在 <linux/jiffies.h> 中除了 jiffies 之外还声明了一个 64 位变量： extern u64 jiffies_64; 链接脚本（ld）在链接内核镜像时将 jiffies 覆盖到 jiffies_64 的起始位置： jiffies = jiffies_64; 因此，在 32 位机器上，jiffies 代表 jiffies_64 的低 32 位；大多数代码仍然直接读 jiffies（低 32 位），而时间管理代码会使用完整的 64 位值以防止溢出。
  • 在 64 位架构上，jiffies_64 和 jiffies 指向相同的值；可以直接读取 jiffies，也可以调用 get_jiffies_64() 来读取完整的 64 位值，二者等效。

在 32 位架构上，无法以原子方式一次性读取 64 位值的两个 32 位字。因此需要get_jiffies_64()来读取完整的 64 位 jiffies。该特殊函数在读取之前通过 xtime_lock 对 jiffies 计数加锁，从而保证读取的一致性与原子性。

jiffies 的环绕（Wraparound）

像任何 C 整数一样，当 jiffies 增加超过其能表示的最大值时会发生溢出（wraparound）。对于 32 位无符号整数，最大值是 2^32 − 1 = 4294967295，因此计数在达到该值后再加一就会回绕到 0。

举例说明一个潜在的问题： 

1
2
3
4
5
6
7
8
unsigned long timeout = jiffies + HZ/2;        /* timeout in 0.5s */
/* do some work ... */
/* then see whether we took too long */
if (timeout > jiffies) {
    /* we did not time out, good ... */
} else {
    /* we timed out, error ... */
}
意图是在半秒后超时。若在设置 timeout 之后 jiffies 发生了回绕（从最大值回到 0），那么 jiffies 可能变得比 timeout 小，导致 if 条件结果被颠倒（逻辑上已经超时但条件判断显示未超时），从而产生错误。

为避免这种情况，内核提供了四个用于比较 tick 计数的宏（位于 <linux/jiffies.h>），它们能正确处理回绕。下面是简化版定义： 

1
2
3
4
#define time_after(unknown, known) ((long)(known) - (long)(unknown) < 0)
#define time_before(unknown, known) ((long)(unknown) - (long)(known) < 0)
#define time_after_eq(unknown, known) ((long)(unknown) - (long)(known) >= 0)
#define time_before_eq(unknown, known) ((long)(known) - (long)(unknown) >= 0)
- 参数说明：unknown 通常为 jiffies（当前时间），known 为要比较的目标时间（例如 timeout）。 - 语义： - time_after(unknown, known)：若 unknown 在 known 之后则返回 true。 - time_before(unknown, known)：若 unknown 在 known 之前则返回 true。 - 带 _eq 的版本在等于时也返回 true。

使用这些宏修改后的超时示例： 

1
2
3
4
5
6
7
unsigned long timeout = jiffies + HZ/2;        /* timeout in 0.5s */
/* ... */
if (time_before(jiffies, timeout)) {
    /* we did not time out, good ... */
} else {
    /* we timed out, error ... */
}

为什么这些宏能防止回绕带来的错误？ - 这些宏利用有符号整数（long）的减法和符号位来判断先后关系：无论是否发生了回绕，通过把差值作为带符号数比较，仍能得到正确的先后顺序（在合理的时间差范围内，这些宏为标准做法并被广泛使用）。你可以用不同参数值自己演练，模拟某一参数回绕到 0 后的情况，观察结果如何保持正确。

用户空间与 HZ（User-Space and HZ）

早期内核（2.6 之前）直接以内核的 HZ 值向用户空间导出基于 tick 的值，这会导致当内核 HZ 改变时用户空间看到的数值不再正确 —— 因为某些用户空间程序假定了特定的 HZ 值。举例：若内核 HZ 被扩大，导出的 uptime 等值会被误放大，用户看到的“20 小时”实际上可能只有 2 小时。

为避免这种兼容性问题，内核定义了 USER_HZ，表示用户空间所期望的 HZ 值（在 x86 上历史上 USER_HZ = 100）。内核中提供了函数用来把以内核 HZ 单位计数的 jiffies 转换成以 USER_HZ 单位的值： - jiffies_to_clock_t()：将（32 位）jiffies（以 HZ 为单位）转换为以 USER_HZ 为单位的 “clock ticks” 值。 - jiffies_64_to_clock_t()：将 64 位 jiffies_64 从 HZ 转换到 USER_HZ。

当 USER_HZ 与 HZ 是整倍数关系、且 USER_HZ ≤ HZ 时，转换表达式较简单，例如： 

1
return x / (HZ / USER_HZ);
若两者不是整倍数关系，则使用更复杂的算法以保持精度与兼容性。

示例（将计时结果转换并输出给用户空间）： 

1
2
3
4
5
6
7
unsigned long start;
unsigned long total_time;

start = jiffies;
/* do some work ... */
total_time = jiffies - start;
printk("That took %lu ticks\n", jiffies_to_clock_t(total_time));
用户空间期望看到的值是以 USER_HZ 为单位的 ticks。如果你想对用户更友好地显示，通常应把结果转换为秒： 
1
printk("That took %lu seconds\n", total_time / HZ);

发表于 分类于

卡码网 98. 所有可达路径

给定一个有 n 个节点的有向无环图，节点编号从 1 到 n。请编写一个程序，找出并返回所有从节点 1 到节点 n 的路径。每条路径应以节点编号的列表形式表示

输入描述 > 第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边 > 后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t 节点中有一条路径

输出描述 > 输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出 -1。 > 注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是 1 3 5,而不是 1 3 5， 5后面没有空格！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<vector>
#include<list>
using namespace std;
vector<vector<int>> result;
vector<int> path;
void dfs(const vector<list<int>> &vnode, int n){
    // if(path.empty())path.push_back(1);
    int cur_i = path.back();
    if(cur_i == n){
        result.push_back(path);
    }else{
        list<int> n_i = vnode[cur_i];
        if(!n_i.empty()){
            for(int i : n_i){
                path.push_back(i);
                dfs(vnode, n);
                path.pop_back();
            }
        }
    }
}
int main(){
    int n, m;
    cin >> n >> m;
    vector<list<int>> vnode(n+1);
    for(int i = 0; i < m; i++){
        int node, next_i;
        cin >> node >> next_i;
        vnode[node].push_back(next_i);
    }
    path.push_back(1);
    dfs(vnode, n);
    if(result.empty()){
        cout << -1;
        return 0;
    }
    for(auto &path : result){
        for(int i = 0; i < path.size()-1; i++){
            cout << path[i] << ' ';
        }
        cout << path.back() << endl;
    }
    return 0;
}

发表于 分类于

42. 接雨水

求雨水高度，需要弹出当前池底值，再求两边最小：min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int water = 0;
        stack<int> st;
        st.push(0);
        for(int i = 1; i < height.size(); i++){
            while(!st.empty() && height[i] > height[st.top()]){
                int mid = st.top();
                st.pop();
                if(!st.empty()){
                    int h = min(height[i], height[st.top()]) - height[mid];
                    int w = i - st.top()-1;
                    water += h * w;
                }
            }
            st.push(i);
        }
        return water;
    }
};

84. 柱状图中最大的矩形

这题我初步想法是对于每个柱，求以它为高度的最大矩形。但是具体怎么用类似前后缀表的方法优化查询，我有点没思路。 看了题解反应过来还是要用单调栈求区间的宽和高，同时因为我们要弹出一个元素来获取左边元素的下标，为了头尾元素能顺利出栈，需要在前后都加入0 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int max_h = 0;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        st.push(0);
        for(int i = 1; i < heights.size(); i++){
            if(heights[i] >= heights[st.top()]){
                st.push(i);
            }else{
                while(!st.empty() && heights[i] < heights[st.top()]){
                    int mid_i = st.top();
                    st.pop();
                    int left_i = st.top();
                    int w = i - left_i - 1;
                    int h = heights[mid_i];
                    max_h = max(max_h, w * h);
                }
                st.push(i);
            }
        }
        return max_h;
    }
};

发表于 分类于

739. 每日温度

维护一个栈来记录未更新的数组值 using xx = xxxx仅可用于为现有变量创建别名，如果数组变量名太长请创建引用 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        stack<int> st;
        vector<int> out_v(temperatures.size(), 0);
        st.push(0);
        for(int i = 1; i < temperatures.size(); i++){
            if(temperatures[i] <= temperatures[st.top()]){
                st.push(i);
            }else{
                while(!st.empty() && temperatures[i] > temperatures[st.top()]){
                    out_v[st.top()] = i - st.top();
                    st.pop();
                }
                st.push(i);
            }
        }
        return out_v;
    }
};

496.下一个更大元素 I

和上一题很像的思路，但是需要借助两个数组都没有重复数字的假设构造map，使答案不超时 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<unordered_map>
class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int>mp;
        for(int i = 0; i < nums1.size(); i++){
            mp[nums1[i]] = i;
        }
        vector<int> ng(nums1.size(), -1);
        stack<int> st;
        st.push(0);
        for(int i = 1; i < nums2.size(); i++){
            while(!st.empty() && nums2[i] > nums2[st.top()]){
                int ntop = nums2[st.top()];
                if(mp.find(ntop) != mp.end()){
                    ng[mp[ntop]] = nums2[i];
                }
                // cout<<endl;
                st.pop();
            }
            st.push(i);
        }
        return ng;
    }
};

503.下一个更大元素II

我想的是找到最大的元素，从下一个数开始遍历一遍，不过看题解直接遍历两遍数组即可 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        vector<int> res(nums.size(), -1);
        // int max_n = nums[0];
        // int max_i = 0;
        // for(int i = 0; i < nums.size(); i++){
        //     if(nums[i] > max_n){
        //         max_n = nums[i];
        //         max_i = i;
        //     }
        // }
        stack<int> st;
        st.push(0);
        for(int j = 1; j < nums.size()*2; j++){
            int n_i = j % nums.size();
            while(!st.empty() && nums[n_i] > nums[st.top()]){
                res[st.top()] = nums[n_i];
                st.pop();
            }
            st.push(n_i);
        }
        return res;
    }
};

发表于 分类于

647. 回文子串

首先是找到递推关系，对于字符串中下标i-j的字串，如果s[i] == s[j]则可以由dp[i+1][j-1]推出dp[i][j] 然后是遍历顺序，因为要先知道dp[i+1][j-1]，所以要从下往上，从左至右遍历 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int countSubstrings(string s) {
        vector<vector<bool>> dp(s.size(),vector<bool>(s.size(), false));
        int cnt = 0;
        for(int i = s.size()-1; i >= 0; i--){
            for(int j = i; j < s.size(); j++){
                if(s[i] != s[j]){
                    dp[i][j] = false;
                }else{
                    if(j - i <= 1){
                        dp[i][j] = true;
                        cnt++;
                    }else{
                        dp[i][j] = dp[i+1][j-1];
                        if(dp[i][j] == true)cnt++;
                    }
                }
            }
        }
        return cnt;
    }
};

516.最长回文子序列

和上一题思路类似 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        vector<vector<int>>dp(s.size(), vector<int>(s.size(),0));
        for(int i = s.size()-1; i >= 0; i--){
            for(int j = i; j < s.size(); j++){
                if(s[i] != s[j]){
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                }else{
                    if(i == j){
                        dp[i][j] = 1;
                    }else if(i - j == 1){
                        dp[i][j] = 2;
                    }else{
                        dp[i][j] = dp[i+1][j-1]+2;
                    }
                }
            }
        }
        return dp[0][s.size()-1];
    }
};

发表于 分类于

DNS查询过程

DNS 用来将主机名和域名转换为IP地址, 其查询过程一般通过以下步骤：

本地DNS缓存检查：首先查询本地DNS缓存，如果缓存中有对应的IP地址，则直接返回结果。 如果本地缓存中没有，则会向本地的DNS服务器（通常由你的互联网服务提供商（ISP）提供， 比如中国移动）发送一个DNS查询请求。 如果本地DNS解析器有该域名的ip地址，就会直接返回，如果没有缓存该域名的解析记录，它会向根DNS服务器发出查询请求。根DNS服务器并不负责解析域名，但它能告诉本地DNS解析器应该向哪个顶级域（.com/.net/.org）的DNS服务器继续查询。 本地DNS解析器接着向指定的顶级域名DNS服务器发出查询请求。顶级域DNS服务器也不负责具体的域名解析，但它能告诉本地DNS解析器应该前往哪个权威DNS服务器查询下一步的信息。 本地DNS解析器最后向权威DNS服务器发送查询请求。 权威DNS服务器是负责存储特定域名和IP地址映射的服务器。当权威DNS服务器收到查询请求时，它会查找"example.com"域名对应的IP地址，并将结果返回给本地DNS解析器。 本地DNS解析器将收到的IP地址返回给浏览器，并且还会将域名解析结果缓存在本地，以便下次访问时更快地响应。 浏览器发起连接： 本地DNS解析器已经将IP地址返回给您的计算机，您的浏览器可以使用该IP地址与目标服务器建立连接，开始获取网页内容。

CDN是什么，有什么作用？

CDN是一种分布式网络服务，通过将内容存储在分布式的服务器上，使用户可以从距离较近的服务器获取所需的内容，从而加速互联网上的内容传输。

就近访问：CDN 在全球范围内部署了多个服务器节点，用户的请求会被路由到距离最近的 CDN 节点，提供快速的内容访问。 内容缓存：CDN 节点会缓存静态资源，如图片、样式表、脚本等。当用户请求访问这些资源时，CDN 会首先检查是否已经缓存了该资源。如果有缓存，CDN 节点会直接返回缓存的资源，如果没有缓存所需资源，它会从源服务器（原始服务器）回源获取资源，并将资源缓存到节点中，以便以后的请求。通过缓存内容，减少了对原始服务器的请求，减轻了源站的负载。 可用性：即使某些节点出现问题，用户请求可以被重定向到其他健康的节点。

发表于 分类于

卡码笔试 263.数据重删

题目描述： 输入一串存储的数据，用N表示数据个数，用K表示数据块的大小，设计一个方法判断当前数据块是否和前面的数据块有重复，两个数据块内容完全一样则表示重复，如果重复则将这个数据块删除，并且在第一个出现数据块的后面增加重复数据的计数，输出经过重删之后的数据内容。 输入示例： 

1
2
3
8 
3 
3 4 5 3 4 5 5 4
输出示例： 
1
3 4 5 2 5 4 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <map>
#include <vector>
#include <iostream>
using namespace std;

int main(){
    int total;
    int len;
    int c;
    vector<int> data;
    cin>>total>>len;
    while(cin>>c){
        data.push_back(c);
    }

    map<vector<int>, int> mp;
    vector<vector<int>> uniqueBlock;
    vector<bool> isUnique;
    for(int i = 0; i < data.size(); i+=len){
        int cnt = 0;
        vector<int> block;
        while(cnt < len && (i+cnt) < data.size()){
            block.push_back(data[i+cnt]);
            // cout<<"pushed in block: "<<data[i+cnt]<<endl;
            cnt++;
        }
        // cout<<endl;
        mp[block]++;
        if(mp[block] == 1){
            isUnique.push_back(true);
        }else{
            isUnique.push_back(false);
        }
        uniqueBlock.push_back(block);
    }
    for(int i = 0; i < uniqueBlock.size(); i++){
        if(isUnique[i] == true){
            for(int n: uniqueBlock[i]){
                cout<<n<<' ';
            }
            cout<<mp[uniqueBlock[i]]<<' ';
        }
    }
    // cout<<endl;

    // cout<<"total data: "<<total<<endl;
    // cout<<"len of blocks: "<<len<<endl;
    // for(int i: data){
    //     cout<<i<<' ';
    // }
    // cout<<endl;
}

发表于 更新于 分类于

这回笔试，我选择寄得比算法多（好久没刷八股题了=_=||），某境外电商的算法还是相对简单的

MySQL的默认事务隔离级别

REPEATABLE READ

算法

我ac了：

  • 求杨辉三角指定行指定区间的和（暴力就可以了）
  • 给定一个数组，这个数组的每一项是一个模块的单元测试，每次合并两个模块都需要执行两个模块单元测试数之和，问合并所有模块需要的最小测试数是多少（从小到大sort一下，再相加即可）

考试时发现我忘记了：

sort库函数怎么传递比较参数（比如我不需要默认的从小到大，而是从大到小该怎么办） 怎么构造并使用大/小顶堆

我没有ac:

打包员有m个相同重量上限k的袋子，需要打包weights数组个物品，这些物品一定是从前向后依次打包的，已知物品个数n, 每个物品重量的数组weights,求k的最小值

这个我本来以为需要背包算法，后来发现二分查找就可以了

发表于 分类于

115.不同的子序列

这题我想到要对于t的每个字符，一在s里匹配到，就从两串的下一个字符开始往后匹配。这么一看感觉开始递归了，不太动态规划。

题解的递推公式如下： 这一类问题，基本是要分析两种情况 - s[i - 1] 与 t[j - 1]相等 - s[i - 1] 与 t[j - 1] 不相等

当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。 - 一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母，所以只需要 dp[i-1][j-1]。 - 一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]。 当s[i - 1] 与 t[j - 1]不相等时，dp[i][j]只有一部分组成，不用s[i - 1]来匹配（就是模拟在s中删除这个元素），即：dp[i - 1][j]

注意上限长度且所有字符一样的s和t，会使得dp超long long的限制，此时使用uint64_t 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(t.size()+1, vector<uint64_t>(s.size()+1,0));
        // dp[0][0] = 1;
        for(int i=0; i<s.size();i++){
            if(s[i] == t[0])dp[0][i] = 1;
        }
        for(int i=1; i<=t.size(); i++){
            for(int j=1; j<=s.size(); j++){
                if(s[j-1] == t[i-1]){
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                    // if(i == 1)dp[i][j] = max(dp[i][j], 1);
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        // for(auto c:dp){
        //     for(int c_i : c){
        //         cout<<c_i<<' ';
        //     }
        //     cout<<endl;
        // }
        return dp[t.size()][s.size()];
    }
};

583. 两个字符串的删除操作

和上一题有些类似的思路 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1,0));
        for(int i = 1; i <= word1.size(); i++)dp[i][0] = i;
        for(int j = 1; j <= word2.size(); j++)dp[0][j] = j;
        for(int i = 1; i <= word1.size(); i++){
            for(int j = 1; j <= word2.size(); j++){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }else{
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+2);
                }
            }
        }
        // for(auto line : dp){
        //     for(auto i : line){
        //         cout<<i<<' ';
        //     }
        //     cout<<endl;
        // }
        return dp[word1.size()][word2.size()];
    }
};

72. 编辑距离

跟上两题差不多的思路，差点就写对了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int minDistance(string word1, string word2) {
        vector<vector<int>> dp(word1.size()+1, vector<int>(word2.size()+1, 0));
        for(int i = 0; i < word1.size(); i++)dp[i+1][0] = (i+1);
        for(int i = 0; i < word2.size(); i++)dp[0][i+1] = (i+1);
        // dp[0][0] = 1;
        for(int i = 1; i <= word1.size(); i++){
            for(int j = 1; j <= word2.size(); j++){
                if(word1[i-1] != word2[j-1]){
                    dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1);
                    dp[i][j] = min(dp[i][j], dp[i-1][j-1]+1);
                }else{
                    dp[i][j] = dp[i-1][j-1];
                }
            }
        }

        // for(auto line : dp){
        //     for(int i : line){
        //         cout << i << ' ';
        //     }
        //     cout << endl;
        // }
        return dp[word1.size()][word2.size()];
    }
};

发表于 更新于 分类于

1143.最长公共子序列

按照动态规划，每次比较成功就加一，取所有值最大的思路是错的，这种会把乱序但是相同的字符也算进去。 于是我想了半天怎么先循环以i,j为右下角的正方形，本来想的是记忆化将i,j赋值为比较后相等的值，看了题解发现得在递推公式上作更改 因为字符中间可能会插入别的字符，所以ac,ace的比较结果和ac,aced的比较结果是一样的 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1, vector<int> (text2.size()+1, 0));
        for(int i = 1; i <= text1.size();i++){
            for(int j = 1; j <= text2.size(); j++){
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = dp[i-1][j-1]+1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

1035.不相交的线

既然一个数只能连一根线，那么其实和上一题是一个意思了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1, vector<int> (nums2.size()+1, 0));
        for(int i = 1; i <= nums1.size(); i++){
            for(int j = 1; j <= nums2.size(); j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};

53. 最大子序和

我想的是，dp[i]由dp[i-1],dp[i-1]+nums[i],nums[i]中的最大值决定，但是这样解会算出不连续的最大值

题解的推算法是这样的： dp[i]只有两个方向可以推出来： - dp[i-1] + nums[i]，即：nums[i]加入当前连续子序列和 - nums[i]，即：从头开始计算当前连续子序列和 再找每个的dp[i]最大值 

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < nums.size(); i++){
            dp[i] = max(dp[i-1]+nums[i], nums[i]);
            if(dp[i] > res)res = dp[i];
        }
        return res;
    }
};

392.判断子序列

常规做的话双指针法即可，按照动态规划来做是和第一题是差不多的思路 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isSubsequence(string s, string t) {
        vector<vector<int>> dp(s.size()+1, vector<int>(t.size()+1, 0));
        for(int i = 1; i <= s.size(); i++){
            for(int j = 1; j <= t.size(); j++){
                if(s[i-1] == t[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[s.size()][t.size()] == s.size() ? true : false;
    }
};

0%