leetCode第19題
10941 ワード
リスト問題を解析する「Remove Nth Node From End of List」
leetcodeは接続リストの問題でListNodeとして入力します.
nは、後からいくつかの要素を削除することを示す.Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
まず私の方法でリンクリストを実現しました
独自の方法で接続リストを実装 # 노드 생성
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 연결 리스트 생성
class linkedList:
def __init__(self):
self.head = None # 포인터
self.size = 0 # 크기
#제일 뒤에 추가하는 함수
def append(self, val):
if not self.head: # 헤더가 없으면 헤더에 추가
self.head = Node(val)
self.size += 1
return
node = self.head # node 변수에 담아서 고정시켜야지 아래 while문이 작동함 즉 헤더는 고정하고 변수에 담긴 self.head는 이동시키고 추가
while node.next: # head의 next가 None일때까지 돌면서 데이터 추가
node = node.next # node에 node.next로 바꿔주면서 추가
node.next = Node(val)
self.size += 1
#뒤에서 삭제하는 함수
def back_delete(self, idx):
real_idx = abs(self.size - idx) #삭제할 위치 0 부터 찾기위해 뺴줌
node = self.head #현재노드
prev = self.head #prev현재 노드의 전
for i in range(real_idx): #real_idx
prev = node #현재 노드를 prev에 저장하고
node = node.next #현재 노드의 next를 노드로 지정
prev.next = node.next #prev.next가 node.next로 가면 node의 연결이 끊겨서 node가 삭제됌
self.size -= 1
削除ロジックが理解できない人のために再説明するなら
prev.next = node.next
2 -> 3 -> 4
prev -> node -> node.next
この形で今はprevnextは3番で、4に変えるという意味です.
そうすると、2->4のとき、3は場所が見つからず削除されます.
しかし、これはleetcodeが望んでいる方法ではありません.
問題を解決するためには、ランニングのテクニックを理解しなければならない.
Runnerテクノロジーとは?
SLOWとFASTへ
1コマごとに移動してFASTとSLOWが2倍以上違うように移動するとFASTが末尾に達するとSLOWは真ん中に位置し,そこから探索を開始すると時間が減少する.
Runnerテクノロジーの説明
# Definition for singly-linked list.
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head) #dummy를 만드는 이유는 head부터 시작해도 되지만 여러 예외처리를 해줘야해서이다.
fast = dummy
slow = dummy
head = dummy
for i in range(n):
fast = fast.next #n만큼 fast를 먼저 이동시켜준다.
#왜냐하면 우리는 뒤에서부터 삭제하기위해 먼저 가있고 하나씩 가면서 fast.next가 None일때 slow가 삭제할 노드전에 위치한다.
#삭제할 노드에 위치하게 짠다면 우리는 prev값을 들고 가지고있어야 노드를 연결한다.
while fast.next: #fast.next가 None일때 까지
fast = fast.next
slow = slow.next
slow.next = slow.next.next #slow가 현재 prev라고 생각하면 편하다.
return head.next #head가 현재 dummy에 위치했으니깐 head.next head로하고
# = dummy를 삭제해도 될거 같은데 [1] 일때를 빼주지 못한다.
#그래서 dummy를 추가하는 이유기도 한다.
Reference
この問題について(leetCode第19題), 我々は、より多くの情報をここで見つけました
https://velog.io/@hongdol/leetCode-19번-문제
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
# 노드 생성
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# 연결 리스트 생성
class linkedList:
def __init__(self):
self.head = None # 포인터
self.size = 0 # 크기
#제일 뒤에 추가하는 함수
def append(self, val):
if not self.head: # 헤더가 없으면 헤더에 추가
self.head = Node(val)
self.size += 1
return
node = self.head # node 변수에 담아서 고정시켜야지 아래 while문이 작동함 즉 헤더는 고정하고 변수에 담긴 self.head는 이동시키고 추가
while node.next: # head의 next가 None일때까지 돌면서 데이터 추가
node = node.next # node에 node.next로 바꿔주면서 추가
node.next = Node(val)
self.size += 1
#뒤에서 삭제하는 함수
def back_delete(self, idx):
real_idx = abs(self.size - idx) #삭제할 위치 0 부터 찾기위해 뺴줌
node = self.head #현재노드
prev = self.head #prev현재 노드의 전
for i in range(real_idx): #real_idx
prev = node #현재 노드를 prev에 저장하고
node = node.next #현재 노드의 next를 노드로 지정
prev.next = node.next #prev.next가 node.next로 가면 node의 연결이 끊겨서 node가 삭제됌
self.size -= 1
削除ロジックが理解できない人のために再説明するならprev.next = node.next
2 -> 3 -> 4
prev -> node -> node.next
この形で今はprevnextは3番で、4に変えるという意味です.
そうすると、2->4のとき、3は場所が見つからず削除されます.
しかし、これはleetcodeが望んでいる方法ではありません.
問題を解決するためには、ランニングのテクニックを理解しなければならない.
Runnerテクノロジーとは?
SLOWとFASTへ
1コマごとに移動してFASTとSLOWが2倍以上違うように移動するとFASTが末尾に達するとSLOWは真ん中に位置し,そこから探索を開始すると時間が減少する.
Runnerテクノロジーの説明
# Definition for singly-linked list.
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head) #dummy를 만드는 이유는 head부터 시작해도 되지만 여러 예외처리를 해줘야해서이다.
fast = dummy
slow = dummy
head = dummy
for i in range(n):
fast = fast.next #n만큼 fast를 먼저 이동시켜준다.
#왜냐하면 우리는 뒤에서부터 삭제하기위해 먼저 가있고 하나씩 가면서 fast.next가 None일때 slow가 삭제할 노드전에 위치한다.
#삭제할 노드에 위치하게 짠다면 우리는 prev값을 들고 가지고있어야 노드를 연결한다.
while fast.next: #fast.next가 None일때 까지
fast = fast.next
slow = slow.next
slow.next = slow.next.next #slow가 현재 prev라고 생각하면 편하다.
return head.next #head가 현재 dummy에 위치했으니깐 head.next head로하고
# = dummy를 삭제해도 될거 같은데 [1] 일때를 빼주지 못한다.
#그래서 dummy를 추가하는 이유기도 한다.
Reference
この問題について(leetCode第19題), 我々は、より多くの情報をここで見つけました
https://velog.io/@hongdol/leetCode-19번-문제
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
# Definition for singly-linked list.
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0, head) #dummy를 만드는 이유는 head부터 시작해도 되지만 여러 예외처리를 해줘야해서이다.
fast = dummy
slow = dummy
head = dummy
for i in range(n):
fast = fast.next #n만큼 fast를 먼저 이동시켜준다.
#왜냐하면 우리는 뒤에서부터 삭제하기위해 먼저 가있고 하나씩 가면서 fast.next가 None일때 slow가 삭제할 노드전에 위치한다.
#삭제할 노드에 위치하게 짠다면 우리는 prev값을 들고 가지고있어야 노드를 연결한다.
while fast.next: #fast.next가 None일때 까지
fast = fast.next
slow = slow.next
slow.next = slow.next.next #slow가 현재 prev라고 생각하면 편하다.
return head.next #head가 현재 dummy에 위치했으니깐 head.next head로하고
# = dummy를 삭제해도 될거 같은데 [1] 일때를 빼주지 못한다.
#그래서 dummy를 추가하는 이유기도 한다.
Reference
この問題について(leetCode第19題), 我々は、より多くの情報をここで見つけました https://velog.io/@hongdol/leetCode-19번-문제テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol