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

Commit5abf24f

Browse files
authored
Added tasks 198-234
1 parent2ea3987 commit5abf24f

File tree

31 files changed

+896
-0
lines changed

31 files changed

+896
-0
lines changed

‎README.md

Lines changed: 33 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+
198\. House Robber
2+
3+
Medium
4+
5+
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and**it will automatically contact the police if two adjacent houses were broken into on the same night**.
6+
7+
Given an integer array`nums` representing the amount of money of each house, return_the maximum amount of money you can rob tonight**without alerting the police**_.
8+
9+
**Example 1:**
10+
11+
**Input:** nums =[1,2,3,1]
12+
13+
**Output:** 4
14+
15+
**Explanation:**
16+
17+
Rob house 1 (money = 1) and then rob house 3 (money = 3).
18+
Total amount you can rob = 1 + 3 = 4.
19+
20+
**Example 2:**
21+
22+
**Input:** nums =[2,7,9,3,1]
23+
24+
**Output:** 12
25+
26+
**Explanation:**
27+
28+
Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
29+
Total amount you can rob = 2 + 9 + 1 = 12.
30+
31+
**Constraints:**
32+
33+
*`1 <= nums.length <= 100`
34+
*`0 <= nums[i] <= 400`
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Dynamic_Programming
2+
# #Algorithm_I_Day_12_Dynamic_Programming #Dynamic_Programming_I_Day_3
3+
# #Level_2_Day_12_Dynamic_Programming #Udemy_Dynamic_Programming #Big_O_Time_O(n)_Space_O(n)
4+
# #2023_11_25_Time_41_ms_(99.28%)_Space_210.9_MB_(86.23%)
5+
6+
# @param {Integer[]} nums
7+
# @return {Integer}
8+
defrob(nums)
9+
return0ifnums.empty?
10+
returnnums[0]ifnums.length ==1
11+
return[nums[0],nums[1]].maxifnums.length ==2
12+
13+
profit=Array.new(nums.length)
14+
profit[0]=nums[0]
15+
profit[1]=[nums[1],nums[0]].max
16+
17+
(2...nums.length).eachdo |i|
18+
profit[i]=[profit[i -1],nums[i] +profit[i -2]].max
19+
end
20+
21+
profit[nums.length -1]
22+
end
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
200\. Number of Islands
2+
3+
Medium
4+
5+
Given an`m x n` 2D binary grid`grid` which represents a map of`'1'`s (land) and`'0'`s (water), return_the number of islands_.
6+
7+
An**island** is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
8+
9+
**Example 1:**
10+
11+
**Input:**
12+
13+
grid = [
14+
["1","1","1","1","0"],
15+
["1","1","0","1","0"],
16+
["1","1","0","0","0"],
17+
["0","0","0","0","0"]
18+
]
19+
20+
**Output:** 1
21+
22+
**Example 2:**
23+
24+
**Input:**
25+
26+
grid = [
27+
["1","1","0","0","0"],
28+
["1","1","0","0","0"],
29+
["0","0","1","0","0"],
30+
["0","0","0","1","1"]
31+
]
32+
33+
**Output:** 3
34+
35+
**Constraints:**
36+
37+
*`m == grid.length`
38+
*`n == grid[i].length`
39+
*`1 <= m, n <= 300`
40+
*`grid[i][j]` is`'0'` or`'1'`.
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Depth_First_Search
2+
# #Breadth_First_Search #Matrix #Union_Find
3+
# #Algorithm_II_Day_6_Breadth_First_Search_Depth_First_Search
4+
# #Graph_Theory_I_Day_1_Matrix_Related_Problems #Level_1_Day_9_Graph/BFS/DFS #Udemy_Graph
5+
# #Big_O_Time_O(M*N)_Space_O(M*N) #2023_11_25_Time_141_ms_(72.68%)_Space_219.4_MB_(87.43%)
6+
7+
# @param {Character[][]} grid
8+
# @return {Integer}
9+
defnum_islands(grid)
10+
islands=0
11+
ifgrid && !grid.empty? && !grid[0].empty?
12+
(0...grid.length).eachdo |i|
13+
(0...grid[0].length).eachdo |j|
14+
ifgrid[i][j] =='1'
15+
dfs_islands(grid,i,j)
16+
islands +=1
17+
end
18+
end
19+
end
20+
end
21+
islands
22+
end
23+
24+
private
25+
26+
defdfs_islands(grid,x,y)
27+
returnifx.negative? ||grid.length <=x ||y.negative? ||grid[0].length <=y ||grid[x][y] !='1'
28+
29+
grid[x][y]='x'
30+
dfs_islands(grid,x +1,y)
31+
dfs_islands(grid,x -1,y)
32+
dfs_islands(grid,x,y +1)
33+
dfs_islands(grid,x,y -1)
34+
end
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: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
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_11_25_Time_52_ms_(93.99%)_Space_211.1_MB_(64.56%)
5+
6+
# Definition for singly-linked list.
7+
# class ListNode
8+
# attr_accessor :val, :next
9+
# def initialize(val = 0, _next = nil)
10+
# @val = val
11+
# @next = _next
12+
# end
13+
# end
14+
# @param {ListNode} head
15+
# @return {ListNode}
16+
defreverse_list(head)
17+
prev=nil
18+
curr=head
19+
whilecurr
20+
next_node=curr.next
21+
curr.next=prev
22+
prev=curr
23+
curr=next_node
24+
end
25+
prev
26+
end
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: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
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_11_25_Time_60_ms_(95.42%)_Space_212.4_MB_(26.72%)
4+
5+
# @param {String} string
6+
# @return {String}
7+
WHITE=0
8+
GRAY=1
9+
BLACK=2
10+
11+
# @param {Integer} num_courses
12+
# @param {Integer[][]} prerequisites
13+
# @return {Boolean}
14+
defcan_finish(num_courses,prerequisites)
15+
adj=Array.new(num_courses){[]}
16+
17+
prerequisites.eachdo |pre|
18+
adj[pre[1]] <<pre[0]
19+
end
20+
21+
colors=Array.new(num_courses,WHITE)
22+
23+
(0...num_courses).eachdo |i|
24+
ifcolors[i] ==WHITE && !adj[i].empty? &&has_cycle(adj,i,colors)
25+
returnfalse
26+
end
27+
end
28+
29+
true
30+
end
31+
32+
private
33+
34+
defhas_cycle(adj,node,colors)
35+
colors[node]=GRAY
36+
37+
adj[node].eachdo |nei|
38+
returntrueifcolors[nei] ==GRAY
39+
returntrueifcolors[nei] ==WHITE &&has_cycle(adj,nei,colors)
40+
end
41+
42+
colors[node]=BLACK
43+
false
44+
end
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: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
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_11_25_Time_167_ms_(69.81%)_Space_227_MB_(33.96%)
5+
6+
# @param {String} string
7+
# @return {String}
8+
classTrie
9+
definitialize
10+
@root=TrieNode.new
11+
@start_with=false
12+
end
13+
14+
=begin
15+
:type word: String
16+
:rtype: Void
17+
=end
18+
definsert(word)
19+
insert_recursive(word,@root,0)
20+
end
21+
22+
=begin
23+
:type word: String
24+
:rtype: Boolean
25+
=end
26+
defsearch(word)
27+
search_recursive(word,@root,0)
28+
end
29+
30+
=begin
31+
:type prefix: String
32+
:rtype: Boolean
33+
=end
34+
defstarts_with(prefix)
35+
search(prefix)
36+
@start_with
37+
end
38+
39+
private
40+
41+
classTrieNode
42+
attr_accessor:children,:is_word
43+
44+
definitialize
45+
@children=Array.new(26)
46+
@is_word=false
47+
end
48+
end
49+
50+
definsert_recursive(word,root,idx)
51+
ifidx ==word.length
52+
root.is_word=true
53+
return
54+
end
55+
56+
index=word[idx].ord -'a'.ord
57+
root.children[index] ||=TrieNode.new
58+
insert_recursive(word,root.children[index],idx +1)
59+
end
60+
61+
defsearch_recursive(word,root,idx)
62+
ifidx ==word.length
63+
@start_with=true
64+
returnroot.is_word
65+
end
66+
67+
index=word[idx].ord -'a'.ord
68+
ifroot.children[index].nil?
69+
@start_with=false
70+
returnfalse
71+
end
72+
73+
search_recursive(word,root.children[index],idx +1)
74+
end
75+
end
76+
77+
# Your Trie object will be instantiated and called as such:
78+
# obj = Trie.new()
79+
# obj.insert(word)
80+
# param_2 = obj.search(word)
81+
# param_3 = obj.starts_with(prefix)

0 commit comments

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