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

Commitcb76925

Browse files
authored
Added tasks 347-1143
1 parente136c84 commitcb76925

File tree

44 files changed

+1173
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

44 files changed

+1173
-0
lines changed

‎README.md

Lines changed: 35 additions & 0 deletions
Large diffs are not rendered by default.
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
classNode
2+
attr_accessor:val,:next,:random
3+
4+
definitialize(val=0,next_node=nil,random=nil)
5+
@val=val
6+
@next=next_node
7+
@random=random
8+
end
9+
10+
defto_s
11+
result=[]
12+
curr=self
13+
14+
whilecurr
15+
result <<"[#{curr.val},#{curr.random ?find_index(curr.random) :'nil'}]"
16+
curr=curr.next
17+
end
18+
19+
'[' +result.join(',') +']'
20+
end
21+
22+
private
23+
24+
deffind_index(target)
25+
index=0
26+
curr=self
27+
28+
whilecurr&.next &&curr !=target
29+
index +=1
30+
curr=curr.next
31+
end
32+
33+
index
34+
end
35+
end
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
138\. Copy List with Random Pointer
2+
3+
Medium
4+
5+
A linked list of length`n` is given such that each node contains an additional random pointer, which could point to any node in the list, or`null`.
6+
7+
Construct a[**deep copy**](https://en.wikipedia.org/wiki/Object_copying#Deep_copy) of the list. The deep copy should consist of exactly`n`**brand new** nodes, where each new node has its value set to the value of its corresponding original node. Both the`next` and`random` pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.**None of the pointers in the new list should point to nodes in the original list**.
8+
9+
For example, if there are two nodes`X` and`Y` in the original list, where`X.random --> Y`, then for the corresponding two nodes`x` and`y` in the copied list,`x.random --> y`.
10+
11+
Return_the head of the copied linked list_.
12+
13+
The linked list is represented in the input/output as a list of`n` nodes. Each node is represented as a pair of`[val, random_index]` where:
14+
15+
*`val`: an integer representing`Node.val`
16+
*`random_index`: the index of the node (range from`0` to`n-1`) that the`random` pointer points to, or`null` if it does not point to any node.
17+
18+
Your code will**only** be given the`head` of the original linked list.
19+
20+
**Example 1:**
21+
22+
![](https://assets.leetcode.com/uploads/2019/12/18/e1.png)
23+
24+
**Input:** head =[[7,null],[13,0],[11,4],[10,2],[1,0]]
25+
26+
**Output:**[[7,null],[13,0],[11,4],[10,2],[1,0]]
27+
28+
**Example 2:**
29+
30+
![](https://assets.leetcode.com/uploads/2019/12/18/e2.png)
31+
32+
**Input:** head =[[1,1],[2,1]]
33+
34+
**Output:**[[1,1],[2,1]]
35+
36+
**Example 3:**
37+
38+
**![](https://assets.leetcode.com/uploads/2019/12/18/e3.png)**
39+
40+
**Input:** head =[[3,null],[3,0],[3,null]]
41+
42+
**Output:**[[3,null],[3,0],[3,null]]
43+
44+
**Example 4:**
45+
46+
**Input:** head =[]
47+
48+
**Output:**[]
49+
50+
**Explanation:** The given linked list is empty (null pointer), so return null.
51+
52+
**Constraints:**
53+
54+
*`0 <= n <= 1000`
55+
*`-10000 <= Node.val <= 10000`
56+
*`Node.random` is`null` or is pointing to some node in the linked list.
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
# #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Linked_List
2+
# #Programming_Skills_II_Day_14 #Udemy_Linked_List #Big_O_Time_O(N)_Space_O(N)
3+
# #2023_11_27_Time_65_ms_(69.84%)_Space_211.3_MB_(52.38%)
4+
5+
require_relative'../../com_github_leetcode/random/node'
6+
7+
# Definition for Node.
8+
# class Node
9+
# attr_accessor :val, :next, :random
10+
# def initialize(val = 0)
11+
# @val = val
12+
# @next = nil
13+
# @random = nil
14+
# end
15+
# end
16+
17+
# @param {Node} node
18+
# @return {Node}
19+
defcopy_random_list(head)
20+
returnnilifhead.nil?
21+
22+
# First pass to create cloned nodes and insert them after the original nodes
23+
curr=head
24+
whilecurr
25+
cloned_node=Node.new(curr.val)
26+
cloned_node.next=curr.next
27+
curr.next=cloned_node
28+
curr=cloned_node.next
29+
end
30+
31+
# Second pass to set the random pointers of the cloned nodes
32+
curr=head
33+
whilecurr
34+
curr.next.random=curr.random.nextifcurr.random
35+
curr=curr.next.next
36+
end
37+
38+
# Third pass to separate the original and cloned nodes
39+
curr=head
40+
new_head=nil
41+
whilecurr
42+
cloned_node=curr.next
43+
new_head ||=cloned_node
44+
curr.next=cloned_node.next
45+
cloned_node.next=curr.next.nextifcurr.next
46+
curr=curr.next
47+
end
48+
49+
new_head
50+
end
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
139\. Word Break
2+
3+
Medium
4+
5+
Given a string`s` and a dictionary of strings`wordDict`, return`true` if`s` can be segmented into a space-separated sequence of one or more dictionary words.
6+
7+
**Note** that the same word in the dictionary may be reused multiple times in the segmentation.
8+
9+
**Example 1:**
10+
11+
**Input:** s = "leetcode", wordDict =["leet","code"]
12+
13+
**Output:** true
14+
15+
**Explanation:** Return true because "leetcode" can be segmented as "leet code".
16+
17+
**Example 2:**
18+
19+
**Input:** s = "applepenapple", wordDict =["apple","pen"]
20+
21+
**Output:** true
22+
23+
**Explanation:** Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.
24+
25+
**Example 3:**
26+
27+
**Input:** s = "catsandog", wordDict =["cats","dog","sand","and","cat"]
28+
29+
**Output:** false
30+
31+
**Constraints:**
32+
33+
*`1 <= s.length <= 300`
34+
*`1 <= wordDict.length <= 1000`
35+
*`1 <= wordDict[i].length <= 20`
36+
*`s` and`wordDict[i]` consist of only lowercase English letters.
37+
* All the strings of`wordDict` are**unique**.
Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
# #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table
2+
# #Dynamic_Programming #Trie #Memoization #Algorithm_II_Day_15_Dynamic_Programming
3+
# #Dynamic_Programming_I_Day_9 #Udemy_Dynamic_Programming #Big_O_Time_O(M+max*N)_Space_O(M+N+max)
4+
# #2023_11_27_Time_64_ms_(79.31%)_Space_211.2_MB_(22.41%)
5+
6+
# @param {String} s
7+
# @param {String[]} word_dict
8+
# @return {Boolean}
9+
defword_break(s,word_dict)
10+
memo=Array.new(s.size -1,nil)
11+
dp=lambdado |i|
12+
returntrueifi <0
13+
returnmemo[i]unlessmemo[i].nil?
14+
15+
memo[i]=word_dict.any?do |word|
16+
s[i -word.size +1..i] ==word &&dp[i -word.size]
17+
end
18+
end
19+
dp[s.size -1]
20+
end
Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
347\. Top K Frequent Elements
2+
3+
Medium
4+
5+
Given an integer array`nums` and an integer`k`, return_the_`k`_most frequent elements_. You may return the answer in**any order**.
6+
7+
**Example 1:**
8+
9+
**Input:** nums =[1,1,1,2,2,3], k = 2
10+
11+
**Output:**[1,2]
12+
13+
**Example 2:**
14+
15+
**Input:** nums =[1], k = 1
16+
17+
**Output:**[1]
18+
19+
**Constraints:**
20+
21+
* <code>1 <= nums.length <= 10<sup>5</sup></code>
22+
*`k` is in the range`[1, the number of unique elements in the array]`.
23+
* It is**guaranteed** that the answer is**unique**.
24+
25+
**Follow up:** Your algorithm's time complexity must be better than`O(n log n)`, where n is the array's size.
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
# #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Array #Hash_Table #Sorting
2+
# #Heap_Priority_Queue #Counting #Divide_and_Conquer #Quickselect #Bucket_Sort
3+
# #Data_Structure_II_Day_20_Heap_Priority_Queue #Big_O_Time_O(n*log(n))_Space_O(k)
4+
# #2023_11_27_Time_67_ms_(83.85%)_Space_212_MB_(84.54%)
5+
6+
# @param {Integer[]} nums
7+
# @param {Integer} k
8+
# @return {Integer[]}
9+
deftop_k_frequent(nums,k)
10+
numhash=Hash.new(0)
11+
nums.each{|num|numhash[num] +=1}
12+
newhash=numhash.sort_by{|k,v| -v}
13+
ret_array=[]
14+
foriin0...k
15+
ret_array <<newhash[i][0]
16+
end
17+
returnret_array
18+
end
Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
394\. Decode String
2+
3+
Medium
4+
5+
Given an encoded string, return its decoded string.
6+
7+
The encoding rule is:`k[encoded_string]`, where the`encoded_string` inside the square brackets is being repeated exactly`k` times. Note that`k` is guaranteed to be a positive integer.
8+
9+
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.
10+
11+
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers,`k`. For example, there won't be input like`3a` or`2[4]`.
12+
13+
**Example 1:**
14+
15+
**Input:** s = "3[a]2[bc]"
16+
17+
**Output:** "aaabcbc"
18+
19+
**Example 2:**
20+
21+
**Input:** s = "3[a2[c]]"
22+
23+
**Output:** "accaccacc"
24+
25+
**Example 3:**
26+
27+
**Input:** s = "2[abc]3[cd]ef"
28+
29+
**Output:** "abcabccdcdcdef"
30+
31+
**Example 4:**
32+
33+
**Input:** s = "abc3[cd]xyz"
34+
35+
**Output:** "abccdcdcdxyz"
36+
37+
**Constraints:**
38+
39+
*`1 <= s.length <= 30`
40+
*`s` consists of lowercase English letters, digits, and square brackets`'[]'`.
41+
*`s` is guaranteed to be**a valid** input.
42+
* All the integers in`s` are in the range`[1, 300]`.
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
# #Medium #Top_100_Liked_Questions #String #Stack #Recursion #Level_1_Day_14_Stack #Udemy_Strings
2+
# #Big_O_Time_O(n)_Space_O(n) #2023_11_27_Time_58_ms_(84.09%)_Space_211.1_MB_(40.91%)
3+
4+
# @param {String} s
5+
# @return {String}
6+
defdecode_string(s)
7+
@i=0
8+
decode_helper(s)
9+
end
10+
11+
private
12+
13+
defdecode_helper(s)
14+
count=0
15+
result=""
16+
17+
while@i <s.length
18+
c=s[@i]
19+
@i +=1
20+
21+
ifletter?(c)
22+
result +=c
23+
elsifdigit?(c)
24+
count=count *10 +c.to_i
25+
elsifc ==']'
26+
break
27+
elsifc =='['
28+
# sub problem
29+
repeat=decode_helper(s)
30+
result +=repeat *count
31+
count=0
32+
end
33+
end
34+
35+
result
36+
end
37+
38+
defletter?(c)
39+
c =~/[a-zA-Z]/
40+
end
41+
42+
defdigit?(c)
43+
c =~/\d/
44+
end
Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
416\. Partition Equal Subset Sum
2+
3+
Medium
4+
5+
Given a**non-empty** array`nums` containing**only positive integers**, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
6+
7+
**Example 1:**
8+
9+
**Input:** nums =[1,5,11,5]
10+
11+
**Output:** true
12+
13+
**Explanation:** The array can be partitioned as[1, 5, 5] and[11].
14+
15+
**Example 2:**
16+
17+
**Input:** nums =[1,2,3,5]
18+
19+
**Output:** false
20+
21+
**Explanation:** The array cannot be partitioned into equal sum subsets.
22+
23+
**Constraints:**
24+
25+
*`1 <= nums.length <= 200`
26+
*`1 <= nums[i] <= 100`
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
# #Medium #Top_100_Liked_Questions #Array #Dynamic_Programming #Level_2_Day_13_Dynamic_Programming
2+
# #Big_O_Time_O(n*sums)_Space_O(n*sums) #2023_11_27_Time_1023_ms_(60.38%)_Space_212.3_MB_(88.68%)
3+
4+
# @param {Integer[]} nums
5+
# @return {Boolean}
6+
defcan_partition(nums)
7+
sums=nums.sum
8+
returnfalseifsums.odd?
9+
10+
sums /=2
11+
dp=Array.new(sums +1,false)
12+
dp[0]=true
13+
14+
nums.eachdo |num|
15+
sums.downto(num)do |sum|
16+
dp[sum]=dp[sum] ||dp[sum -num]
17+
end
18+
end
19+
20+
dp[sums]
21+
end

0 commit comments

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