排列
找下一个 https://leetcode.com/problems/next-permutationvoid nextPermutation(vector<int>& nums) { if(nums.size()<2){ return; } int i,j; for(i=nums.size()-2;i>=0;i--){ if(nums[i]<nums[i+1]){ //1.找最后一个左边比右边小的begin sort(nums.begin()+i+1,nums.end()); //2.后面的升序排 for(j=i+1;j<nums.size();j++){ if(nums[j]>nums[i]){ //3.找比begin大的第一个数交换 swap(nums[i],nums[j]); return; } } break; } } if(i<0){ sort(nums.begin(),nums.end()); return; }}Anmhttps://leetcode.com/problems/permutations-ii/vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> ret; if(nums.empty()){ return ret; } sort(nums.begin(),nums.end()); //1.排序 每次第一个都会入，如果不排序 跳过重复会用不了 permuteInner(nums,0,ret); return ret;}void permuteInner(vector<int> nums,int stable,vector<vector<int>>& ret) { if(stable==nums.size()-1){ ret.push_back(nums); return; } for(int j=stable;j<nums.size();j++){ //2.跳过重复 if(stable!=j&&nums[j]==nums[stable]){ continue; } //3.相当于前面j位已经排好，求j后面的排序组合，但前面j位可以是后面的任何一个。交换 swap(nums[stable],nums[j]); permuteInner(nums,stable+1,ret); } }Cmn 非重复
vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> ret{{}}; ret.push_back(tmp); for(int i=0;i<nums.size();i++){ subsetsInner(nums[i], ret); } return ret; }void subsetsInner(int num,vector<vector<int>>& ret){ int len=ret.size(); for(int i=0;i<len;i++){ vector<int> tmp=ret[i]; tmp.push_back(num); ret.push_back(tmp); }}Cmn 重复的排序
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());vector<vector<int>> ret{{}};for(int i=0;i<nums.size();i++){ vector<int> tmp(1,nums[i]); while(i<nums.size()-1&&nums[i+1]==nums[i]){ i++; tmp.push_back(nums[i]); } subsetsWithDup2(tmp,ret);}return ret;}
void subsetsWithDup2(vector<int>& nums,vector<vector<int>>& ret){
int len=ret.size();for(int i=0;i<len;i++){ for(int j=1;j<=nums.size();j++){ vector<int> tmp=ret[i]; tmp.insert(tmp.end(),nums.begin(),nums.begin()+j); ret.push_back(tmp); }}}
可重复和
vector<vector<int>> combinationSum(vector<int>& candidates, int target) { vector<vector<int>> ret; vector<int> sret; sort(candidates.begin(),candidates.end()); combinationSumInner(candidates,0,target,sret,ret); return ret;}void combinationSumInner(vector<int>& candidates,int begin,int target,vector<int>& sret,vector<vector<int>>& ret){ for(int i=begin;i<candidates.size();i++){ if(target-candidates[i]>0){ 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<int>& candidates,int begin,int target,vector<int>& sret,vector<vector<int>>& ret){ for(int i=begin;i<candidates.size();i++){ if(i>begin && candidates[i]==candidates[i-1]) continue; //去重复 if(target-candidates[i]>0&&(i<candidates.size()-1)){ sret.push_back(candidates[i]); combinationSumInner(candidates,i+1,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(int k,int begin,int n,vector<int>& sret,vector<vector<int>>& 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-1sum的问题。常规复杂度n^(k-1)
2-sum 首尾指针。或者一个hash 另一个查加和
3-sum 一个for 两个首尾。只要后面的
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<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>(); //采用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图
dijkstras
sptSet邻接表 距离值 0和最大a) 选择sptSet中不存在的顶点u并具有最小距离值。b）包括u到sptSet。c）更新u的所有相邻顶点的距离值。要更新距离值，请遍历所有相邻顶点。对于每个相邻顶点v，如果u（来自源）和边缘uv的权重的距离值之和小于v的距离值，则更新v的距离值。#include <stdio.h> #include <limits.h> // 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\n"); for (int i = 0; i < V; i++) printf("%d tt %d\n", 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 <bits/stdc++.h> 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<<"The following matrix shows the shortest distances" " between every pair of vertices \n"; for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (dist[i][j] == INF) cout<<"INF"<<" "; else cout<<dist[i][j]<<" "; } cout<<endl; } } // Driver code int main() { int graph[V][V] = { {0, 5, INF, 10}, {INF, 0, 3, INF}, {INF, INF, 0, 1}, {INF, INF, INF, 0} }; // Print the solution floydWarshall(graph); return 0; } 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<int>::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<int>::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<int> queue; visited[s] = true; queue.push_back(s); list<int>::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<int> &Stack) { // Mark the current node as visited. visited[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::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<int> 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<int>::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; } 另一种：不相交集
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是桥