Leetcode

template < class T,                        // set::key_type/value_type
           class Compare = less<T>,        // set::key_compare/value_compare
           class Alloc = allocator<T>      // set::allocator_type
           > class set;

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

string word1 = "hello";
string word2 = "hall";
// m means the number of word1
// n means the number of word2
// del, rep, ins represents change from word1 to word2
int m = word1.size();
int n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
dp[0][0] = 0;
for(int i = 1; i <= m; ++i){
	dp[i][0] = i;
	for(int j = 1; j <= n; ++j){
		dp[0][j] = j;
		int del = dp[i - 1][j] + 1;
		int ins = dp[i][j - 1] + 1;
		// do nothing and replace a letter
		int rep = word1[i] == word2[j]? dp[i - 1][j - 1]: dp[i - 1][j - 1] + 1;
		// "aaa" "aa" word1[2] == word1[1] and min step is delete(dp[i-1][j]) 
		// not do nothing(dp[i-1][j-1])
		// the following is wrong
		// if(word1[i] == word2[j])
		//     dp[i][j] = min(del, ins);
		// else
		//     dp[i][j] = min({del, ins, dp[i - 1][j - 1] + 1});
		dp[i][j] = min({del, ins, rep});
	}
}
return dp[m][n];

// 3 vector/array: dist, visited, path  
dist[] = std::numeric_limits<>::max()
visited[]=0
path[]
queue Q
dist[start_node] = 0
// any operations for Q will influence visited  
Q.push(start_node)
//when node is in Q, his visited is 1  
visited[start_node] = 1
while(!Q){
	u = Q.front()
	Q.pop()
	// node leaves, his visited becomes 0
	visited[u] = 0
	for(all edges connected node v for node u){
		//fasten
		if(dist[u] + edgesTov < dist[v]){
			path[u] = v
			dist[v] = dist[u] + edgesTov        
                                                
        if(!visited[v]){
				Q.push(v)
				visited[v] = 1;
			}
		}
	}
}

void pointToVector(TreeNode * p, vector<int>& res)
	{
		res.push_back(p->val);
		if ((p->left == nullptr)&&(p->right == nullptr)) {
			sumAll += cal(res);
			return;
		}
		if (p->left != nullptr) {
			pointToVector(p->left, res);
			res.pop_back();
		}
		if (p->right != nullptr) {
			pointToVector(p->right, res);
			res.pop_back();
		}
	}

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
        DFS(G, u)
}

// the first step: source is start point
void dfs(vector<vector<int>>& graph, int source, int target, vector<vector<int>>& path)
{
	onePath.push_back(source);
	if (source == target)
	{
		path.push_back(onePath);
	}
	for (auto i : graph[source])
	{
			dfs(graph, i, target, path);
			//every recursive location, think about the following pop_back
			onePath.pop_back();
	}
}
int main(){
	int target = graph.size() - 1;
	vector<vector<int>> path;
	dfs(graph, 0, target, path);
}

void removeDuplicate(std::vector<string>& s)
	{
		sort(s.begin(), s.end());
		for (int i = 1; i < s.size(); ++i)
		{
			if (s[i - 1] == s[i])
			{
				s.erase(s.begin()+i-1);
				--i; // point is here
			}
		}
	}

//for inserter
#include <iterator>
// for swap
#include <algorithm>
set<int> __intersection;
set<int> temp = v.at(0);
for (int i = 0; i < v.size(); ++i){
	set_intersection(temp.begin(), temp.end(), v.at(i).begin(), v.at(i).end(),
	std::inserter(__intersection, __intersecion.begin())); 
	// __intersection has function insert(), so std::inserter is OK
	// if changed to back_inserter from inserter, error for not
	// have push_back for __intersection, because __intersection is
	// a set not a vector
	std::swap(__intersecion, temp);
	__intersection.clear(); // clean set of containing each time's result
}

#include <sstream>   
long long int stringToNum(const string& str)
{  
    istringstream iss(str);  
    long long int num;  
    iss >> num;  
    return num;      
}

long long int stringToNum(const string &str)
{
	map<char, int> m;
	long long int x = 0;
	for(int i = 0; i< str.size(); ++i){
		x = x * 10 + m[i];
	}
	return x;
}

int a = 10;
char *intStr = itoa(a);
string str = string(intStr);

int a = 10;
stringstream ss;
ss << a;
string str = ss.str();

#include <string>
std::string s = std::to_string(42);

#include <sstream>

std::string number;
std::stringstream strstream;
strstream << 1L;
strstream >> number;

//1.
string str="123";
atoi( str.c_str() );
//2.
std::stoi(str);
//3.
std::stringstream ss(str);
ss >> thevalue;

string str;
double value = atof(str.c_str());

string word;  
openfile >> word;
double lol = atof(word.c_str());

//**最后输出的number只能显示s中的六位（从高位数）**
string s="235.19123";
std::stringstream ss(s);
double number=0;
ss>>number;

TreeNode* InsertNodeBST(TreeNode* root, const int insertVal){
	if(!root)
		return new TreeNode(insertVal);
	if(root->val < insertVal)
		root->right = InsertNodeBST(root->right, insertVal);
	else
		root->left = InsertNodeBST(root->left, insertVal);
	}
	return root;
}

TreeNode* deleteNodeBST(TreeNode* root, const int deleteVal){
	if(root->val < insertVal)
		root->right = deleteNodeBST(root->right, deleteVal);
	else if(root->val > insertVal)
		root->left = deleteNodeBST(root->left, deleteVal);
	else{
		if(!root->left || !root->right){
			auto nonempty = root->left == nullptr? root->right: root->left;
			return nonempty;
		}
		else{
			auto min_node = root->right;
			while(min_node->left)
				min_node = min_node->left;
			root->val = min_node->val;
			root->right = deleteNodeBST(root->right, min_node->val);
		}
	}
	return root;
}

void dfs(TreeNode* root, const vector<int>& to_delete){
        if(root->left != nullptr)
            dfs(root->left, to_delete);
        if(root->right != nullptr)
            dfs(root->right, to_delete);
        if(std::find(to_delete.begin(), to_delete.end(), root->val) != to_delete.end()){
            if(root->left != nullptr)
                forest.push_back(root->left);
            if(root->right != nullptr)
                forest.push_back(root->right);
		// the flowing code can not delete node *root*
            root->val = NULL;
            root->left = nullptr;
            root->right = nullptr;
            root = nullptr; 
		}
}

TreeNode* dfs(TreeNode* root, const vector<int>& to_delete){
        if(root->left != nullptr)
            root->left = dfs(root->left, to_delete);
        if(root->right != nullptr)
            root->right = dfs(root->right, to_delete);
        if(std::find(to_delete.begin(), to_delete.end(), root->val) != to_delete.end()){
            if(root->left != nullptr)
                forest.push_back(root->left);
            if(root->right != nullptr)
                forest.push_back(root->right);
			return nullptr;
		}
		return root;
}

template<class T>
class Test{};
// specialization of above class
template<>
class Test<int>{};

template<class T>
class Test{};
template<>
class Test<int> {
public:
	int operator()(int h) {
		return h*h;
	}
};
int main() {
	// return x = 9
	// ()return Test object and 
	// (3) overload operation()
	auto x = Test<int>()(3);
	return 0;
}

#include <unordered_set>
class Test {
private:
	int x;
	int y;
public:
	Test(int xx, int yy) {
		x = xx;
		y = yy;
	}
	int getX() const{
		return x;
	}
	int getY() const{
		return y;
	}
	bool operator==(Test t2) const {
		return x == t2.x && y == t2.y;
	}
};
namespace std {
	template<>
	struct hash<Test>{
		int operator()(const Test t) const{
			return hash<int>()(t.getX()) ^ (hash<int>()(t.getY()));
		}
	};
}
int main() {
	unordered_set<Test> t;
	t.insert(Test(1, 2));
	t.insert(Test(2, 3));
	t.insert(Test(2, 3));
	// size == 2
	cout << t.size() << endl;
	return 0;
}

#include <set>
class Test {
private:
	int x;
	int y;
public:
	Test(int xx, int yy) {
		x = xx;
		y = yy;
	}
	int getX() const{
		return x;
	}
	int getY() const{
		return y;
	}
	bool operator< (Test t2) const {
		return x + y < t2.x + t2.y;
	}
};
int main() {
	set<Test> t2;
	t2.insert(Test(1, 2));
	t2.insert(Test(2, 3));
	t2.insert(Test(1, 2));
	// size == 2
	std::cout << t2.size() << std::endl;
	return 0;
}

void quickSort(vector<int> &nums, int left, int right) {
		int i = left;
		int j = right;
		int pivot = nums[left];
		while (i < j) {
			// key point is you need to find val from right
			// if the following whiles are changed in order, then
			// nums[i]/[j] is larger than nums[left].
			// There is an error when exchange nums[left] = nums[i] out of the range
			while (i < j && nums[j] >= pivot)
				--j;
			// <= is necessary, because i should be started from left not left + 1
			while (i < j && nums[i] <= pivot)
				++i;
			auto temp = nums[i];
			nums[i] = nums[j];
			nums[j] = temp;
		}
		nums[left] = nums[i];
		nums[i] = pivot;
		if (i > left)
			quickSort(nums, left, i - 1);
		// not else if, you need to iterate two segment
		if (i < right)
			quickSort(nums, i + 1, right);
	}
	vector<int> sortArray(vector<int>& nums) {
		quickSort(nums, 0, nums.size() - 1);
		return nums;
	}

class Solution {
public:
	void merge(vector<int> &nums, int l, int m, int r) {
		vector<int> left;
		vector<int> right;
		copy(nums.begin() + l, nums.begin() + m + 1, std::back_inserter(left));
		copy(nums.begin() + m + 1, nums.begin() + r + 1, std::back_inserter(right));
		int i = 0;
		int j = 0;
		int k = l;
		while (i < left.size() && j < right.size()) {
			if (left[i] < right[j]) {
				nums[k] = left[i];
				++i;
			}
			else {
				nums[k] = right[j];
				++j;
			}
			++k;
		}
		while (i < left.size()) {
			nums[k] = left[i];
			++k; ++i;
		}
		while (j < right.size()) {
			nums[k] = right[j];
			++k; ++j;
		}
	}
	void mergeSort(vector<int> &nums, int l, int r) {
		int m = l + (r - l) / 2;
		if(l < m)
			mergeSort(nums, l, m);
		if(m + 1 < r)
			mergeSort(nums, m + 1, r);
		merge(nums, l, m, r);
	}
};

class Solution {
public:
	// put ith element of nums in right place
	void build_heap(vector<int> &nums, int size, int i) {
		int large = i;
		if (i * 2 + 1 < size && nums[large] < nums[i * 2 + 1])
			large = i * 2 + 1;
		if (i * 2 + 2 < size && nums[large] < nums[i * 2 + 2])
			large = i * 2 + 2;
		if (i != large) {
			int temp = nums[i];
			nums[i] = nums[large];
			nums[large] = temp;
			build_heap(nums, size, large);
		}
	}
	vector<int> sortArray(vector<int> & nums) {
		// node which has children is not leaf
		// put non-leaf nodes in right place
		for (int i = nums.size() / 2 - 1; i >= 0; --i)
			build_heap(nums, nums.size(), i);
		// max heap has been built now
		for (int i = nums.size() - 1; i >= 0; --i) {
			// swap nums[0] and nums[i]
			// order has been finished from i to end
			int temp = nums[0];
			nums[0] = nums[i];
			nums[i] = temp;
			// the second param: i - end has order
			// the third param: the first element(nums[0]) 
			// changes its place. need to change it only.
			build_heap(nums, i, 0);
		}
		return nums;
	}
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
    // note 4 conditions
        if(!p && !q)
            return true;
        if(!q || !p)
            return false;
        if(p->val != q->val)
            return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};