-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
1258 lines (843 loc) · 83.2 KB
/
index.html
File metadata and controls
1258 lines (843 loc) · 83.2 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="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
<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="/lib/font-awesome/css/all.min.css">
<script id="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"zehai.info","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
</script>
<meta name="description" content="会做饭的厨子">
<meta property="og:type" content="website">
<meta property="og:title" content="Zehai'blog">
<meta property="og:url" content="http://zehai.info/index.html">
<meta property="og:site_name" content="Zehai'blog">
<meta property="og:description" content="会做饭的厨子">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="Zhang Zehai">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="http://zehai.info/">
<script id="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : true,
isPost : false,
lang : 'en'
};
</script>
<title>Zehai'blog</title>
<noscript>
<style>
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage">
<div class="container use-motion">
<div class="headband"></div>
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="Toggle navigation bar">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<h1 class="site-title">Zehai'blog</h1>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
<i class="fa fa-search fa-fw fa-lg"></i>
</div>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="main-menu menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section"><i class="fa fa-home fa-fw"></i>Home</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>Tags</a>
</li>
<li class="menu-item menu-item-categories">
<a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>Categories</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>Archives</a>
</li>
<li class="menu-item menu-item-about">
<a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>About</a>
</li>
<li class="menu-item menu-item-network">
<a href="/cnetwork/" rel="section"><i class="fa fa-mobile fa-fw"></i>network</a>
</li>
<li class="menu-item menu-item-computeros">
<a href="/ComputerOS/" rel="section"><i class="fa fa-desktop fa-fw"></i>computerOs</a>
</li>
<li class="menu-item menu-item-interview">
<a href="/Interview/" rel="section"><i class="fa fa-user fa-fw"></i>interview</a>
</li>
<li class="menu-item menu-item-java">
<a href="/Java/" rel="section"><i class="fa fa-tasks fa-fw"></i>java</a>
</li>
<li class="menu-item menu-item-like">
<a href="/Like/" rel="section"><i class="fa fa-book fa-fw"></i>like</a>
</li>
<li class="menu-item menu-item-nodejs">
<a href="/Nodejs/" rel="section"><i class="fa fa-plane fa-fw"></i>nodejs</a>
</li>
<li class="menu-item menu-item-redis">
<a href="/Redis/" rel="section"><i class="fa fa-database fa-fw"></i>redis</a>
</li>
<li class="menu-item menu-item-structure">
<a href="/Structure/" rel="section"><i class="fa fa-table fa-fw"></i>structure</a>
</li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>Search
</a>
</li>
</ul>
</nav>
<div class="search-pop-overlay">
<div class="popup search-popup">
<div class="search-header">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off"
placeholder="Searching..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div id="search-result">
<div id="no-result">
<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
</div>
</div>
</div>
</div>
</div>
</header>
<div class="back-to-top">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
<main class="main">
<div class="main-inner">
<div class="content-wrap">
<div class="content index posts-expand">
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/08/13/2021-08-13-Leetcode233/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/08/13/2021-08-13-Leetcode233/" class="post-title-link" itemprop="url">Leetcode233</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-08-13 11:54:52" itemprop="dateCreated datePublished" datetime="2021-08-13T11:54:52+08:00">2021-08-13</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2021-08-16 16:19:18" itemprop="dateModified" datetime="2021-08-16T16:19:18+08:00">2021-08-16</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<h4 id="233-数字-1-的个数"><a href="#233-数字-1-的个数" class="headerlink" title="233. 数字 1 的个数"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/number-of-digit-one/">233. 数字 1 的个数</a></h4><p>难度困难303收藏分享切换为英文接收动态反馈</p>
<p>给定一个整数 <code>n</code>，计算所有小于等于 <code>n</code> 的非负整数中数字 <code>1</code> 出现的个数。</p>
<p><strong>示例 1：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n = 13</span><br><span class="line">输出：6</span><br></pre></td></tr></table></figure>
<p><strong>示例 2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：n = 0</span><br><span class="line">输出：0</span><br></pre></td></tr></table></figure>
<p><strong>提示：</strong></p>
<ul>
<li><code>0 <= n <= 2 * 109</code></li>
</ul>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><p>拿到题目很奇怪，这道题暴力解答也就是个稍稍大于o(n)的复杂度，作为hard题目出现，只能说明暴力会超时</p>
<p>那么先回顾一下整体的超时代码段</p>
<figure class="highlight js"><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></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">{number}</span> <span class="variable">n</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">{number}</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> countDigitOne = <span class="function"><span class="keyword">function</span> (<span class="params">n</span>) </span>{</span><br><span class="line"> <span class="keyword">let</span> counter = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> i = n; i > <span class="number">0</span>; i--) {</span><br><span class="line"> <span class="keyword">let</span> num = i;</span><br><span class="line"> <span class="keyword">while</span> (num > <span class="number">0</span>) {</span><br><span class="line"> <span class="keyword">if</span> (num % <span class="number">10</span> === <span class="number">1</span>) {</span><br><span class="line"> counter++;</span><br><span class="line"> }</span><br><span class="line"> num = <span class="built_in">Math</span>.floor(num / <span class="number">10</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> counter</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
<p>超时之后我就开始找规律，个位1只会出现1次，十位只会出现10次，百位是100次，之后是数学方法就不解了（懒orz）,答案的主要部分</p>
<figure class="highlight js"><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="keyword">for</span> (<span class="keyword">let</span> k = <span class="number">0</span>; n >= mulk; ++k) {</span><br><span class="line"> ans += (<span class="built_in">Math</span>.floor(n / (mulk * <span class="number">10</span>))) * mulk + <span class="built_in">Math</span>.min(<span class="built_in">Math</span>.max(n % (mulk * <span class="number">10</span>) - mulk + <span class="number">1</span>, <span class="number">0</span>), mulk);</span><br><span class="line"> mulk *= <span class="number">10</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>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/08/13/2021-08-13-Leetcode133/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/08/13/2021-08-13-Leetcode133/" class="post-title-link" itemprop="url">Leetcode133</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-08-13 11:48:19 / Modified: 11:55:24" itemprop="dateCreated datePublished" datetime="2021-08-13T11:48:19+08:00">2021-08-13</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<h4 id="133-克隆图"><a href="#133-克隆图" class="headerlink" title="133. 克隆图"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/clone-graph/">133. 克隆图</a></h4><p>难度中等390收藏分享切换为英文接收动态反馈</p>
<p>给你无向 <strong><a target="_blank" rel="noopener" href="https://baike.baidu.com/item/连通图/6460995?fr=aladdin">连通</a></strong> 图中一个节点的引用，请你返回该图的 <a target="_blank" rel="noopener" href="https://baike.baidu.com/item/深拷贝/22785317?fr=aladdin"><strong>深拷贝</strong></a>（克隆）。</p>
<p>图中的每个节点都包含它的值 <code>val</code>（<code>int</code>） 和其邻居的列表（<code>list[Node]</code>）。</p>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><p>dfs就可以解决</p>
<p>题目提供了索引就是val，所以map的key可以使用val来简化体积</p>
<figure class="highlight js"><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></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * // Definition for a Node.</span></span><br><span class="line"><span class="comment"> * function Node(val, neighbors) {</span></span><br><span class="line"><span class="comment"> * this.val = val === undefined ? 0 : val;</span></span><br><span class="line"><span class="comment"> * this.neighbors = neighbors === undefined ? [] : neighbors;</span></span><br><span class="line"><span class="comment"> * };</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">{Node}</span> <span class="variable">node</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">{Node}</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> cloneGraph = <span class="function"><span class="keyword">function</span> (<span class="params">node</span>) </span>{</span><br><span class="line"> <span class="keyword">if</span> (!node) <span class="keyword">return</span>;</span><br><span class="line"> <span class="keyword">let</span> isVisit = <span class="keyword">new</span> <span class="built_in">Map</span>();</span><br><span class="line"> <span class="comment">//dfs</span></span><br><span class="line"> <span class="keyword">const</span> dfs = <span class="function"><span class="keyword">function</span> (<span class="params">item</span>) </span>{</span><br><span class="line"> <span class="keyword">const</span> newNode = <span class="keyword">new</span> Node(item.val);</span><br><span class="line"> isVisit.set(item.val, newNode);</span><br><span class="line"> <span class="comment">// console.log('isVist===>',isVisit)</span></span><br><span class="line"> <span class="comment">// deep clone</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> neighbor <span class="keyword">of</span> item.neighbors) {</span><br><span class="line"> <span class="keyword">if</span> (!isVisit.has(neighbor.val)) {</span><br><span class="line"> dfs(neighbor);</span><br><span class="line"> }</span><br><span class="line"> newNode.neighbors.push(isVisit.get(neighbor.val))</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> dfs(node);</span><br><span class="line"> <span class="keyword">return</span> isVisit.get(node.val);</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/08/04/2021-08-04-LeetCode611/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/08/04/2021-08-04-LeetCode611/" class="post-title-link" itemprop="url">LeetCode611</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-08-04 15:37:34 / Modified: 15:50:16" itemprop="dateCreated datePublished" datetime="2021-08-04T15:37:34+08:00">2021-08-04</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<h4 id="611-有效三角形的个数"><a href="#611-有效三角形的个数" class="headerlink" title="611. 有效三角形的个数"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/valid-triangle-number/">611. 有效三角形的个数</a></h4><p>难度中等230收藏分享切换为英文接收动态反馈</p>
<p>给定一个包含非负整数的数组，你的任务是统计其中可以组成三角形三条边的三元组个数。</p>
<p><strong>示例 1:</strong></p>
<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><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">输入: [2,2,3,4]</span><br><span class="line">输出: 3</span><br><span class="line">解释:</span><br><span class="line">有效的组合是: </span><br><span class="line">2,3,4 (使用第一个 2)</span><br><span class="line">2,3,4 (使用第二个 2)</span><br><span class="line">2,2,3</span><br></pre></td></tr></table></figure>
<p><strong>注意:</strong></p>
<ol>
<li>数组长度不超过1000。</li>
<li>数组里整数的范围为 [0, 1000]。</li>
</ol>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><p>排序后根据，a+b>c 套两层for循环确定ab，理论上还可以再套一层for循环确定c，但是复杂度太高，达到o(n^3)的复杂度，我们可以通过二分法，找到a+b<c 和a+b>c的极限值，极限左边都是符合要求的数据，从而n降为lgn的复杂度</p>
<figure class="highlight js"><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="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">{number[]}</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">{number}</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> triangleNumber = <span class="function"><span class="keyword">function</span>(<span class="params">nums</span>) </span>{</span><br><span class="line"> <span class="keyword">if</span> (nums.length < <span class="number">3</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">let</span> ans = <span class="number">0</span>;</span><br><span class="line"> nums = nums.sort();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i < nums.length ; i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> j = i + <span class="number">1</span>; j < nums.length ; j++) {</span><br><span class="line"> <span class="comment">// 二分</span></span><br><span class="line"> <span class="keyword">let</span> left = j + <span class="number">1</span>, right = nums.length - <span class="number">1</span>, k = j;</span><br><span class="line"> <span class="keyword">while</span> (left <= right) {</span><br><span class="line"> <span class="keyword">const</span> mid = <span class="built_in">Math</span>.floor((left + right) / <span class="number">2</span>);</span><br><span class="line"> <span class="keyword">if</span> (nums[mid] < nums[i] + nums[j]) {</span><br><span class="line"> k = mid;</span><br><span class="line"> left = mid + <span class="number">1</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> right = mid - <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> ans += k - j;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> ans;</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/08/03/2021-08-03-Leetcode581/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/08/03/2021-08-03-Leetcode581/" class="post-title-link" itemprop="url">Leetcode581</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-08-03 16:12:31 / Modified: 16:17:25" itemprop="dateCreated datePublished" datetime="2021-08-03T16:12:31+08:00">2021-08-03</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<h4 id="581-最短无序连续子数组"><a href="#581-最短无序连续子数组" class="headerlink" title="581. 最短无序连续子数组"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/">581. 最短无序连续子数组</a></h4><p>难度中等609收藏分享切换为英文接收动态反馈</p>
<p>给你一个整数数组 <code>nums</code> ，你需要找出一个 <strong>连续子数组</strong> ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。</p>
<p>请你找出符合题意的 <strong>最短</strong> 子数组，并输出它的长度。</p>
<p><strong>示例 1：</strong></p>
<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">输入：nums = [2,6,4,8,10,9,15]</span><br><span class="line">输出：5</span><br><span class="line">解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。</span><br></pre></td></tr></table></figure>
<p><strong>示例 2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums = [1,2,3,4]</span><br><span class="line">输出：0</span><br></pre></td></tr></table></figure>
<p><strong>示例 3：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：nums = [1]</span><br><span class="line">输出：0</span><br></pre></td></tr></table></figure>
<p><strong>提示：</strong></p>
<ul>
<li><code>1 <= nums.length <= 104</code></li>
<li><code>-105 <= nums[i] <= 105</code></li>
</ul>
<p><strong>进阶：</strong>你可以设计一个时间复杂度为 <code>O(n)</code> 的解决方案吗？</p>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><p>目前想到的方法</p>
<ul>
<li>偏数学，找到最大最小值为界</li>
<li>排序找差别，确定子数组两边下标</li>
<li>排序后用二分（稍微提升）</li>
</ul>
<figure class="highlight js"><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></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">{number[]}</span> <span class="variable">nums</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">{number}</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> findUnsortedSubarray = <span class="function"><span class="keyword">function</span> (<span class="params">nums</span>) </span>{</span><br><span class="line"> <span class="keyword">let</span> start, end = -<span class="number">1</span>, point = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">let</span> max = -<span class="number">100000</span>, min = <span class="number">10000</span>;<span class="comment">//题目给的大小区间</span></span><br><span class="line"> <span class="keyword">while</span> (point < nums.length) {</span><br><span class="line"> <span class="comment">// 找分界点</span></span><br><span class="line"> max > nums[point] ? end = point : max = nums[point]</span><br><span class="line"> min < nums[nums.length - point - <span class="number">1</span>] ? start = nums.length - point - <span class="number">1</span> : min = nums[nums.length - point - <span class="number">1</span>]</span><br><span class="line"> point++;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> end === -<span class="number">1</span> ? <span class="number">0</span> : end - start + <span class="number">1</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>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/08/02/2021-08-02-Leetcode743/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/08/02/2021-08-02-Leetcode743/" class="post-title-link" itemprop="url">2021-08-02-Leetcode743</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-08-02 21:21:52 / Modified: 23:05:45" itemprop="dateCreated datePublished" datetime="2021-08-02T21:21:52+08:00">2021-08-02</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<h4 id="743-网络延迟时间"><a href="#743-网络延迟时间" class="headerlink" title="743. 网络延迟时间"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/network-delay-time/">743. 网络延迟时间</a></h4><p>难度中等371收藏分享切换为英文接收动态反馈</p>
<p>有 <code>n</code> 个网络节点，标记为 <code>1</code> 到 <code>n</code>。</p>
<p>给你一个列表 <code>times</code>，表示信号经过 <strong>有向</strong> 边的传递时间。 <code>times[i] = (ui, vi, wi)</code>，其中 <code>ui</code> 是源节点，<code>vi</code> 是目标节点， <code>wi</code> 是一个信号从源节点传递到目标节点的时间。</p>
<p>现在，从某个节点 <code>K</code> 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 <code>-1</code> 。</p>
<p><strong>示例 1：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2019/05/23/931_example_1.png" alt="img"></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2</span><br><span class="line">输出：2</span><br></pre></td></tr></table></figure>
<p><strong>示例 2：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：times = [[1,2,1]], n = 2, k = 1</span><br><span class="line">输出：1</span><br></pre></td></tr></table></figure>
<p><strong>示例 3：</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">输入：times = [[1,2,1]], n = 2, k = 2</span><br><span class="line">输出：-1</span><br></pre></td></tr></table></figure>
<p><strong>提示：</strong></p>
<ul>
<li><code>1 <= k <= n <= 100</code></li>
<li><code>1 <= times.length <= 6000</code></li>
<li><code>times[i].length == 3</code></li>
<li><code>1 <= ui, vi <= n</code></li>
<li><code>ui != vi</code></li>
<li><code>0 <= wi <= 100</code></li>
<li>所有 <code>(ui, vi)</code> 对都 <strong>互不相同</strong>（即，不含重复边）</li>
</ul>
<h2 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h2><p>明显的思路，</p>
<ul>
<li>Dijkstra</li>
</ul>
<figure class="highlight js"><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></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> networkDelayTime = <span class="function"><span class="keyword">function</span> (<span class="params">times, n, k</span>) </span>{</span><br><span class="line"> <span class="keyword">const</span> INF = <span class="built_in">Number</span>.MAX_SAFE_INTEGER;<span class="comment">// max value</span></span><br><span class="line"> <span class="keyword">const</span> g = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(INF).map(<span class="function">() =></span> <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(INF));</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">const</span> t <span class="keyword">of</span> times) {</span><br><span class="line"> <span class="keyword">const</span> x = t[<span class="number">0</span>] - <span class="number">1</span>, y = t[<span class="number">1</span>] - <span class="number">1</span>;</span><br><span class="line"> g[x][y] = t[<span class="number">2</span>];<span class="comment">// 赋值</span></span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">const</span> dist = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(INF);<span class="comment">//distance</span></span><br><span class="line"> dist[k - <span class="number">1</span>] = <span class="number">0</span>;<span class="comment">//k 本身为0</span></span><br><span class="line"> <span class="keyword">const</span> used = <span class="keyword">new</span> <span class="built_in">Array</span>(n).fill(<span class="literal">false</span>);<span class="comment">//遍历标记</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i < n; ++i) {<span class="comment">//遍历每个顶点</span></span><br><span class="line"> <span class="keyword">let</span> x = -<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> y = <span class="number">0</span>; y < n; ++y) {</span><br><span class="line"> <span class="comment">// 未标记过并且(x为-1 或者 y的距离小于x的距离) 准备需要更新的节点</span></span><br><span class="line"> <span class="keyword">if</span> (!used[y] && (x === -<span class="number">1</span> || dist[y] < dist[x])) {</span><br><span class="line"> x = y;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> used[x] = <span class="literal">true</span>;<span class="comment">//遍历标记</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> y = <span class="number">0</span>; y < n; ++y) {</span><br><span class="line"> <span class="comment">// k到x的最小值</span></span><br><span class="line"> dist[y] = <span class="built_in">Math</span>.min(dist[y], dist[x] + g[x][y]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">let</span> ans = <span class="built_in">Math</span>.max(...dist);<span class="comment">//最小值的最大值</span></span><br><span class="line"> <span class="keyword">return</span> ans === INF ? -<span class="number">1</span> : ans;</span><br><span class="line">};</span><br><span class="line"><span class="built_in">console</span>.log(networkDelayTime([[<span class="number">2</span>, <span class="number">1</span>, <span class="number">1</span>], [<span class="number">2</span>, <span class="number">3</span>, <span class="number">1</span>], [<span class="number">3</span>, <span class="number">4</span>, <span class="number">1</span>]], <span class="number">4</span>, <span class="number">2</span>))</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/08/02/2021-08-02-mongodbTransaction/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/08/02/2021-08-02-mongodbTransaction/" class="post-title-link" itemprop="url">mongodbTransaction</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-08-02 09:34:41 / Modified: 09:36:53" itemprop="dateCreated datePublished" datetime="2021-08-02T09:34:41+08:00">2021-08-02</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">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/mongoDB/" itemprop="url" rel="index"><span itemprop="name">mongoDB</span></a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>前几天面试官说mongodb5出了事务，就赶紧来看看，毕竟业务层处理还是挺麻烦的，以前只支持操作的原子性</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/07/31/2021-07-31-Leetcode144/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/07/31/2021-07-31-Leetcode144/" class="post-title-link" itemprop="url">Leetcode144</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-07-31 23:49:38" itemprop="dateCreated datePublished" datetime="2021-07-31T23:49:38+08:00">2021-07-31</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2021-08-01 00:13:20" itemprop="dateModified" datetime="2021-08-01T00:13:20+08:00">2021-08-01</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<h4 id="144-二叉树的前序遍历"><a href="#144-二叉树的前序遍历" class="headerlink" title="144. 二叉树的前序遍历"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/binary-tree-preorder-traversal/">144. 二叉树的前序遍历</a></h4><p>总体思路递归，easy等级</p>
<figure class="highlight js"><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="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for a binary tree node.</span></span><br><span class="line"><span class="comment"> * function TreeNode(val, left, right) {</span></span><br><span class="line"><span class="comment"> * this.val = (val===undefined ? 0 : val)</span></span><br><span class="line"><span class="comment"> * this.left = (left===undefined ? null : left)</span></span><br><span class="line"><span class="comment"> * this.right = (right===undefined ? null : right)</span></span><br><span class="line"><span class="comment"> * }</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">{TreeNode}</span> <span class="variable">root</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">{number[]}</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> preorderTraversal = <span class="function"><span class="keyword">function</span> (<span class="params">root</span>) </span>{</span><br><span class="line"> <span class="keyword">const</span> ans = [];</span><br><span class="line"> recursion(root, ans);</span><br><span class="line"> <span class="keyword">return</span> ans</span><br><span class="line">};</span><br><span class="line"><span class="function"><span class="keyword">function</span> <span class="title">recursion</span>(<span class="params">root, ans</span>) </span>{</span><br><span class="line"> <span class="keyword">if</span> (root === <span class="literal">null</span>) <span class="keyword">return</span>;</span><br><span class="line"> ans.push(root.val);</span><br><span class="line"> recursion(root.left, ans)</span><br><span class="line"> recursion(root.right, ans)</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/07/27/2021-07-27-second-minimum-node-in-a-binary-tree/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/07/27/2021-07-27-second-minimum-node-in-a-binary-tree/" class="post-title-link" itemprop="url">second-minimum-node-in-a-binary-tree</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-07-27 21:53:51" itemprop="dateCreated datePublished" datetime="2021-07-27T21:53:51+08:00">2021-07-27</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2021-08-01 00:13:27" itemprop="dateModified" datetime="2021-08-01T00:13:27+08:00">2021-08-01</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="Leetcode-671"><a href="#Leetcode-671" class="headerlink" title="Leetcode 671"></a>Leetcode 671</h1><h4 id="671-二叉树中第二小的节点"><a href="#671-二叉树中第二小的节点" class="headerlink" title="671. 二叉树中第二小的节点"></a><a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/second-minimum-node-in-a-binary-tree/">671. 二叉树中第二小的节点</a></h4><p>难度简单198收藏分享切换为英文接收动态反馈</p>
<p>给定一个非空特殊的二叉树，每个节点都是正数，并且每个节点的子节点数量只能为 <code>2</code> 或 <code>0</code>。如果一个节点有两个子节点的话，那么该节点的值等于两个子节点中较小的一个。</p>
<p>更正式地说，<code>root.val = min(root.left.val, root.right.val)</code> 总成立。</p>
<p>给出这样的一个二叉树，你需要输出所有节点中的<strong>第二小的值。</strong>如果第二小的值不存在的话，输出 -1 <strong>。</strong></p>
<p><strong>示例 1：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2020/10/15/smbt1.jpg" alt="img"></p>
<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">输入：root = [2,2,5,null,null,5,7]</span><br><span class="line">输出：5</span><br><span class="line">解释：最小的值是 2 ，第二小的值是 5 。</span><br></pre></td></tr></table></figure>
<p><strong>示例 2：</strong></p>
<p><img src="https://assets.leetcode.com/uploads/2020/10/15/smbt2.jpg" alt="img"></p>
<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">输入：root = [2,2,2]</span><br><span class="line">输出：-1</span><br><span class="line">解释：最小的值是 2, 但是不存在第二小的值。</span><br></pre></td></tr></table></figure>
<p><strong>提示：</strong></p>
<ul>
<li>树中节点数目在范围 <code>[1, 25]</code> 内</li>
<li><code>1 <= Node.val <= 231 - 1</code></li>
<li>对于树中每个节点 <code>root.val == min(root.left.val, root.right.val)</code></li>
</ul>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><p>如题意，父节点就是最小值，借鉴了答案，递归条件写错了</p>
<figure class="highlight js"><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></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for a binary tree node.</span></span><br><span class="line"><span class="comment"> * function TreeNode(val, left, right) {</span></span><br><span class="line"><span class="comment"> * this.val = (val===undefined ? 0 : val)</span></span><br><span class="line"><span class="comment"> * this.left = (left===undefined ? null : left)</span></span><br><span class="line"><span class="comment"> * this.right = (right===undefined ? null : right)</span></span><br><span class="line"><span class="comment"> * }</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param <span class="type">{TreeNode}</span> <span class="variable">root</span></span></span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return <span class="type">{number}</span></span></span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> findSecondMinimumValue = <span class="function"><span class="keyword">function</span> (<span class="params">root</span>) </span>{</span><br><span class="line"></span><br><span class="line"> <span class="keyword">let</span> ans = -<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">const</span> parentValue = root.val;<span class="comment">//root value</span></span><br><span class="line"></span><br><span class="line"> <span class="keyword">const</span> dfs = <span class="function">(<span class="params">node</span>) =></span> {</span><br><span class="line"> <span class="keyword">if</span> (node === <span class="literal">null</span>) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (ans !== -<span class="number">1</span> && node.val >= ans) {</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (node.val > parentValue) {</span><br><span class="line"> ans = node.val;</span><br><span class="line"> }</span><br><span class="line"> dfs(node.left);</span><br><span class="line"> dfs(node.right);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> dfs(root);</span><br><span class="line"> <span class="keyword">return</span> ans;</span><br><span class="line">};</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/07/26/2021-07-26-%E8%88%AA%E7%8F%AD%E9%A2%84%E8%AE%A2%E7%BB%9F%E8%AE%A1/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/07/26/2021-07-26-%E8%88%AA%E7%8F%AD%E9%A2%84%E8%AE%A2%E7%BB%9F%E8%AE%A1/" class="post-title-link" itemprop="url">1109. 航班预订统计</a>
</h2>
<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">Posted on</span>
<time title="Created: 2021-07-26 16:59:16" itemprop="dateCreated datePublished" datetime="2021-07-26T16:59:16+08:00">2021-07-26</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">Edited on</span>
<time title="Modified: 2021-07-27 22:51:25" itemprop="dateModified" datetime="2021-07-27T22:51:25+08:00">2021-07-27</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">In</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>
</header>
<div class="post-body" itemprop="articleBody">
<p>#Leetcode-<a target="_blank" rel="noopener" href="https://leetcode-cn.com/problems/corporate-flight-bookings/">1109. 航班预订统计</a></p>
<p>难度中等157收藏分享切换为英文接收动态反馈</p>
<p>这里有 <code>n</code> 个航班，它们分别从 <code>1</code> 到 <code>n</code> 进行编号。</p>
<p>有一份航班预订表 <code>bookings</code> ，表中第 <code>i</code> 条预订记录 <code>bookings[i] = [firsti, lasti, seatsi]</code> 意味着在从 <code>firsti</code> 到 <code>lasti</code> （<strong>包含</strong> <code>firsti</code> 和 <code>lasti</code> ）的 <strong>每个航班</strong> 上预订了 <code>seatsi</code> 个座位。</p>
<p>请你返回一个长度为 <code>n</code> 的数组 <code>answer</code>，其中 <code>answer[i]</code> 是航班 <code>i</code> 上预订的座位总数。</p>
<p><strong>示例 1：</strong></p>
<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><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></pre></td><td class="code"><pre><span class="line">输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5</span><br><span class="line">输出：[10,55,45,25,25]</span><br><span class="line">解释：</span><br><span class="line">航班编号 1 2 3 4 5</span><br><span class="line">预订记录 1 ： 10 10</span><br><span class="line">预订记录 2 ： 20 20</span><br><span class="line">预订记录 3 ： 25 25 25 25</span><br><span class="line">总座位数： 10 55 45 25 25</span><br><span class="line">因此，answer = [10,55,45,25,25]</span><br></pre></td></tr></table></figure>
<p><strong>示例 2：</strong></p>
<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><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">输入：bookings = [[1,2,10],[2,2,15]], n = 2</span><br><span class="line">输出：[10,25]</span><br><span class="line">解释：</span><br><span class="line">航班编号 1 2</span><br><span class="line">预订记录 1 ： 10 10</span><br><span class="line">预订记录 2 ： 15</span><br><span class="line">总座位数： 10 25</span><br><span class="line">因此，answer = [10,25]</span><br></pre></td></tr></table></figure>
<p><strong>提示：</strong></p>
<ul>
<li><code>1 <= n <= 2 * 104</code></li>
<li><code>1 <= bookings.length <= 2 * 104</code></li>
<li><code>bookings[i].length == 3</code></li>
<li><code>1 <= firsti <= lasti <= n</code></li>
<li><code>1 <= seatsi <= 104</code></li>
</ul>
<h1 id="Solution"><a href="#Solution" class="headerlink" title="Solution"></a>Solution</h1><p>题目到是很简单，主要做的就是一维数组做个累加，时间复杂度O(N^2)</p>
<figure class="highlight js"><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></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> corpFlightBookings = <span class="function"><span class="keyword">function</span> (<span class="params">bookings, n</span>) </span>{</span><br><span class="line"> <span class="keyword">const</span> answer = [];</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> i = <span class="number">0</span>; i < n; i++)answer.push(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> item <span class="keyword">of</span> bookings) {</span><br><span class="line"> <span class="keyword">const</span> [first, last, seats] = item;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">let</span> j = first; j <= last; j++) {</span><br><span class="line"> answer[j-<span class="number">1</span>] += seats;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> answer;</span><br><span class="line"></span><br><span class="line">};</span><br><span class="line"><span class="built_in">console</span>.log(corpFlightBookings([[<span class="number">1</span>, <span class="number">2</span>, <span class="number">10</span>], [<span class="number">2</span>, <span class="number">3</span>, <span class="number">20</span>], [<span class="number">2</span>, <span class="number">5</span>, <span class="number">25</span>]], <span class="number">5</span>))</span><br></pre></td></tr></table></figure>
<p>但是时间只超过了50%，就考虑问题</p>
<p>问题应该在O^2的复杂度上</p>
<p>后来想遍历的时候</p>
<ul>
<li>Array(n).fill(0) 代码更优美</li>
<li>把<strong>增量</strong>加在数组里，最后走for循环跑一次就可以降一层for循环</li>
</ul>
<figure class="highlight js"><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"><span class="keyword">const</span> [first, last, seats] = item;</span><br><span class="line">answer[first - <span class="number">1</span>] += seats;</span><br><span class="line"><span class="keyword">if</span> (last < n) answer[last] -= seats;</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="http://zehai.info/2021/07/16/2021-07-16-Leetcode%E5%89%91%E6%8C%8753/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="Zhang Zehai">
<meta itemprop="description" content="会做饭的厨子">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Zehai'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">