Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit7756dba

Browse files
authored
Added tasks 206-221
1 parent943dce6 commit7756dba

File tree

11 files changed

+385
-0
lines changed

11 files changed

+385
-0
lines changed

‎README.md

Lines changed: 29 additions & 0 deletions
Large diffs are not rendered by default.
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
206\. Reverse Linked List
2+
3+
Easy
4+
5+
Given the`head` of a singly linked list, reverse the list, and return_the reversed list_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg)
10+
11+
**Input:** head =[1,2,3,4,5]
12+
13+
**Output:**[5,4,3,2,1]
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg)
18+
19+
**Input:** head =[1,2]
20+
21+
**Output:**[2,1]
22+
23+
**Example 3:**
24+
25+
**Input:** head =[]
26+
27+
**Output:**[]
28+
29+
**Constraints:**
30+
31+
* The number of nodes in the list is the range`[0, 5000]`.
32+
*`-5000 <= Node.val <= 5000`
33+
34+
**Follow up:** A linked list can be reversed either iteratively or recursively. Could you implement both?
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Linked_List #Recursion
2+
// #Data_Structure_I_Day_8_Linked_List #Algorithm_I_Day_10_Recursion_Backtracking
3+
// #Level_1_Day_3_Linked_List #Udemy_Linked_List #Big_O_Time_O(N)_Space_O(1)
4+
// #2023_10_09_Time_51_ms_(92.87%)_Space_44.3_MB_(96.03%)
5+
6+
import{ListNode}from'../../com_github_leetcode/listnode'
7+
8+
/*
9+
* Definition for singly-linked list.
10+
* class ListNode {
11+
* val: number
12+
* next: ListNode | null
13+
* constructor(val?: number, next?: ListNode | null) {
14+
* this.val = (val===undefined ? 0 : val)
15+
* this.next = (next===undefined ? null : next)
16+
* }
17+
* }
18+
*/
19+
functionreverseList(head:ListNode|null):ListNode|null{
20+
letprev:ListNode|null=null
21+
letcurr:ListNode|null=head
22+
while(curr!==null){
23+
constnext:ListNode|null=curr.next
24+
curr.next=prev
25+
prev=curr
26+
curr=next
27+
}
28+
returnprev
29+
}
30+
31+
export{reverseList}
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+
* <code>1 <= numCourses <= 10<sup>5</sup></code>
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**.
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Depth_First_Search
2+
// #Breadth_First_Search #Graph #Topological_Sort #Big_O_Time_O(N)_Space_O(N)
3+
// #2023_10_09_Time_68_ms_(70.14%)_Space_47.7_MB_(73.55%)
4+
5+
constWHITE=0
6+
constGRAY=1
7+
constBLACK=2
8+
9+
functioncanFinish(numCourses:number,prerequisites:number[][]):boolean{
10+
constadj:number[][]=Array.from({length:numCourses},()=>[])
11+
for(constpreofprerequisites){
12+
adj[pre[1]].push(pre[0])
13+
}
14+
constcolors:number[]=newArray(numCourses).fill(WHITE)
15+
for(leti=0;i<numCourses;i++){
16+
if(colors[i]===WHITE&&adj[i].length>0&&hasCycle(adj,i,colors)){
17+
returnfalse
18+
}
19+
}
20+
returntrue
21+
}
22+
23+
functionhasCycle(adj:number[][],node:number,colors:number[]):boolean{
24+
colors[node]=GRAY
25+
for(constneiofadj[node]){
26+
if(colors[nei]===GRAY){
27+
returntrue
28+
}
29+
30+
if(colors[nei]===WHITE&&hasCycle(adj,nei,colors)){
31+
returntrue
32+
}
33+
}
34+
colors[node]=BLACK
35+
returnfalse
36+
}
37+
38+
export{canFinish}
Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
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**
17+
18+
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
19+
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
20+
21+
**Output:**[null, null, true, false, true, null, true]
22+
23+
**Explanation:**
24+
25+
Trie trie = new Trie();
26+
trie.insert("apple"); trie.search("apple"); // return True
27+
trie.search("app"); // return False
28+
trie.startsWith("app"); // return True
29+
trie.insert("app");
30+
trie.search("app"); // return True
31+
32+
**Constraints:**
33+
34+
*`1 <= word.length, prefix.length <= 2000`
35+
*`word` and`prefix` consist only of lowercase English letters.
36+
* At most <code>3 * 10<sup>4</sup></code> calls**in total** will be made to`insert`,`search`, and`startsWith`.
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table #Design #Trie
2+
// #Level_2_Day_16_Design #Udemy_Trie_and_Heap
3+
// #Big_O_Time_O(word.length())_or_O(prefix.length())_Space_O(N)
4+
// #2023_10_09_Time_168_ms_(80.99%)_Space_79.5_MB_(14.46%)
5+
6+
classTrieNode{
7+
children:TrieNode[]
8+
isWord:boolean
9+
10+
constructor(){
11+
this.children=newArray<TrieNode>(26)
12+
this.isWord=false
13+
}
14+
}
15+
16+
classTrie{
17+
privateroot:TrieNode
18+
privatestartWith:boolean
19+
20+
privatestaticreadonlyALPHABET_SIZE=26
21+
22+
constructor(){
23+
this.root=newTrieNode()
24+
this.startWith=false
25+
}
26+
27+
// Inserts a word into the trie.
28+
insert(word:string):void{
29+
this.insertRecursive(word,this.root,0)
30+
}
31+
32+
privateinsertRecursive(word:string,node:TrieNode,idx:number):void{
33+
if(idx===word.length){
34+
node.isWord=true
35+
return
36+
}
37+
constcharIndex=this.getCharIndex(word.charAt(idx))
38+
if(!node.children[charIndex]){
39+
node.children[charIndex]=newTrieNode()
40+
}
41+
this.insertRecursive(word,node.children[charIndex],idx+1)
42+
}
43+
44+
// Returns if the word is in the trie.
45+
search(word:string):boolean{
46+
this.startWith=false
47+
returnthis.searchRecursive(word,this.root,0)
48+
}
49+
50+
privatesearchRecursive(word:string,node:TrieNode,idx:number):boolean{
51+
if(idx===word.length){
52+
this.startWith=true
53+
returnnode.isWord
54+
}
55+
56+
constcharIndex=this.getCharIndex(word.charAt(idx))
57+
if(!node.children[charIndex]){
58+
this.startWith=false
59+
returnfalse
60+
}
61+
returnthis.searchRecursive(word,node.children[charIndex],idx+1)
62+
}
63+
64+
// Returns if there is any word in the trie
65+
// that starts with the given prefix.
66+
startsWith(prefix:string):boolean{
67+
this.search(prefix)
68+
returnthis.startWith
69+
}
70+
71+
privategetCharIndex(char:string):number{
72+
returnchar.charCodeAt(0)-'a'.charCodeAt(0)
73+
}
74+
}
75+
76+
/*
77+
* Your Trie object will be instantiated and called as such:
78+
* var obj = new Trie()
79+
* obj.insert(word)
80+
* var param_2 = obj.search(word)
81+
* var param_3 = obj.startsWith(prefix)
82+
*/
83+
84+
export{Trie}
Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
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+
**Example 1:**
10+
11+
**Input:** nums =[3,2,1,5,6,4], k = 2
12+
13+
**Output:** 5
14+
15+
**Example 2:**
16+
17+
**Input:** nums =[3,2,3,1,2,4,5,5,6], k = 4
18+
19+
**Output:** 4
20+
21+
**Constraints:**
22+
23+
* <code>1 <= k <= nums.length <= 10<sup>4</sup></code>
24+
* <code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code>
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+
// #Big_O_Time_O(n*log(n))_Space_O(log(n)) #2023_10_09_Time_148_ms_(54.45%)_Space_51.5_MB_(73.60%)
4+
5+
functionfindKthLargest(nums:number[],k:number):number{
6+
nums.sort((prev,next)=>next-prev)
7+
returnnums[k-1]
8+
}
9+
10+
export{findKthLargest}
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'`.
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
// #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Matrix
2+
// #Dynamic_Programming_I_Day_16 #Big_O_Time_O(m*n)_Space_O(m*n)
3+
// #2023_10_09_Time_83_ms_(79.70%)_Space_50.2_MB_(56.39%)
4+
5+
functionmaximalSquare(matrix:string[][]):number{
6+
constm=matrix.length
7+
if(m===0){
8+
return0
9+
}
10+
constn=matrix[0].length
11+
if(n===0){
12+
return0
13+
}
14+
constdp:number[][]=newArray(m+1).fill(0).map(()=>newArray(n+1).fill(0))
15+
letmax=0
16+
for(leti=0;i<m;i++){
17+
for(letj=0;j<n;j++){
18+
if(matrix[i][j]==='1'){
19+
// 1 + minimum from cell above, cell to the left, cell diagonal upper-left
20+
constnext=1+Math.min(dp[i][j],Math.min(dp[i+1][j],dp[i][j+1]))
21+
// keep track of the maximum value seen
22+
if(next>max){
23+
max=next
24+
}
25+
dp[i+1][j+1]=next
26+
}
27+
}
28+
}
29+
returnmax*max
30+
}
31+
32+
export{maximalSquare}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp