【6.C++ベース】-アルゴリズムleetcode
23916 ワード
きそ
ツリー
広さ優先探索(breadth−first−search)、深さ優先探索(depth−first−search)、および中順遍歴、後順遍歴、および前順遍歴の違い.スタックは常に最大値を見つけることができるが,代価は他のいずれかの値を探すのに要する時間がO(n)である.挿入と削除に要する時間は依然としてO(logn)辞書ツリーツリーツリーツリーツリーツリーである-』ツリー検索=』バランスツリー/赤黒ツリー検索、挿入と削除はO(log n)
整列
Cmn非繰返し
Cmn重複ソート
繰り返し可能
繰り返し不可能
数値加算
k−sum問題は和k−1 sumの問題に移行した.従来の複雑度n^(k-1)2-sumヘッダポインタ.あるいは1つのhashのもう1つのチャガと3-sumの1つのforの2つの首尾です.後ろの4-sum 2個が先にキャッシュされ、2-sumのchaheが使用されます.
チェーンテーブル
文字列
回文のManacherアルゴリズム.
mpに長さを保存し、最小のものを先に取ります.そしてここから++を比較してRが大きくなると、Rとcを新しい値に再付与します.
KMP:
図
dijkstras
Floydマルチソース最短パスは、最初は1番の頂点のみを経由して中継を許可し、次に1番と2番の頂点のみを経由して中継を許可します.
また、DFS+が前経路上にあるか否かを判定する(visited+rectrace)
もう1つ:交差しない
接点と橋
接点:low[v]>=dnf[u]ブリッジ:low[v]>dnf[u]V-Uがブリッジであることを示す
DP
01リュックサックansx=max(ansx-1,ansx-1]+v[x]);1階だけ必要です.ここで逆順でなければ,計算が完了するたびに新しいiのdp[j]が前のi−1のdp[j]を上書きする.iは計算を繰り返し,複数回用いられた.例えばリュックサックV=8.2-3,1-2のもの
初期化:充填された---0だけが0を満たすことができて、その他の初期化は負に無限に充填する必要はありません---すべての初期は0完全にリュックサックです:すべての品物は無限の部品を取ることができます
マルチバックパック:max{dp[j-kvolume[i]+kvalue[i]}0<=k<=num[i]しかし最適化可能:バイナリ組合せ数、k個を使用しない.バイナリを使わない場合は、9つのアイテムに分割する必要があります.バイナリを利用して、9より小さいバイナリ数1 2 4 8に分割すればいいです.
最小編集距離は、2つの列がどれだけ変化したかと同じです.異なるかif(word 1[i-1]==word 2[j-1])edi=edi-1を追加/削除/交換する.else edi = min(min(edi + 1, edi - 1 + 1), edi - 1 + 1);
LIS(最長増分順)通常DP:
まず配列endsを作成し、最初の要素を入れて、その後の要素を比較し、遍歴した新しい要素がends配列の最初の要素より小さい場合は、最初の要素を新しい要素に置き換え、遍歴した新しい要素がends配列の末尾の要素よりも大きい場合は、この新しい要素をends配列の末尾に追加します(元の末尾の要素を上書きしないことに注意).遍歴した新しい要素がends配列の最初の要素より大きく、最後の要素より小さい場合、二分ルックアップ法で最初の新しい要素より小さくない位置を見つけ、位置の元の数字を上書きし、nums配列全体を遍歴するまで
マルチモードマッチング.KMPのように,パターンをfail(kmpのnext)ベースツリーとして構築した.
A*イニシアチブ
計算されたcloseリストへの追加計算されるopenlistは、計算されるたびに最小の(始点代価+終点推定代価)を探します.
int search(vector& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left <= right) {
int mid = left + (right-left)/2;
if(nums[mid] < target) {
left = mid+1;
} else if(nums[mid] > target) {
right = mid-1;
} else {
return mid;
}
}
return -1;
}
（merge sort） （quicksort） （radix sort）nlogn
，
，
void selectKItems(int stream[], int n, int k)
{
int i; // index for elements in stream[]
int reservoir[k];
for (i = 0; i < k; i++)
reservoir[i] = stream[i];
srand(time(NULL));
for (; i < n; i++)
{
int j = rand() % (i+1);
if (j < k)
reservoir[j] = stream[i];
}
printf("Following are k randomly selected items
");
printArray(reservoir, k);
}
。
int countPrimes(int n) {
vector prime(n, true);
prime[0] = false, prime[1] = false;
for (int i = 0; i < sqrt(n); ++i) {
if (prime[i]) {
for (int j = i*i; j < n; j += i) {
prime[j] = false;
}
}
}
return count(prime.begin(), prime.end(), true);
}
：bit = num & (1 << x); num ^= 1 << x;
：Cnk=n! / k!(n-k)! Cnk=Cn-1k+Cn-1k-1 Cnk=Cnn-k Ank=n!/(n-k)! Ann=n!
http://www.cs.trincoll.edu/~ram/cpsc110/inclass/conversions.html ツリー
広さ優先探索(breadth−first−search)、深さ優先探索(depth−first−search)、および中順遍歴、後順遍歴、および前順遍歴の違い.スタックは常に最大値を見つけることができるが,代価は他のいずれかの値を探すのに要する時間がO(n)である.挿入と削除に要する時間は依然としてO(logn)辞書ツリーツリーツリーツリーツリーツリーである-』ツリー検索=』バランスツリー/赤黒ツリー検索、挿入と削除はO(log n)
整列
https://leetcode.com/problems/next-permutation
void nextPermutation(vector& nums) {
int n = nums.size(), k, l;
for (k = n - 2; k >= 0; k--) {
if (nums[k] < nums[k + 1]) {
break;
}
}
if (k < 0) {
reverse(nums.begin(), nums.end());
} else {
for (l = n - 1; l > k; l--) {
if (nums[l] > nums[k]) {
break;
}
}
swap(nums[k], nums[l]);
reverse(nums.begin() + k + 1, nums.end());
}
} Anm
https://leetcode.com/problems/permutations-ii/
vector> permuteUnique(vector& nums) {
vector> ret;
if(nums.empty()){
return ret;
}
sort(nums.begin(),nums.end()); //1. ，
permuteInner(nums,0,ret);
return ret;
}
void permuteInner(vector nums,int stable,vector>& ret) {
if(stable==nums.size()-1){
ret.push_back(nums);
return;
}
for(int j=stable;j Cmn非繰返し
vector> subsets(vector& nums) {
vector> ret{{}};
ret.push_back(tmp);
for(int i=0;i>& ret){
int len=ret.size();
for(int i=0;i tmp=ret[i];
tmp.push_back(num);
ret.push_back(tmp);
}
} Cmn重複ソート
vector> subsetsWithDup(vector& nums) {
sort(nums.begin(),nums.end());
vector> ret{{}};
for(int i=0;i tmp(1,nums[i]);
while(i& nums,vector>& ret){
int len=ret.size();
for(int i=0;i tmp=ret[i];
tmp.insert(tmp.end(),nums.begin(),nums.begin()+j);
ret.push_back(tmp);
}
}
} 繰り返し可能
vector> combinationSum(vector& candidates, int target) {
vector> ret;
vector sret;
sort(candidates.begin(),candidates.end());
combinationSumInner(candidates,0,target,sret,ret);
return ret;
}
void combinationSumInner(vector& candidates,int begin,int target,vector& sret,vector>& ret){
for(int i=begin;i0){
sret.push_back(candidates[i]);
combinationSumInner(candidates,i,target-candidates[i],sret,ret);
sret.erase(sret.end()-1);
}else if(target-candidates[i]==0){
sret.push_back(candidates[i]);
ret.push_back(sret);
sret.erase(sret.end()-1);
}
}
} 繰り返し不可能
void combinationSumInner(vector& candidates,int begin,int target,vector& sret,vector>& ret){
for(int i=begin;ibegin && candidates[i]==candidates[i-1]) continue; //
if(target-candidates[i]>0&&(i 数値加算
void combinationSumInner(int k,int begin,int n,vector& sret,vector>& ret){
for(int i=begin;i<10;i++){
if(n-i>0&&(i<9)&&k>1){
sret.push_back(i);
combinationSumInner(k-1,i+1,n-i,sret,ret); //
sret.erase(sret.end()-1);
}else if(n-i==0&&k==1){
sret.push_back(i);
ret.push_back(sret);
sret.erase(sret.end()-1);
}
}
} k−sum問題は和k−1 sumの問題に移行した.従来の複雑度n^(k-1)2-sumヘッダポインタ.あるいは1つのhashのもう1つのチャガと3-sumの1つのforの2つの首尾です.後ろの4-sum 2個が先にキャッシュされ、2-sumのchaheが使用されます.
チェーンテーブル
next random
// 2 1 ，
//l1->next->random = l1->random->next
RandomListNode *copyRandomList(RandomListNode *head) {
RandomListNode *newHead, *l1, *l2;
if (head == NULL) return NULL;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
l2 = new RandomListNode(l1->label);
l2->next = l1->next;
l1->next = l2;
}
newHead = head->next;
for (l1 = head; l1 != NULL; l1 = l1->next->next) {
if (l1->random != NULL) l1->next->random = l1->random->next;
}
for (l1 = head; l1 != NULL; l1 = l1->next) {
l2 = l1->next;
l1->next = l2->next;
if (l2->next != NULL) l2->next = l2->next->next;
}
return newHead;
}
// map ，random
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) return head;
RandomListNode newHead = new RandomListNode(head.label);
RandomListNode oldp = head.next;
RandomListNode newp = newHead;
Map map = new HashMap();
// map
map.put(newp, head);
while (oldp != null) {//
RandomListNode newTemp = new RandomListNode(oldp.label);
map.put(newTemp, oldp);
newp.next = newTemp;
newp=newp.next;
oldp=oldp.next;
}
oldp=head;
newp=newHead;
while (newp!=null){// random
newp.random=map.get(newp).random;// random
newp=newp.next;
oldp=oldp.next;
}
return head;
}
ListNode* reverseList(ListNode* head) {
ListNode* cur = NULL;
while (head) {
ListNode* next = head -> next;
head -> next = cur;
cur = head;
head = next;
}
return cur;
}
ListNode* reverseList(ListNode* head) {
if (!head || !(head -> next)) {
return head;
}
ListNode* node = reverseList(head -> next);
head -> next -> next = head;
head -> next = NULL;
return node;
} 。 。head
文字列
https://blog.csdn.net/whdAlive/article/details/81132383
回文のManacherアルゴリズム.
mpに長さを保存し、最小のものを先に取ります.そしてここから++を比較してRが大きくなると、Rとcを新しい値に再付与します.
KMP:
図
： ， setup ， v setup ， 。 O(N^2)
， for(0-v)， 0-V i j 。 。 0 1， V O(N^3)
primer setup 。 。 setup=v O(N^2)
krusal ， （ ）， V-1 O(ElogE)
：dfs !visted || rec。 rec
union find （findparent 。union ）
DFS 。
foreach(V) topu(V)
topu foreachV u topu(u) dijkstras
sptSet
0
a) sptSet u 。
b） u sptSet。
c） u 。 ， 。 v， u（ ） uv v ， v 。
#include
#include
// Number of vertices in the graph
#define V 9
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source
");
for (int i = 0; i < V; i++)
printf("%d tt %d
", i, dist[i]);
}
void dijkstra(int graph[V][V], int src)
{
int dist[V];
bool sptSet[V];
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist, V);
} // driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}
Floydマルチソース最短パスは、最初は1番の頂点のみを経由して中継を許可し、次に1番と2番の頂点のみを経由して中継を許可します.
#include
using namespace std;
#define V 4
#define INF 99999
void printSolution(int dist[][V]);
void floydWarshall (int graph[][V])
{
int dist[V][V], i, j, k;
for (i = 0; i < V; i++)
for (j = 0; j < V; j++)
dist[i][j] = graph[i][j];
for (k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (i = 0; i < V; i++)
{
// Pick all vertices as destination for the
// above picked source
for (j = 0; j < V; j++)
{
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
// Print the shortest distance matrix
printSolution(dist);
}
/* A utility function to print solution */
void printSolution(int dist[][V])
{
cout< DFS
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and
// print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent
// to this vertex
list::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function
// to print DFS traversal
DFSUtil(v, visited);
} void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and
// print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent
// to this vertex
list::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function
// to print DFS traversal
DFSUtil(v, visited);
}
word search
class GFG {
// Let the given dictionary be following
static final String dictionary[] = { "GEEKS", "FOR", "QUIZ", "GUQ", "EE" };
static final int n = dictionary.length;
static final int M = 3, N = 3;
static boolean isWord(String str)
{
// Linearly search all words
for (int i = 0; i < n; i++)
if (str.equals(dictionary[i]))
return true;
return false;
}
// A recursive function to print all words present on boggle
static void findWordsUtil(char boggle[][], boolean visited[][], int i,
int j, String str)
{
visited[i][j] = true;
str = str + boggle[i][j];
// If str is present in dictionary, then print it
if (isWord(str))
System.out.println(str);
// Traverse 8 adjacent cells of boggle[i][j]
for (int row = i - 1; row <= i + 1 && row < M; row++)
for (int col = j - 1; col <= j + 1 && col < N; col++)
if (row >= 0 && col >= 0 && !visited[row][col])
findWordsUtil(boggle, visited, row, col, str);
str = "" + str.charAt(str.length() - 1);
visited[i][j] = false;
}
// Prints all words present in dictionary.
static void findWords(char boggle[][])
{
// Mark all characters as not visited
boolean visited[][] = new boolean[M][N];
// Initialize current string
String str = "";
// Consider every character and look for all words
// starting with this character
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
findWordsUtil(boggle, visited, i, j, str);
}
}
BFS
void Graph::BFS(int s)
{
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
list queue;
visited[s] = true;
queue.push_back(s);
list::iterator i;
while(!queue.empty())
{
s = queue.front();
cout << s << " ";
queue.pop_front();
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
DFS 。 DFS ， ， ， DFS 。 ， 。 ， ， 。 ， 。 ， （ ） ， 。
void Graph::topologicalSortUtil(int v, bool visited[],
stack &Stack)
{
// Mark the current node as visited.
visited[v] = true;
// Recur for all the vertices adjacent to this vertex
list::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
topologicalSortUtil(*i, visited, Stack);
// Push current vertex to stack which stores result
Stack.push(v);
}
void Graph::topologicalSort()
{
stack Stack;
// Mark all the vertices as not visited
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to store Topological
// Sort starting from all vertices one by one
for (int i = 0; i < V; i++)
if (visited[i] == false)
topologicalSortUtil(i, visited, Stack);
// Print contents of stack
while (Stack.empty() == false)
{
cout << Stack.top() << " ";
Stack.pop();
}
}
primer: ，
Kruskal：
1. 。
2. 。 。 ， 。 ， 。
3. ＃2， （V-1） 。
また、DFS+が前経路上にあるか否かを判定する(visited+rectrace)
bool Graph::isCyclicUtil(int v, bool visited[], bool *recStack)
{
if(visited[v] == false)
{
// Mark the current node as visited and part of recursion stack
visited[v] = true;
recStack[v] = true;
// Recur for all the vertices adjacent to this vertex
list::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
{
if ( !visited[*i] && isCyclicUtil(*i, visited, recStack) )
return true;
else if (recStack[*i])
return true;
}
}
recStack[v] = false; // remove the vertex from recursion stack
return false;
}
bool Graph::isCyclic()
{
// Mark all the vertices as not visited and not part of recursion
// stack
bool *visited = new bool[V];
bool *recStack = new bool[V];
for(int i = 0; i < V; i++)
{
visited[i] = false;
recStack[i] = false;
}
// Call the recursive helper function to detect cycle in different
// DFS trees
for(int i = 0; i < V; i++)
if (isCyclicUtil(i, visited, recStack))
return true;
return false;
} もう1つ:交差しない
int find(int parent[], int i)
{
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
// A utility function to do union of two subsets
void Union(int parent[], int x, int y)
{
int xset = find(parent, x);
int yset = find(parent, y);
if(xset != yset)
{
parent[xset] = yset;
}
}
int isCycle( Graph* graph )
{
// Allocate memory for creating V subsets
int *parent = new int[graph->V * sizeof(int)];
// Initialize all subsets as single element sets
memset(parent, -1, sizeof(int) * graph->V);
// Iterate through all edges of graph, find subset of both
// vertices of every edge, if both subsets are same, then
// there is cycle in graph.
for(int i = 0; i < graph->E; ++i)
{
int x = find(parent, graph->edge[i].src);
int y = find(parent, graph->edge[i].dest);
if (x == y)
return 1;
Union(parent, x, y);
}
return 0;
} 接点と橋
接点:low[v]>=dnf[u]ブリッジ:low[v]>dnf[u]V-Uがブリッジであることを示す
DP
01リュックサックansx=max(ansx-1,ansx-1]+v[x]);1階だけ必要です.ここで逆順でなければ,計算が完了するたびに新しいiのdp[j]が前のi−1のdp[j]を上書きする.iは計算を繰り返し,複数回用いられた.例えばリュックサックV=8.2-3,1-2のもの
for(int i=1;i<=n;i++)
for(int j=v;j>=volume[i];j--)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
初期化:充填された---0だけが0を満たすことができて、その他の初期化は負に無限に充填する必要はありません---すべての初期は0完全にリュックサックです:すべての品物は無限の部品を取ることができます
for(int i=1;i<=n;i++)
for(int j=volume[i];j<=v;j++)
dp[j]=max(dp[j],dp[j-volume[i]]+value[i]);
マルチバックパック:max{dp[j-kvolume[i]+kvalue[i]}0<=k<=num[i]しかし最適化可能:バイナリ組合せ数、k個を使用しない.バイナリを使わない場合は、9つのアイテムに分割する必要があります.バイナリを利用して、9より小さいバイナリ数1 2 4 8に分割すればいいです.
最小編集距離は、2つの列がどれだけ変化したかと同じです.異なるかif(word 1[i-1]==word 2[j-1])edi=edi-1を追加/削除/交換する.else edi = min(min(edi + 1, edi - 1 + 1), edi - 1 + 1);
LIS(最長増分順)通常DP:
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}まず配列endsを作成し、最初の要素を入れて、その後の要素を比較し、遍歴した新しい要素がends配列の最初の要素より小さい場合は、最初の要素を新しい要素に置き換え、遍歴した新しい要素がends配列の末尾の要素よりも大きい場合は、この新しい要素をends配列の末尾に追加します(元の末尾の要素を上書きしないことに注意).遍歴した新しい要素がends配列の最初の要素より大きく、最後の要素より小さい場合、二分ルックアップ法で最初の新しい要素より小さくない位置を見つけ、位置の元の数字を上書きし、nums配列全体を遍歴するまで
int lengthOfLIS(vector& nums) {
if (nums.empty()) return 0;
vector ends{nums[0]};
for (auto a : nums) {
if (a < ends[0]) ends[0] = a;
else if (a > ends.back()) ends.push_back(a);
else {
int left = 0, right = ends.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (ends[mid] < a) left = mid + 1;
else right = mid;
}
ends[right] = a;
}
}
return ends.size();
} マルチモードマッチング.KMPのように,パターンをfail(kmpのnext)ベースツリーとして構築した.
A*イニシアチブ
計算されたcloseリストへの追加計算されるopenlistは、計算されるたびに最小の(始点代価+終点推定代価)を探します.