8000 Added tasks 21-39 · jscrdev/LeetCode-in-Racket@ca47413 · GitHub
[go: up one dir, main page]
Skip to content

Commit ca47413

Browse files
ThanhNITThanhNIT
authored
Added tasks 21-39
1 parent 1644dc7 commit ca47413

File tree

21 files changed

+645
-0
lines changed

21 files changed

+645
-0
lines changed

‎README.md

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

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

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
; #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Linked_List #Recursion
2+
; #Data_Structure_I_Day_7_Linked_List #Algorithm_I_Day_10_Recursion_Backtracking
3+
; #Level_1_Day_3_Linked_List #Udemy_Linked_List #Top_Interview_150_Linked_List
4+
; #Big_O_Time_O(m+n)_Space_O(m+n) #2025_02_03_Time_0_(100.00%)_Space_102.38_(66.67%)
5+
6+
; Definition for singly-linked list:
7+
#|
8+
9+
; val : integer?
10+
; next : (or/c list-node? #f)
11+
(struct list-node
12+
(val next) #:mutable #:transparent)
13+
14+
; constructor
15+
(define (make-list-node [val 0])
16+
(list-node val #f))
17+
18+
|#
19+
20+
(define/contract (merge-two-lists list1 list2)
21+
(-> (or/c list-node? #f) (or/c list-node? #f) (or/c list-node? #f))
22+
(cond
23+
[(not list1) list2]
24+
[(not list2) list1]
25+
[(< (list-node-val list1) (list-node-val list2)) (list-node (list-node-val list1) (merge-two-lists (list-node-next list1) list2))]
26+
[else (list-node (list-node-val list2) (merge-two-lists (list-node-next list2) list1))]
27+
)
28+
)

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

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
21\. Merge Two Sorted Lists
2+
3+
Easy
4+
5+
Merge two sorted linked lists and return it as a **sorted** list. The list should be made by splicing together the nodes of the first two lists.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg)
10+
11+
**Input:** l1 = [1,2,4], l2 = [1,3,4]
12+
13+
**Output:** [1,1,2,3,4,4]
14+
15+
**Example 2:**
16+
17+
**Input:** l1 = [], l2 = []
18+
19+
**Output:** []
20+
21+
**Example 3:**
22+
23+
**Input:** l1 = [], l2 = [0]
24+
25+
**Output:** [0]
26+
27+
**Constraints:**
28+
29+
* The number of nodes in both lists is in the range `[0, 50]`.
30+
* `-100 <= Node.val <= 100`
31+
* Both `l1` and `l2` are sorted in **non-decreasing** order.

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

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
; #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Dynamic_Programming
2+
; #Backtracking #Algorithm_II_Day_11_Recursion_Backtracking #Udemy_Backtracking/Recursion
3+
; #Top_Interview_150_Backtracking #Big_O_Time_O(2^n)_Space_O(n)
4+
; #2025_02_03_Time_3_(100.00%)_Space_101.96_(100.00%)
5+
6+
(define (generate-parenthesis n)
7+
(let ([res '()])
8+
(let loop ([opening 0] [closing 0] [path ""])
9+
(cond ((and (= opening n) (= closing n))
10+
(set! res (cons path res)))
11+
(else
12+
(when (< opening n)
13+
(loop (add1 opening) closing (string-append path "(")))
14+
(when (< closing opening)
15+
(loop opening (add1 closing) (string-append path ")")))))
16+
res)))

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

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
22\. Generate Parentheses
2+
3+
Medium
4+
5+
Given `n` pairs of parentheses, write a function to _generate all combinations of well-formed parentheses_.
6+
7+
**Example 1:**
8+
9+
**Input:** n = 3
10+
11+
**Output:** ["((()))","(()())","(())()","()(())","()()()"]
12+
13+
**Example 2:**
14+
15+
**Input:** n = 1
16+
17+
**Output:** ["()"]
18+
19+
**Constraints:**
20+
21+
* `1 <= n <= 8`

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
; #Hard #Top_100_Liked_Questions #Top_Interview_Questions #Heap_Priority_Queue #Linked_List
2+
; #Divide_and_Conquer #Merge_Sort #Top_Interview_150_Divide_and_Conquer
3+
; #Big_O_Time_O(k*n*log(k))_Space_O(log(k)) #2025_02_03_Time_306_(100.00%)_Space_130.68_(100.00%)
4+
5+
; Definition for singly-linked list:
6+
#|
7+
8+
; val : integer?
9+
; next : (or/c list-node? #f)
10+
(struct list-node
11+
(val next) #:mutable #:transparent)
12+
13+
; constructor
14+
(define (make-list-node [val 0])
15+
(list-node val #f))
16+
17+
|#
18+
19+
(define/contract (merge-k-lists lists)
20+
(-> (listof (or/c list-node? #f)) (or/c list-node? #f))
21+
(define (merge-two-lists l1 l2)
22+
(cond
23+
[(not l1) l2]
24+
[(not l2) l1]
25+
[(< (list-node-val l1) (list-node-val l2))
26+
(set-list-node-next! l1 (merge-two-lists (list-node-next l1) l2))
27+
l1]
28+
[else
29+
(set-list-node-next! l2 (merge-two-lists l1 (list-node-next l2)))
30+
l2]))
31+
32+
(define (merge lists)
33+
(cond
34+
[(empty? lists) #f]
35+
[(= (length lists) 1) (car lists)]
36+
[else
37+
(merge-two-lists (car lists) (merge (cdr lists)))]))
38+
39+
(merge lists)
40+
)

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

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
23\. Merge k Sorted Lists
2+
3+
Hard
4+
5+
You are given an array of `k` linked-lists `lists`, each linked-list is sorted in ascending order.
6+
7+
_Merge all the linked-lists into one sorted linked-list and return it._
8+
9+
**Example 1:**
10+
11+
**Input:** lists = [[1,4,5],[1,3,4],[2,6]]
12+
13+
**Output:** [1,1,2,3,4,4,5,6]
14+
15+
**Explanation:** The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6
16+
17+
**Example 2:**
18+
19+
**Input:** lists = []
20+
21+
**Output:** []
22+
23+
**Example 3:**
24+
25+
**Input:** lists = [[]]
26+
27+
**Output:** []
28+
29+
**Constraints:**
30+
31+
* `k == lists.length`
32+
* `0 <= k <= 10^4`
33+
* `0 <= lists[i].length <= 500`
34+
* `-10^4 <= lists[i][j] <= 10^4`
35+
* `lists[i]` is sorted in **ascending order**.
36+
* The sum of `lists[i].length` won't exceed `10^4`.

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

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
; #Medium #Top_100_Liked_Questions #Linked_List #Recursion #Data_Structure_II_Day_12_Linked_List
2+
; #Udemy_Linked_List #Big_O_Time_O(n)_Space_O(1)
3+
; #2025_02_03_Time_0_(100.00%)_Space_101.59_(100.00%)
4+
5+
; Definition for singly-linked list:
6+
#|
7+
8+
; val : integer?
9+
; next : (or/c list-node? #f)
10+
(struct list-node
11+
(val next) #:mutable #:transparent)
12+
13+
; constructor
14+
(define (make-list-node [val 0])
15+
(list-node val #f))
16+
17+
|#
18+
19+
(define (swap-pairs head)
20+
(let ([dummy (list-node 0 head)])
21+
(begin
22+
(set-list-node-next! dummy head)
23+
(let loop ([cur head]
24+
[prev dummy])
25+
(cond
26+
[(or (eq? cur #f) (eq? (list-node-next cur) #f)) #f]
27+
[else (begin
28+
(set-list-node-next! prev (list-node-next cur))
29+
(set-list-node-next! cur (list-node-next (list-node-next cur)))
30+
(set-list-node-next! (list-node-next prev) cur)
31+
32+
(loop (list-node-next cur) cur))]))
33+
(list-node-next dummy))))

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

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
24\. Swap Nodes in Pairs
2+
3+
Medium
4+
5+
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2020/10/03/swap_ex1.jpg)
10+
11+
**Input:** head = [1,2,3,4]
12+
13+
**Output:** [2,1,4,3]
14+
15+
**Example 2:**
16+
17+
**Input:** head = []
18+
19+
**Output:** []
20+
21+
**Example 3:**
22+
23+
**Input:** head = [1]
24+
25+
**Output:** [1]
26+
27+
**Constraints:**
28+
29+
* The number of nodes in the list is in the range `[0, 100]`.
30+
* `0 <= Node.val <= 100`

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

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
; #Hard #Top_100_Liked_Questions #Linked_List #Recursion #Data_Structure_II_Day_13_Linked_List
2+
; #Udemy_Linked_List #Top_Interview_150_Linked_List #Big_O_Time_O(n)_Space_O(k)
3+
; #2025_02_03_Time_0_(100.00%)_Space_101.65_(100.00%)
4+
5+
; Definition for singly-linked list:
6+
#|
7+
8+
; val : integer?
9+
; next : (or/c list-node? #f)
10+
(struct list-node
11+
(val next) #:mutable #:transparent)
12+
13+
; constructor
14+
(define (make-list-node [val 0])
15+
(list-node val #f))
16+
17+
|#
18+
19+
(define (reverse-k l k next)
20+
(if (or (= 0 k) (not l)) next
21+
(let ([n (list-node-next l)])
22+
(set-list-node-next! l next)
23+
(reverse-k n (- k 1) l))))
24+
25+
(define (reverse-group-k h c k i)
26+
(cond [(= i k) (reverse-k h k (reverse-group-k c c k 0))]
27+
[(not c) h]
28+
[else (reverse-group-k h (list-node-next c) k (+ 1 i))]))
29+
30+
(define (reverse-k-group head k) (reverse-group-k head head k 0))

0 commit comments

Comments
 (0)
0