8000 Added tasks 41-62 · jscrdev/LeetCode-in-Racket@0afdabc · GitHub
[go: up one dir, main page]
Skip to content

Commit 0afdabc

Browse files
ThanhNITThanhNIT
authored
Added tasks 41-62
1 parent ca47413 commit 0afdabc

File tree

21 files changed

+619
-0
lines changed

21 files changed

+619
-0
lines changed

‎README.md

Lines changed: 40 additions & 0 deletions
Large diffs are not rendered by default.

‎src/main/racket/g0001_0100/s0041_first_missing_positive/Solution.rkt

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
; #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Udemy_Arrays
2+
; #Big_O_Time_O(n)_Space_O(n) #2025_02_03_Time_11_(100.00%)_Space_132.67_(100.00%)
3+
4+
(define/contract (first-missing-positive nums)
5+
(-> (listof exact-integer?) exact-integer?)
6+
(let* ((len (length nums))
7+
(vec (list->vector nums)))
8+
(define (swap i j)
9+
(let ((temp (vector-ref vec i)))
10+
(vector-set! vec i (vector-ref vec j))
11+
(vector-set! vec j temp)))
12+
(for ([i (in-range len)])
13+
(let loop ()
14+
(let* ((num (vector-ref vec i))
15+
(pos (- num 1)))
16+
(when (and (> num 0) (<= num len) (not (= (vector-ref vec pos) num)))
17+
(swap i pos)
18+
(loop)))))
19+
(let find-missing ((i 0))
20+
(cond
21+
((= i len) (+ len 1))
22+
((not (= (vector-ref vec i) (+ i 1))) (+ i 1))
23+
(else (find-missing (+ i 1)))))))

‎src/main/racket/g0001_0100/s0041_first_missing_positive/readme.md

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
41\. First Missing Positive
2+
3+
Hard
4+
5+
Given an unsorted integer array `nums`, return the smallest missing positive integer.
6+
7+
You must implement an algorithm that runs in `O(n)` time and uses constant extra space.
8+
9+
**Example 1:**
10+
11+
**Input:** nums = [1,2,0]
12+
13+
**Output:** 3
14+
15+
**Explanation:** The numbers in the range [1,2] are all in the array.
16+
17+
**Example 2:**
18+
19+
**Input:** nums = [3,4,-1,1]
20+
21+
**Output:** 2
22+
23+
**Explanation:** 1 is in the array but 2 is missing.
24+
25+
**Example 3:**
26+
27+
**Input:** nums = [7,8,9,11,12]
28+
29+
**Output:** 1
30+
31+
**Explanation:** The smallest positive integer 1 is missing.
32+
33+
**Constraints:**
34+
35+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
36+
* <code>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1</code>

‎src/main/racket/g0001_0100/s0042_trapping_rain_water/Solution.rkt

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
; #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming #Two_Pointers
2+
; #Stack #Monotonic_Stack #Dynamic_Programming_I_Day_9 #Udemy_Two_Pointers
3+
; #Top_Interview_150_Array/String #Big_O_Time_O(n)_Space_O(1)
4+
; #2025_02_03_Time_0_(100.00%)_Space_129.13_(100.00%)
5+
6+
(define (trap height)
7+
(define H (list->vector height))
8+
9+
(define (go water left right L R)
10+
(cond [(>= left right) water]
11+
[else
12+
(cond [(<= L R) (go (+ water
13+
(max (- (min L R)
14+
(vector-ref H (add1 left)))
15+
0))
16+
(add1 left)
17+
right
18+
(max L (vector-ref H (add1 left)))
19+
R)]
20+
[else (go (+ water
21+
(max (- (min L R)
22+
(vector-ref H (sub1 right)))
23+
0))
24+
left
25+
(sub1 right)
26+
L
27+
(max R (vector-ref H (sub1 right))))])]))
28+
(go 0
29+
0
30+
(sub1 (length height))
31+
(vector-ref H 0)
32+
(vector-ref H (sub1 (length height)))))

‎src/main/racket/g0001_0100/s0042_trapping_rain_water/readme.md

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
42\. Trapping Rain Water
2+
3+
Hard
4+
5+
Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png)
10+
11+
**Input:** height = [0,1,0,2,1,0,1,3,2,1,2,1]
12+
13+
**Output:** 6
14+
15+
**Explanation:** The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.
16+
17+
**Example 2:**
18+
19+
**Input:** height = [4,2,0,3,2,5]
20+
21+
**Output:** 9
22+
23+
**Constraints:**
24+
25+
* `n == height.length`
26+
* <code>1 <= n <= 2 * 10<sup>4</sup></code>
27+
* <code>0 <= height[i] <= 10<sup>5</sup></code>

‎src/main/racket/g0001_0100/s0045_jump_game_ii/Solution.rkt

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
; #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Greedy
2+
; #Algorithm_II_Day_13_Dynamic_Programming #Dynamic_Programming_I_Day_4
3+
; #Top_Interview_150_Array/String #Big_O_Time_O(n)_Space_O(1)
4+
; #2025_02_03_Time_631_(100.00%)_Space_132.16_(100.00%)
5+
6+
(define (init-vec len)
7+
(let ([prepare-vec (make-vector len 99999)])
8+
(begin (vector-set! prepare-vec 0 0) prepare-vec)))
9+
10+
(define (set-cost! vec p elem)
11+
(if (= elem 0) vec
12+
(let* ([p-cost (vector-ref vec p)]
13+
[now-cost (add1 p-cost)]
14+
[target-cost (vector-ref vec (+ p elem))])
15+
(begin (vector-set! vec (+ p elem) (min now-cost target-cost))
16+
(set-cost! vec p (- elem 1))))))
17+
18+
(define (simple-dp cache p steps)
19+
(if (= 0 (length steps)) (vector-ref cache (- p 1))
20+
(simple-dp (set-cost! cache p (car steps)) (add1 p) (cdr steps))))
21+
22+
(define (start-dp steps) (simple-dp (init-vec 200000) 0 steps))
23+
24+
(define/contract (jump nums)
25+
(-> (listof exact-integer?) exact-integer?)
26+
(start-dp nums))

‎src/main/racket/g0001_0100/s0045_jump_game_ii/readme.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
45\. Jump Game II
2+
3+
Medium
4+
5+
Given an array of non-negative integers `nums`, you are initially positioned at the first index of the array.
6+
7+
Each element in the array represents your maximum jump length at that position.
8+
9+
Your goal is to reach the last index in the minimum number of jumps.
10+
11+
You can assume that you can always reach the last index.
12+
13+
**Example 1:**
14+
15+
**Input:** nums = [2,3,1,1,4]
16+
17+
**Output:** 2
18+
19+
**Explanation:** The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
20+
21+
**Example 2:**
22+
23+
**Input:** nums = [2,3,0,1,4]
24+
25+
**Output:** 2
26+
27+
**Constraints:**
28+
29+
* <code>1 <= nums.length <= 10<sup>4</sup></code>
30+
* `0 <= nums[i] <= 1000`

‎src/main/racket/g0001_0100/s0046_permutations/Solution.rkt

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
; #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Backtracking
2+
; #Algorithm_I_Day_11_Recursion_Backtracking #Level_2_Day_20_Brute_Force/Backtracking
3+
; #Udemy_Backtracking/Recursion #Top_Interview_150_Backtracking #Big_O_Time_O(n*n!)_Space_O(n+n!)
4+
; #2025_02_03_Time_0_(100.00%)_Space_101.43_(66.67%)
5+
6+
(define/contract (permute nums)
7+
(-> (listof exact-integer?) (listof (listof exact-integer?)))
8+
(cond [(empty? nums) (list empty)]
9+
[else (for/fold ([l empty])([i nums])
10+
(append (map (lambda (lst) (cons i lst)) (permute (remove i nums))) l)
11+
)
12+
]))

‎src/main/racket/g0001_0100/s0046_permutations/readme.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
46\. Permutations
2+
3+
Medium
4+
5+
Given an array `nums` of distinct integers, return _all the possible permutations_. You can return the answer in **any order**.
6+
7+
**Example 1:**
8+
9+
**Input:** nums = [1,2,3]
10+
11+
**Output:** [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
12+
13+
**Example 2:**
14+
15+
**Input:** nums = [0,1]
16+
17+
**Output:** [[0,1],[1,0]]
18+
19+
**Example 3:**
20+
21+
**Input:** nums = [1]
22+
23+
**Output:** [[1]]
24+
25+
**Constraints:**
26+
27+
* `1 <= nums.length <= 6`
28+
* `-10 <= nums[i] <= 10`
29+
* All the integers of `nums` are **unique**.

‎src/main/racket/g0001_0100/s0049_group_anagrams/Solution.rkt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
; #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #String #Hash_Table #Sorting
2+
; #Data_Structure_II_Day_8_String #Programming_Skills_II_Day_11 #Udemy_Strings
3+
; #Top_Interview_150_Hashmap #Big_O_Time_O(n*k_log_k)_Space_O(n)
4+
; #2025_02_03_Time_72_(100.00%)_Space_131.77_(100.00%)
5+
6+
(define (group-anagrams strs)
7+
(group-by (compose1 (curryr sort char<?) string->list) strs))

‎src/main/racket/g0001_0100/s0049_group_anagrams/readme.md

Lines cha 10000 nged: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
49\. Group Anagrams
2+
3+
Medium
4+
5+
Given an array of strings `strs`, group **the anagrams** together. You can return the answer in **any order**.
6+
7+
An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
8+
9+
**Example 1:**
10+
11+
**Input:** strs = ["eat","tea","tan","ate","nat","bat"]
12+
13+
**Output:** [["bat"],["nat","tan"],["ate","eat","tea"]]
14+
15+
**Example 2:**
16+
17+
**Input:** strs = [""]
18+
19+
**Output:** [[""]]
20+
21+
**Example 3:**
22+
23+
**Input:** strs = ["a"]
24+
25+
**Output:** [["a"]]
26+
27+
**Constraints:**
28+
29+
* <code>1 <= strs.length <= 10<sup>4</sup></code>
30+
* `0 <= strs[i].length <= 100`
31+
* `strs[i]` consists of lowercase English letters.

‎src/main/racket/g0001_0100/s0051_n_queens/Solution.rkt

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
; #Hard #Top_100_Liked_Questions #Array #Backtracking #Big_O_Time_O(N!)_Space_O(N)
2+
; #2025_02_03_Time_123_(100.00%)_Space_129.70_(100.00%)
3+
4+
(define (reverse sequence)
5+
(foldr (lambda (x y) (append y (list x))) `() sequence))
6+
7+
(define (accumulate op initial sequence)
8+
(if (null? sequence)
9+
initial
10+
(op (car sequence)
11+
(accumulate op initial (cdr sequence)))))
12+
13+
(define (enumerate-interval low high)
14+
(if (> low high)
15+
`()
16+
(cons low (enumerate-interval (+ low 1) high))))
17+
18+
(define (flatmap proc seq)
19+
(accumulate append `() (map proc seq)))
20+
21+
(define (queens board-size)
22+
(define (queen-cols k)
23+
(if (= k 0)
24+
(list empty-board)
25+
(filter
26+
(lambda (positions) (safe? k positions))
27+
(flatmap
28+
(lambda (rest-of-queens)
29+
(map (lambda (new-row)
30+
(adjoin-position new-row k rest-of-queens))
31+
(enumerate-interval 1 board-size)))
32+
(queen-cols (- k 1))))))
33+
(queen-cols board-size))
34+
35+
(define (adjoin-position new-row k rest-of-queens)
36+
(append rest-of-queens (list (cons new-row k))))
37+
38+
(define empty-board `())
39+
40+
(define (all proc items)
41+
(define (iter items)
42+
(cond ((null? items) #t)
43+
((proc (car items)) (iter (cdr items)))
44+
(else #f)))
45+
(iter items))
46+
47+
; None in row, and none in either diagonal
48+
(define (safe? k positions)
49+
(define (safe-combo? a b)
50+
(not (or (= (car a) (car b))
51+
(= (abs (- (car a) (car b)))
52+
(abs (- (cdr a) (cdr b)))))))
53+
(all (lambda (p) (safe-combo? (car (reverse positions)) p)) (cdr (reverse positions))))
54+
55+
; board building to bridge solution to LC format
56+
(define (cdr-by-car lst)
57+
(map cdr (sort lst >= #:key car)))
58+
59+
(define (solution-to-board n soln)
60+
(map (lambda (row) (make-row row n)) (cdr-by-car soln)))
61+
62+
(define (make-row k n)
63+
(string-join (list (k-dots (- k 1)) "Q" (k-dots (- n k))) ""))
64+
65+
(define (k-dots k)
66+
(string-join (make-list k ".") ""))
67+
68+
(define/contract (solve-n-queens n)
69+
(-> exact-integer? (listof (listof string?)))
70+
(map (lambda (soln) (solution-to-board n soln)) (queens n))
71+
)

‎src/main/racket/g0001_0100/s0051_n_queens/readme.md

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
51\. N-Queens
2+
3+
Hard
4+
5+
The **n-queens** puzzle is the problem of placing `n` queens on an `n x n` chessboard such that no two queens attack each other.
6+
7+
Given an integer `n`, return _all distinct solutions to the **n-queens puzzle**_. You may return the answer in **any order**.
8+
9+
Each solution contains a distinct board configuration of the n-queens' placement, where `'Q'` and `'.'` both indicate a queen and an empty space, respectively.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2020/11/13/queens.jpg)
14+
15+
**Input:** n = 4
16+
17+
**Output:** [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
18+
19+
**Explanation:** There exist two distinct solutions to the 4-queens puzzle as shown above
20+
21+
**Example 2:**
22+
23+
**Input:** n = 1
24+
25+
**Output:** [["Q"]]
26+
27+
**Constraints:**
28+
29+
* `1 <= n <= 9`

‎src/main/racket/g0001_0100/s0053_maximum_subarray/Solution.rkt

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
; #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming
2+
; #Divide_and_Conquer #Data_Structure_I_Day_1_Array #Dynamic_Programming_I_Day_5
3+
; #Udemy_Famous_Algorithm #Top_Interview_150_Kadane's_Algorithm #Big_O_Time_O(n)_Space_O(1)
4+
; #2025_02_03_Time_51_(100.00%)_Space_140.95_(100.00%)
5+
6+
(define/contract (recur nums)
7+
(-> (listof exact-integer?) pair?)
8+
(if (empty? nums) (cons 0 -1000000)
9+
(let* ([i (first nums)]
10+
[res (recur (cdr nums))]
11+
[currBest (car res)]
12+
[bestSofar (cdr res)]
13+
[currNew (max i (+ currBest i))]
14+
)
15+
(cons currNew (max bestSofar currNew)))))
16+
17+
(define/contract (max-sub-array nums)
18+
(-> (listof exact-integer?) exact-integer?)
19+
(cdr (recur nums)))

0 commit comments

Comments
 (0)
0