Permutation of string

Backtracking Time Complexity: O(n*n!) # include <stdio.h>   void swap (char *x, char *y) {     char temp;     temp = *x;     *x = *y;     *y = temp; }    /* Function to print permutations of string    This function takes three parameters:    1. String    2. Starting index of the string    3. Ending index of the string. */ void permute(char *a, int i, int n) {    int j;    if (i == n)      printf("%s\n", a); //Base case    else    {         for (j = i; j <= n; j++) //Recursion case        {           swap((a+i), (a+j));           permute(a, i+1, n);           swap((a+i), (a+j)); //Backtrack!!!        }    } }   int main() {    char a[] = "ABC";     permute(a, 0, 2);    getchar();    return 0; }

Output:

ABC
ACB
BAC
BCA
CBA
CAB

Best time to buy and sell stock -- Leetcode

Question:

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Answer:
Follow-up: to print out the start and end day time.

int maxProfit(vector<int> &prices,int &start, int &end) {
        int minv = INT_MAX, maxv = 0, dif = 0, int k;
        for(int i=0;i<prices.size();++i){
            if(prices[i]<minv){
                minv = prices[i];
                k = i;                     //Just to keep previous latest minv index, when maxv updated!      
            }
            dif = prices[i] - minv;
            if(dif> maxv){
                maxv = dif;
                start = k;
                end = i;
            }
        }
        return maxv;
    }

Judge whether a undirected graph is a Tree

Question:
To judge whether a undirected graph is a Tree (don't have specify the d-ary value of tree...)
(== judge whether a undirected graph is acyclic) For a undirected graph, acyclic graph is just a tree.

Answer:
Key point:
1. Exclude the "root" node, every node can only has '1' parent;
2. Every node can have many children nodes.
3. Should notice about how many connectd components there are. (including isolated node)

#include <stdio.h>
#include <unordered_set>
#include <vector>
#include <iostream>

using namespace std;

struct GNode{
int val;
vector<GNode*> connection;
};

bool JudgeGTHelp(GNode *cur,GNode *par, unordered_set<GNode*> &sset){
if(!cur) return false;
    if(cur->connection.size()==1 && cur->connection[0] == par) return true;     //leaf node, only has '1' parent, base case.

for(int i=0; i<cur->connection.size();++i){
GNode *p = cur->connection[i];
if(p == par) continue;

if(sset.find(p)!= sset.end()) return false;    //To ensure the child node only has '1' parent,i.e.==cur, not traversed by other pars!!!
   sset.insert(p);
if(!JudgeGTHelp(p,cur,sset)) return false;     //Recursion case.
}
return true;
}

bool JudgeGT(GNode *p,unordered_set<GNode*> &sset){
return JudgeGTHelp(p, 0,sset);
}

int main(){
vector<GNode*> vertices;         //include all GNodes in a graph.
unordered_set<GNode*> sset;
GNode * q = vertices[0];
bool res = JudgeGT(q,sset);
if(res==false) cout<<"False"<<endl;
for(int i=0;i<vertices.size();++i){
if(sset.find(vertices[i]) == sset.end()){        //To check for if there exist any other unconnected component!!!
break;
cout<<"False"<<endl;
}
}
cout<<"True, the graph is a tree."<<endl;
getchar();
return 0;
}