# 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();
else if(n == 2) return to_string(nums[0]) + "/" + to_string(nums[1]);
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 Binary Tree Tilt

LeetCode Binary Tree Tilt
Given a binary tree, return the tilt of the whole tree.
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.
The tilt of the whole tree is defined as the sum of all nodes' tilt.
Example:

Input:
1
/   \
2     3
Output: 1
Explanation:
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1


Note:

1. The sum of node values in any subtree won't exceed the range of 32-bit integer.
2. All the tilt values won't exceed the range of 32-bit integer.

class Solution {
private:
void dfs(TreeNode* root, int& sum, int& tilt){
if(root == NULL) {
sum = 0;
tilt = 0;
} else {
int lsum = 0, rsum = 0, ltilt = 0, rtilt = 0;
dfs(root->left, lsum, ltilt);
dfs(root->right, rsum, rtilt);
sum = lsum + rsum + root->val;
tilt = ltilt + rtilt + abs(lsum - rsum);
}
}
public:
int findTilt(TreeNode* root) {
int sum = 0, tilt = 0;
dfs(root, sum, tilt);
return tilt;
}
};


# LeetCode Array Partition I

LeetCode Array Partition I
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), ..., (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:

Input: [1,4,3,2]
Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4.


Note:

1. n is a positive integer, which is in the range of [1, 10000].
2. All the integers in the array will be in the range of [-10000, 10000].

class Solution {
public:
int arrayPairSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
int ans = 0;
for(int i = 0; i < nums.size(); i += 2) ans += nums[i];
return ans;
}
};


# LeetCode Student Attendance Record II

LeetCode Student Attendance Record II
Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 109 + 7.
A student attendance record is a string that only contains the following three characters:

1. 'A' : Absent.
2. 'L' : Late.
3. 'P' : Present.

A record is regarded as rewardable if it doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
Example 1:

Input: n = 2
Output: 8
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times.


Note: The value of n won't exceed 100,000.

dp[n][0][0]=sum(dp[n-1][0])：要求长度为n、包含0个'A'，且以0个'L'结尾的字符串个数；所以前n-1肯定也只包含0个'A'，但是前n-1可以以0、1或2个'L'结尾，因为我第n个字符不放'L'就能保证前n以0个'L'结尾。所以dp[n][0][0]=sum(dp[n-1][0])。其他的类似分析有：

• dp[n][0][1]=dp[n-1][0][0]
• dp[n][0][2]=dp[n-1][0][1]
• dp[n][1][0]=sum(dp[n-1][0])+sum(dp[n-1][1])
• dp[n][1][1]=dp[n-1][1][0]
• dp[n][1][2]=dp[n-1][1][1]

const int kMOD = 1000000007;
class Solution {
private:
long long getSum(vector<int>& v) {
long long ans = 0;
for(const int &i : v) ans += i;
return ans % kMOD;
}
public:
int checkRecord(int n) {
vector<vector<int>> dp = {{1, 1, 0}, {1, 0, 0}};
for(int i = 2; i <= n; ++i){
vector<vector<int>> ndp = {{0, 0, 0}, {0, 0, 0}};
ndp[0][0] = getSum(dp[0]);
ndp[0][1] = dp[0][0];
ndp[0][2] = dp[0][1];
ndp[1][0] = (getSum(dp[1]) + getSum(dp[0])) % kMOD;
ndp[1][1] = dp[1][0];
ndp[1][2] = dp[1][1];
dp = ndp;
}
return (getSum(dp[0]) + getSum(dp[1])) % kMOD;
}
};


# LeetCode Student Attendance Record I

LeetCode Student Attendance Record I
You are given a string representing an attendance record for a student. The record only contains the following three characters:

1. 'A' : Absent.
2. 'L' : Late.
3. 'P' : Present.

A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).
You need to return whether the student could be rewarded according to his attendance record.
Example 1:

Input: "PPALLP"
Output: True


Example 2:

Input: "PPALLL"
Output: False

class Solution {
public:
bool checkRecord(string s) {
int n = s.size();
int A = 0, L = 0;
for(size_t i = 0; i < n; ++i){
if(s[i] == 'A'){
++A;
if(A > 1) return false;
}
else if(s[i] == 'L'){
int tmp = 0;
while(i < n && s[i] == 'L'){
++tmp;
++i;
}
--i; // caution
L = max(tmp, L);
if(L > 2) return false;
}
}
return true;
}
};


# LeetCode Longest Uncommon Subsequence I

LeetCode Longest Uncommon Subsequence I
Given a group of two strings, you need to find the longest uncommon subsequence of this group of two strings. The longest uncommon subsequence is defined as the longest subsequence of one of these strings and this subsequence should not be any subsequence of the other strings.
A subsequence is a sequence that can be derived from one sequence by deleting some characters without changing the order of the remaining elements. Trivially, any string is a subsequence of itself and an empty string is a subsequence of any string.
The input will be two strings, and the output needs to be the length of the longest uncommon subsequence. If the longest uncommon subsequence doesn't exist, return -1.
Example 1:

Input: "aba", "cdc"
Output: 3
Explanation: The longest uncommon subsequence is "aba" (or "cdc"),
because "aba" is a subsequence of "aba",
but not a subsequence of any other strings in the group of two strings.


Note:

1. Both strings' lengths will not exceed 100.
2. Only letters from a ~ z will appear in input strings.

class Solution {
public:
int findLUSlength(string a, string b) {
return a == b ? -1 : max(a.size(), b.size());
}
};


# LeetCode Reverse Words in a String III

LeetCode Reverse Words in a String III
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.
Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"


Note: In the string, each word is separated by single space and there will not be any extra space in the string.

class Solution {
public:
string reverseWords(string s) {
int i = 0, j = 0, n = s.size();
while (j < n) {
while (j < n&&s[j] != ' ')++j;
reverse(s.begin() + i, s.begin() + j);
i = ++j;
}
return s;
}
};


# hihoCoder 1507-可疑的记录

hihoCoder 1507-可疑的记录

### 输出

3
1 2
1 3
1 3

2 3

1. 首先，如果这一行x,y中y如果出现1，则这一行肯定是有问题的，因为1是根节点，不可能在右边。
2. 其次，如果出现x==y，也有问题，因为树没有自回路。
3. 最后，正常的树中除了根节点，每个节点有且仅有一个父亲节点，如果添加了一行，且不满足上面两种情况，则肯定会出现某个点的父亲节点有两个！所以我们只需要找出出现两个父亲节点的节点即可，而且这两个父亲都有可疑。

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int n, x, y;
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d", &n);
vector<int> xarry(n + 1, 0), yarry(n + 1, 0);
for (int i = 0; i < n; ++i) {
scanf("%d %d", &xarry[i], &yarry[i]);
}
vector<vector<int>> parent(n + 1, vector<int>());
for (int i = 0; i < n; ++i) {
if (yarry[i] == 1) { // 根节点不可能在右边
printf("%d\n", i + 1);
break;
}
if (xarry[i] == yarry[i]) { // 没有自回路
printf("%d\n", i + 1);
break;
}
parent[yarry[i]].push_back(i + 1);
}
for (int i = 1; i <= n; ++i) {
if (parent[i].size() > 1) {
printf("%d %d ", parent[i][0], parent[i][1]);
break; // 因为只添加了一行，所以只可能有一个节点有两个父亲
}
}
return 0;
}


# hihoCoder 1508-剑刃风暴

hihoCoder 1508-剑刃风暴

### 输出

10 2
0 10
0 10
9 10
1 2
4 5
8 8
8 4
4 2
7 7
0 7

3

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 2005;
const double PI = acos(-1.0);
//const double R = 1.0;//定义覆盖圆半径为R
int T, n, total, R;
struct Point {
double x, y;
}point[MAX_N];
struct Angle {
double data;
int is;
bool operator < (const Angle& rhs) const {
return data<rhs.data;
}
}angle[MAX_N * 2];
inline double Dis(Point a, Point b)//计算线段ab的长度
{
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
inline double God(Point a, Point b)//计算向量ab的极角
{
double res = atan(fabs((b.y - a.y) / (b.x - a.x)));
if (b.y<a.y) {
if (b.x<a.x) res += PI;
else res = 2 * PI - res;
}
else {
if (b.x<a.x) res = PI - res;
}
return res;
}
void solve()
{
int res = 1;
for (int i = 0; i<n; i++) {
total = 0;
for (int j = 0; j<n; j++) {
if (i == j) continue;
double dist = Dis(point[i], point[j]);
if (dist>2.0 * R) continue;
double base = God(point[i], point[j]);
double extra = acos((dist / 2.0) / R); //计算差角
angle[total].data = base - extra; // in
angle[total++].is = 1;
angle[total].data = base + extra; // out
angle[total++].is = -1;
}
if (total <= res) continue;
sort(angle, angle + total);
int tmp = 1;
for (int j = 0; j<total; j++) {
tmp += angle[j].is;
res = max(res, tmp);
}
}
printf("%d\n", res);
}
int main()
{
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &R);
for (int i = 0; i<n; i++) {
scanf("%lf %lf", &point[i].x, &point[i].y);
}
solve();
return 0;
}


# hihoCoder 1506-投掷硬币

hihoCoder 1506-投掷硬币

### 输出

2 1
0.5 0.5

0.500000

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
double ans = 0;
int n, m;
void dfs(const vector<double>& probs, double curprob, int step, int up) {
if (up == m) {
double oneans = curprob;
for (int i = step; i < n; ++i)oneans *= (1 - probs[i]);
ans += oneans;
return;
}
if (step < n) {
dfs(probs, curprob*probs[step], step + 1, up + 1);
dfs(probs, curprob*(1 - probs[step]), step + 1, up);
}
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
vector<double> probs(n, 0);
for (int i = 0; i < n; ++i) scanf("%lf", &probs[i]);
dfs(probs, 1, 0, 0);
printf("%lf\n", ans);
return 0;
}


#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
int main() {
//freopen("input.txt", "r", stdin);
int n, m;
scanf("%d %d", &n, &m);
vector<double> probs(n + 1, 0);
for (int i = 1; i <= n; ++i)scanf("%lf", &probs[i]);
vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
dp[0][0] = 1.0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) { //现在有i枚硬币，所以正面向上的个数j不超过i
dp[i][j] += dp[i - 1][j - 1] * probs[i];  // head
dp[i][j - 1] += dp[i - 1][j - 1] * (1 - probs[i]); // tail
}
}
printf("%lf\n", dp[n][m]);
return 0;
}