leetcode

排列

找下一个 https://leetcode.com/problems/next-permutation
void 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;
    }
}

Anm
https://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是桥