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

Commit a6b880a

Browse files
ThanhNITThanhNIT
authored
Added tasks 207-300
1 parent c923d2d commit a6b880a

File tree

21 files changed

+630
-0
lines changed

21 files changed

+630
-0
lines changed

‎README.md

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

‎src/main/racket/g0201_0300/s0207_course_schedule/Solution.rkt

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
; #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search
2+
; #Breadth_First_Search #Graph #Topological_Sort #Top_Interview_150_Graph_General
3+
; #Big_O_Time_O(N)_Space_O(N) #2025_02_10_Time_4_(100.00%)_Space_101.62_(100.00%)
4+
5+
(define (can-finish num-courses prereqs)
6+
(let ([adj (make-hash)]
7+
[seen (make-vector num-courses 0)])
8+
(for ([x prereqs])
9+
(hash-set! adj (first x)
10+
(cons (second x) (hash-ref adj (first x) '()))))
11+
12+
(define (dfs node)
13+
(cond ((= 1 (vector-ref seen node)) #f)
14+
((= 2 (vector-ref seen node)) #t)
15+
(else
16+
(vector-set! seen node 1)
17+
(if (andmap dfs (hash-ref adj node '()))
18+
(begin
19+
(vector-set! seen node 2)
20+
#t)
21+
#f))))
22+
23+
(andmap dfs (hash-keys adj))))

‎src/main/racket/g0201_0300/s0207_course_schedule/readme.md

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
207\. Course Schedule
2+
3+
Medium
4+
5+
There are a total of `numCourses` courses you have to take, labeled from `0` to `numCourses - 1`. You are given an array `prerequisites` where <code>prerequisites[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> indicates that you **must** take course <code>b<sub>i</sub></code> first if you want to take course <code>a<sub>i</sub></code>.
6+
7+
* For example, the pair `[0, 1]`, indicates that to take course `0` you have to first take course `1`.
8+
9+
Return `true` if you can finish all courses. Otherwise, return `false`.
10+
11+
**Example 1:**
12+
13+
**Input:** numCourses = 2, prerequisites = [[1,0]]
14+
15+
**Output:** true
16+
17+
**Explanation:** There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
18+
19+
**Example 2:**
20+
21+
**Input:** numCourses = 2, prerequisites = [[1,0],[0,1]]
22+
23+
**Output:** false
24+
25+
**Explanation:** There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
26+
27+
**Constraints:**
28+
29+
* `1 <= numCourses <= 2000`
30+
* `0 <= prerequisites.length <= 5000`
31+
* `prerequisites[i].length == 2`
32+
* <code>0 <= a<sub>i</sub>, b<sub>i</sub> < numCourses</code>
33+
* All the pairs prerequisites[i] are **unique**.

‎src/main/racket/g0201_0300/s0208_implement_trie_prefix_tree/Trie.rkt

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
; #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table #Design #Trie
2+
; #Level_2_Day_16_Design #Udemy_Trie_and_Heap #Top_Interview_150_Trie
3+
; #Big_O_Time_O(word.length())_or_O(prefix.length())_Space_O(N)
4+
; #2025_02_10_Time_102_(100.00%)_Space_134.45_(100.00%)
5+
6+
(define trie%
7+
(class object%
8+
(super-new)
9+
10+
;; Define TrieNode struct
11+
(struct trie-node (children is-word?) #:mutable)
12+
13+
;; Root node of the Trie
14+
(init-field)
15+
(define root (trie-node (make-hash) #f))
16+
(define start-with? #f)
17+
18+
;; Inserts a word into the trie.
19+
(define/public (insert word)
20+
(define (insert-helper node word idx)
21+
(if (= idx (string-length word))
22+
(set-trie-node-is-word?! node #t)
23+
(let* ([ch (string-ref word idx)]
24+
[children (trie-node-children node)]
25+
[next-node (hash-ref children ch (lambda () (trie-node (make-hash) #f)))])
26+
(hash-set! children ch next-node)
27+
(insert-helper next-node word (+ idx 1)))))
28+
(insert-helper root word 0))
29+
30+
;; Searches for a word in the trie.
31+
(define/public (search word)
32+
(define (search-helper node word idx)
33+
(if (= idx (string-length word))
34+
(begin
35+
(set! start-with? #t)
36+
(trie-node-is-word? node))
37+
(let* ([ch (string-ref word idx)]
38+
[children (trie-node-children node)]
39+
[next-node (hash-ref children ch #f)])
40+
(if next-node
41+
(search-helper next-node word (+ idx 1))
42+
(begin
43+
(set! start-with? #f)
44+
#f)))))
45+
(search-helper root word 0))
46+
47+
;; Checks if any word in the trie starts with the given prefix.
48+
(define/public (starts-with prefix)
49+
(send this search prefix)
50+
start-with?)))
51+
52+
;; Your trie% object will be instantiated and called as such:
53+
;; (define obj (new trie%))
54+
;; (send obj insert word)
55+
;; (define param_2 (send obj search word))
56+
;; (define param_3 (send obj starts-with prefix))

‎src/main/racket/g0201_0300/s0208_implement_trie_prefix_tree/readme.md

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
208\. Implement Trie (Prefix Tree)
2+
3+
Medium
4+
5+
A [**trie**](https://en.wikipedia.org/wiki/Trie) (pronounced as "try") or **prefix tree** is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
6+
7+
Implement the Trie class:
8+
9+
* `Trie()` Initializes the trie object.
10+
* `void insert(String word)` Inserts the string `word` into the trie.
11+
* `boolean search(String word)` Returns `true` if the string `word` is in the trie (i.e., was inserted before), and `false` otherwise.
12+
* `boolean startsWith(String prefix)` Returns `true` if there is a previously inserted string `word` that has the prefix `prefix`, and `false` otherwise.
13+
14+
**Example 1:**
15+
16+
**Input** ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
17+
18+
**Output:** [null, null, true, false, true, null, true]
19+
20+
**Explanation:**
21+
22+
Trie trie = new Trie();
23+
24+
trie.insert("apple");
25+
26+
trie.search("apple"); // return True
27+
28+
trie.search("app"); // return False
29+
30+
trie.startsWith("app"); // return True
31+
32+
trie.insert("app");
33+
34+
trie.search("app"); // return True
35+
36+
**Constraints:**
37+
38+
* `1 <= word.length, prefix.length <= 2000`
39+
* `word` and `prefix` consist only of lowercase English letters.
40+
* At most <code>3 * 10<sup>4</sup></code> calls **in total** will be made to `insert`, `search`, and `startsWith`.

‎src/main/racket/g0201_0300/s0215_kth_largest_element_in_an_array/Solution.rkt

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
; #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Sorting #Heap_Priority_Queue
2+
; #Divide_and_Conquer #Quickselect #Data_Structure_II_Day_20_Heap_Priority_Queue
3+
; #Top_Interview_150_Heap #Big_O_Time_O(n*log(n))_Space_O(log(n))
4+
; #2025_02_10_Time_79_(100.00%)_Space_135.10_(100.00%)
5+
6+
(define/contract (find-kth-largest nums k)
7+
(-> (listof exact-integer?) exact-integer? exact-integer?)
8+
(let* ([sorted-nums (sort nums >)] ; Sort in descending order
9+
[index (- k 1)]) ; Convert 1-based to 0-based index
10+
(list-ref sorted-nums index))) ; Return the k-th largest element

‎src/main/racket/g0201_0300/s0215_kth_largest_element_in_an_array/readme.md

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
215\. Kth Largest Element in an Array
2+
3+
Medium
4+
5+
Given an integer array `nums` and an integer `k`, return _the_ <code>k<sup>th</sup></code> _largest element in the array_.
6+
7+
Note that it is the <code>k<sup>th</sup></code> largest element in the sorted order, not the <code>k<sup>th</sup></code> distinct element.
8+
9+
You must solve it in `O(n)` time complexity.
10+
11+
**Example 1:**
12+
13+
**Input:** nums = [3,2,1,5,6,4], k = 2
14+
15+
**Output:** 5
16+
17+
**Example 2:**
18+
19+
**Input:** nums = [3,2,3,1,2,4,5,5,6], k = 4
20+
21+
**Output:** 4
22+
23+
**Constraints:**
24+
25+
* <code>1 <= k <= nums.length <= 10<sup>5</sup></code>
26+
* <code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code>

‎src/main/racket/g0201_0300/s0221_maximal_square/Solution.rkt

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
; #Medium #Array #Dynamic_Programming #Matrix #Dynamic_Programming_I_Day_16
2+
; #Top_Interview_150_Multidimensional_DP #Big_O_Time_O(m*n)_Space_O(m*n)
3+
; #2025_02_10_Time_426_(100.00%)_Space_130.80_(100.00%)
4+
5+
(define/contract (maximal-square matrix)
6+
(-> (listof (listof char?)) exact-integer?)
7+
(let* ([m (length matrix)]
8+
[n (if (zero? m) 0 (length (first matrix)))]
9+
[dp (make-hash)] ; Hash table to simulate a 2D array
10+
[max-size 0])
11+
12+
(define (get-dp i j)
13+
(hash-ref dp (cons i j) 0)) ; Default to 0 if not found
14+
15+
;; Iterate over the matrix
16+
(for ([i (in-range m)])
17+
(for ([j (in-range n)])
18+
(when (char=? (list-ref (list-ref matrix i) j) #\1)
19+
(let* ([min-neighbor (min (get-dp i j) (get-dp (+ i 1) j) (get-dp i (+ j 1)))]
20+
[size (+ 1 min-neighbor)])
21+
(hash-set! dp (cons (+ i 1) (+ j 1)) size)
22+
(set! max-size (max max-size size))))))
23+
24+
(* max-size max-size))) ; Return area of the largest square

‎src/main/racket/g0201_0300/s0221_maximal_square/readme.md

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
221\. Maximal Square
2+
3+
Medium
4+
5+
Given an `m x n` binary `matrix` filled with `0`'s and `1`'s, _find the largest square containing only_ `1`'s _and return its area_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2020/11/26/max1grid.jpg)
10+
11+
**Input:** matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
12+
13+
**Output:** 4
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2020/11/26/max2grid.jpg)
18+
19+
**Input:** matrix = [["0","1"],["1","0"]]
20+
21+
**Output:** 1
22+
23+
**Example 3:**
24+
25+
**Input:** matrix = [["0"]]
26+
27+
**Output:** 0
28+
29+
**Constraints:**
30+
31+
* `m == matrix.length`
32+
* `n == matrix[i].length`
33+
* `1 <= m, n <= 300`
34+
* `matrix[i][j]` is `'0'` or `'1'`.

‎src/main/racket/g0201_0300/s0226_invert_binary_tree/Solution.rkt

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
; #Easy #Depth_First_Search #Tree #Binary_Search #Binary_Tree #Binary_Search_II_Day_10
2+
; #Top_Interview_150_Binary_Tree_General #2025_02_10_Time_0_(100.00%)_Space_129.49_(100.00%)
3+
4+
; Definition for a binary tree node.
5+
#|
6+
7+
; val : integer?
8+
; left : (or/c tree-node? #f)
9+
; right : (or/c tree-node? #f)
10+
(struct tree-node
11+
(val left right) #:mutable #:transparent)
12+
13+
; constructor
14+
(define (make-tree-node [val 0])
15+
(tree-node val #f #f))
16+
17+
|#
18+
19+
(define/contract (count-nodes root)
20+
(-> (or/c tree-node? #f) exact-integer?)
21+
(if (not root)
22+
0
23+
(+ 1 (count-nodes (tree-node-left root))
24+
(count-nodes (tree-node-right root)))))

0 commit comments

Comments
 (0)
0