-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
1745 lines (1048 loc) · 87.4 KB
/
index.html
File metadata and controls
1745 lines (1048 loc) · 87.4 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 class="theme-next gemini use-motion" lang="">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">
<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
<link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />
<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />
<link href="/css/main.css?v=5.1.4" rel="stylesheet" type="text/css" />
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.4">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=5.1.4">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=5.1.4">
<link rel="mask-icon" href="/images/logo.svg?v=5.1.4" color="#222">
<meta name="keywords" content="Hexo, NexT" />
<meta property="og:type" content="website">
<meta property="og:title" content="Hanzhi's BLOG">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="Hanzhi's BLOG">
<meta property="og:locale" content="default">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Hanzhi's BLOG">
<script type="text/javascript" id="hexo.configurations">
var NexT = window.NexT || {};
var CONFIG = {
root: '/',
scheme: 'Gemini',
version: '5.1.4',
sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
fancybox: true,
tabs: true,
motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
duoshuo: {
userId: '0',
author: 'Author'
},
algolia: {
applicationID: '',
apiKey: '',
indexName: '',
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"}
}
};
</script>
<link rel="canonical" href="http://yoursite.com/"/>
<title>Hanzhi's BLOG</title>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="default">
<div class="container sidebar-position-left
page-home">
<div class="headband"></div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-wrapper">
<div class="site-meta ">
<div class="custom-logo-site-title">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<span class="site-title">Hanzhi's BLOG</span>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<p class="site-subtitle"></p>
</div>
<div class="site-nav-toggle">
<button>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section">
<i class="menu-item-icon fa fa-fw fa-home"></i> <br />
Home
</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section">
<i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
Tags
</a>
</li>
<li class="menu-item menu-item-categories">
<a href="/categories/" rel="section">
<i class="menu-item-icon fa fa-fw fa-th"></i> <br />
Categories
</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section">
<i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
Archives
</a>
</li>
<li class="menu-item menu-item-about">
<a href="/about/" rel="section">
<i class="menu-item-icon fa fa-fw fa-user"></i> <br />
About
</a>
</li>
<li class="menu-item menu-item-search">
<a href="javascript:;" class="popup-trigger">
<i class="menu-item-icon fa fa-search fa-fw"></i> <br />
Search
</a>
</li>
</ul>
<div class="site-search">
<div class="popup search-popup local-search-popup">
<div class="local-search-header clearfix">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<span class="popup-btn-close">
<i class="fa fa-times-circle"></i>
</span>
<div class="local-search-input-wrapper">
<input autocomplete="off"
placeholder="Searching..." spellcheck="false"
type="text" id="local-search-input">
</div>
</div>
<div id="local-search-result"></div>
</div>
</div>
</nav>
</div>
</header>
<main id="main" class="main">
<div class="main-inner">
<div class="content-wrap">
<div id="content" class="content">
<section id="posts" class="posts-expand">
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/06/18/LeetCode-New-Summary/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Hanzhi Yang">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/avatar.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Hanzhi's BLOG">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/06/18/LeetCode-New-Summary/" itemprop="url">LeetCode New Summary</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Post created" itemprop="dateCreated datePublished" datetime="2018-06-18T21:18:39+08:00">
2018-06-18
</time>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-calendar-check-o"></i>
</span>
<span class="post-meta-item-text">Post modified:</span>
<time title="Post modified" itemprop="dateModified" datetime="2018-06-20T23:19:31+08:00">
2018-06-20
</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></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="2018-6-20"><a href="#2018-6-20" class="headerlink" title="2018-6-20"></a>2018-6-20</h1><h2 id="855-Exam-Room"><a href="#855-Exam-Room" class="headerlink" title="855. Exam Room"></a>855. Exam Room</h2><blockquote>
<p>In an exam room, there are N seats in a single row, numbered 0, 1, 2, …, N-1.<br>When a student enters the room, they must sit in the seat that maximizes the distance to the closest person. If there are multiple such seats, they sit in the seat with the lowest number. (Also, if no one is in the room, then the student sits at seat number 0.)<br>Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room. It is guaranteed that any calls to ExamRoom.leave(p) have a student sitting in seat p.</p>
</blockquote>
<p>Example 1:</p>
<blockquote>
<p><strong>Input:</strong> [“ExamRoom”,”seat”,”seat”,”seat”,”seat”,”leave”,”seat”], [[10],[],[],[],[],[4],[]]<br><strong>Output:</strong> [null,0,9,4,2,null,5]<br><strong>Explanation:</strong><br>ExamRoom(10) -> null<br>seat() -> 0, no one is in the room, then the student sits at seat number 0.<br>seat() -> 9, the student sits at the last seat number 9.<br>seat() -> 4, the student sits at the last seat number 4.<br>seat() -> 2, the student sits at the last seat number 2.<br>leave(4) -> null<br>seat() -> 5, the student sits at the last seat number 5.<br></p>
</blockquote>
<p>Note:</p>
<blockquote>
<ol>
<li>0 <= N <= 10^9</li>
<li>ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.</li>
<li>Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.</li>
</ol>
</blockquote>
<p><strong>IDEA:</strong><br>We notice that the range of N is from 0 to 10^9 so it is not wise to create an array to store every seat’s state. We can use segment to present the seat’s state and two points of a segment are both occupied.<br>In this case, the corner case are the first seat and the last point because their segments have just one point and the other is the boundry of the array which we need pay attention to.</p>
<p><strong>Solution:</strong><br>Keyword: TreeSet, Point, Priority(Haven’t been reached, do it in few days later) </p>
<p><strong><a href="https://github.com/TCoherence/LeetCodeExercise/blob/master/855.%20Exam%20Room.java" target="_blank" rel="noopener">CODE</a></strong> </p>
<h1 id="2018-6-19"><a href="#2018-6-19" class="headerlink" title="2018-6-19"></a>2018-6-19</h1><h2 id="854-K-Similar-Strings"><a href="#854-K-Similar-Strings" class="headerlink" title="854. K-Similar Strings"></a>854. K-Similar Strings</h2><blockquote>
<p>Strings A and B are K-similar (for some non-negative integer K) if we can swap the positions of two letters in A exactly K times so that the resulting string equals B. </p>
<p>Given two anagrams A and B, return the smallest K for which A and B are K-similar.</p>
</blockquote>
<p><strong>Example 1:</strong></p>
<blockquote>
<p>Input: A = “ab”, B = “ba”<br>Output: 1 </p>
</blockquote>
<p><strong>Example 2:</strong> </p>
<blockquote>
<p>Input: A = “abc”, B = “bca”<br>Output: 2 </p>
</blockquote>
<p><strong>Example 3:</strong> </p>
<blockquote>
<p>Input: A = “abac”, B = “baca”<br>Output: 2 </p>
</blockquote>
<p><strong>Example 4:</strong> </p>
<blockquote>
<p>Input: A = “aabc”, B = “abca”<br>Output: 2 </p>
</blockquote>
<p><strong>Note:</strong></p>
<blockquote>
<ol>
<li><= A.length == B.length <= 20</li>
<li>A and B contain only lowercase letters from the set {‘a’, ‘b’, ‘c’, ‘d’, ‘e’, ‘f’}</li>
</ol>
</blockquote>
<p><strong>IDEA</strong>:<br>When it comes to the shortest distance or shortest of something, we need to consider BFS first. After all, it is the most common algs to solve this problem.<br>In this problem, we use BFS to guarantee the result is shortest, then we swap every pair in A to reach B and <em>offer (because in java queue, the func is offer())</em> all the results to queue then use BFS to solve it.</p>
<p><strong><a href="https://github.com/TCoherence/LeetCodeExercise/blob/master/854.%20K-Similar%20Strings.java" target="_blank" rel="noopener">CODE</a></strong> </p>
<h1 id="2018-6-18"><a href="#2018-6-18" class="headerlink" title="2018-6-18"></a>2018-6-18</h1><h2 id="853-Car-Fleet"><a href="#853-Car-Fleet" class="headerlink" title="853. Car Fleet"></a>853. Car Fleet</h2><blockquote>
<p>N cars are going to the same destination along a one lane road. The destination is target miles away. Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.<br>A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.The distance between these two cars is ignored - they are assumed to have the same position.<br>A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.<br>If a car catches up to a car fleet right at the destination point,it will still be considered as one car fleet. </p>
<p>How many car fleets will arrive at the destination?</p>
</blockquote>
<p><strong>Example 1:</strong></p>
<blockquote>
<p><strong>Input</strong>: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]<br><strong>Output:</strong> 3<br><strong>Explanation:</strong><br>The cars starting at 10 and 8 become a fleet, meeting each other at 12.<br>The car starting at 0 doesn’t catch up to any other car, so it is a fleet by itself.<br>The cars starting at 5 and 3 become a fleet, meeting each other at 6.<br>Note that no other cars meet these fleets before the destination, so the answer is 3.</p>
</blockquote>
<p><strong>Note:</strong> </p>
<ol>
<li>0 <= N <= 10 ^ 4</li>
<li>0 < target <= 10 ^ 6</li>
<li>0 < speed[i] <= 10 ^ 6</li>
<li>0 <= position[i] < target</li>
<li>All initial positions are different.</li>
</ol>
<p><strong>IDEA:</strong><br>We need to find the fleets, so we need to know if one car will catch another one. To simplify the process, we sort the original position array, let’s say in ascending sequence, then we have a new array, let’s name it <em>pos</em>. Then the end of <em>pos</em> is closest to the target and the head of <em>pos</em> is farest to the target.<br>Now from the end of the array, we calculate the time that every car need to take to reach the target, if one car <strong><em>A</em></strong> firstly is ahead of car <strong><em>B</em></strong> but the time of car <strong><em>A</em></strong> need to take to reach the target is larger than <strong><em>B</em></strong>‘s time, it means that car <strong><em>B</em></strong> catches car <strong><em>A</em></strong> in no doubt, which means they are views as one car fleet.<br>So the key of this solution is:</p>
<ol>
<li>sort position</li>
<li>calculate the time consumption</li>
<li>compare the time consumption from the end to the head with current time and determine the occurence of car catching.</li>
</ol>
<p><strong><a href="https://github.com/TCoherence/LeetCodeExercise/blob/master/853.%20Car%20Fleet.java" target="_blank" rel="noopener">CODE</a></strong></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/05/09/Algorithms/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Hanzhi Yang">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/avatar.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Hanzhi's BLOG">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/05/09/Algorithms/" itemprop="url">Algorithms</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Post created" itemprop="dateCreated datePublished" datetime="2018-05-09T09:34:46+08:00">
2018-05-09
</time>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-calendar-check-o"></i>
</span>
<span class="post-meta-item-text">Post modified:</span>
<time title="Post modified" itemprop="dateModified" datetime="2018-05-09T21:32:06+08:00">
2018-05-09
</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></i>
</span>
<span class="post-meta-item-text">In</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/summary/" itemprop="url" rel="index">
<span itemprop="name">summary</span>
</a>
</span>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="ALGORITHM"><a href="#ALGORITHM" class="headerlink" title="ALGORITHM"></a>ALGORITHM</h1><h2 id="1-Backtracking"><a href="#1-Backtracking" class="headerlink" title="1. Backtracking"></a>1. Backtracking</h2><h2 id="2-DP-learning"><a href="#2-DP-learning" class="headerlink" title="2. DP ( learning )"></a>2. DP ( learning )</h2><h2 id="3-BFS-amp-DFS"><a href="#3-BFS-amp-DFS" class="headerlink" title="3. BFS & DFS"></a>3. BFS & DFS</h2><h2 id="4"><a href="#4" class="headerlink" title="4."></a>4.</h2>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="http://yoursite.com/2018/05/06/LeetCode-Exercise/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="Hanzhi Yang">
<meta itemprop="description" content="">
<meta itemprop="image" content="/images/avatar.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Hanzhi's BLOG">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/05/06/LeetCode-Exercise/" itemprop="url">LeetCode Exercise</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Post created" itemprop="dateCreated datePublished" datetime="2018-05-06T23:20:50+08:00">
2018-05-06
</time>
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-calendar-check-o"></i>
</span>
<span class="post-meta-item-text">Post modified:</span>
<time title="Post modified" itemprop="dateModified" datetime="2018-06-18T21:20:27+08:00">
2018-06-18
</time>
</span>
<span class="post-category" >
<span class="post-meta-divider">|</span>
<span class="post-meta-item-icon">
<i class="fa fa-folder-o"></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></p><h1 style="text-align:center">Leetcode</h1> <p></p>
<blockquote>
<p>This is a temporary post to record the experience of doing leetcode and will be rewrite and rearrange the layout (Typesetting) ASAP.<br>In the future I will sum up all the algs I know to a new post and write a new post to record the exercise. Hope I can do it well<br>2018.5.6</p>
</blockquote>
<hr>
<blockquote>
<p>Updated 2018-5-9, the following days will be tough and I have to rearrange the quantity of leetcode problems. The next 2 weeks’ focus is on GRADUATTION PROJECT & Side Project preparation.<br>Fight.</p>
</blockquote>
<h1 id="2018-5-14"><a href="#2018-5-14" class="headerlink" title="2018-5-14"></a>2018-5-14</h1><p>98.Validate Binary Search Tree<br>My first thought is using a stack to store the BST in preorder and compare the new-to-stack element’s value <strong>a</strong> with stack.peek() = <strong>b</strong> , if a > b then it is false;<br>When I check the Discussion Section and I find a more concise way to solve it.</p>
<blockquote>
<p>we can use localmin and localmax to restrict the range of local element’s value, but if we want to cover the whole range of Integer we have to set the original value of localmin to <strong><em>Long.MIN_VALUE</em></strong> and localmax to <strong><em>Long.MAX_VALUE</em></strong> which is not recommanded. So we can add two more boolean variable <strong><em>hasMin</em></strong> and <strong><em>hasMax</em></strong> to indicate whether we need check the upperbound or lowerbound.<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">boolean</span> <span class="title">isValidBST</span><span class="params">(TreeNode node, <span class="keyword">int</span> localMin, <span class="keyword">int</span> localMax, <span class="keyword">boolean</span> hasMin, <span class="keyword">boolean</span> hasMax)</span></span></span><br></pre></td></tr></table></figure></p>
</blockquote>
<p>111.Minimum Depth of Binary Tree<br>recursive:<br>compute the minimum depth of every node (left and right), especially when it comes to a situation that left or right is 0, we need to return the other side’s length, and we have a <strong>tricky</strong> code:<br><figure class="highlight java"><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> (left == <span class="number">0</span> || right == <span class="number">0</span> ) ? left + right + <span class="number">1</span> : Math.min(left, right) + <span class="number">1</span>;</span><br></pre></td></tr></table></figure></p>
<p>110.Balanced Binary Tree<br>use the same idea of No.111 problem :<br>compute the length of left and right subtree and compare them and return the boolean value.</p>
<p>257.Binary Tree Paths<br>like a backtracking problem.<br>Have learned the new API of StringBuilder class:<br><figure class="highlight java"><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">StringBuilder sb = <span class="keyword">new</span> StringBuilder();</span><br><span class="line">sb.delete(<span class="keyword">int</span> start, <span class="keyword">int</span> end); <span class="comment">// delete the element from start to end - 1.</span></span><br><span class="line">sb.setLength(<span class="keyword">int</span> length); <span class="comment">// set the length of StringBuilder, I think this one is more convenient than the former one when it comes to deletion.</span></span><br></pre></td></tr></table></figure></p>
<p>695.Max Area of Island<br>With a “DFS” tag but it seems like a BFS problem.use a 2d array to record whether a position has been visited.</p>
<h1 id="2018-5-10"><a href="#2018-5-10" class="headerlink" title="2018-5-10"></a>2018-5-10</h1><p>343.Integer Break<br>很难受,没有想出DP的解决方法!!争取明天弄一下DP的方法!</p>
<h1 id="2018-5-9"><a href="#2018-5-9" class="headerlink" title="2018-5-9"></a>2018-5-9</h1><p>今天看到了一个很nice的关于DP的总结,也算是弄清楚了一点点DC,DP和greedy的关系图了。<br>1、DP算法起源于DC,一个问题的解,可以分解为求解一系列子问题的解。同时包含有重叠子问题。这就得到了DP的第一个黄金准则:某个问题有独立的,重叠的子问题。也就是说,如果子问题不独立,没有办法分治。独立但是不重叠,直接遍历即可,也就是分治的实现。如果有重叠,那就是DP的用武之地了。<br>2、DP算法的黄金准则2,:最优子问题。很明显,DP的本质在于不重复计算子问题,因为把其计算结果存储起来了。也就是之前说过的state。</p>
<ol start="714">
<li><p>Best Time to Buy and Sell Stock with Transaction Fee</p>
</li>
<li><p>Best Time to Buy and Sell Stock with Cooldown</p>
</li>
<li><p>Best Time to Buy and Sell Stock IV<br>很难受,有了状态转移方程写不出代码。。<br>原来之前的代码原理上没有任何问题。。。。出在了边界条件的判断失误,导致少算了一个。<br>我说思路没问题怎么一直有问题。。<br>!!!</p>
</li>
<li><p>Best Time to Buy and Sell Stock III</p>
</li>
</ol>
<h1 id="2018-5-8"><a href="#2018-5-8" class="headerlink" title="2018-5-8"></a>2018-5-8</h1><ol start="338">
<li><p>Counting Bits<br>真的很巧妙,右移一位之后,就只要判断奇偶来决定bit的个数了。虽然我和他们遍历一样,但是指令时间花费太多。。。。<br>而且我只是找到了一个规律,却没有找到更核心简便的规律。更重要的是,没有用DP的思想。。</p>
</li>
<li><p>Best Time to Buy and Sell Stock II<br>Greedy</p>
</li>
</ol>
<h1 id="2018-5-7"><a href="#2018-5-7" class="headerlink" title="2018-5-7"></a>2018-5-7</h1><ol start="746">
<li><p>Min Cost Climbing Stairs</p>
</li>
<li><p>Range Sum Query - Immutable<br>尽管是在 DP tag下面做的,但是完完全全没有往这个方向去想。。。还是brute force解决。<br>可以利用sum,记录[0,i]</p>
</li>
</ol>
<hr>
<h1 id="2018-4-10"><a href="#2018-4-10" class="headerlink" title="2018-4-10"></a>2018-4-10</h1><p>Array Partition I<br>Arrays.sort,是Arrays!</p>
<p>Max Consecutive Ones<br>都说了是Consecutive ones还在考虑连续的0,不知道题目到底看没。</p>
<p>Toeplitz Matrix<br>关键是对角,不一定要分组的。</p>
<p>Move Zeroes<br>又是低级错误。。。。数组数值被下标代替。。。。</p>
<p>week 5<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">In in = new In(args[0]);</span><br></pre></td></tr></table></figure></p>
<p>&&语句前后顺序很重要!<br><figure class="highlight plain"><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></pre></td><td class="code"><pre><span class="line">if( x.lb != null && rect.intersects(x.lb.rect) ) </span><br><span class="line">// the upper and the lower act the same</span><br><span class="line">if( x.lb != null ){</span><br><span class="line"> if(rect.intersects(x.lb.rect)</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>所以一旦反过来变成这样就会出问题,因为x.lb可能为Null<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">rect.intersects(x.lb.rect) && x.lb != null</span><br></pre></td></tr></table></figure></p>
<p>nearest 是x.lb或者x.rt的rect的判断而不是对x.rect的判断</p>
<h1 id="2018-4-11"><a href="#2018-4-11" class="headerlink" title="2018-4-11"></a>2018-4-11</h1><p>今天看了两个算法:<br>BFS : Breadth-First-Search<br>DFS: Deapth-First-Search</p>
<p>BFS: 采用FIFO结构</p>
<p>顶点进队列<br>while(队列非空){<br> 把周围的未经过的顶点进队列。<br> 出队列。<br>}<br>结束循环,遍历所有节点。</p>
<p>DFS:栈</p>
<p>先把所有节点标白<br>顶点进栈,将其标灰<br>while(栈非空){<br> if(邻节点有白){</p>
<pre><code>节点标灰色
</code></pre><p>进入节点,将其压栈。<br> }<br> else (邻节点无白){</p>
<pre><code>将该点出栈
}
</code></pre><p>}</p>
<h1 id="2018-4-16"><a href="#2018-4-16" class="headerlink" title="2018-4-16"></a>2018-4-16</h1><p>现在准备看KMP算法,在回文算法题的discussion中看到。、</p>
<h1 id="2018-4-17"><a href="#2018-4-17" class="headerlink" title="2018-4-17"></a>2018-4-17</h1><p>复习week1 内容,Topological sort是redraw DAG so all edge point upwards.1) DFS, 2) return vertex in postorder</p>
<p>脑子不清醒了:<br>1、数组元素居然用 [ ] 括起来;<br>2、数组长度是num.length不是num.length{}<br>3、二分法的判断条件是high >= low,有一个等于号!!!</p>
<p>① 167. Two Sum II - Input array is sorted<br>sort 二分法还是不如两头相加来的方便。两头相加真是太牛逼了。<br>要注意的几个点是 int相加溢出,用long存储。判断参数。</p>
<p>② 169. Majority Element<br>自己第一反应是简单粗暴的创建一个65536数组,直接存储,两次for进行brute serach<br>想想有没有更好的方法<br>看了discussion:<br>1、牛逼,充分利用了major element数量大于一半,直接对数计数,遇到就加,碰到就减,最后留下来的肯定是major element<br>2、bit操作,很神奇。但是不知道为什么能够得到正确的结果。<br>3、hash table,暂时没学过,明天学习。<br>4、sorting,直接获取中间位数字即可 </p>
<p>③ 448. Find All Numbers Disappeared in an Array<br>第一反应: sort之后,根据offset计算disappear的值<br>看了discussion:<br>1、利用数组元素作为索引标记。核心在于数组中的元素个数和最大的数是相同的,也就是都是n。我之前以为可以小于n所以一直觉得很有问题。重点还是要好好审题啊。总是有小问题。<br>得到思路之后自己写,又出现了小问题:写出了List<int>。。。emmm多注意小细节。</int></p>
<p>提交之后发现有时间更短的,果然用了额外数组空间。</p>
<p>④ 717. 1-bit and 2-bit Characters<br>很简答的一道题目。。。emmm就是低级错误还是有:<br>1、变量都没声明就开始用了。<br>2、if语句乱用 。。。<br>3、大思路正确但是细节方面还是有瑕疵,跳跃检查没事但是忽略了最终都会跳到同一个位置。。</p>
<p>⑤ 121. Best Time to Buy and Sell Stock<br>思路很清晰的一道题目,但是自己还是考虑不够。<br>1、先入为主,没有考虑多种可能,认为只有一种可能,所以直接判断左边最小和右边最大。致使[2,4,1]这种testcase都output = 0,(因为左边最小是1所以 1 - 1 = 0)</p>
<p>刚刚看了 Best Time to Buy and Sell Stock II,听说要用贪心算法,没有接触过,明天对其进行了解。</p>
<h1 id="2018-4-18"><a href="#2018-4-18" class="headerlink" title="2018-4-18"></a>2018-4-18</h1><p>① 128. Longest Consecutive Sequence (有问题,没有达到O(n) 的要求却AC 100)<br>要求O(N),所以第一反应就是sort之后直接go through,O(n)+O(nlogn),不知道这算不算O(n)….数量级上是一样的。<br>提交后居然第一次AC 100,卧槽。。。。<br>尽管如此,第一次提交忽略的一个corner case,就是都是consecutive的时候,就不会执行到else语句当中。这个要多注意。<br>★ if-else语句要注意是否都会执行到。</p>
<p>② 217. Contains Duplicate<br>sort之后直接判断。发现自己已经迷上了sort【然而好像时间复杂度。。。。】</p>
<p>③ 268. Missing Number<br>sort之后 go through或者二分查找</p>
<p>看了discussion发现,有两个灵性的解法,但是比较特殊,因为只能找到少一个的<br>1、SUM操作,然后减array<br>2、XOR操作,因为a^b^b = a,所以将1 ~ n 所有与array中的所有XOR,就能得到missing number</p>
<p>④ 661. Image Smoother<br>第一反应还是brute 解决。<br>看完discussion,似乎大多也是brute。<br>但是有一个厉害的老哥,利用了255是8bit,int是16bit,将前8bit作为计算结果存储,最后整体右移8位!!!强的一笔,节约了一倍的空间。<br>反思:<br>1、自己边界判断都能弄错,服了。真是不知道在干嘛。。。。<br>2、循环变量居然忘记初始化????</p>
<p>⑤ 628. Maximum Product of Three Numbers<br>很奇怪,为什么sort之后直接计算的速率还不如不算的速率?因为时间复杂度不同。</p>
<p>⑥ 746. Min Cost Climbing Stairs<br>go through, i处判断i+1, i+2</p>
<p>第一次提交出错,[0,0,0,0]<br>很玄学,因为判断顺序的问题,先进行了计算后进行了判断,所以先出界,然后判断。抛出异常<br>第二次提交出错,[0,2,2,1]<br>改成两头运算,但是感觉很虚,方法冗长。</p>
<p>思路完全错误,应该动态规划。贪心算法似乎有问题。还是没有搞懂贪心算法和动态规划的区别。这道题目先放一放吧。把这两个算法弄懂了再来做。</p>
<p>⑦ 697. Degree of an Array<br>思路:<br>go through array, 统计value(degree),first_index,last_index<br>然后计算degree,和minimum_length<br>时间复杂度<br>go through – O(n)<br> 统计,链表的话就是O(n), hashmap/hashtable 是 O(1)<br>计算degree, go through O(n)</p>
<p>引出hashmap和hashtable的区别问题。</p>
<hr>
<blockquote>
<p>重新规划,先刷1-300.</p>
</blockquote>
<ol>
<li><p>Two Sum<br>失去了sorted这个条件就只会brute解决了,看了大神的解答发现可以用HashMap,可以尝试一下用HashMap解决。</p>
</li>
<li><p>Add Two Numbers<br>easy,设置res和carry两个数分别记录加后%10的值和进位,然后判断l1,l2是否为同时为null为结束循环条件。<br>但是忽略了同时为null时也有可能carry = 1,导致错误。<br>同时计算res加了c,计算c的时候却没有,同样导致错误。多加小心。</p>
</li>
<li><p>Longest Substring Without Repeating Characters<br>两个index,一个头一个尾,hashmap存储,一旦tail发现重复,回溯到重复点,重新查找,并且保存当前maxlen<br>思路正确,但是很遗憾,代码编写错误还是很多。<br>值得注意的是<br>1、s.length() 和 a.length String的length是带括号的,而数组不带。<br>2、找s中对应下标的char是s.charAt(index),而数组直接a[index]即可<br>3、<br>|原始类型|封装类|<br>|:—|:—-|<br>|boolean| Boolean|<br>|char | Character|<br>|byte | Byte|<br>|short | Short|<br>|int | Integer|<br>|long | Long|<br>|float | Float|<br>|double | Double|<br>4、<strong>遇见if-else一定要多加注意,看有没有可能一直if或者一直else导致某些特定语句没有执行到。。。。</strong></p>
</li>
</ol>
<h1 id="2018-4-20"><a href="#2018-4-20" class="headerlink" title="2018-4-20"></a>2018-4-20</h1><ol start="7">
<li><p>Reverse Integer<br>第一反应,boolean sign保留符号,然后abs计算,改成string,逆序,改回long int,输出。<br>还是太复杂了,直接从尾部go through,但是overflow有一个很奇妙的地方,x / 10 != a即可证明其overflow(<a href="https://leetcode.com/problems/reverse-integer/discuss/4060/My-accepted-15-lines-of-code-for-Java/126400?page=1)" target="_blank" rel="noopener">https://leetcode.com/problems/reverse-integer/discuss/4060/My-accepted-15-lines-of-code-for-Java/126400?page=1)</a><br>java int是32bit</p>
</li>
<li><p>Palindrome Number<br>和7一样计算出值直接 ==,而且如果入参 <0 直接返回false</p>
</li>
<li><p>Roman to Integer<br>找最大值,然后go through,小于最大的index做减法,大于的做加法。<br>仍然有漏洞,最大的可能多次出现。且多次出现仅有可能在头部。</p>
</li>
</ol>
<ol start="21">
<li><p>Merge Two Sorted Lists<br>题目根本没有说要保持sorted。。。<br>改了之后过了</p>
</li>
<li><p>Valid Parentheses<br>利用stack,检查。但是时间花费较多,似乎用数组更快,这是为什么呢?</p>
</li>
</ol>
<ol start="29">
<li>Divide Two Integers (Medium)<br>这种数据的edge case一定有overflow!!!!<br>java中 int cannot be converted to boolean</li>
</ol>
<h1 id="2018-4-21-(29今天也把他弄懂。)"><a href="#2018-4-21-(29今天也把他弄懂。)" class="headerlink" title="2018-4-21 (29今天也把他弄懂。)"></a>2018-4-21 (29今天也把他弄懂。)</h1><ol start="38">
<li>Count and Say<br>递归计算,时间开销很大。<br>学习其他人的方法。<br>1、利用循环调用函数进行计算,能用循环尽量用循环,因为递归在不断开销新的资源,每一次调用都会产生新的资源,而循环能够尽量再同一空间上进行计算,能够减少资源的开销。<br>2、char[] 与 String之间的变化,String有个toCharArray()变成char数组,所以没必要每次都用s.charAt(index)来读取char<br>3、新学到StringBuilder类<br>4、数组长度length,字符串长度length()<br>5、改为循环,仍然没有利用StringBuilder,发现时间开销依旧很大,改为Stringbuilder之后瞬间提升,原因是什么呢?<br>这是因为String的长度大小是不可变的,当我们进行拼接的时候重新创建了一个新的String类型数据,所以不断的循环导致不断的开销。而StringBuilder的长度是可变的,所以一直在同一个内存空间操作,速度大大提升。如下图所示</li>
</ol>
<p>String 长度大小不可变<br>StringBuffer 和 StringBuilder 长度可变<br>StringBuffer 线程安全 StringBuilder 线程不安全<br>StringBuilder 速度快</p>
<ol start="35">
<li><p>Search Insert Position<br>easy binary search</p>
</li>
<li><p>Remove Duplicates from Sorted Array<br>easy index increase to go through. duplicates is invalid and can be overwrited</p>
</li>
</ol>
<ol start="27">
<li>Remove Element<br>same way as 26 but no need to check index == len - 1. just record the number of deleted elements.</li>
</ol>
<ol start="29">
<li>Divide Two Integers (Medium)<br>采用brute方法直接exceed time limit,很难受。看看别人怎么做的吧<br>1、擦,被秒杀。。。这个bit 操作真的很骚。。。而且我记得之前也有一道题目涉及到了bit操作。<br>2、其实对divisor进行自加加然后对其结果再次自加,也有移位的效果。<br>所以其实就是耍了一个trick,说不能用乘除和mod,就利用移位达到快速定位的效果,这个其实也相当于 go through和二分的区别。 </li>
</ol>
<ol start="13">
<li>Roman to Integer<br>右有大,负加。<br>右无大(碰边界),正加。<br>思路完全正确,之前居然没有想到。<br>但是发现了新的问题:<br>Java中 Hashmap性能上似乎不如switch语句,原因暂时不知道,只看到了几个关键词:JVM, tableswitch, Lookupswitch, HashMap自己的构造函数中默认构造大小。</li>
</ol>
<ol start="14">
<li>Longest Common Prefix<br>其实是一道没有太大意思的题目,思路清晰,仅仅锻炼一下自己码代码的细节的问题:<br>1、charAt是函数,用的()括号而不是 []<br>2、char[][] 是不存在的。只有char[]<br>3、一定要注意自己的for循环里面,是否将 i 写成了常数</li>
</ol>
<h1 id="2018-4-21"><a href="#2018-4-21" class="headerlink" title="2018-4-21"></a>2018-4-21</h1><ol start="4">
<li>Median of Two Sorted Arrays()<br>要求是log(m+n)<br>重点是弄懂median的作用,其作用是分割成两个部分,左边最大小于右边最小。且左右大小相等。所以基于这个亮点对其中一个进行binarysearch,然后另外一个因为要保持大小相同,所以也在同时binarysearch,达到log的效果。<br>尽管如此,原理还是没有完全弄透彻。Hard果然是Hard。。。<br>需要反复复习。</li>
</ol>
<ol start="53">
<li><p>Maximum Subarray<br>直接遍历整个数组,从第一个大于0开始,sum进行累加,<br>if sum >= 0 i++,maxsum = Math.max( maxsum, sum),<br>else sum < 0, i++, sum = 0; maxsum = Math.max ( maxsum, sum);<br>O(n) 时间复杂度。<br>说可以用分治的方法 divide and conquer, 开始学习怎么做。<br>如果按照我刚刚从大于0的开始,要出问题。因为可能全为负值,导致出错。<br>思路还是正确的,看完讨论发现大家都是O(n)的时间复杂度。<br>我的思路上是遍历,但是用到了分治的思想,但是自己没有看出来。<br>分:i 遍历,寻找前 i 个sum最大的。<br>治:根据第 i - 1 个情况,若小于0,清零计算,大于0,不作改动。然后加nums[i],然后与前一时刻最大值比较。其实这里sum 相当于状态,maxsum就是历史。</p>
</li>
<li><p>Length of Last Word</p>
</li>
<li><p>Plus One</p>
</li>
</ol>
<ol start="69">
<li><p>Sqrt(x)<br>耍了一个trick,直接从Integer.MAX_VALUE的平方根开始算。</p>
</li>
<li><p>Climbing Stairs</p>
</li>
<li><p>Remove Duplicates from Sorted List<br>easy,但是实现过程中还是有小问题:<br>1、没有判断是否相同直接跳到下一个节点导致:【1,1,1,1,1】处理完变成了【1,1,1】。因为第二个处理完之后跳到了第三个,处理完第四个跳到第五个。。。。</p>
</li>
<li><p>Merge Sorted Array<br>虽然不可以从最小的开始,但我们可以从最大的开始啊。</p>
</li>
</ol>
<ol start="67">
<li><p>Add Binary<br>StringBuilder 可以append不同类型的,不一定要char型。而且可以不同类型组合。</p>
</li>
<li><p>Maximum Depth of Binary Tree</p>
</li>
<li><p>Same Tree</p>
</li>
</ol>
<ol start="136">
<li><p>Single Number<br>这个还是简单的,毕竟两个相同的数字进行异或即可。</p>
</li>
<li><p>Single Number II<br>这个就很难受了,弄了一个晚上。感受到了自己的菜鸡。<br>利用状态转移,设置不同状态表示接收到了不同的bit个数,因为某一个,数字的固定位置比特肯定是只出现一次的。<br>所以只要弄一个只有固定比特为1的状态,其余以方便优先选择。</p>
</li>
<li><p>Single Number III<br>位运算,求反,本来和原来的数完全相对,相与变成0,但是加1之后,能够找到最右不同的比特,也可以说从低到高第一个不同的bit<br>解释如下:</p>
<figure class="highlight plain"><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"> s1 a1 b1 c1</span><br><span class="line"> s2 a2 b2 c2</span><br><span class="line">^ —————</span><br><span class="line"></span><br><span class="line"> s a b c</span><br><span class="line">// NOT s_ a_ b_ c_</span><br><span class="line"></span><br><span class="line"> —————</span><br></pre></td></tr></table></figure>
</li>
</ol>
<p>①c = 1,说明c1 c2 不同<br>②c = 0,说明c1,c2相同,则c_ = 1,<br>③+1之后,将进位,也就等同于+1到b,继续①②两步<br> after find the rightest bit, then we diff & -diff, we can make the bits lower than the rightest bit to zero, the rightest will be ‘1’ and those bits higher than the rightest will be ‘0’ because of ~ operation</p>
<ol start="12">
<li>Integer to Roman<br>easy</li>
</ol>
<ol start="273">
<li>Integer to English Words<br>easy</li>
</ol>
<ol start="6">
<li><p>ZigZag Conversion<br>找规律题目</p>
</li>
<li><p>Generate Parentheses<br>backtracking题目,但是属于easy的范围,仍然没有完全弄懂backtracking的原理,明天可以找backtracking题目进行熟悉。</p>
</li>
</ol>
<ol start="125">
<li>Valid Palindrome<br>easy,没有太刁难。首尾移动判断即可。</li>
</ol>
<ol start="680">
<li><p>Valid Palindrome II<br>多了一个简单的判断。</p>
</li>
<li><p>Path Sum<br>思路还是很清晰的,但是在代码实现过程仍然要注意几个问题:<br>1、参数可以是null,但是不能对null进行操作,所以在对参数进行操作时要注意是否为null,尤其当对多个参数进行判断的时候。因为自己总是仅判断一个情况,那就是全为null的情况。</p>
</li>
</ol>
<ol start="101">
<li>Symmetric Tree<br>这里居然出现了一个低级错误——对节点本身进行判断,而不是其中的值。。。</li>
</ol>
<h1 id="2018-4-29"><a href="#2018-4-29" class="headerlink" title="2018-4-29"></a>2018-4-29</h1><ol start="141">
<li>Linked List Cycle<br>可以利用head作为标志,全部指向head,如果有一个节点已经指向了head说明了有loop,但是这样会破坏原来的数据结构。若要copy古来又无法满足without using extra space<br>2、brilliant,利用walker和runner,一个走一步一个走两步,如果loop肯定能相遇,如果到了末端没相遇则没有!</li>
</ol>
<ol start="784">
<li>Letter Case Permutation<br>backtrack 练习题,慢慢摸到了一点点门路。<br>现在对其理解就是<br>建立一个helper用于递归调用:</li>
</ol>
<figure class="highlight plain"><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">helper(...){</span><br><span class="line"> if ( i < len ){</span><br><span class="line"> if(isValid) </span><br><span class="line"> go left;</span><br><span class="line"> some operations;</span><br><span class="line"> go right;</span><br><span class="line"> else back to i-1(return )</span><br><span class="line"> }</span><br><span class="line"> else{</span><br><span class="line"> store;</span><br><span class="line"> return;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<ol start="142">
<li>Linked List Cycle II</li>
</ol>
<p>很遗憾,自己的方法还是不如别人的方法。</p>
<p>l1 = the distance from head to the node where cycle begins<br>l2 = the distance from the node where cycle begins to the node where walker and runner meet<br>l3 = the distance from the node where walker and runner meet to the node where cycle begins.<br>when first meet, we have<br>l1+l2 = (l1+l2+l3+l2) / 2, because the time used is the same<br>so l1 = l3.</p>
<ol start="46">
<li>Permutations<br>也算是知道了自己的错误了。思路没有错误,但是数据处理上出现了问题,因为lastres是重复使用的,当我add的时候一直加的同一个地址,所以最后在remove掉的时候把lastres所对应的空间数据全部remove掉导致没有任何数据了。</li>
</ol>
<ol start="17">
<li><p>Letter Combinations of a Phone Number</p>
</li>
<li><p>Permutations II<br>感觉很有代表性的一道题目,做出了这个题目之后其他的duplicate几乎有迎刃而解了。</p>
</li>
<li><p>Subsets</p>
</li>
<li><p>Combinations</p>
</li>
<li><p>Combination Sum</p>
</li>
</ol>
<ol start="40">
<li><p>Combination Sum II</p>
</li>