-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
1339 lines (955 loc) · 122 KB
/
index.html
File metadata and controls
1339 lines (955 loc) · 122 KB
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 5.4.1">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/6.6.0/css/all.min.css" integrity="sha256-5eIC48iZUHmSlSUz9XtjRyK2mzQkHScZY1WdMaoz74E=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/animate.css/3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
<script class="next-config" data-name="main" type="application/json">{"hostname":"mackz-maxw.github.io","root":"/","images":"/images","scheme":"Muse","darkmode":false,"version":"8.21.1","exturl":false,"sidebar":{"position":"left","width_expanded":320,"width_dual_column":240,"display":"always","padding":18,"offset":12},"hljswrap":true,"copycode":{"enable":false,"style":null},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"duration":200,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"}}</script><script src="/js/config.js"></script>
<meta name="description" content="乘上燃犀船，还未曾去过倒悬山。">
<meta property="og:type" content="website">
<meta property="og:title" content="Maxw的小站">
<meta property="og:url" content="https://mackz-maxw.github.io/index.html">
<meta property="og:site_name" content="Maxw的小站">
<meta property="og:description" content="乘上燃犀船，还未曾去过倒悬山。">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="Mackz-Maxw">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://mackz-maxw.github.io/">
<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":true,"isPost":false,"lang":"zh-CN","comments":"","permalink":"","path":"index.html","title":""}</script>
<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>Maxw的小站</title>
<noscript>
<link rel="stylesheet" href="/css/noscript.css">
</noscript>
<link rel="alternate" href="/atom.xml" title="Maxw的小站" type="application/atom+xml">
</head>
<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
<div class="headband"></div>
<main class="main">
<div class="column">
<header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<i class="logo-line"></i>
<h1 class="site-title">Maxw的小站</h1>
<i class="logo-line"></i>
</a>
<p class="site-subtitle" itemprop="description">Maxw学习记录</p>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger" aria-label="搜索" role="button">
</div>
</div>
</div>
<nav class="site-nav">
<ul class="main-menu menu"><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
</ul>
</nav>
</header>
<aside class="sidebar">
<div class="sidebar-inner sidebar-overview-active">
<ul class="sidebar-nav">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<div class="sidebar-panel-container">
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
<p class="site-author-name" itemprop="name">Mackz-Maxw</p>
<div class="site-description" itemprop="description">乘上燃犀船，还未曾去过倒悬山。</div>
</div>
<div class="site-state-wrap animated">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">110</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<a href="/categories/">
<span class="site-state-item-count">9</span>
<span class="site-state-item-name">分类</span></a>
</div>
</nav>
</div>
<div class="links-of-author animated">
<span class="links-of-author-item">
<a href="https://github.com/mackz-maxw" title="GitHub → https://github.com/mackz-maxw" rel="noopener me" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
</span>
</div>
</div>
</div>
</div>
</aside>
</div>
<div class="main-inner index posts-expand">
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/12/04/oper_sys29timer/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/12/04/oper_sys29timer/" class="post-title-link" itemprop="url">操作系统基础 | 6.1 定时器与时间管理 - 定时器：节拍，赫兹和jiffies</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-12-05 06:51:56 / 修改时间：06:53:35" itemprop="dateCreated datePublished" datetime="2025-12-05T06:51:56+08:00">2025-12-05</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/os-basic/" itemprop="url" rel="index"><span itemprop="name">os basic</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="定时器与时间管理"><strong>定时器与时间管理</strong></h3>
<p>时间的流逝对内核至关重要。大量内核函数是由时间驱动的，而非事件驱动¹。其中一些函数是周期性的，例如调度器运行队列的平衡或屏幕刷新。它们按照固定计划执行，比如每秒100次。内核还会在未来某个相对时间调度其他函数，例如延迟的磁盘I/O。举例来说，内核可能会调度一个500毫秒后执行的任务。最后，内核还必须管理系统运行时间以及当前日期和时间。</p>
<p>需注意相对时间与绝对时间的区别。调度一个5秒后发生的事件不需要绝对时间的概念——只需相对时间（例如，从现在起5秒后）。相反，管理当前时间不仅要求内核理解时间的流逝，还需要掌握某种绝对时间度量。这两个概念对时间管理都至关重要。</p>
<p>此外，处理周期性事件与内核调度未来特定时间点事件的方式在实现上有所不同。周期性事件（比如每10毫秒一次）由系统定时器驱动。系统定时器是一种可编程硬件，能够以固定频率发出中断。该定时器的中断处理程序（称为定时器中断）负责更新系统时间并执行周期性工作。系统定时器及其定时器中断是Linux的核心，也是本章的重点内容。</p>
<p>本章的另一个重点是动态定时器，这种机制用于调度在指定时间间隔后仅执行一次的事件。例如，软盘设备驱动程序使用定时器在指定空闲时间后关闭软盘驱动器电机。内核可以动态创建和销毁定时器。本章将探讨动态定时器的内核实现，以及可供代码调用的相关接口。</p>
<p>¹
更准确地说，时间驱动事件也属于事件驱动——这里的事件即指时间的流逝。但在本章中，我们特别强调时间驱动事件，因为其在内核中出现的频率及重要性尤为突出。</p>
<h3 id="内核的时间概念"><strong>内核的时间概念</strong></h3>
<p>显然，计算机对时间的理解有些抽象。实际上，内核必须与系统硬件协同工作来理解和管理时间。硬件提供了一个系统定时器，内核借助它来度量时间的流逝。该系统定时器基于电子时钟源运行，例如数字时钟或处理器频率。系统定时器会按照预设频率（称为节拍率）触发（通常称为"命中"或"弹出"）。当系统定时器触发时，它会发出一个中断，内核通过特定的中断处理程序来处理该中断。</p>
<p>由于内核知晓预设的节拍率，它就能计算出任意两次连续定时器中断之间的时间间隔。这个周期称为一个"节拍"，相当于
1/(节拍率) 秒。这正是内核追踪实际时间和系统运行时间的方式。</p>
<p>实际时间（即一天中的具体时刻）对用户空间应用程序至关重要。内核之所以要追踪实际时间，根本原因在于内核控制着定时器中断。一系列系统调用向用户空间提供日期和时间信息。系统运行时间（即系统启动后的相对时间）对内核空间和用户空间都很有用。大量代码必须感知时间的流逝。两次运行时间读数（当前值与过去值）之间的差值，就是这种相对性的简单度量。</p>
<p>定时器中断对操作系统的管理至关重要。大量内核功能的生灭都与时间流逝紧密相关。定时器中断定期执行的部分工作包括：</p>
<ul>
<li>更新系统运行时间</li>
<li>更新实际时间</li>
<li>在SMP系统上，确保调度器运行队列处于平衡状态，若不平衡则进行平衡调整（如第4章"进程调度"所述）</li>
<li>运行所有已到期的动态定时器</li>
<li>更新资源使用情况和处理器时间统计信息</li>
</ul>
<p>其中部分工作会在每次定时器中断时执行——也就是说，这些工作以节拍率的频率执行。而其他函数则定期执行，但仅在第n次定时器中断时才触发。也就是说，这些函数以节拍率的某个分数频率执行。在"定时器中断处理程序"一节中，我们将详细探讨该中断处理程序。</p>
<h3 id="节拍率hz">节拍率：HZ</h3>
<p>系统定时器的频率（即节拍率）是在系统启动时，基于一个静态的预处理器定义
HZ 来设定的。对于每个受支持的体系结构，HZ
的值都不同。在某些受支持的体系结构中，它甚至在不同的机器类型之间也存在差异。</p>
<p>内核在 <code><asm/param.h></code>
头文件中定义了该值。节拍率的频率为 HZ 赫兹，周期为 1/HZ
秒。例如，在默认情况下，x86 架构将 HZ 定义为 100。因此，i386
上的定时器中断频率为 100Hz，即每秒发生 100
次（每百分之一秒一次，也就是每 10 毫秒一次）。HZ 的其他常见值还有 250 和
1000，分别对应 4 毫秒和 1 毫秒的周期。</p>
<p>在编写内核代码时，切勿假定 HZ
具有任何特定值。如今这已不是一个常见的错误，因为许多体系结构的节拍率各不相同。然而，在过去，Alpha
是唯一节拍率不等于 100Hz 的架构，经常会看到代码错误地硬编码了值
100，而实际上本应使用 HZ 值。后文将展示在内核代码中使用 HZ 的示例。</p>
<p>定时器中断的频率至关重要。正如您所看到的，定时器中断执行大量工作。实际上，内核的整个时间概念都源于系统定时器的周期性。选择合适的值，就像经营一段成功的关系，全在于权衡妥协。</p>
<h4 id="理想的-hz-值">理想的 HZ 值</h4>
<p>从 Linux 的最初版本开始，i386 架构的定时器中断频率一直是 100
Hz。然而，在 2.5 开发系列期间，频率被提升到了 1000
Hz，并且（像这类事情一样）引起了争议。尽管频率后来又回到了 100
Hz，但它现在是一个配置选项，允许用户编译具有自定义 HZ
值的内核。由于系统的许多部分都依赖于定时器中断，改变其频率会对系统产生显著影响。当然，选择较大或较小的
HZ 值各有优缺点。</p>
<p>提高节拍率意味着定时器中断运行得更频繁。因此，它执行的工作也会更频繁地发生。这带来以下好处：</p>
<ul>
<li>定时器中断具有更高的分辨率，因此所有定时事件也具有更高的分辨率。</li>
<li>定时事件的准确性得到提高。</li>
</ul>
<p>分辨率随着节拍率的提高而同比例提升。例如，当 HZ=100
时，定时器的粒度是 10 毫秒。换句话说，所有周期性事件都沿着定时器中断的
10
毫秒周期发生，无法保证更精细的精度(我们这里使用的是计算机领域的"精度"含义，而非科学上的。科学上的精度是对可重复性的统计度量。在计算机中，精度是指用于表示一个值的有效数字位数)。而当
HZ=1000 时，分辨率是 1 毫秒——精细了 10 倍。尽管内核代码可以创建具有 1
毫秒分辨率的定时器，但并不能保证在 HZ=100 时提供的精度足以在优于 10
毫秒间隔的任何时间点上执行定时器。</p>
<p>同样，准确性也以相同的方式提高。假设内核在随机时间启动定时器，由于定时器可能在任何时间到期，但仅在定时器中断发生时才会被执行，因此定时器的平均误差为定时器中断周期的一半。例如，对于
HZ=100，事件发生的时间平均会在期望时间的 +/- 5
毫秒范围内。因此，平均误差为 5 毫秒。对于 HZ=1000，平均误差降至 0.5
毫秒——提高了十倍。</p>
<h4 id="提高-hz-值节拍率的优势"><strong>提高 HZ
值（节拍率）的优势</strong></h4>
<p>更高的分辨率和准确性带来了多重优势：</p>
<ul>
<li>内核定时器以更精细的分辨率和更高的准确性执行。（这带来了大量改进，其中之一如下所述。）</li>
<li>诸如 <code>poll()</code> 和 <code>select()</code>
这类可选择使用超时值的系统调用，能够以更高的精度执行。</li>
<li>资源使用情况或系统运行时间等测量值，能以更精细的分辨率被记录。</li>
<li>进程抢占的发生更加精确。</li>
</ul>
<p>最显而易见的性能提升，来自于 <code>poll()</code> 和
<code>select()</code>
超时精度的改善。这种改进可能相当显著；一个重度使用这些系统调用的应用程序，可能会浪费大量时间等待定时器中断，而实际上超时时间早已到期。请记住，平均误差（即可能浪费的时间）是定时器中断周期的一半。</p>
<p>提高节拍率的另一个好处是进程抢占的准确性更高，从而降低了调度延迟。回顾第
4 章，定时器中断负责递减运行进程的时间片计数。当计数减至零时，会设置
<code>need_resched</code>
标志，并且内核会尽快运行调度器。现在假设一个给定的进程正在运行，其时间片剩余
2 毫秒。在 2
毫秒后，调度器应该抢占当前运行进程并开始执行一个新进程。但不幸的是，这个事件直到下一次定时器中断发生时才会被处理，而这可能不是在
2 毫秒之后。最坏的情况下，下一次定时器中断可能要在 <code>1/HZ</code>
秒之后才会到来！当 <code>HZ=100</code> 时，一个进程可能额外多运行近 10
毫秒。当然，这一切会达到平衡，公平性得以保持，因为所有任务在调度时都承受着相同的不精确度——但问题不在这里。问题的根源在于延迟抢占所产生的<strong>延迟</strong>。如果待调度的任务有对时间敏感的操作需要执行，例如重新填充音频缓冲区，那么这种延迟可能是不可接受的。将节拍率提高到
1000Hz，能将最坏情况下的调度超限降低到仅 1
毫秒，平均情况下的超限降低到仅 0.5 毫秒。</p>
<h4 id="提高-hz-值节拍率的劣势"><strong>提高 HZ
值（节拍率）的劣势</strong></h4>
<p>既然提高节拍率有这么多好处，那它一定有某些缺点，否则最初就会设定为
1000Hz（甚至更高）。确实，存在一个主要问题：更高的节拍率意味着更频繁的定时器中断，也就意味着更高的开销，因为处理器必须花费更多时间来执行定时器中断处理程序。节拍率越高，处理器执行定时器中断所花费的时间就越多。这不仅导致可用于其他工作的处理器时间减少，还会更频繁地冲击处理器的缓存并增加功耗。</p>
<p>关于开销影响的问题存在争议。从 <code>HZ=100</code> 提高到
<code>HZ=1000</code>
显然会带来十倍的开销。然而，最初的开销究竟有多大呢？最终的共识是，至少在现代系统上，<code>HZ=1000</code>
并不会产生不可接受的开销，并且向 1000Hz
定时器的转变对性能的损害并不大。尽管如此，在 2.6
内核中，仍然可以在编译时为 <code>HZ</code>
设置不同的值（并非任意值，例如在x86上一般为100，500和1000）。</p>
<p><strong>无节拍操作系统</strong></p>
<p>您可能会问，操作系统是否真的需要一个固定的定时器中断？尽管这已成为 40
年来的常态，几乎所有通用操作系统都采用类似于本章所述的定时器中断，但
Linux 内核支持一个称为"无节拍操作"的选项。当内核构建时设置了
<code>CONFIG_HZ</code>
配置选项，系统会根据待处理的定时器动态地调度定时器中断。定时器中断不再是固定地每
1
毫秒触发一次，而是根据需要被动态地调度和重新调度。如果下一个定时器设定在
3 毫秒后触发，那么定时器中断就在 3
毫秒后触发。在此之后，如果没有工作需要处理的时间长达 50
毫秒，内核会将中断重新调度到 50 毫秒后再触发。</p>
<p>减少开销是受欢迎的，但真正的收益在于功耗的节省，尤其是在空闲系统上。在基于标准节拍的系统中，即使是在空闲期间，内核也需要处理定时器中断。而在无节拍系统中，空闲时刻不会被不必要的定时中断所打断，从而降低了系统功耗。无论空闲期是
200 毫秒还是 200 秒，长期累积的收益将转化为可观的节电效果。</p>
<h3 id="jiffies变量">jiffies变量</h3>
<ul>
<li>jiffies
是一个全局变量，记录自系统启动以来发生的时钟“滴答”（tick）数量。内核在启动时将其初始化为
0，并在每次定时器中断时将其加 1。</li>
<li>由于每秒有 HZ 次定时器中断，所以每秒有 HZ 个
jiffies。系统运行时间（uptime）等于 jiffies / HZ（秒）。</li>
<li>实际实现略有复杂：内核初始化 jiffies
为一个“特殊的初始值”（offset），使变量更频繁地溢出以便捕捉
bug；要取得真实值时要先减去这个偏移。</li>
</ul>
<h4 id="在内核中的声明与常用换算">在内核中的声明与常用换算</h4>
<ul>
<li>jiffies 在头文件 <linux/jiffies.h> 中声明为： extern unsigned
long volatile jiffies;</li>
<li>把秒转换为 jiffies（ticks）： seconds * HZ</li>
<li>把 jiffies 转换为秒： jiffies / HZ</li>
<li>将秒换算为 ticks 更常见，例如设置未来某个时间点： unsigned long
time_stamp = jiffies; /* now <em>/ unsigned long next_tick = jiffies +
1; /</em> one tick from now <em>/ unsigned long later = jiffies +
5</em>HZ; /* five seconds from now <em>/ unsigned long fraction =
jiffies + HZ / 10; /</em> a tenth of a second from now */</li>
<li>一般只有与用户空间通信时才会把 ticks
换算为秒，内核内部通常不关心绝对时间。</li>
</ul>
<h4 id="jiffies-的内部表示与溢出问题">jiffies 的内部表示与溢出问题</h4>
<ul>
<li>jiffies 一直定义为 unsigned long：在 32 位架构上是 32 位，在 64
位架构上是 64 位。</li>
<li>示例溢出时间：若 HZ=100，32-bit jiffies 大约在 497 天后溢出；若
HZ=1000，则约在 49.7 天后溢出。</li>
<li>如果在所有架构上都把 jiffies 存为 64 位（u64），对于合理的 HZ
值，jiffies
将几乎永远不会溢出。但出于性能和历史兼容性的考虑，开发者希望保留 jiffies
为 unsigned long。</li>
<li>解决办法（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 位值以防止溢出。</li>
<li>在 64 位架构上，jiffies_64 和 jiffies 指向相同的值；可以直接读取
jiffies，也可以调用 get_jiffies_64() 来读取完整的 64
位值，二者等效。</li>
</ul>
<blockquote>
<p>在 32 位架构上，无法以原子方式一次性读取 64 位值的两个 32
位字。因此需要get_jiffies_64()来读取完整的 64 位
jiffies。该特殊函数在读取之前通过 xtime_lock 对 jiffies
计数加锁，从而保证读取的一致性与原子性。</p>
</blockquote>
<h4 id="jiffies-的环绕wraparound">jiffies 的环绕（Wraparound）</h4>
<p>像任何 C 整数一样，当 jiffies
增加超过其能表示的最大值时会发生溢出（wraparound）。对于 32
位无符号整数，最大值是 2^32 − 1 =
4294967295，因此计数在达到该值后再加一就会回绕到 0。</p>
<p>举例说明一个潜在的问题： <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">unsigned</span> <span class="type">long</span> timeout = jiffies + HZ/<span class="number">2</span>; <span class="comment">/* timeout in 0.5s */</span></span><br><span class="line"><span class="comment">/* do some work ... */</span></span><br><span class="line"><span class="comment">/* then see whether we took too long */</span></span><br><span class="line"><span class="keyword">if</span> (timeout > jiffies) {</span><br><span class="line"> <span class="comment">/* we did not time out, good ... */</span></span><br><span class="line">} <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">/* we timed out, error ... */</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure> 意图是在半秒后超时。若在设置
<code>timeout</code> 之后 <code>jiffies</code> 发生了回绕（从最大值回到
0），那么 <code>jiffies</code> 可能变得比 <code>timeout</code> 小，导致
<code>if</code>
条件结果被颠倒（逻辑上已经超时但条件判断显示未超时），从而产生错误。</p>
<p>为避免这种情况，内核提供了四个用于比较 tick 计数的宏（位于
<code><linux/jiffies.h></code>），它们能正确处理回绕。下面是简化版定义：
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">define</span> time_after(unknown, known) ((long)(known) - (long)(unknown) < 0)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> time_before(unknown, known) ((long)(unknown) - (long)(known) < 0)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> time_after_eq(unknown, known) ((long)(unknown) - (long)(known) >= 0)</span></span><br><span class="line"><span class="meta">#<span class="keyword">define</span> time_before_eq(unknown, known) ((long)(known) - (long)(unknown) >= 0)</span></span><br></pre></td></tr></table></figure> - 参数说明：<code>unknown</code> 通常为
<code>jiffies</code>（当前时间），<code>known</code>
为要比较的目标时间（例如 <code>timeout</code>）。 - 语义： -
<code>time_after(unknown, known)</code>：若 unknown 在 known 之后则返回
true。 - <code>time_before(unknown, known)</code>：若 unknown 在 known
之前则返回 true。 - 带 <code>_eq</code> 的版本在等于时也返回 true。</p>
<p>使用这些宏修改后的超时示例： <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">unsigned</span> <span class="type">long</span> timeout = jiffies + HZ/<span class="number">2</span>; <span class="comment">/* timeout in 0.5s */</span></span><br><span class="line"><span class="comment">/* ... */</span></span><br><span class="line"><span class="keyword">if</span> (time_before(jiffies, timeout)) {</span><br><span class="line"> <span class="comment">/* we did not time out, good ... */</span></span><br><span class="line">} <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">/* we timed out, error ... */</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>为什么这些宏能防止回绕带来的错误？ -
这些宏利用有符号整数（long）的减法和符号位来判断先后关系：无论是否发生了回绕，通过把差值作为带符号数比较，仍能得到正确的先后顺序（在合理的时间差范围内，这些宏为标准做法并被广泛使用）。你可以用不同参数值自己演练，模拟某一参数回绕到
0 后的情况，观察结果如何保持正确。</p>
<h2 id="用户空间与-hzuser-space-and-hz">用户空间与 HZ（User-Space and
HZ）</h2>
<p>早期内核（2.6 之前）直接以内核的 HZ 值向用户空间导出基于 tick
的值，这会导致当内核 HZ 改变时用户空间看到的数值不再正确 ——
因为某些用户空间程序假定了特定的 HZ 值。举例：若内核 HZ 被扩大，导出的
uptime 等值会被误放大，用户看到的“20 小时”实际上可能只有 2 小时。</p>
<p>为避免这种兼容性问题，内核定义了 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。</p>
<p>当 USER_HZ 与 HZ 是整倍数关系、且 USER_HZ ≤ HZ
时，转换表达式较简单，例如： <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">return</span> x / (HZ / USER_HZ);</span><br></pre></td></tr></table></figure>
若两者不是整倍数关系，则使用更复杂的算法以保持精度与兼容性。</p>
<p>示例（将计时结果转换并输出给用户空间）： <figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">unsigned</span> <span class="type">long</span> start;</span><br><span class="line"><span class="type">unsigned</span> <span class="type">long</span> total_time;</span><br><span class="line"></span><br><span class="line">start = jiffies;</span><br><span class="line"><span class="comment">/* do some work ... */</span></span><br><span class="line">total_time = jiffies - start;</span><br><span class="line">printk(<span class="string">"That took %lu ticks\n"</span>, <span class="type">jiffies_to_clock_t</span>(total_time));</span><br></pre></td></tr></table></figure>
用户空间期望看到的值是以 USER_HZ 为单位的
ticks。如果你想对用户更友好地显示，通常应把结果转换为秒：
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">printk(<span class="string">"That took %lu seconds\n"</span>, total_time / HZ);</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/11/20/kamacode43graph/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/11/20/kamacode43graph/" class="post-title-link" itemprop="url">代码随想录 | 刷题-图论1</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-11-21 04:56:23 / 修改时间：04:56:32" itemprop="dateCreated datePublished" datetime="2025-11-21T04:56:23+08:00">2025-11-21</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="卡码网-98.-所有可达路径">卡码网 98. 所有可达路径</h3>
<p>给定一个有 n 个节点的有向无环图，节点编号从 1 到
n。请编写一个程序，找出并返回所有从节点 1 到节点 n
的路径。每条路径应以节点编号的列表形式表示</p>
<p>输入描述 > 第一行包含两个整数 N，M，表示图中拥有 N 个节点，M 条边
> 后续 M 行，每行包含两个整数 s 和 t，表示图中的 s 节点与 t
节点中有一条路径</p>
<p>输出描述 >
输出所有的可达路径，路径中所有节点之间空格隔开，每条路径独占一行，存在多条路径，路径输出的顺序可任意。如果不存在任何一条路径，则输出
-1。 > 注意输出的序列中，最后一个节点后面没有空格！ 例如正确的答案是
<code>1 3 5</code>,而不是 <code>1 3 5</code>， 5后面没有空格！</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><vector></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><list></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">vector<vector<<span class="type">int</span>>> result;</span><br><span class="line">vector<<span class="type">int</span>> path;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">dfs</span><span class="params">(<span class="type">const</span> vector<list<<span class="type">int</span>>> &vnode, <span class="type">int</span> n)</span></span>{</span><br><span class="line"> <span class="comment">// if(path.empty())path.push_back(1);</span></span><br><span class="line"> <span class="type">int</span> cur_i = path.<span class="built_in">back</span>();</span><br><span class="line"> <span class="keyword">if</span>(cur_i == n){</span><br><span class="line"> result.<span class="built_in">push_back</span>(path);</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> list<<span class="type">int</span>> n_i = vnode[cur_i];</span><br><span class="line"> <span class="keyword">if</span>(!n_i.<span class="built_in">empty</span>()){</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i : n_i){</span><br><span class="line"> path.<span class="built_in">push_back</span>(i);</span><br><span class="line"> <span class="built_in">dfs</span>(vnode, n);</span><br><span class="line"> path.<span class="built_in">pop_back</span>();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="type">int</span> n, m;</span><br><span class="line"> cin >> n >> m;</span><br><span class="line"> vector<list<<span class="type">int</span>>> <span class="built_in">vnode</span>(n+<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < m; i++){</span><br><span class="line"> <span class="type">int</span> node, next_i;</span><br><span class="line"> cin >> node >> next_i;</span><br><span class="line"> vnode[node].<span class="built_in">push_back</span>(next_i);</span><br><span class="line"> }</span><br><span class="line"> path.<span class="built_in">push_back</span>(<span class="number">1</span>);</span><br><span class="line"> <span class="built_in">dfs</span>(vnode, n);</span><br><span class="line"> <span class="keyword">if</span>(result.<span class="built_in">empty</span>()){</span><br><span class="line"> cout << <span class="number">-1</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> &path : result){</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < path.<span class="built_in">size</span>()<span class="number">-1</span>; i++){</span><br><span class="line"> cout << path[i] << <span class="string">' '</span>;</span><br><span class="line"> }</span><br><span class="line"> cout << path.<span class="built_in">back</span>() << endl;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/11/20/kamacode42monos/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/11/20/kamacode42monos/" class="post-title-link" itemprop="url">代码随想录 | 刷题-单调栈2</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-11-21 04:55:57 / 修改时间：04:56:09" itemprop="dateCreated datePublished" datetime="2025-11-21T04:55:57+08:00">2025-11-21</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="接雨水">42. 接雨水</h3>
<p>求雨水高度，需要弹出当前池底值，再求两边最小：min(凹槽左边高度,
凹槽右边高度) - 凹槽底部高度 <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="function"><span class="type">int</span> <span class="title">trap</span><span class="params">(vector<<span class="type">int</span>>& height)</span> </span>{</span><br><span class="line"> <span class="type">int</span> water = <span class="number">0</span>;</span><br><span class="line"> stack<<span class="type">int</span>> st;</span><br><span class="line"> st.<span class="built_in">push</span>(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i < height.<span class="built_in">size</span>(); i++){</span><br><span class="line"> <span class="keyword">while</span>(!st.<span class="built_in">empty</span>() && height[i] > height[st.<span class="built_in">top</span>()]){</span><br><span class="line"> <span class="type">int</span> mid = st.<span class="built_in">top</span>();</span><br><span class="line"> st.<span class="built_in">pop</span>();</span><br><span class="line"> <span class="keyword">if</span>(!st.<span class="built_in">empty</span>()){</span><br><span class="line"> <span class="type">int</span> h = <span class="built_in">min</span>(height[i], height[st.<span class="built_in">top</span>()]) - height[mid];</span><br><span class="line"> <span class="type">int</span> w = i - st.<span class="built_in">top</span>()<span class="number">-1</span>;</span><br><span class="line"> water += h * w;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> st.<span class="built_in">push</span>(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> water;</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure></p>
<h3 id="柱状图中最大的矩形">84. 柱状图中最大的矩形</h3>
<p>这题我初步想法是对于每个柱，求以它为高度的最大矩形。但是具体怎么用类似前后缀表的方法优化查询，我有点没思路。
看了题解反应过来还是要用单调栈求区间的宽和高，同时因为我们要弹出一个元素来获取左边元素的下标，为了头尾元素能顺利出栈，需要在前后都加入0
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="function"><span class="type">int</span> <span class="title">largestRectangleArea</span><span class="params">(vector<<span class="type">int</span>>& heights)</span> </span>{</span><br><span class="line"> stack<<span class="type">int</span>> st;</span><br><span class="line"> <span class="type">int</span> max_h = <span class="number">0</span>;</span><br><span class="line"> heights.<span class="built_in">insert</span>(heights.<span class="built_in">begin</span>(), <span class="number">0</span>);</span><br><span class="line"> heights.<span class="built_in">push_back</span>(<span class="number">0</span>);</span><br><span class="line"> st.<span class="built_in">push</span>(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i < heights.<span class="built_in">size</span>(); i++){</span><br><span class="line"> <span class="keyword">if</span>(heights[i] >= heights[st.<span class="built_in">top</span>()]){</span><br><span class="line"> st.<span class="built_in">push</span>(i);</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">while</span>(!st.<span class="built_in">empty</span>() && heights[i] < heights[st.<span class="built_in">top</span>()]){</span><br><span class="line"> <span class="type">int</span> mid_i = st.<span class="built_in">top</span>();</span><br><span class="line"> st.<span class="built_in">pop</span>();</span><br><span class="line"> <span class="type">int</span> left_i = st.<span class="built_in">top</span>();</span><br><span class="line"> <span class="type">int</span> w = i - left_i - <span class="number">1</span>;</span><br><span class="line"> <span class="type">int</span> h = heights[mid_i];</span><br><span class="line"> max_h = <span class="built_in">max</span>(max_h, w * h);</span><br><span class="line"> }</span><br><span class="line"> st.<span class="built_in">push</span>(i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> max_h;</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/10/25/kamacode41monos/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/10/25/kamacode41monos/" class="post-title-link" itemprop="url">代码随想录 | 刷题-单调栈1</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-10-26 09:27:51 / 修改时间：09:28:12" itemprop="dateCreated datePublished" datetime="2025-10-26T09:27:51+08:00">2025-10-26</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="每日温度">739. 每日温度</h3>
<p>维护一个栈来记录未更新的数组值
<code>using xx = xxxx</code>仅可用于为现有变量创建别名，如果数组变量名太长请创建引用
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="function">vector<<span class="type">int</span>> <span class="title">dailyTemperatures</span><span class="params">(vector<<span class="type">int</span>>& temperatures)</span> </span>{</span><br><span class="line"> stack<<span class="type">int</span>> st;</span><br><span class="line"> <span class="function">vector<<span class="type">int</span>> <span class="title">out_v</span><span class="params">(temperatures.size(), <span class="number">0</span>)</span></span>;</span><br><span class="line"> st.<span class="built_in">push</span>(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i < temperatures.<span class="built_in">size</span>(); i++){</span><br><span class="line"> <span class="keyword">if</span>(temperatures[i] <= temperatures[st.<span class="built_in">top</span>()]){</span><br><span class="line"> st.<span class="built_in">push</span>(i);</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">while</span>(!st.<span class="built_in">empty</span>() && temperatures[i] > temperatures[st.<span class="built_in">top</span>()]){</span><br><span class="line"> out_v[st.<span class="built_in">top</span>()] = i - st.<span class="built_in">top</span>();</span><br><span class="line"> st.<span class="built_in">pop</span>();</span><br><span class="line"> }</span><br><span class="line"> st.<span class="built_in">push</span>(i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> out_v;</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure></p>
<h3 id="下一个更大元素-i">496.下一个更大元素 I</h3>
<p>和上一题很像的思路，但是需要借助两个数组都没有重复数字的假设构造map，使答案不超时
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><unordered_map></span></span></span><br><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="function">vector<<span class="type">int</span>> <span class="title">nextGreaterElement</span><span class="params">(vector<<span class="type">int</span>>& nums1, vector<<span class="type">int</span>>& nums2)</span> </span>{</span><br><span class="line"> unordered_map<<span class="type">int</span>, <span class="type">int</span>>mp;</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < nums1.<span class="built_in">size</span>(); i++){</span><br><span class="line"> mp[nums1[i]] = i;</span><br><span class="line"> }</span><br><span class="line"> <span class="function">vector<<span class="type">int</span>> <span class="title">ng</span><span class="params">(nums1.size(), <span class="number">-1</span>)</span></span>;</span><br><span class="line"> stack<<span class="type">int</span>> st;</span><br><span class="line"> st.<span class="built_in">push</span>(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i < nums2.<span class="built_in">size</span>(); i++){</span><br><span class="line"> <span class="keyword">while</span>(!st.<span class="built_in">empty</span>() && nums2[i] > nums2[st.<span class="built_in">top</span>()]){</span><br><span class="line"> <span class="type">int</span> ntop = nums2[st.<span class="built_in">top</span>()];</span><br><span class="line"> <span class="keyword">if</span>(mp.<span class="built_in">find</span>(ntop) != mp.<span class="built_in">end</span>()){</span><br><span class="line"> ng[mp[ntop]] = nums2[i];</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// cout<<endl;</span></span><br><span class="line"> st.<span class="built_in">pop</span>();</span><br><span class="line"> }</span><br><span class="line"> st.<span class="built_in">push</span>(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> ng;</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br></pre></td></tr></table></figure></p>
<h3 id="下一个更大元素ii">503.下一个更大元素II</h3>
<p>我想的是找到最大的元素，从下一个数开始遍历一遍，不过看题解直接遍历两遍数组即可
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="function">vector<<span class="type">int</span>> <span class="title">nextGreaterElements</span><span class="params">(vector<<span class="type">int</span>>& nums)</span> </span>{</span><br><span class="line"> <span class="function">vector<<span class="type">int</span>> <span class="title">res</span><span class="params">(nums.size(), <span class="number">-1</span>)</span></span>;</span><br><span class="line"> <span class="comment">// int max_n = nums[0];</span></span><br><span class="line"> <span class="comment">// int max_i = 0;</span></span><br><span class="line"> <span class="comment">// for(int i = 0; i < nums.size(); i++){</span></span><br><span class="line"> <span class="comment">// if(nums[i] > max_n){</span></span><br><span class="line"> <span class="comment">// max_n = nums[i];</span></span><br><span class="line"> <span class="comment">// max_i = i;</span></span><br><span class="line"> <span class="comment">// }</span></span><br><span class="line"> <span class="comment">// }</span></span><br><span class="line"> stack<<span class="type">int</span>> st;</span><br><span class="line"> st.<span class="built_in">push</span>(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j < nums.<span class="built_in">size</span>()*<span class="number">2</span>; j++){</span><br><span class="line"> <span class="type">int</span> n_i = j % nums.<span class="built_in">size</span>();</span><br><span class="line"> <span class="keyword">while</span>(!st.<span class="built_in">empty</span>() && nums[n_i] > nums[st.<span class="built_in">top</span>()]){</span><br><span class="line"> res[st.<span class="built_in">top</span>()] = nums[n_i];</span><br><span class="line"> st.<span class="built_in">pop</span>();</span><br><span class="line"> }</span><br><span class="line"> st.<span class="built_in">push</span>(n_i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> res;</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/10/24/kamacode40palin/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/10/24/kamacode40palin/" class="post-title-link" itemprop="url">代码随想录 | 刷题-动态规划13</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-10-24 22:50:36 / 修改时间：22:50:45" itemprop="dateCreated datePublished" datetime="2025-10-24T22:50:36+08:00">2025-10-24</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="回文子串">647. 回文子串</h3>
<p>首先是找到递推关系，对于字符串中下标i-j的字串，如果<code>s[i] == s[j]</code>则可以由<code>dp[i+1][j-1]</code>推出<code>dp[i][j]</code>
然后是遍历顺序，因为要先知道<code>dp[i+1][j-1]</code>，所以要从下往上，从左至右遍历
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="function"><span class="type">int</span> <span class="title">countSubstrings</span><span class="params">(string s)</span> </span>{</span><br><span class="line"> vector<vector<<span class="type">bool</span>>> <span class="built_in">dp</span>(s.<span class="built_in">size</span>(),<span class="built_in">vector</span><<span class="type">bool</span>>(s.<span class="built_in">size</span>(), <span class="literal">false</span>));</span><br><span class="line"> <span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = s.<span class="built_in">size</span>()<span class="number">-1</span>; i >= <span class="number">0</span>; i--){</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> j = i; j < s.<span class="built_in">size</span>(); j++){</span><br><span class="line"> <span class="keyword">if</span>(s[i] != s[j]){</span><br><span class="line"> dp[i][j] = <span class="literal">false</span>;</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">if</span>(j - i <= <span class="number">1</span>){</span><br><span class="line"> dp[i][j] = <span class="literal">true</span>;</span><br><span class="line"> cnt++;</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> dp[i][j] = dp[i+<span class="number">1</span>][j<span class="number">-1</span>];</span><br><span class="line"> <span class="keyword">if</span>(dp[i][j] == <span class="literal">true</span>)cnt++;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> cnt;</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure></p>
<h3 id="最长回文子序列">516.最长回文子序列</h3>
<p>和上一题思路类似 <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> {</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line"> <span class="function"><span class="type">int</span> <span class="title">longestPalindromeSubseq</span><span class="params">(string s)</span> </span>{</span><br><span class="line"> vector<vector<<span class="type">int</span>>><span class="built_in">dp</span>(s.<span class="built_in">size</span>(), <span class="built_in">vector</span><<span class="type">int</span>>(s.<span class="built_in">size</span>(),<span class="number">0</span>));</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = s.<span class="built_in">size</span>()<span class="number">-1</span>; i >= <span class="number">0</span>; i--){</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> j = i; j < s.<span class="built_in">size</span>(); j++){</span><br><span class="line"> <span class="keyword">if</span>(s[i] != s[j]){</span><br><span class="line"> dp[i][j] = <span class="built_in">max</span>(dp[i+<span class="number">1</span>][j], dp[i][j<span class="number">-1</span>]);</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">if</span>(i == j){</span><br><span class="line"> dp[i][j] = <span class="number">1</span>;</span><br><span class="line"> }<span class="keyword">else</span> <span class="keyword">if</span>(i - j == <span class="number">1</span>){</span><br><span class="line"> dp[i][j] = <span class="number">2</span>;</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> dp[i][j] = dp[i+<span class="number">1</span>][j<span class="number">-1</span>]+<span class="number">2</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> dp[<span class="number">0</span>][s.<span class="built_in">size</span>()<span class="number">-1</span>];</span><br><span class="line"> }</span><br><span class="line">};</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/10/21/kamabagu8/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/10/21/kamabagu8/" class="post-title-link" itemprop="url">代码随想录 | 八股-DNS与CDN</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-10-22 07:38:41 / 修改时间：07:41:44" itemprop="dateCreated datePublished" datetime="2025-10-22T07:38:41+08:00">2025-10-22</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/comp-basic/" itemprop="url" rel="index"><span itemprop="name">comp basic</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="dns查询过程">DNS查询过程</h3>
<p>DNS 用来将主机名和域名转换为IP地址, 其查询过程一般通过以下步骤：</p>
<p>本地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地址与目标服务器建立连接，开始获取网页内容。</p>
<h3 id="cdn是什么有什么作用">CDN是什么，有什么作用？</h3>
<p>CDN是一种分布式网络服务，通过将内容存储在分布式的服务器上，使用户可以从距离较近的服务器获取所需的内容，从而加速互联网上的内容传输。</p>
<p>就近访问：CDN
在全球范围内部署了多个服务器节点，用户的请求会被路由到距离最近的 CDN
节点，提供快速的内容访问。 内容缓存：CDN
节点会缓存静态资源，如图片、样式表、脚本等。当用户请求访问这些资源时，CDN
会首先检查是否已经缓存了该资源。如果有缓存，CDN
节点会直接返回缓存的资源，如果没有缓存所需资源，它会从源服务器（原始服务器）回源获取资源，并将资源缓存到节点中，以便以后的请求。通过缓存内容，减少了对原始服务器的请求，减轻了源站的负载。
可用性：即使某些节点出现问题，用户请求可以被重定向到其他健康的节点。</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/10/21/kamapentest_data/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/10/21/kamapentest_data/" class="post-title-link" itemprop="url">代码随想录 | 刷题-模拟笔试1</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-10-22 00:22:01 / 修改时间：00:21:42" itemprop="dateCreated datePublished" datetime="2025-10-22T00:22:01+08:00">2025-10-22</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/leetcode/" itemprop="url" rel="index"><span itemprop="name">leetcode</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="卡码笔试-263.数据重删">卡码笔试 263.数据重删</h3>
<p>题目描述：
输入一串存储的数据，用N表示数据个数，用K表示数据块的大小，设计一个方法判断当前数据块是否和前面的数据块有重复，两个数据块内容完全一样则表示重复，如果重复则将这个数据块删除，并且在第一个出现数据块的后面增加重复数据的计数，输出经过重删之后的数据内容。
输入示例： <figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">8 </span><br><span class="line">3 </span><br><span class="line">3 4 5 3 4 5 5 4</span><br></pre></td></tr></table></figure> 输出示例： <figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">3 4 5 2 5 4 1</span><br></pre></td></tr></table></figure> <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string"><map></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string"><vector></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string"><iostream></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="type">int</span> total;</span><br><span class="line"> <span class="type">int</span> len;</span><br><span class="line"> <span class="type">int</span> c;</span><br><span class="line"> vector<<span class="type">int</span>> data;</span><br><span class="line"> cin>>total>>len;</span><br><span class="line"> <span class="keyword">while</span>(cin>>c){</span><br><span class="line"> data.<span class="built_in">push_back</span>(c);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> map<vector<<span class="type">int</span>>, <span class="type">int</span>> mp;</span><br><span class="line"> vector<vector<<span class="type">int</span>>> uniqueBlock;</span><br><span class="line"> vector<<span class="type">bool</span>> isUnique;</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < data.<span class="built_in">size</span>(); i+=len){</span><br><span class="line"> <span class="type">int</span> cnt = <span class="number">0</span>;</span><br><span class="line"> vector<<span class="type">int</span>> block;</span><br><span class="line"> <span class="keyword">while</span>(cnt < len && (i+cnt) < data.<span class="built_in">size</span>()){</span><br><span class="line"> block.<span class="built_in">push_back</span>(data[i+cnt]);</span><br><span class="line"> <span class="comment">// cout<<"pushed in block: "<<data[i+cnt]<<endl;</span></span><br><span class="line"> cnt++;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// cout<<endl;</span></span><br><span class="line"> mp[block]++;</span><br><span class="line"> <span class="keyword">if</span>(mp[block] == <span class="number">1</span>){</span><br><span class="line"> isUnique.<span class="built_in">push_back</span>(<span class="literal">true</span>);</span><br><span class="line"> }<span class="keyword">else</span>{</span><br><span class="line"> isUnique.<span class="built_in">push_back</span>(<span class="literal">false</span>);</span><br><span class="line"> }</span><br><span class="line"> uniqueBlock.<span class="built_in">push_back</span>(block);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < uniqueBlock.<span class="built_in">size</span>(); i++){</span><br><span class="line"> <span class="keyword">if</span>(isUnique[i] == <span class="literal">true</span>){</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> n: uniqueBlock[i]){</span><br><span class="line"> cout<<n<<<span class="string">' '</span>;</span><br><span class="line"> }</span><br><span class="line"> cout<<mp[uniqueBlock[i]]<<<span class="string">' '</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// cout<<endl;</span></span><br><span class="line"></span><br><span class="line"> <span class="comment">// cout<<"total data: "<<total<<endl;</span></span><br><span class="line"> <span class="comment">// cout<<"len of blocks: "<<len<<endl;</span></span><br><span class="line"> <span class="comment">// for(int i: data){</span></span><br><span class="line"> <span class="comment">// cout<<i<<' ';</span></span><br><span class="line"> <span class="comment">// }</span></span><br><span class="line"> <span class="comment">// cout<<endl;</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
<link itemprop="mainEntityOfPage" href="https://mackz-maxw.github.io/2025/10/21/intv_xp/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Mackz-Maxw">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Maxw的小站">
<meta itemprop="description" content="乘上燃犀船，还未曾去过倒悬山。">
</span>
<span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
<meta itemprop="name" content="undefined | Maxw的小站">
<meta itemprop="description" content="">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2025/10/21/intv_xp/" class="post-title-link" itemprop="url">算法笔试 | 某厂后端复盘</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2025-10-22 00:18:49" itemprop="dateCreated datePublished" datetime="2025-10-22T00:18:49+08:00">2025-10-22</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>