プログラマーコース、データ構造、アルゴリズム-1

26868 ワード

講座アルゴリズム#アルゴリズム# テキストリンク

データ構造とアルゴリズム-1 link

第1回概要

2強です。リニアアレイ

pythonのlistはデータ型に制限されません
O(1)操作

要素.append()

を追加

要素.pop()

を取り出します
O(n)操作

要素.insert()

を挿入
削除

要素.del()

その他
探索

要素:.index()

実習。

ターゲット:値Lをリストxに挿入して昇順に適合

def solution(L, x):
    for i, v in enumerate(L):
        if v > x:
            L.insert(i, x)
            break
    else:
        L.append(x)
    return L

実習。

ターゲット:リストLからx値のindexを返し、不在時に-1を返します.

def solution(L, x):
    answer = []
    for i, v in enumerate(L):
        if v == x:
            answer.append(i)
    if len(answer) == 0:
        answer.append(-1)
    
    return answer

ベスト3並べ替えと参照

組み込みソート機能
1.Python内蔵関数sorted()-ソートされたリストを返す(deepcopy)
2.リストに使用可能な方法.sort()-リストをソートする
逆順序ソート(逆)reverse=trueをパラメータとして渡す
ex) sorted(L, reverse=true) , L.sort(reverse=true)ソート方法の指定(キー)
JavaのComparatorに似ています.sorted(L, key=lambda x: len(x))を使用すると、Lリストのオブジェクト値の文字列長が短い順に並べられます.dictionaryデータ型は、L.sort(key=lambda x:x['score'], reverse=true)の形式でx[「score」値の大きな順序でソートすることもできる.
ナビゲーションアルゴリズム
1.リニアサーチ(Linear Search)-順次サーチ、O(n)
2.バイナリサーチ(binary search)-位置合わせが可能な場合は、半分割ナビゲーション、O(logn)

実習。

ターゲット:効率を向上させるために、バイナリナビゲーションで昇順に配列された配列にxのindex値を返し、不在時に-1を返します.

def solution(L, x):
    low=0
    high=len(L)-1
    answer = 0
    while(low<=high):
        mid=(low+high)//2
        if L[mid]==x:
            answer = mid
            break
        elif L[mid]>x:
            high=mid-1
        else:
            low=mid+1
    else:
	    return -1
    return answer

ベスト4再帰アルゴリズムの基礎

実習。

目標:フィボナッチ数列の実現

貴

	```python
	def solution(x):
	    answer = 0;
	    if x <= 1:
	        answer = x
	    else:
	        answer = solution(x-1) + solution(x-2)
	    return answer
	```

複文

	```python
	def solution(x):
	    answer = 0;
	    if x <= 1:
	        answer = x
	    else:
	        now = 1;
	        before = 0;
	        for i in range(1, x):
	            answer = before + now
	            before = now
	            now = answer
	    return answer
	```

ベスト5。再帰アルゴリズム(Recursive Algorithms)応用

生産資源効率:再帰<繰返し

実習。

ターゲット:再帰バイナリナビゲーションの実装

def solution(L, x, l, u):
    if x < L[l] or x > L[u]:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l , mid - 1)

    else:
        return solution(L, x, mid + 1 , u)

ベスト6。アルゴリズム複雑度

漸近表現

Big-θ : 平均複雑度はθ(n)であり、

と表記されている.

Big-O:最悪の場合は複雑度(主に使用)、O(n)は

を表す

kg-Ω:最適複雑度Ω(n)、

と表記

サンプルソートアルゴリズム-マージソート(merge sort)
ソートする配列を最小比較単位で分割して比較->O(logn)
マージ整列の最小比較セルアレイ->O(n)=>O(nlogn)
六講実習.X

7強。リンクリスト(1)

一方向接続リスト

リストを構造化するには、次のターゲットのアドレスを参照します.

特定の要素(k)

を参照してください.

リスト

を巡る

の長さ

を得る

実習。

ターゲット:ループ関数を実装し、チェーンテーブルをループし、各ノードの値をリストとして作成して返します.

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None

class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        returnList = []
        target = self.head
        while target is not None:
            returnList.append(target.data)
            target = target.next
        
        return returnList

ベスト8リンクリスト(2)

要素の挿入(挿入)

削除(削除)

要素

2 2 2つのリストをマージ

9強。リンクリスト(3)

リンクリストのタイトルとして仮想ノードを追加

class Node:
	def __init__(self, item):
		self.data = item
		self.next = None
		
class LinkedList:
	def __init__(self):
		self.nodeCount = 0
		self.head = Node(None)
		self.tail = None
		self.head.next = self.tail

	def __repr__(self):
		if self.nodeCount == 0:
			return 'LinkedList: empty'
			
		s = ''
		curr = self.head
		while curr.next:
			curr = curr.next
			s += repr(curr.data)
			if curr.next is not None:
				s += ' -> '
		return s

	def getLength(self):
		return self.nodeCount

	def traverse(self):
		result = []
		curr = self.head
		while curr.next:
			curr = curr.next
			result.append(curr.data)
		return result

	def getAt(self, pos):
		if pos < 0 or pos > self.nodeCount:
			return None
		i = 0
		curr = self.head
		while i < pos:
			curr = curr.next
			i += 1

		return curr

	def insertAfter(self, prev, newNode):
		newNode.next = prev.next
		if prev.next is None:
			self.tail = newNode
		prev.next = newNode
		self.nodeCount += 1
		return True

	def insertAt(self, pos, newNode):
		if pos < 1 or pos > self.nodeCount + 1:
			return False
		if pos != 1 and pos == self.nodeCount + 1:
			prev = self.tail
		else:
			prev = self.getAt(pos - 1)
		return self.insertAfter(prev, newNode)

	def concat(self, L):
		self.tail.next = L.head.next
		if L.tail:
			self.tail = L.tail
		self.nodeCount += L.nodeCount

実習。

ターゲット:抽出ノードの関数を実装する

def popAfter(self, prev):
    curr = prev.next
    if prev.data is None:
        prev.next = curr.next
        self.tail = curr.next
    elif prev.next == self.tail:
        prev.next = None
        self.tail = prev
    else:
        prev.next = curr.next

    self.nodeCount -= 1
    return curr.data


def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError

    prev = self.getAt(pos - 1)
    return self.popAfter(prev)

Reference

この問題について(プログラマーコース、データ構造、アルゴリズム-1), 我々は、より多くの情報をここで見つけました https://velog.io/@1sonjm/프로그래머스-강좌-자료구조와-알고리즘-1

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

LinuxはどのようにMQを実現して自動的にキューマネージャを起動します

Git の使い方 (with SourceTree)