-
Notifications
You must be signed in to change notification settings - Fork 0
/
old-leetcode.org
10408 lines (8772 loc) · 327 KB
/
old-leetcode.org
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
#+FILETAG: :learning:note:
#+LATEX_HEADER: \usepackage{amsmath}
#+SETUPFILE: ../theme-readtheorg.setup
#+EXPORT_FILE_NAME: ../../yatsky.github.io/leetcode.html
#+HTML_LINK_HOME: ../website/index.html
* Programming practice
** LeetCode :leetcode:
#+BEGIN: clocktable :scope subtree :maxlevel 2
#+CAPTION: Clock summary at [2020-04-16 Thu 07:38]
| Headline | Time | |
|--------------+------------+----------|
| *Total time* | *2d 13:16* | |
|--------------+------------+----------|
| \_ LeetCode | | 2d 13:16 |
#+END:
DEADLINE: <2019-12-31 Tue>
[[https://leetcode.com/progress/][My progress]]
*** Plan
:PROPERTIES:
:Effort: 1:00
:END:
:LOGBOOK:
CLOCK: [2019-09-09 Mon 09:18]--[2019-09-09 Mon 09:45] => 0:27
:END:
**** Good resources :resource:
1. [[https://leetcode.com/discuss/career/216554/from-0-to-clearing-uberappleamazonlinkedingoogle][From 0 to clearing]]
2. [[https://www.reddit.com/r/cscareerquestions/comments/6luszf/a_leetcode_grinding_guide/][A leetcode grinding guide]]
*** TODO Execution
SCHEDULED: <2019-11-06 Wed 15:00 +1d>
:PROPERTIES:
:LAST_REPEAT: [2020-04-23 Thu 07:53]
:END:
- State "DONE" from "TODO" [2020-04-23 Thu 07:53]
- State "DONE" from "TODO" [2020-04-23 Thu 07:53]
- State "DONE" from "TODO" [2020-04-23 Thu 07:53]
- State "DONE" from "TODO" [2020-04-23 Thu 07:52]
- State "DONE" from "TODO" [2020-04-23 Thu 07:52]
- State "DONE" from "TODO" [2020-04-23 Thu 07:52]
- State "DONE" from "TODO" [2020-04-17 Fri 09:51]
- State "DONE" from "TODO" [2020-04-17 Fri 09:51]
- State "DONE" from "TODO" [2020-04-16 Thu 14:27]
- State "DONE" from "TODO" [2020-04-16 Thu 08:09]
- State "DONE" from "TODO" [2020-04-14 Tue 22:16]
- State "DONE" from "TODO" [2020-04-14 Tue 12:26]
- State "DONE" from "TODO" [2020-04-13 Mon 21:22]
- State "DONE" from "TODO" [2020-04-13 Mon 14:51]
- State "DONE" from "TODO" [2020-04-09 Thu 14:56]
- State "DONE" from "TODO" [2020-04-09 Thu 14:04]
- State "DONE" from "TODO" [2020-04-09 Thu 10:21]
- State "DONE" from "TODO" [2020-02-01 Sat 11:32]
- State "DONE" from "TODO" [2020-01-27 Mon 11:33]
- State "DONE" from "TODO" [2019-10-18 Fri 11:18]
- State "DONE" from "TODO" [2019-10-17 Thu 16:53]
- State "DONE" from "TODO" [2019-10-17 Thu 15:00]
- State "DONE" from "TODO" [2019-10-16 Wed 21:57]
- State "DONE" from "TODO" [2019-10-16 Wed 14:46]
- State "DONE" from "TODO" [2019-10-14 Mon 21:19]
- State "DONE" from "TODO" [2019-10-14 Mon 16:19]
- State "DONE" from "TODO" [2019-10-14 Mon 14:04]
- State "DONE" from "TODO" [2019-10-10 Thu 21:17]
- State "DONE" from "TODO" [2019-10-09 Wed 21:57]
- State "DONE" from "TODO" [2019-10-08 Tue 20:59]
- State "DONE" from "TODO" [2019-10-07 Mon 21:05]
- State "DONE" from "TODO" [2019-10-05 Sat 11:21]
- State "DONE" from "TODO" [2019-10-04 Fri 21:46]
- State "DONE" from "TODO" [2019-10-03 Thu 19:42]
- State "DONE" from "TODO" [2019-10-03 Thu 09:27]
- State "DONE" from "TODO" [2019-10-02 Wed 21:18]
- State "DONE" from "TODO" [2019-10-02 Wed 20:02]
- State "DONE" from "TODO" [2019-10-02 Wed 19:28]
- State "DONE" from "TODO" [2019-09-30 Mon 19:59]
- State "DONE" from "TODO" [2019-09-28 Sat 14:31]
- State "DONE" from "TODO" [2019-09-28 Sat 13:43]
- State "DONE" from "TODO" [2019-09-27 Fri 20:15]
- State "DONE" from "TODO" [2019-09-27 Fri 15:26]
- State "DONE" from "TODO" [2019-09-26 Thu 18:02]
- State "DONE" from "TODO" [2019-09-26 Thu 15:47]
- State "DONE" from "TODO" [2019-09-26 Thu 14:21]
- State "DONE" from "TODO" [2019-09-24 Tue 20:39]
- State "DONE" from "TODO" [2019-09-23 Mon 20:08]
- State "DONE" from "TODO" [2019-09-20 Fri 09:13]
- State "DONE" from "TODO" [2019-09-20 Fri 09:13]
- State "DONE" from "TODO" [2019-09-16 Mon 21:58]
- State "DONE" from "TODO" [2019-09-16 Mon 21:58]
- State "DONE" from "TODO" [2019-09-15 Sun 19:52]
- State "DONE" from "TODO" [2019-09-13 Fri 20:54]
- State "DONE" from "TODO" [2019-09-12 Thu 21:37]
- State "DONE" from "TODO" [2019-09-11 Wed 20:34]
- State "DONE" from "TODO" [2019-09-10 Tue 19:09]
- State "DONE" from "TODO" [2019-09-09 Mon 19:08]
:LOGBOOK:
CLOCK: [2019-09-14 Sat 11:48]--[2019-09-14 Sat 12:02] => 0:14
CLOCK: [2019-09-14 Sat 08:49]--[2019-09-14 Sat 10:27] => 1:38
CLOCK: [2019-09-14 Sat 08:44]--[2019-09-14 Sat 08:49] => 0:05
CLOCK: [2019-09-13 Fri 19:47]--[2019-09-13 Fri 20:54] => 1:07
CLOCK: [2019-09-13 Fri 19:00]--[2019-09-13 Fri 19:47] => 0:47
CLOCK: [2019-09-12 Thu 16:26]--[2019-09-12 Thu 17:41] => 1:15
CLOCK: [2019-09-11 Wed 20:13]--[2019-09-11 Wed 20:23] => 0:10
CLOCK: [2019-09-10 Tue 16:16]--[2019-09-10 Tue 16:39] => 0:23
CLOCK: [2019-09-10 Tue 15:34]--[2019-09-10 Tue 16:16] => 0:42
CLOCK: [2019-09-09 Mon 19:34]--[2019-09-09 Mon 20:03] => 0:29
CLOCK: [2019-09-09 Mon 09:54]--[2019-09-09 Mon 09:54] => 0:00
:END:
Two questions a day should be enough. Don't spend over 30 minutes on one question.
Should be ordered by Difficulty, Acceptance rate(high to low), with Solution.
| question type | easy | medium | hard |
|---------------------------+-------+--------+-------|
| total number of questions | ~ 200 | ~ 350 | ~ 150 |
|---------------------------+-------+--------+-------|
| <2019-09-09 Mon> | 2 | 0 | 0 |
| <2019-09-10 Tue> | 2 | 0 | 0 |
| <2019-09-11 Wed> | 2 | 0 | 0 |
| <2019-09-12 Thu> | 2 | 0 | 0 |
| <2019-09-13 Fri> | 2 | 0 | 0 |
| <2019-09-14 Sat> | 6 | 0 | 0 |
| <2019-09-15 Sun> | 2 | 0 | 0 |
| <2019-09-16 Mon> | 2 | 0 | 0 |
| <2019-09-17 Tue> | 2 | 0 | 0 |
| | | | |
*** Question list
:LOGBOOK:
CLOCK: [2020-04-09 Thu 08:51]--[2020-04-09 Thu 09:01] => 0:10
:END:
| Done | # | Title | Acceptance | Difficulty |
|------+------+---------------------------------------------------+------------+------------|
| 1 | 762 | Prime Number of Set Bits in Binary Representation | 62.10% | Easy |
| 1 | 771 | Jewels and Stones | 84.80% | Easy |
| 1 | 938 | Range Sum of BST | 79.70% | Easy |
| 1 | 804 | Unique Morse Code Words | 76.20% | Easy |
| 1 | 832 | Flipping an Image | 75.00% | Easy |
| 1 | 905 | Sort Array By Parity | 73.80% | Easy |
| 1 | 728 | Self Dividing Numbers | 73.30% | Easy |
| 1 | 961 | N-Repeated Element in Size 2N Array | 73.20% | Easy |
| 1 | 617 | Merge Two Binary Trees | 73.10% | Easy |
| 1 | 657 | Robot Return to Origin | 73.00% | Easy |
| 1 | 977 | Squares of a Sorted Array | 72.30% | Easy |
| 1 | 942 | DI String Match | 71.40% | Easy |
| 1 | 461 | Hamming Distance | 71.30% | Easy |
| 1 | 561 | Array Partition I | 71.20% | Easy |
| 1 | 852 | Peak Index in a Mountain Array | 71.00% | Easy |
| 1 | 933 | Number of Recent Calls | 70.80% | Easy |
| 1 | 590 | N-ary Tree Postorder Traversal | 70.80% | Easy |
| 1 | 589 | N-ary Tree Preorder Traversal | 70.80% | Easy |
| 1 | 700 | Search in a Binary Search Tree | 70.70% | Easy |
| 1 | 944 | Delete Columns to Make Sorted | 70.00% | Easy |
| 1 | 811 | Subdomain Visit Count | 68.40% | Easy |
| 1 | 876 | Middle of the Linked List | 68.40% | Easy |
| 1 | 922 | Sort Array By Parity II | 68.20% | Easy |
| 1 | 557 | Reverse Words in a String III | 68.20% | Easy |
| 1 | 897 | Increasing Order Search Tree | 68.00% | Easy |
| 1 | 559 | Maximum Depth of N-ary Tree | 67.70% | Easy |
| 1 | 929 | Unique Email Addresses | 67.60% | Easy |
| 1 | 965 | Univalued Binary Tree | 67.30% | Easy |
| 1 | 883 | Projection Area of 3D Shapes | 67.10% | Easy |
| 1 | 509 | Fibonacci Number | 67.00% | Easy |
| 1 | 1047 | Remove All Adjacent Duplicates In String | 66.90% | Easy |
| 1 | 821 | Shortest Distance to a Character | 66.00% | Easy |
| 1 | 908 | Smallest Range I | 65.30% | Easy |
| 1 | 893 | Groups of Special-Equivalent Strings | 65.30% | Easy |
| 1 | 872 | Leaf-Similar Trees | 64.80% | Easy |
| 1 | 136 | Single Number | 64.70% | Easy |
| 1 | 104 | Maximum Depth of Binary Tree | 64.50% | Easy |
| 1 | 806 | Number of Lines To Write String | 64.20% | Easy |
| 1 | 766 | Toeplitz Matrix | 63.90% | Easy |
| 1 | 867 | Transpose Matrix | 63.20% | Easy |
| 1 | 682 | Baseball Game | 62.80% | Easy |
| 1 | 496 | Next Greater Element I | 62.60% | Easy |
| 1 | 784 | Letter Case Permutation | 62.30% | Easy |
| 1 | 226 | Invert Binary Tree | 62.20% | Easy |
| 1 | 884 | Uncommon Words from Two Sentences | 62.20% | Easy |
| 1 | 669 | Trim a Binary Search Tree | 62.10% | Easy |
| 1 | 985 | Sum of Even Numbers After Queries | 61.90% | Easy |
| 1 | 824 | Goat Latin | 61.90% | Easy |
| 1 | 637 | Average of Levels in Binary Tree | 61.70% | Easy |
| 1 | 412 | Fizz Buzz | 61.50% | Easy |
| 1 | 575 | Distribute Candies | 61.00% | Easy |
| 1 | 206 | Reverse Linked List | 60.40% | Easy |
| 1 | 1103 | Distribute Candies to People | 60.30% | Easy |
| 1 | 868 | Binary Gap | 60.20% | Easy |
| 1 | 349 | Intersection of Two Arrays | 60.20% | Easy |
| 1 | 566 | Reshape the Matrix | 60.00% | Easy |
| 1 | 237 | Delete Node in a Linked List | 59.00% | Easy |
| 1 | 693 | Binary Number with Alternating Bits | 59.00% | Easy |
| 1 | 1089 | Duplicate Zeros | 58.80% | Easy |
| 1 | 892 | Surface Area of 3D Shapes | 58.20% | Easy |
| 1 | 812 | Largest Triangle Area | 57.60% | Easy |
| 1 | 917 | Reverse Only Letters | 57.40% | Easy |
| 1 | 888 | Fair Candy Swap | 57.40% | Easy |
| 1 | 976 | Largest Perimeter Triangle | 57.30% | Easy |
| 1 | 283 | Move Zeroes | 57.20% | Easy |
| 1 | 521 | Longest Uncommon Subsequence I | 57.20% | Easy |
| 1 | 896 | Monotonic Array | 56.90% | Easy |
| 1 | 1137 | N-th Tribonacci Number | 56.70% | Easy |
| 1 | 788 | Rotated Digits | 56.70% | Easy |
| 1 | 169 | Majority Element | 56.30% | Easy |
| 1 | 485 | Max Consecutive Ones | 56.20% | Easy |
| 1 | 690 | Employee Importance | 56.10% | Easy |
| 1 | 748 | Shortest Completing Word | 56.10% | Easy |
| 1 | 292 | Nim Game | 56.10% | Easy |
| 1 | 108 | Convert Sorted Array to Binary Search Tree | 55.80% | Easy |
| 1 | 1029 | Two City Scheduling | 55.80% | Easy |
| 1 | 242 | Valid Anagram | 55.60% | Easy |
| 1 | 122 | Best Time to Buy and Sell Stock II | 55.60% | Easy |
| 1 | 448 | Find All Numbers Disappeared in an Array | 55.40% | Easy |
| 1 | 696 | Count Binary Substrings | 55.20% | Easy |
| 1 | 217 | Contains Duplicate | 55.20% | Easy |
| 1 | 953 | Verifying an Alien Dictionary | 54.90% | Easy |
| 1 | 653 | Two Sum IV - Input is a BST | 54.50% | Easy |
| 1 | 538 | Convert BST to Greater Tree | 54.00% | Easy |
| 1 | 937 | Reorder Data in Log Files | 53.60% | Easy |
| 1 | 733 | Flood Fill | 53.30% | Easy |
| 1 | 606 | Construct String from Binary Tree | 53.30% | Easy |
| 1 | 697 | Degree of an Array | 53.20% | Easy |
| 1 | 167 | Two Sum II - Input array is sorted | 52.90% | Easy |
| 1 | 1 | Two Sum | 45.20% | Easy |
| 1 | 7 | Reverse Integer | 25.60% | Easy |
| 1 | 1342 | Number of Steps to Reduce a Number to Zero | 86.20% | Easy |
| 1 | 709 | To Lower Case | 78.70% | Easy |
| 0 | 339 | Nested List Weight Sum | 72.20% | Easy |
| 0 | 346 | Moving Average from Data Stream | 69.40% | Easy |
| 0 | 359 | Logger Rate Limiter | 69.10% | Easy |
| 0 | 1394 | Find Lucky Integer in an Array | 68.90% | Easy |
| 0 | 1337 | The K Weakest Rows in a Matrix | 68.60% | Easy |
| 0 | 344 | Reverse String | 66.10% | Easy |
| 0 | 476 | Number Complement | 63.40% | Easy |
| 0 | 751 | IP to CIDR | 62.00% | Easy |
| 0 | 266 | Palindrome Permutation | 61.30% | Easy |
| 0 | 800 | Similar RGB Color | 61.30% | Easy |
| 0 | 1260 | Shift 2D Grid | 61.10% | Easy |
| 0 | 243 | Shortest Word Distance | 60.20% | Easy |
| 0 | 706 | Design HashMap | 59.60% | Easy |
| 0 | 1009 | Complement of Base 10 Integer | 59.40% | Easy |
| 0 | 705 | Design HashSet | 59.00% | Easy |
| 0 | 1332 | Remove Palindromic Subsequences | 57.40% | Easy |
| 0 | 13 | Roman to Integer | 54.80% | Easy |
| 0 | 389 | Find the Difference | 54.50% | Easy |
| 0 | 252 | Meeting Rooms | 53.90% | Easy |
| 0 | 993 | Cousins in Binary Tree | 52.30% | Easy |
| 0 | 100 | Same Tree | 52.00% | Easy |
| 0 | 21 | Merge Two Sorted Lists | 51.90% | Easy |
| 0 | 783 | Minimum Distance Between BST Nodes | 51.80% | Easy |
| 0 | 387 | First Unique Character in a String | 51.70% | Easy |
| 0 | 383 | Ransom Note | 51.70% | Easy |
| 0 | 256 | Paint House | 51.40% | Easy |
| 0 | 860 | Lemonade Change | 51.10% | Easy |
| 0 | 704 | Binary Search | 50.80% | Easy |
| 0 | 661 | Image Smoother | 50.70% | Easy |
| 0 | 118 | Pascal's Triangle | 50.70% | Easy |
| 0 | 268 | Missing Number | 50.60% | Easy |
| 0 | 350 | Intersection of Two Arrays II | 50.60% | Easy |
| 0 | 202 | Happy Number | 50.10% | Easy |
| 0 | 599 | Minimum Index Sum of Two Lists | 50.10% | Easy |
| 0 | 997 | Find the Town Judge | 50.00% | Easy |
| 0 | 453 | Minimum Moves to Equal Array Elements | 49.80% | Easy |
| 0 | 409 | Longest Palindrome | 49.80% | Easy |
| 0 | 121 | Best Time to Buy and Sell Stock | 49.70% | Easy |
| 0 | 257 | Binary Tree Paths | 49.60% | Easy |
| 0 | 796 | Rotate String | 49.50% | Easy |
| 0 | 598 | Range Addition II | 49.30% | Easy |
| 0 | 746 | Min Cost Climbing Stairs | 49.30% | Easy |
| 0 | 717 | 1-bit and 2-bit Characters | 49.00% | Easy |
| 0 | 830 | Positions of Large Groups | 48.90% | Easy |
| 0 | 836 | Rectangle Overlap | 48.70% | Easy |
| 0 | 235 | Lowest Common Ancestor of a Binary Search Tree | 48.50% | Easy |
| 0 | 543 | Diameter of Binary Tree | 48.40% | Easy |
| 0 | 563 | Binary Tree Tilt | 47.80% | Easy |
| 0 | 232 | Implement Queue using Stacks | 47.70% | Easy |
| 0 | 541 | Reverse String II | 47.60% | Easy |
| 0 | 191 | Number of 1 Bits | 47.60% | Easy |
| 0 | 119 | Pascal's Triangle II | 47.50% | Easy |
| 0 | 720 | Longest Word in Dictionary | 47.40% | Easy |
| 0 | 844 | Backspace String Compare | 47.30% | Easy |
| 0 | 27 | Remove Element | 47.20% | Easy |
| 0 | 9 | Palindrome Number | 47.10% | Easy |
| 0 | 994 | Rotting Oranges | 47.10% | Easy |
| 0 | 628 | Maximum Product of Three Numbers | 46.90% | Easy |
| 0 | 551 | Student Attendance Record I | 46.70% | Easy |
| 0 | 270 | Closest Binary Search Tree Value | 46.50% | Easy |
| 0 | 70 | Climbing Stairs | 46.40% | Easy |
| 0 | 53 | Maximum Subarray | 45.90% | Easy |
| 0 | 101 | Symmetric Tree | 45.90% | Easy |
| 0 | 594 | Longest Harmonious Subsequence | 45.70% | Easy |
| 0 | 674 | Longest Continuous Increasing Subsequence | 45.40% | Easy |
| 0 | 925 | Long Pressed Name | 45.10% | Easy |
| 0 | 744 | Find Smallest Letter Greater Than Target | 45.00% | Easy |
| 0 | 758 | Bold Words in String | 44.60% | Easy |
| 0 | 83 | Remove Duplicates from Sorted List | 44.60% | Easy |
| 0 | 989 | Add to Array-Form of Integer | 44.10% | Easy |
| 0 | 819 | Most Common Word | 43.90% | Easy |
| 0 | 572 | Subtree of Another Tree | 43.80% | Easy |
| 0 | 26 | Remove Duplicates from Sorted Array | 43.80% | Easy |
| 0 | 38 | Count and Say | 43.50% | Easy |
| 0 | 225 | Implement Stack using Queues | 43.30% | Easy |
| 0 | 724 | Find Pivot Index | 43.10% | Easy |
| 0 | 671 | Second Minimum Node In a Binary Tree | 42.90% | Easy |
| 0 | 231 | Power of Two | 42.90% | Easy |
| 0 | 67 | Add Binary | 42.80% | Easy |
| 0 | 110 | Balanced Binary Tree | 42.70% | Easy |
| 0 | 303 | Range Sum Query - Immutable | 42.50% | Easy |
| 0 | 849 | Maximize Distance to Closest Person | 42.30% | Easy |
| 0 | 716 | Max Stack | 42.10% | Easy |
| 0 | 66 | Plus One | 42.00% | Easy |
| 0 | 326 | Power of Three | 42.00% | Easy |
| 0 | 374 | Guess Number Higher or Lower | 41.80% | Easy |
| 0 | 734 | Sentence Similarity | 41.80% | Easy |
| 0 | 198 | House Robber | 41.70% | Easy |
| 0 | 645 | Set Mismatch | 41.60% | Easy |
| 0 | 35 | Search Insert Position | 41.50% | Easy |
| 0 | 155 | Min Stack | 41.50% | Easy |
| 0 | 747 | Largest Number At Least Twice of Others | 41.30% | Easy |
| 0 | 342 | Power of Four | 41.20% | Easy |
| 0 | 643 | Maximum Average Subarray I | 41.00% | Easy |
| 0 | 367 | Valid Perfect Square | 41.00% | Easy |
| 0 | 112 | Path Sum | 40.20% | Easy |
| 0 | 443 | String Compression | 40.10% | Easy |
| 0 | 141 | Linked List Cycle | 40.00% | Easy |
| 0 | 970 | Powerful Integers | 39.70% | Easy |
| 0 | 441 | Arranging Coins | 39.50% | Easy |
| 0 | 624 | Maximum Distance in Arrays | 38.60% | Easy |
| 0 | 160 | Intersection of Two Linked Lists | 38.50% | Easy |
| 0 | 88 | Merge Sorted Array | 38.40% | Easy |
| 0 | 234 | Palindrome Linked List | 38.30% | Easy |
| 0 | 20 | Valid Parentheses | 38.30% | Easy |
| 0 | 172 | Factorial Trailing Zeroes | 37.70% | Easy |
| 0 | 434 | Number of Segments in a String | 37.50% | Easy |
| 0 | 203 | Remove Linked List Elements | 37.30% | Easy |
| 0 | 219 | Contains Duplicate II | 37.00% | Easy |
| 0 | 111 | Minimum Depth of Binary Tree | 36.80% | Easy |
| 0 | 840 | Magic Squares In Grid | 36.70% | Easy |
| 0 | 604 | Design Compressed String Iterator | 36.60% | Easy |
| 0 | 949 | Largest Time for Given Digits | 36.10% | Easy |
| 0 | 680 | Valid Palindrome II | 35.90% | Easy |
| 0 | 190 | Reverse Bits | 35.60% | Easy |
| 0 | 941 | Valid Mountain Array | 35.50% | Easy |
| 0 | 687 | Longest Univalue Path | 35.40% | Easy |
| 0 | 507 | Perfect Number | 35.30% | Easy |
| 0 | 14 | Longest Common Prefix | 34.80% | Easy |
| 0 | 125 | Valid Palindrome | 34.60% | Easy |
| 0 | 874 | Walking Robot Simulation | 34.40% | Easy |
| 0 | 914 | X of a Kind in a Deck of Cards | 34.00% | Easy |
| 0 | 28 | Implement strStr() | 33.90% | Easy |
| 0 | 278 | First Bad Version | 33.50% | Easy |
| 0 | 189 | Rotate Array | 33.40% | Easy |
| 0 | 69 | Sqrt(x) | 33.10% | Easy |
| 0 | 170 | Two Sum III - Data structure design | 32.90% | Easy |
| 0 | 633 | Sum of Square Numbers | 32.40% | Easy |
| 0 | 686 | Repeated String Match | 32.10% | Easy |
| 0 | 605 | Can Place Flowers | 31.60% | Easy |
| 0 | 581 | Shortest Unsorted Continuous Subarray | 30.80% | Easy |
| 0 | 414 | Third Maximum Number | 30.10% | Easy |
| 0 | 859 | Buddy Strings | 27.60% | Easy |
| 0 | 665 | Non-decreasing Array | 19.40% | Easy |
|------+------+---------------------------------------------------+------------+------------|
| 93 | 227 | 0.39912281 | 0 | 0 |
#+TBLFM: @229$1=vsum(@I..II)::@229$2=vlen(@I..@II)::@229$3=@230$1 / @229$2
*** Review
:PROPERTIES:
:LAST_REPEAT: [2019-09-20 Fri 09:13]
:END:
- State "DONE" from "TODO" [2019-09-20 Fri 09:13]
- State "DONE" from "TODO" [2019-09-20 Fri 09:13]
- State "DONE" from "TODO" [2019-09-16 Mon 21:58]
- State "DONE" from "TODO" [2019-09-16 Mon 21:58]
- State "DONE" from "TODO" [2019-09-16 Mon 21:58]
- State "DONE" from "TODO" [2019-09-16 Mon 21:58]
- State "DONE" from "TODO" [2019-09-13 Fri 22:15]
- State "DONE" from "TODO" [2019-09-11 Wed 20:34]
- State "DONE" from "TODO" [2019-09-10 Tue 19:09]
- State "DONE" from "TODO" [2019-09-09 Mon 20:08]
:LOGBOOK:
CLOCK: [2019-09-09 Mon 20:03]--[2019-09-09 Mon 20:05] => 0:02
CLOCK: [2019-09-09 Mon 09:54]--[2019-09-09 Mon 09:54] => 0:00
:END:
Review individual questions.
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| date | question number | review |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| <2019-09-09 Mon 19:43> | 771. Jewels and stones | Use brute force - python3 or use ~sum([S.count(j) for j in J])~ |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| <2019-09-09 Mon 20:02> | 938. Range sum of BST | Use recursive algorithm (I knew) - also need to know that you *can define |
| | | a function inside another* |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| <2019-09-10 Tue 16:00> | 804. Unique Morse Code Word | Hash code of two lists containing same elements can be different, hence |
| | |the ~''.join~ |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| <2019-09-10 Tue 16:38> | 832. Flipping an Image | Use ~map(func, iterable)~ function would be a great idea |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| <2019-09-11 Wed 20:31> | 905. Sort array by parity | list.insert() always moves current element at the position to the right, |
| | |even when the index is -1 |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| <2019-09-11 Wed 20:33> | 961. N-repeated elemnts in size 2N array | The target element is the one that appears twice |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| <2019-09-11 Wed 21:39> | 977. squares of a sorted array | Can use binary insertion or two pointer algorithm |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| | | |
+------------------------+------------------------------------------+---------------------------------------------------------------------------+
| date | quesiton number | review |
| <2019-09-16 Mon 21:39> | 509 | There are 6 ways to do this! |
| <2019-09-16 Mon> | | |
| | | |
*** Solutions [108/108]
#+BEGIN: clocktable :scope subtree :maxlevel 1
#+CAPTION: Clock summary at [2020-04-16 Thu 08:10]
| Headline | Time |
|--------------+-----------|
| *Total time* | *2d 1:36* |
|--------------+-----------|
#+END:
227 Questions in total
**** DONE 771 Jewels and stones
- ~J~ represents jewels
- characters in ~J~ are distinctive
- ~S~ represents stones
- letters are case-sensitive
- calculate the number of stones that are jewels
**** DONE 938 Range Sum of BST
- given the *root* node of a binary search tree
- return the sum of values of all nodes with value between ~L~ and ~R~ (inclusive)
- the BST is guaranteed to have unique values
- The number of nodes in the tree is at most 10000
- the final answer is guaranteed to be less than 2^31
**** DONE 804 Unique Morse Code words
- letter is mapped to a series of dots and dashes
-
#+name: unique_morse_code_words
#+begin_src python
def uniqueMorseRepresentations(words):
map_list=[".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
store = []
for w in words:
# 0-based index
new_morse = "".join([map_list[ord(c) - 97] for c in w])
if new_morse not in store:
store.append(new_morse)
return len(store)
return uniqueMorseRepresentations(['gin', 'zen', 'gig', 'msg'])
#+end_src
#+RESULTS: unique_morse_code_words
: 2
**** DONE 832 Flipping an Image
- given a matrix ~A~
- flip it horizontally, i.e. [1, 1, 0] to [0, 1, 1]
- invert it, i.e. change 1 to 0 and 0 to 1
#+name: flipping_an_image
#+begin_src python
def flip_and_invert_image(A):
new_image = []
for i in A:
rev_i = i[::-1]
inv_i = [1-p for p in rev_i]
new_image.append(inv_i)
return new_image
return flip_and_invert_image([[1,1,0],[1,0,1],[0,0,0]])
#+end_src
#+name: flipping_image_example_code
#+begin_src python
def flip_and_invert_image(A):
result = []
for row in A:
result.append(list(map(lambda x: 0 if x==1 else 1, row[::-1])))
return result
return flip_and_invert_image([[1,1,0],[1,0,1],[0,0,0]])
#+end_src
#+RESULTS: flipping_image_example_code
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
#+RESULTS: flipping_an_image
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
**** DONE 905 Sort array by parity
- given an array ~A~ of non-negative integers
- return an array consisting of all the even elements of ~A~, followed by all the odd elements of A
#+name: sort_array_by_parity
#+begin_src python
def sort_array_by_parity(A):
sorted_list = []
for e in A:
if e % 2 == 0:
sorted_list.insert(0, e)
else:
# insert() wouldn't work because it shifts 0 at index -1 to the right.
# sorted_list.insert(-1, e)
sorted_list.append(e)
return sorted_list
return sort_array_by_parity([0,1])
#+end_src
#+RESULTS: sort_array_by_parity
| 0 | 1 |
**** DONE 961 N-Repeated elements in size 2N array
- ~N+1~ unique elements in an array ~A~ of size ~2N~
- exactly one of these elements is repeated ~N~ times
- return the element that repeated ~N~ times
#+name: n_repeated_elements_in_size_2N_array
#+begin_src python
def repeated_n_times(A):
store = []
for e in A:
if e in store:
return e
else:
store.append(e)
#+end_src
**** DONE 657 Robot return to origin
- robot starts at position (0, 0), the origin
- given the sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves
- the move sequence is represented by a string
- valid moves are R(ight), L(eft), U(p), D(own)
- if the robot returns to origin after the moves, return true, else, return false
- where the robot faces is irrelevant
#+begin_src python
def robot_returned(moves):
MOVE_MAP = {'U':1, 'D': -1, 'R':1, 'L':-1}
x_coord = 0
y_coord = 0
for m in moves:
if m in 'UD':
y_coord += MOVE_MAP[m]
else:
x_coord += MOVE_MAP[m]
if x_coord == 0 and y_coord == 0:
return True
return False
#+end_src
**** DONE 977 Squares of a sorted array
- given an array of integers ~A~ in non-decreasing order
- return an array of the squares of each number, also in sorted non-decreasing order
My instinct tells me to use a type of Insertion Sort. But it actually can use Binary Search???
#+name: quick solution
#+begin_src python
def sorted_squares(A):
return sorted(x*x for x in A)
#+end_src
#+name: my_solution
#+begin_src python
def sorted_squares(A):
sorted_tobe_inserted = []
# sanity check
if A[0] >= 0:
return [x**2 for x in A]
if A[-1] <= 0:
return [x**2 for x in A[::-1]]
# mixed negatives and positives
result_list = A.copy()
def find_positive_and_insert(A, sorted_tobe_inserted):
for idx, x in enumerate(A):
if x < 0:
sorted_tobe_inserted.insert(0, -1 * x)
else:
return idx
def binary_insert(elem, target, left, right):
# base case, if L == R
# right == left + 1 is also an edge case
if left == right or (right == left + 1):
if elem <= target[left]:
target.insert(left, elem)
else:
target.insert(left+1, elem)
return
else:
m = (left+right)//2
if elem <= target[m]:
binary_insert(elem, target, left, m)
else:
binary_insert(elem, target, m, right)
idx = find_positive_and_insert(A, sorted_tobe_inserted)
target = A[idx::]
for elem in sorted_tobe_inserted:
binary_insert(elem, target, 0, len(target))
return [x**2 for x in target]
return sorted_squares([-4, -1, 3, 10])
#+end_src
#+name: my_solution_improved
#+begin_src python
def sorted_squares(A):
sorted_tobe_inserted = []
# sanity check
if A[0] >= 0:
return [x**2 for x in A]
if A[-1] <= 0:
return [x**2 for x in A[::-1]]
# mixed negatives and positives
result_list = A.copy()
def find_positive_and_insert(A, sorted_tobe_inserted):
for idx, x in enumerate(A):
if x < 0:
sorted_tobe_inserted.insert(0, -1 * x)
else:
return idx
def binary_insert(elem, target, left, right):
# base case, if L == R
if left == right or (right == left + 1):
if elem <= target[left]:
target.insert(left, elem)
else:
target.insert(left+1, elem)
return
else:
m = (left+right)//2
if elem <= target[m]:
binary_insert(elem, target, left, m)
else:
binary_insert(elem, target, m + 1, right)
idx = find_positive_and_insert(A, sorted_tobe_inserted)
target = A[idx::]
for elem in sorted_tobe_inserted:
binary_insert(elem, target, 0, len(target))
return [x**2 for x in target]
return sorted_squares([-4, -1, 3, 10])
#+end_src
#+name: two_pointers
#+begin_src python
def sorted_squares(A):
N = len(A)
# i, j: negative, positive parts
j = 0
# find all negatives
while j < N and A[j] < 0:
j += 1
i = j - 1
ans = []
# loop until negatives or positives run out
while 0 <= i and j < N:
if A[i]**2 < A[j]**2:
ans.append(A[i]**2)
i -= 1
else:
ans.append(A[j]**2)
j += 1
# deal with anything that's still out there
while i >= 0:
ans.append(A[i]**2)
i -= 1
while j < N:
ans.append(A[j]**2)
j += 1
return ans
return sorted_squares([-3, -2, 2, 3, 4])
#+end_src
#+RESULTS: two_pointers
| 4 | 4 | 9 | 9 | 16 |
#+RESULTS: my_solution_improved
| 1 | 9 | 16 | 100 |
#+RESULTS:
| 1 | 9 | 16 | 100 |
**** DONE 728 Self dividing numbers
- a self-dividing number(sdn) is a number that is divisible by every digit it contains
- 128 % 1 == 0, 128 % 2 == 0, 128 % 8 == 0
- sdn does not have the digit zero
- given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible
#+name: my_sdn
#+begin_src python
def self_dividing_number(left, right):
def is_dividing_number(num):
# converting the num to str so we can check if it contains zero
test = str(num)
if '0' in test:
return False
else:
for digit in test:
if num % int(digit) != 0:
return False
return True
ans = []
# the solution must have a loop through the list [left, right + 1]
for num in range(left, right + 1):
if is_dividing_number(num):
ans.append(num)
return ans
#+end_src
**** DONE 617 Merging two binary trees
- given two binary trees and put one of them to cover the other
- some nodes of the two trees are overlapped while the others are not
- merge them into a new binary tree
- if two nodes overlap, then sum node values up as the new value of the merged node
- otherwise, the NOT null node will be used as the node of the new tree
#+name: merge_two_binary_trees
#+begin_src python
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def merge_binary_trees(t1, t2):
def reaches_leaf(node: TreeNode):
return node.left == None and node.right == None
# dfs merge
def merge_binary_trees_recursive(ans_node, node1, node2):
# base case
ans_node.val = node1.val + node2.val
ans_node.left = TreeNode(0)
ans_node.right = TreeNode(0)
if reaches_leaf(node1) and reaches_leaf(node2):
ans_node.left = None
ans_node.right = None
return
elif node1.left == None and node2.left == None:
ans_node.left = None
elif node1.right == None and node2.right == None:
ans_node.right = None
if ans_node.left != None:
node1.left = TreeNode(0) if node1.left == None else node1.left
node2.left = TreeNode(0) if node2.left == None else node2.left
merge_binary_trees_recursive(ans_node.left, node1.left, node2.left)
if ans_node.right != None:
node1.right = TreeNode(0) if node1.right == None else node1.right
node2.right = TreeNode(0) if node2.right == None else node2.right
merge_binary_trees_recursive(ans_node.right, node1.right, node2.right)
else:
return
# this defensive programming is not beautiful but required to pass the test
if t1 == None:
return t2
if t2 == None:
return t1
ans_node = TreeNode(0)
merge_binary_trees_recursive(ans_node, t1, t2)
return ans_node
t1 = TreeNode(1)
t1.left = TreeNode(3)
t1.right = TreeNode(2)
t1.left.left = TreeNode(5)
t2 = TreeNode(2)
t2.left = TreeNode(1)
t2.left.right = TreeNode(4)
t2.right = TreeNode(3)
t2.right.right = TreeNode(7)
return merge_binary_trees(t1, t2)
#+end_src
#+name: merge_two_binary_trees_solution
#+begin_src python
# this method does not care if t1 or t2 is None
def merge_trees(t1, t2):
if t1 is None:
return t2
if t2 is None:
return t1
t1.val += t2.val
t1.left = merge_trees(t1.left, t2.left)
t1.right = merge_trees(t1.right, t2.right)
return t1
#+end_src
#+RESULTS: merge_two_binary_trees
: <__main__.main.<locals>.TreeNode object at 0x000001C04C99C438>
**** DONE 852 Peak index in a mountain array
***** Gathering information
an array ~A~ is a *mountian* if
- ~A.length >= 3~
- there exists some ~0 < i < A.length - 1 such that ~A[0] < ... A[i-1] < A[i] > A[i+1] >...>A[A.length - 1]~
given an array that is definitely a mountain, return any ~i~.
***** Tackling process
Because ~A~ is *definitely a mountain*, then for some ~i~ that matches the definition, ~A[0:i+1] # python list~ is strictly in increasing order. Our goal is to find the ~i~ such that ~A[i+1] < A[i]~
#+name: peak_index_in_mountain_arr
#+begin_src python
def peak_index_in_mountain_arr(A: List[int]) -> int:
for i, num in enumerate(A):
if i == len(A) - 1:
return i
else:
if A[i+1] < num:
return i
#+end_src
**** DONE 561 Array partition I
***** Gathering information
- given an array of *2n* integers
- group these integers into *n* pairs of integers
- such that (a1, b1)...(an, bn) make the *sum of min(ai, bi)* for all i from 1 to n as large as possible
***** Tackling process
It can be proven that if the elements of the array is ordered, then grouping them two at a time sequentially will provide the largest sum of min(ai, bi).
If we want the smallest sum of min(ai, bi), we can pair the ordered list from both sides.
#+name: array_partitioin_1
#+begin_src python
def array_partition_1(A):
sorted_a = sorted(A)
sum = 0
for i in range(0, len(A), 2):
sum += min(sorted_a[i], sorted_a[i+1])
return sum
#+end_src
#+name: one_line_solution
#+begin_src python
def array_partition_1(nums);
return sum(sorted(nums)[::2])
#+end_src
**** DONE 942 DI string match
***** Gathering information
- given a string ~S~ that *only* contains "I" (increase) or "D" (descrease)
- let ~N = S.length~
- return *any* permutation ~A~ of ~[0, 1, ..., N]~ such that for all ~i = 0, ..., N-1~
- ~A[i] < A[i+1] if S[i] == "I"~
- ~A[i] > A[i+1] if S[i] == "D"~
***** Tackling process
We can find that ~A~ [0, 1, ...N] is in order, and if we let "D" = -1, "I" = 1, and assume that we start from 0, then we can have
a *function f(x) = sum(x0, x1, ..., xi) where xi = 1 if S[i] == "I" else xi = -1 and i in [0, N]*.
First we get the f(x) for every i, then we assign numbers from ~A~ to each f(x) in decsending order.
For example
| | D | I | D | I |
| 0 | -1 | 0 | -1 | 0 |
| 4 | 1 | 3 | 0 | 2 |
| | | | | |
#+name: di_string_match
#+begin_src python
def di_string_match(S:str):
DI_MAP = {"D": -1, "I": 1}
nums = list(range(len(S) + 1))
di_sum = 0
di_nums = [(di_sum, 0)]
for i, c in enumerate(S):
di_sum += DI_MAP[c]
di_nums.append((di_sum, i + 1))
di_nums_sorted = sorted(di_nums, key=lambda x: x[0])
ans = [None] * len(nums)
for i, pos in enumerate([idx[1] for idx in di_nums_sorted]):
ans[pos] = nums[i]
return ans
return di_string_match("DDI")
#+end_src
#+RESULTS: di_string_match
| 3 | 1 | 0 | 2 |
**** DONE 944 Delete columns to make sorted
***** Gathering information
- given an array ~A~ of ~N~ lowercase letter strings, all of the same length
- choose any set of deletion indices, and for each string, we delete all the characters in those indices
- suppose we choose a set of deletion indices ~D~ such that after deletion, each remaining column in ~A~ is in *non-decreasing* sorted order
- return the minimum possible value of ~D.length~
For example
#+name: original
| c | d | g |
| b | a | h |
| a | f | i |
We choose ~D=[1]~
#+name: after_deletion
| c | d | g |
| a | f | i |
***** Tackling process
#+name: delete_columns_to_make_sorted
#+begin_src python
def delete_cols_to_sort(A):
def is_sorted(col):
if col == sorted(col):
return True
return False
d_len = 0
if len(A) == 0:
return d_len
else:
for i, c in enumerate(A[0]):
if not is_sorted([letters[i] for letters in A]):
d_len += 1
return d_len
return delete_cols_to_sort(["cba", "daf", "ghi"])
#+end_src
#+name: original_solution
#+begin_src python
def min_deletion_size(A):
ans = 0
for col in zip(*A):
if any(col[i] > col[i+1] for i in xrange(len(col) -1)):
ans += 1
return ans
#+end_src
#+RESULTS: delete_columns_to_make_sorted
: 1
**** DONE 933 Number of recent calls
:LOGBOOK:
CLOCK: [2019-09-14 Sat 13:36]--[2019-09-14 Sat 14:12] => 0:36
:END:
***** Gathering information
- write a class ~RecentCounter~ to count recent requests
- it has only one method, ~ping(int t)~, where t represents some time in milliseconds
- return the number of ~ping~s that have been made from 3000 milliseconds ago, [t -3000, t], until now
- it is guaranteed that every call to ~ping~ uses a strictly larger value of t than before
***** Tackling process
#+name: recen_counter
#+begin_src python
# This works but takes too much time that it hangs
class RecentCounter:
def __init__(self):
self.calls = []
def ping(self, t):
self.calls.append(t)
count = 0
new_list = []
for i in range(len(self.calls) - 1, -1, -1):
if t - self.calls[i] <= 3000:
count += 1
new_list.insert(0, self.calls[i])
else:
break
self.calls = new_list
return count
#+end_src
#+name: recen_counter_mysolution_improved
#+begin_src python
class RecentCounter:
def __init__(self):
self.calls = []
def ping(self, t):
self.calls.append(t)
while self.calls[0] < t - 3000:
self.calls.pop(0)
return len(self.calls)
#+end_src
#+name: solution
#+begin_src python
# This is faster
import collections
class RecentCounter:
def __init__(self):
self.calls = collections.deque()
def ping(self, t):
self.calls.append(t)
while self.calls[0] < t - 3000:
self.calls.popleft()
return len(self.calls)
#+end_src
#+RESULTS: recen_counter
: 1
**** DONE 700 Search in Binary Search Tree
:LOGBOOK:
CLOCK: [2019-09-14 Sat 14:18]--[2019-09-14 Sat 14:34] => 0:16
:END:
***** Gathering information
- given the root node of a BST and a value
- find the node in the BST that the node's value equals the given value
- return the subtree rooted with the node
- if the such node does not exist, return NULL
***** Tackling process
DFS search
#+name: searchBST
#+begin_src python
def searchBST(root, val):
# base case
if root is None or root.val == val:
return root
else:
return searchBST(root.left, val) if val > root.val else searchBST(root.right, val)