perogram

2019-05-29から1日間の記事一覧

強連結成分分解して縮約するとDAGになる

強連結とは 「有向」グラフにて、各頂点が行き来できる状態 強連結成分分解とは 有向グラフを、強連結なグラフに分解すること 縮約とは 頂点をマージすること DAGとは Directed Acyclic Graph 有向グラフだけどサイクルしていない、つまり強連結ではないグラ…

有効な括弧の最大長さ Longest valid Parentheses

Quiz https://practice.geeksforgeeks.org/problems/longest-valid-parentheses/0 Submission https://practice.geeksforgeeks.org/viewSol.php?subId=14381873&pid=1247&user=peroon 例 4 (()( ()()(( ((()()()))) ()(())( 2 4 10 6 Code ll maxLen(string …

配列からペアでない2つの数字を見つける。XOR

ペアでない数字は2つ(x, y)あるという設定 例 Input: {12, 23, 34, 12, 12, 23, 12, 45} Output: 34 and 45 ソートすれば O(n log n) しかしO(n)の解法がある https://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array…