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

Commitb324331

Browse files
authored
Added tasks 139-148
1 parent13e1675 commitb324331

File tree

15 files changed

+597
-0
lines changed

15 files changed

+597
-0
lines changed
Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
namespaceLeetCodeNet.G0101_0200.S0139_word_break{
2+
3+
usingXunit;
4+
5+
publicclassSolutionTest{
6+
[Fact]
7+
publicvoidWordBreak(){
8+
Assert.True(newSolution().WordBreak("leetcode",newList<string>{"leet","code"}));
9+
}
10+
11+
[Fact]
12+
publicvoidWordBreak2(){
13+
Assert.True(newSolution().WordBreak("applepenapple",newList<string>{"apple","pen"}));
14+
}
15+
16+
[Fact]
17+
publicvoidWordBreak3(){
18+
Assert.False(newSolution().WordBreak("catsandog",newList<string>{"cats","dog","sand","and","cat"}));
19+
}
20+
}
21+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
namespaceLeetCodeNet.G0101_0200.S0141_linked_list_cycle{
2+
3+
usingXunit;
4+
usingLeetCodeNet.Com_github_leetcode;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidHasCycle(){
9+
ListNodelistNode1=newListNode(3);
10+
listNode1.next=newListNode(2);
11+
listNode1.next.next=newListNode(0);
12+
listNode1.next.next.next=newListNode(-4);
13+
listNode1.next.next.next.next=listNode1.next;
14+
Assert.True(newSolution().HasCycle(listNode1));
15+
}
16+
17+
[Fact]
18+
publicvoidHasCycle2(){
19+
ListNodelistNode1=newListNode(1);
20+
listNode1.next=newListNode(2);
21+
listNode1.next.next=listNode1;
22+
Assert.True(newSolution().HasCycle(listNode1));
23+
}
24+
25+
[Fact]
26+
publicvoidHasCycle3(){
27+
ListNodelistNode1=newListNode(1);
28+
Assert.False(newSolution().HasCycle(listNode1));
29+
}
30+
}
31+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
namespaceLeetCodeNet.G0101_0200.S0142_linked_list_cycle_ii{
2+
3+
usingXunit;
4+
usingLeetCodeNet.Com_github_leetcode;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidDetectCycle(){
9+
ListNodelistNode1=newListNode(3);
10+
listNode1.next=newListNode(2);
11+
listNode1.next.next=newListNode(0);
12+
listNode1.next.next.next=newListNode(-4);
13+
listNode1.next.next.next.next=listNode1.next;
14+
Assert.True(newSolution().DetectCycle(listNode1)==listNode1.next);
15+
}
16+
17+
[Fact]
18+
publicvoidDetectCycle2(){
19+
ListNodelistNode1=newListNode(1);
20+
listNode1.next=newListNode(2);
21+
listNode1.next.next=listNode1;
22+
Assert.True(newSolution().DetectCycle(listNode1)==listNode1);
23+
}
24+
25+
[Fact]
26+
publicvoidDetectCycle3(){
27+
ListNodelistNode1=newListNode(1);
28+
Assert.Equal(null,newSolution().DetectCycle(listNode1));
29+
}
30+
}
31+
}
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
namespaceLeetCodeNet.G0101_0200.S0146_lru_cache{
2+
3+
usingXunit;
4+
5+
publicclassLRUCacheTest{
6+
[Fact]
7+
publicvoidLruCache(){
8+
LRUCachelruCache=newLRUCache(2);
9+
// cache is {1=1}
10+
lruCache.Put(1,1);
11+
// cache is {1=1, 2=2}
12+
lruCache.Put(2,2);
13+
// return 1
14+
Assert.Equal(1,lruCache.Get(1));
15+
// LRU key was 2, evicts key 2, cache is {1=1, 3=3}
16+
lruCache.Put(3,3);
17+
// returns -1 (not found)
18+
Assert.Equal(-1,lruCache.Get(2));
19+
// LRU key was 1, evicts key 1, cache is {4=4, 3=3}
20+
lruCache.Put(4,4);
21+
// return -1 (not found)
22+
Assert.Equal(-1,lruCache.Get(1));
23+
// return 3
24+
Assert.Equal(3,lruCache.Get(3));
25+
// return 4
26+
Assert.Equal(4,lruCache.Get(4));
27+
}
28+
}
29+
}
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
namespaceLeetCodeNet.G0101_0200.S0148_sort_list{
2+
3+
usingXunit;
4+
usingLeetCodeNet.Com_github_leetcode;
5+
6+
publicclassSolutionTest{
7+
[Fact]
8+
publicvoidSortList(){
9+
ListNodelistNode1=newListNode(4);
10+
listNode1.next=newListNode(2);
11+
listNode1.next.next=newListNode(1);
12+
listNode1.next.next.next=newListNode(3);
13+
Assert.Equal("1, 2, 3, 4",newSolution().SortList(listNode1).ToString());
14+
}
15+
16+
[Fact]
17+
publicvoidSortList2(){
18+
ListNodelistNode1=newListNode(-1);
19+
listNode1.next=newListNode(5);
20+
listNode1.next.next=newListNode(3);
21+
listNode1.next.next.next=newListNode(4);
22+
listNode1.next.next.next.next=newListNode(0);
23+
Assert.Equal("-1, 0, 3, 4, 5",newSolution().SortList(listNode1).ToString());
24+
}
25+
26+
[Fact]
27+
publicvoidSortList3(){
28+
Assert.Equal(null,newSolution().SortList(null));
29+
}
30+
}
31+
}
Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
namespaceLeetCodeNet.G0101_0200.S0139_word_break{
2+
3+
// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #String #Hash_Table
4+
// #Dynamic_Programming #Trie #Memoization #Algorithm_II_Day_15_Dynamic_Programming
5+
// #Dynamic_Programming_I_Day_9 #Udemy_Dynamic_Programming #Big_O_Time_O(M+max*N)_Space_O(M+N+max)
6+
// #2024_01_09_Time_64_ms_(98.44%)_Space_49.2_MB_(10.24%)
7+
8+
publicclassSolution{
9+
privateDictionary<string,bool>visited=new();
10+
privateHashSet<string>?set;
11+
12+
publicboolWordBreak(strings,IList<string>wordDict){
13+
set=newHashSet<string>(wordDict);
14+
returnCheckWordBreak(s);
15+
}
16+
17+
publicboolCheckWordBreak(strings){
18+
if(visited.ContainsKey(s)){
19+
returnvisited[s];
20+
}
21+
if(set.Contains(s)){
22+
returntrue;
23+
}
24+
for(inti=0;i<s.Length;i++){
25+
if(set.Contains(s.Substring(0,i))&&CheckWordBreak(s.Substring(i))){
26+
visited[s]=true;
27+
returntrue;
28+
}
29+
}
30+
visited[s]=false;
31+
returnfalse;
32+
}
33+
}
34+
}
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: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
namespaceLeetCodeNet.G0101_0200.S0141_linked_list_cycle{
2+
3+
// #Easy #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Two_Pointers #Linked_List
4+
// #Data_Structure_I_Day_7_Linked_List #Udemy_Linked_List #Big_O_Time_O(N)_Space_O(1)
5+
// #2024_01_09_Time_76_ms_(99.02%)_Space_46.5_MB_(16.05%)
6+
7+
usingLeetCodeNet.Com_github_leetcode;
8+
9+
/**
10+
* Definition for singly-linked list.
11+
* public class ListNode {
12+
* public int val;
13+
* public ListNode next;
14+
* public ListNode(int x) {
15+
* val = x;
16+
* next = null;
17+
* }
18+
* }
19+
*/
20+
publicclassSolution{
21+
publicboolHasCycle(ListNodehead){
22+
if(head==null){
23+
returnfalse;
24+
}
25+
ListNodefast=head.next;
26+
ListNodeslow=head;
27+
while(fast!=null&&fast.next!=null){
28+
if(fast==slow){
29+
returntrue;
30+
}
31+
fast=fast.next.next;
32+
slow=slow.next;
33+
}
34+
returnfalse;
35+
}
36+
}
37+
}
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
141\. Linked List Cycle
2+
3+
Easy
4+
5+
Given`head`, the head of a linked list, determine if the linked list has a cycle in it.
6+
7+
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the`next` pointer. Internally,`pos` is used to denote the index of the node that tail's`next` pointer is connected to.**Note that`pos` is not passed as a parameter**.
8+
9+
Return`true`_if there is a cycle in the linked list_. Otherwise, return`false`.
10+
11+
**Example 1:**
12+
13+
![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)
14+
15+
**Input:** head =[3,2,0,-4], pos = 1
16+
17+
**Output:** true
18+
19+
**Explanation:** There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
20+
21+
**Example 2:**
22+
23+
![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)
24+
25+
**Input:** head =[1,2], pos = 0
26+
27+
**Output:** true
28+
29+
**Explanation:** There is a cycle in the linked list, where the tail connects to the 0th node.
30+
31+
**Example 3:**
32+
33+
![](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)
34+
35+
**Input:** head =[1], pos = -1
36+
37+
**Output:** false
38+
39+
**Explanation:** There is no cycle in the linked list.
40+
41+
**Constraints:**
42+
43+
* The number of the nodes in the list is in the range <code>[0, 10<sup>4</sup>]</code>.
44+
* <code>-10<sup>5</sup> <= Node.val <= 10<sup>5</sup></code>
45+
*`pos` is`-1` or a**valid index** in the linked-list.
46+
47+
**Follow up:** Can you solve it using`O(1)` (i.e. constant) memory?
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
namespaceLeetCodeNet.G0101_0200.S0142_linked_list_cycle_ii{
2+
3+
// #Medium #Top_100_Liked_Questions #Hash_Table #Two_Pointers #Linked_List
4+
// #Data_Structure_II_Day_10_Linked_List #Level_1_Day_4_Linked_List #Udemy_Linked_List
5+
// #Big_O_Time_O(N)_Space_O(1) #2024_01_09_Time_72_ms_(94.58%)_Space_43.8_MB_(18.67%)
6+
7+
usingLeetCodeNet.Com_github_leetcode;
8+
9+
/**
10+
* Definition for singly-linked list.
11+
* public class ListNode {
12+
* public int val;
13+
* public ListNode next;
14+
* public ListNode(int x) {
15+
* val = x;
16+
* next = null;
17+
* }
18+
* }
19+
*/
20+
publicclassSolution{
21+
publicListNodeDetectCycle(ListNodehead){
22+
if(head==null||head.next==null){
23+
returnnull;
24+
}
25+
ListNodeslow=head;
26+
ListNodefast=head;
27+
while(fast!=null&&fast.next!=null){
28+
fast=fast.next.next;
29+
slow=slow.next;
30+
if(slow==fast){
31+
break;
32+
}
33+
}
34+
if(fast==null||fast.next==null){
35+
returnnull;
36+
}
37+
slow=head;
38+
while(slow!=fast){
39+
slow=slow.next;
40+
fast=fast.next;
41+
}
42+
returnslow;
43+
}
44+
}
45+
}

0 commit comments

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