class Solution {
public:
	void minmax(vector<vector<int>>& v, int& minid, int& maxid)
	{
		minid = 0, maxid = 0;
		for (int i = 1; i < v.size(); i++) {
			if (v[minid][0] > v[i][0])minid = i;
			if (v[maxid].back() < v[i].back())maxid = i;
		}
	}
	int maxDistance(vector<vector<int>>& v) {
		int minid = 0, maxid = 0;
		minmax(v, minid, maxid);
		int a = v[minid][0], b = v[maxid].back();
		if (minid != maxid)return b - a;
		v.erase(v.begin() + minid);
		minmax(v, minid, maxid);
		int c = v[minid][0], d = v[maxid].back();
		return max(b - c, d - a);
	}
};

class Solution {
public:
	int smallestFactorization(int num) {
        if(num==1)return 1;
		int a2 = 0, a3 = 0, a5 = 0, a7 = 0;
		while (num % 2 == 0)a2++, num /= 2;
		while (num % 3 == 0)a3++, num /= 3;
		while (num % 5 == 0)a5++, num /= 5;
		while (num % 7 == 0)a7++, num /= 7;
		if (num > 1)return 0;
		vector<int>vf;
		while (a7--)vf.push_back(7);
		while (a5--)vf.push_back(5);
		while (a2 >= 3)a2 -= 3, vf.push_back(8);
		while (a3 >= 2)a3 -= 2, vf.push_back(9);
		int k = 1;
		while (a2--)k *= 2;
		while (a3--)k *= 3;
		if (k == 12)vf.push_back(2), vf.push_back(6);
		else if (k > 1)vf.push_back(k);
		if (vf.size() > 10)return 0;
		sort(vf.begin(), vf.end());
		long long n = 0;
		for (auto& vi : vf)n *= 10, n += vi;
		if (n > INT_MAX)return 0;
		return n;
	}
};

class Solution {
public:
	int smallestFactorization(int num) {
		if (num == 1)return 1;
		vector<int>vf;
		for (int i = 9; i > 1; i--)while (num % i == 0)num/=i, vf.insert(vf.begin(),i);
		if (num>1 || vf.size() > 10)return 0;
		long long n = 0;
		for (auto& vi : vf)n *= 10, n += vi;
		if (n > INT_MAX)return 0;
		return n;
	}
};

class Solution {
public:
	double findMaxAverage(vector<int>& nums, int k) {
		int s = 0;
		for (int i = 0; i < k; i++)s += nums[i];
		double ans = s;
		for (int i = k; i < nums.size(); i++) {
			s += nums[i] - nums[i - k], ans = max(ans, s*1.0);
		}
		return ans / k;
	}
};

#define op(a,b) (a<b)?a:b //min型
int n;
int num[100000];
int ans[400000];

void build(int key, int low, int high)
{
	if (low == high)
	{
		ans[key] = num[low];
		return;
	}
	int mid = (low + high) / 2;
	build(key * 2, low, mid);
	build(key * 2 + 1, mid + 1, high);
	ans[key] = op(ans[key * 2], ans[key * 2 + 1]);
}

void update(int key, int low, int high, int uplace)
{
	if (low == high)
	{
		ans[key] = num[low];
		return;
	}
	int mid = (low + high) / 2;
	if (uplace <= mid)update(key * 2, low, mid, uplace);
	else update(key * 2 + 1, mid + 1, high, uplace);
	ans[key] = op(ans[key * 2], ans[key * 2 + 1]);
}

int query(long long key, int low, int high, int x, int y)
{
	if (low == x && high == y)return ans[key];
	int mid = (low + high) / 2;
	if (mid < x)return query(key * 2 + 1, mid + 1, high, x, y);
	if (mid >= y)return query(key * 2, low, mid, x, y);
	int a = query(key * 2, low, mid, x, mid);
	int b = query(key * 2 + 1, mid + 1, high, mid + 1, y);
	return  op(a, b);
}

class Solution {
public:
	int kEmptySlots(vector<int>& bulbs, int k) {
		n = bulbs.size();
		int ans = INT_MAX;
		for (int i = 0; i < n; i++)num[bulbs[i]] = i;
		if (k == 0) {
			for (int i = 1; i < n; i++)ans = ans = min(ans, max(num[i], num[i + 1]) + 1);
			return ans;
		}
		build(1, 1, n);
		for (int i = 0; i + k + 1 < n; i++) {
			if (i % 1000 == 0)cout << i;
			int q = query(1, 1, n, i + 2, i + k + 1);
			if (q < num[i+1] || q < num[i + k + 2])continue;
			ans = min(ans, max(num[i + 1], num[i + k + 2]) + 1);
		}
		if (ans == INT_MAX)ans = -1;
		return ans;
	}
};

class Solution {
public:
	bool hasAlternatingBits2(int n) {
		if (n == 0)return true;
		if (n % 4 == 1)return hasAlternatingBits2(n / 4);
		return false;
	}
	bool hasAlternatingBits(int n) {
		if (n % 2 == 0)n /= 2;
		return hasAlternatingBits2(n);
	}
};

int s[16];
 
class Solution {
public:
    bool canPartitionKSubsets(vector<int> &nums, int k, int deep)
    {
        if (deep >= nums.size())return true;
        for (int j = 0; j <= deep && j < k; j++) {
            if (s[j] < nums[deep])continue;
            s[j] -= nums[deep];
            if (canPartitionKSubsets(nums, k, deep + 1))return true;
            s[j] += nums[deep];
        }
        return false;
    }
    bool canPartitionKSubsets(vector<int> &nums, int k)
    {
        if (nums.size() < k || k <= 0 || k > 16)return false;
        sort(nums.begin(),nums.end(),greater<int>());
        int anss = 0;
        for (auto it = nums.begin(); it != nums.end(); it++) anss += *it;
        if (anss % k) return false;
        anss /= k;
        for (int i = 0; i < k; i++) s[i] = anss;
        return canPartitionKSubsets(nums, k, 0);
    }
};

map<string,int>exitt;
map<string,int>m;

void init(vector<string>& words)
{
    exitt.clear();
    m.clear();
    for(int i=0;i<words.size();i++){
        exitt[words[i]]=1;
    }
}

string preString(string s)
{
    if(s.length()<=1){
        return "";
    }
    return s.substr(0,s.length()-1);
}

int dp(string s)
{
    if(m[s])return m[s];
    if(s.length()==1)return 1;
    if(exitt[preString(s)] && dp(preString(s))>0)return m[s]=dp(preString(s))+1;
    return m[s]=-1;
}

class Solution {
public:
    string longestWord(vector<string>& words) {
        init(words);
        string ans="";
        for(int i=0;i<words.size();i++){
            int ret=dp(words[i]);
            if(ret==-1)continue;
            if(ans.length()<words[i].length() || ans.length()==words[i].length() && ans>words[i])
                ans=words[i];
        }
        cout<<exitt["e"];
        return ans;
    }
};

class Solution {
public:
	int monotoneIncreasingDigits(int N) {
		int key = 1111111111, ans = 0, num = 9;
		while (key)
		{
			while (N >= key && num > 0)
			{
				N -= key, ans += key, num--;
			}
			key /= 10;
		}
		return ans;
	}
};

class Solution {
public:
    int s[10001];
    int ans[10001];
    int dp(int k)
    {
        if(k<0)return 0;
        if(ans[k])return ans[k];
        return ans[k]=max(s[k]+dp(k-2),dp(k-1));
    }
    int deleteAndEarn(vector<int>& nums) {
        if(nums.size()==0)return 0;
        memset(ans,0,sizeof(int)*10001);
        memset(s,0,sizeof(int)*10001);
        for(int i=0;i<nums.size();i++)s[nums[i]]+=nums[i];
        return dp(10000);
    }
};

class Solution {
public:
	map< TreeNode*, int>m;
	map< TreeNode*, int>m2;
	bool flag;
	int dfs(TreeNode* root, int& num)
	{
		if (!root->left && !root->right) {
			m[root] = 1, num = m2[root] = root->val;
			return 1;
		}
		int deep = INT_MAX;
		if (root->left)deep = dfs(root->left, num) + 1, m2[root] = num;
		if (root->right) {
			int ret = dfs(root->right, num);
			if (deep > ret + 1) {
				deep = min(deep, ret + 1), m2[root] = num;
			}
			else num = m2[root];
		}
		m[root] = deep;
		return deep;
	}
	int dfs2(TreeNode* root, int k, int n, int& num) {
		if (root->val == k) {
			int ans = m[root];
			num = m2[root];
			return min(ans, n + 1);
		}
		if (root->left) {
			int ans = dfs2(root->left, k, min(n + 1, m[root]), num);
			if (flag && ans == min(n + 1, m[root]) + 1)num = m2[root];
			else if (ans != -1) {
				flag = false;
				return ans + 1;
			}
			if (ans != -1)return ans - 1;
		}
		if (root->right) {
			int ans = dfs2(root->right, k, min(n + 1, m[root]), num);
			if (flag && ans == min(n + 1, m[root]) + 1)num = m2[root];
			else if (ans != -1) {
				flag = false;
				return ans + 1;
			}
			if (ans != -1)return ans - 1;
		}
		return -1;
	}
	int findClosestLeaf(TreeNode* root, int k) {
		int num;
		flag = true;
		dfs(root, num);
		dfs2(root, k, m[root] - 1, num);
		return num;
	}
};

class Solution {
public:
	int hammingWeight(int n) {
		int ans = 0;
		while (n)
		{
			n ^= (n&(-n));
			ans++;
		}
		return ans;
	}
	int countPrimeSetBits(int L, int R) {
		set<int>se = { 2, 3, 5, 7 ,11,13,17,19};
		int ans = 0;
		for (int i = L; i <= R; i++)
		{
			if (se.find(hammingWeight(i)) != se.end())ans++;
		}
		return ans;
	}
};

class Solution {
public:
	bool ok(vector<int>& stations, int k, double d)
	{
		int s = 0;
		for (int i = 1; i < stations.size(); i++)s += (stations[i] - stations[i - 1]) / d;
		return s <= k;
	}
	double minmaxGasDist(vector<int>& stations, int k) {
		double low = 1.0 / k, high = stations.back() - stations[0];
		while (high - low > 0.00001) {
			double mid = (low + high) / 2;
			if (ok(stations, k, mid))high = mid;
			else low = mid;
		}
		return high;
	}
};

输入：color = "#09f166"
输出："#11ee66"
解释： 
因为相似度计算得出 -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73
这已经是所有可以简写的颜色中最相似的了

输入：color = "#4e3fe1"
输出："#5544dd"

class Solution {
public:
	int toNum(char c)
	{
		if (c >= '0' && c <= '9')return c - '0';
		return c - 'a' + 10;
	}
	char toChar(int n)
	{
		char ans = '0';
		if (n < 10)return ans + n;
		ans = 'a';
		return ans + n - 10;
	}
	string similarRGB(string color) {
		for (int i = 1; i < color.size(); i += 2) {
			int x = toNum(color[i]);
			int y = toNum(color[i+1]);
			int s = x * 16 + y;
			int k = 0, d = INT_MAX;
			for (int i = 0; i < 16; i++) {
				s -= i * 17;
				if (s * s < d)d = s * s, k = i;
				s+= i * 17;
			}
			color[i] = toChar(k);
			color[i+1] = toChar(k);
		}
		return color;
	}
};