# LeetCode Super Pow

LeetCode Super Pow
Your task is to calculate ab mod 1337 where a is a positive integer and b is an extremely large positive integer given in the form of an array.
Example1:

a = 2
b = [3]
Result: 8


Example2:

a = 2
b = [1,0]
Result: 1024

typedef unsigned long long ull;
class Solution {
private:
const static int MOD = 1337;
ull fastPow(ull x, ull y) {
ull ans = 1;
while (y) {
if (y & 1)ans = (ans*x) % MOD;
y >>= 1;
x = (x*x) % MOD;
}
return ans;
}
public:
int superPow(int a, vector<int>& b) {
ull ans = 1;
for (int i = 0; i < b.size(); ++i) {
ans = fastPow(ans, 10)*fastPow(a, b[i]) % MOD;
}
return ans;
}
};


# LeetCode Valid Square

LeetCode Valid Square
Given the coordinates of four points in 2D space, return whether the four points could construct a square.
The coordinate (x,y) of a point is represented by an integer array with two integers.
Example:

Input: p1 = [0,0], p2 = [1,1], p3 = [1,0], p4 = [0,1]
Output: True


Note:

1. All the input integers are in the range [-10000, 10000].
2. A valid square has four equal sides with positive length and four equal angles (90-degree angles).
3. Input points have no order.

p3------p4
|       |
|       |
p1------p2


class Solution2 {
private:
// 计算距离的平方
int distSquare(const vector<int>& p1, const vector<int>& p2) {
return (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
}
// 判断直线(p1,p2)和直线(p3,p4)是否垂直
bool isVertical(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
return (p2[0] - p1[0])*(p4[0] - p3[0]) + (p2[1] - p1[1])*(p4[1] - p3[1]) == 0;
}
// 在2|p1p2|==2|p1p3|==|p1p4|的条件下，判断是否能形成正方形
bool helper(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
if (!isVertical(p1, p2, p1, p3))return false;
if (!isVertical(p4, p3, p4, p2))return false;
int len2 = distSquare(p4, p2), len3 = distSquare(p4, p3);
return len2 == len3;
}
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
int len2 = distSquare(p1, p2), len3 = distSquare(p1, p3), len4 = distSquare(p1, p4);
if (len2 == 0 || len3 == 0 || len4 == 0)return false;
if (len2 == len3 && 2 * len2 == len4) return helper(p1, p2, p3, p4);
if (len2 == len4 && 2 * len2 == len3) return helper(p1, p2, p4, p3);
if (len3 == len4 && 2 * len3 == len2) return helper(p1, p3, p4, p2);
return false;
}
};


class Solution {
private:
// 计算距离的平方
int distSquare(const vector<int>& p1, const vector<int>& p2) {
return (p1[0] - p2[0])*(p1[0] - p2[0]) + (p1[1] - p2[1])*(p1[1] - p2[1]);
}
public:
bool validSquare(vector<int>& p1, vector<int>& p2, vector<int>& p3, vector<int>& p4) {
unordered_map<int, int> umdist;
vector<vector<int>> points = { p1,p2,p3,p4 };
for (int i = 0; i < 4; ++i) {
for (int j = i + 1; j < 4; ++j) {
int dist = distSquare(points[i], points[j]);
if (dist == 0)return false;
++umdist[dist];
}
}
return umdist.size() == 2;
}
};


# LeetCode Array Nesting

LeetCode Array Nesting
A zero-indexed array A consisting of N different integers is given. The array contains all integers in the range [0, N - 1].
Sets S[K] for 0 <= K < N are defined as follows:
S[K] = { A[K], A[A[K]], A[A[A[K]]], ... }.
Sets S[K] are finite for each K and should NOT contain duplicates.
Write a function that given an array A consisting of N integers, return the size of the largest set S[K] for this array.
Example 1:

Input: A = [5,4,0,3,1,6,2]
Output: 4
Explanation:
A[0] = 5, A[1] = 4, A[2] = 0, A[3] = 3, A[4] = 1, A[5] = 6, A[6] = 2.
One of the longest S[K]:
S[0] = {A[0], A[5], A[6], A[2]} = {5, 6, 2, 0}


Note:

1. N is an integer within the range [1, 20,000].
2. The elements of A are all distinct.
3. Each element of array A is an integer within the range [0, N-1].

class Solution {
private:
int nest(vector<int> &nums, vector<int> &visited, int k) {
int ans = 0;
while (visited[k] == 0) {
visited[k] = 1;
++ans;
k = nums[k];
}
return ans;
}
public:
int arrayNesting(vector<int>& nums) {
int n = nums.size();
vector<int> visited(n, 0);
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
if (visited[i] == 0) {
int cur = nest(nums, visited, i);
ans = max(ans, cur);
}
}
return ans;
}
};


# LeetCode Different Ways to Add Parentheses

LeetCode Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.
Example 1
Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]
Example 2
Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

class Solution {
private:
int operate(int a, int b, char c) {
switch (c) {
case '+':return a + b;
case '-':return a - b;
case '*':return a*b;
}
}
public:
vector<int> diffWaysToCompute(string input) {
int n = input.size();
vector<int> ans;
bool found = false;
for (int i = 0; i < n; ++i) {
if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
found = true;
vector<int> lefts = diffWaysToCompute(input.substr(0, i));
vector<int> rights = diffWaysToCompute(input.substr(i + 1));
for (int j = 0; j < lefts.size(); ++j) {
for (int k = 0; k < rights.size(); ++k) {
ans.push_back(operate(lefts[j], rights[k], input[i]));
}
}
}
}
if (!found)return{ atoi(input.c_str()) };
return ans;
}
};


# LeetCode Fraction Addition and Subtraction

Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should be irreducible fraction. If your final result is an integer, say 2, you need to change it to the format of fraction that has denominator 1. So in this case, 2 should be converted to 2/1.
Example 1:

Input:"-1/2+1/2"
Output: "0/1"


Example 2:

Input:"-1/2+1/2+1/3"
Output: "1/3"


Example 3:

Input:"1/3-1/2"
Output: "-1/6"


Example 4:

Input:"5/3+1/3"
Output: "2/1"


Note:

1. The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
2. Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
3. The input only contains valid irreducible fractions, where the numerator and denominator of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
4. The number of given fractions will be in the range [1,10].
5. The numerator and denominator of the final result are guaranteed to be valid and in the range of 32-bit int.

class Solution {
private:
int gcd(int x, int y) {
while (y) {
int tmp = x % y;
x = y;
y = tmp;
}
return x;
}
int lcm(int x, int y) {
return x * y / gcd(x, y);
}
public:
vector<int> num, denom; // 分子，分母
expression += "+"; // 哨兵
int i = 0, j = 0;
bool isnum = true;
for (j = 0; j < expression.size(); ++j) {
if (j != 0 && (expression[j] == '/' || expression[j] == '-' || expression[j] == '+')) {
int one = atoi(expression.substr(i, j - i).c_str());
if (isnum)num.push_back(one);
else denom.push_back(one);
isnum = !isnum;
if (expression[j] == '/') i = j + 1;
else i = j;
}
}
int fm = 1;
for (int i = 0; i < denom.size(); ++i)fm = lcm(fm, denom[i]);
int fz = 0;
for (int i = 0; i < num.size(); ++i)fz += num[i] * (fm / denom[i]);
int g = 0;
if (fz < 0)
g = gcd(-fz, fm);
else
g = gcd(fz, fm);
}
};


# LeetCode Optimal Division

LeetCode Optimal Division
Given a list of positive integers, the adjacent integers will perform the float division. For example, [2,3,4] -> 2 / 3 / 4.
However, you can add any number of parenthesis at any position to change the priority of operations. You should find out how to add parenthesis to get the maximum result, and return the corresponding expression in string format. Your expression should NOT contain redundant parenthesis.
Example:

Input: [1000,100,10,2]
Output: "1000/(100/10/2)"
Explanation:
1000/(100/10/2) = 1000/((100/10)/2) = 200
However, the bold parenthesis in "1000/((100/10)/2)" are redundant,
since they don't influence the operation priority. So you should return "1000/(100/10/2)".
Other cases:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2


Note:

1. The length of the input array is [1, 10].
2. Elements in the given array will be in range [2, 1000].
3. There is only one optimal division for each test case.

struct T {
double lfMax, lfMin;
string strMax, strMin;
};
class Solution {
private:
T optimal(vector<int>& nums, int start, int end){
T t;
if(start == end){
t.lfMax = t.lfMin = nums[start];
t.strMax = t.strMin = to_string(nums[start]);
return t;
}
t.lfMax = std::numeric_limits<double>::min();
t.lfMin = std::numeric_limits<double>::max();
for(int i = start; i < end; ++i){
T tl = optimal(nums, start, i);
T tr = optimal(nums, i + 1, end);
if(tl.lfMax / tr.lfMin > t.lfMax){
t.lfMax = tl.lfMax / tr.lfMin;
t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : "");
}
if(tl.lfMin / tr.lfMax < t.lfMin){
t.lfMin = tl.lfMin / tr.lfMax;
t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : "");
}
}
return t;
}
public:
string optimalDivision(vector<int>& nums) {
T t = optimal(nums, 0, nums.size() - 1);
return t.strMax;
}
};


struct T {
double lfMax, lfMin;
string strMax, strMin;
};
class Solution {
private:
T optimal(vector<int>& nums, int start, int end, vector<vector<T>>& memo){
if(memo[start][end].strMax != "" || memo[start][end].strMin != "") return memo[start][end];
T t;
if(start == end){
t.lfMax = t.lfMin = nums[start];
t.strMax = t.strMin = to_string(nums[start]);
memo[start][end] = t;
return t;
}
t.lfMax = std::numeric_limits<double>::min();
t.lfMin = std::numeric_limits<double>::max();
for(int i = start; i < end; ++i){
T tl = optimal(nums, start, i, memo);
T tr = optimal(nums, i + 1, end, memo);
if(tl.lfMax / tr.lfMin > t.lfMax){
t.lfMax = tl.lfMax / tr.lfMin;
t.strMax = tl.strMax + "/" + (i + 1 != end ? "(" : "") + tr.strMin + (i + 1 != end ? ")" : "");
}
if(tl.lfMin / tr.lfMax < t.lfMin){
t.lfMin = tl.lfMin / tr.lfMax;
t.strMin = tl.strMin + "/" + (i + 1 != end ? "(" : "") + tr.strMax + (i + 1 != end ? ")" : "");
}
}
memo[start][end] = t;
return t;
}
public:
string optimalDivision(vector<int>& nums) {
vector<vector<T>> memo(nums.size(), vector<T>(nums.size()));
T t = optimal(nums, 0, nums.size() - 1, memo);
return t.strMax;
}
};


class Solution {
public:
string optimalDivision(vector<int>& nums) {
int n = nums.size();
string ans = to_string(nums[0]) + "/(";
for(int i = 1; i < n - 1; ++i){
ans += to_string(nums[i]) + "/";
}
return ans + to_string(nums[n-1]) + ")";
}
};


# LeetCode Complex Number Multiplication

LeetCode Complex Number Multiplication
Given two strings representing two complex numbers.
You need to return a string representing their multiplication. Note i2 = -1 according to the definition.
Example 1:

Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.


Example 2:

Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.


Note:

1. The input strings will not have extra blank.
2. The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form.

class Solution {
void str2cpx(const string& s, int& c1, int&c2) {
int i = 0, j = 0;
while (s[j] != '+')++j;
c1 = atoi(s.substr(i, j - i).c_str());
i = ++j;
while (s[j] != 'i')++j;
c2 = atoi(s.substr(i, j - i).c_str());
}
public:
string complexNumberMultiply(string a, string b) {
int a1 = 0, a2 = 0, b1 = 0, b2 = 0, c1 = 0, c2 = 0;
str2cpx(a, a1, a2);
str2cpx(b, b1, b2);
c1 = a1*b1 - a2*b2;
c2 = a1*b2 + a2*b1;
}
};


# LeetCode Water and Jug Problem

LeetCode Water and Jug Problem
You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.
If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.
Operations allowed:

• Fill any of the jugs completely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.

Example 1: (From the famous "Die Hard" example)

Input: x = 3, y = 5, z = 4
Output: True


Example 2:

Input: x = 2, y = 6, z = 5
Output: False

1. 盛满5L水罐；
2. 将5L水罐中的水导入3L水罐，此时5L水罐中还剩2L水；
3. 将3L水罐中的水清空；
4. 将5L水罐中的2L水倒入3L水罐中；
5. 盛满5L水罐；
6. 将5L水罐中的水倒入3L水罐中，此时5L水罐中剩余4L水，3L水罐中是满的；
7. 将3L水罐中的水清空，此时只剩5L水罐中的4L水。

class Solution {
private:
int gcd(int x, int y) {
return y == 0 ? x : gcd(y, x%y);
}
public:
bool canMeasureWater(int x, int y, int z) {
return z == 0 || (x + y >= z&&z%gcd(x, y) == 0);
}
};


# LeetCode Lexicographical Numbers

LeetCode Lexicographical Numbers
Given an integer n, return 1 - n in lexicographical order.
For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].
Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

class Solution {
public:
vector<int> lexicalOrder(int n) {
vector<int> ans;
int cur = 1;
for (int i = 1; i <= n; ++i) {
ans.push_back(cur);
if (cur * 10 <= n)cur *= 10;
else if (cur % 10 != 9 && cur + 1 <= n)++cur;
else {
while ((cur / 10) % 10 == 9)cur /= 10;
cur = cur / 10 + 1;
}
}
return ans;
}
};


# LeetCode Bulb Switcher

LeetCode Bulb Switcher
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:

Given n = 3.
At first, the three bulbs are [off, off, off].
After first round, the three bulbs are [on, on, on].
After second round, the three bulbs are [on, off, on].
After third round, the three bulbs are [on, off, off].
So you should return 1, because there is only one bulb is on.

class Solution {
public:
int bulbSwitch(int n) {
if (n == 0)return 0;
vector<int> bulbs(n + 1, 1);
for (int i = 2; i <= n; ++i) {
for (int j = 1; j*i <= n; ++j)bulbs[j*i] = !bulbs[j*i];
}
int ans = 0;
for (int i = 1; i <= n; ++i)if (bulbs[i])++ans;
return ans;
}
};


1~n有floor(sqrt(n))个完全平方数，所以结果就是floor(sqrt(n))。

class Solution {
public:
int bulbSwitch(int n) {
return floor(sqrt(n));
}
};