# hihoCoder 1552-缺失的拼图

hihoCoder 1552-缺失的拼图

### 输出

5
0 0 4 5
0 0 3 1
0 1 2 5
3 0 4 5
2 2 3 5

2 1 3 2

#include<algorithm>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<set>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> Point;
int main() {
//freopen("input.txt", "r", stdin);
int n;
scanf("%d", &n);
map<Point, int> hash;
int a, b, c, d;
while (n--) {
Point left_bottom, right_top;
scanf("%d %d %d %d", &left_bottom.first, &left_bottom.second, &right_top.first, &right_top.second);
Point left_top = Point(left_bottom.first, right_top.second), right_bottom = Point(right_top.first, left_bottom.second);
++hash[left_bottom];
++hash[right_top];
++hash[left_top];
++hash[right_bottom];
}
set<Point> ans;
for (auto p : hash) {
if (p.second % 2 == 1) {
ans.insert(p.first);
}
}
a = c = ans.begin()->first;
b = d = ans.begin()->second;
for (auto p : ans) {
a = min(a, p.first);
b = min(b, p.second);
c = max(c, p.first);
d = max(d, p.second);
}
printf("%d %d %d %d\n", a, b, c, d);
return 0;
}


# hihoCoder 1543-SCI表示法

hihoCoder 1543-SCI表示法

### 输出

2
15
8

5
1

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
freopen("input.txt", "r", stdin);
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
if (n == 1 || n == 2) {
printf("1\n");
} else {
ll i = 1, j = 2;
ll sum = i + j, ans = 0;
while (true) {
while (j <= n && sum < n) {
++j;
sum += j;
}
if (j > n)break;
while (i < j && sum > n) {
sum -= i;
++i;
}
if (sum == n) {
//printf("%d\n", j - i + 1);
ans = max(ans, j - i + 1);
break;
}
}
printf("%lld\n", ans);
}
}
return 0;
}


#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;
typedef long long ll;
ll t, n;
int main() {
freopen("input.txt", "r", stdin);
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
if (n == 1 || n == 2) {
printf("1\n");
}
else {
ll ans = 1;
for (ll i = 1; i < n; ++i) {
ll sum = (1 + i)*i / 2;
if (sum > n)break;
ll left = sum - n;
if (left%i == 0) {
ans = max(ans, i);
}
}
printf("%lld\n", ans);
}
}
return 0;
}


# LeetCode 4 Keys Keyboard

LeetCode 4 Keys Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: (A): Prints one 'A' on screen.
Key 2: (Ctrl-A): Select the whole screen.
Key 3: (Ctrl-C): Copy selection to buffer.
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed.
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
Example 1:

Input: N = 3
Output: 3
Explanation:
We can at most get 3 A's on screen by pressing following key sequence:
A, A, A


Example 2:

Input: N = 7
Output: 9
Explanation:
We can at most get 9 A's on screen by pressing following key sequence:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V


Note:

1. 1 <= N <= 50
2. Answers will be in the range of 32-bit signed integer.

• A: 打印一个字符A
• Ctrl-A: 全选
• Ctrl-C: 复制
• Ctrl-V: 粘贴

class Solution {
public:
int maxA(int N) {
if (N <= 6)return N;
vector<int> dp(N + 1, 0);
for (int i = 1; i <= 6; ++i)dp[i] = i;
for (int i = 7; i <= N; ++i) {
for (int b = i - 3; b >= 1; --b) {
dp[i] = max(dp[i], dp[b] + dp[b] * (i - b - 2));
}
}
return dp[N];
}
};


# LeetCode Set Mismatch

LeetCode Set Mismatch
The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:

Input: nums = [1,2,2,4]
Output: [2,3]


Note:

1. The given array size will in the range [2, 10000].
2. The given array's numbers won't have any order.

class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
unordered_set<int> hash;
int sum = 0, n = nums.size();
for (const auto& num : nums) {
if (hash.find(num) != hash.end())ans[0] = num;
hash.insert(num);
sum += num;
}
ans[1] = ans[0] - sum + n*(n + 1) / 2;
return ans;
}
};


class Solution {
public:
vector<int> findErrorNums(vector<int>& nums) {
vector<int> ans(2, 0);
for (int i = 0; i < nums.size(); ++i) {
int idx = nums[i] < 0 ? -nums[i] : nums[i];
if (nums[idx - 1] < 0) {
ans[0] = idx;
} else {
nums[idx - 1] = -nums[idx - 1];
}
}
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] > 0) {
ans[1] = i + 1;
break;
}
}
return ans;
}
};


# LeetCode Solve the Equation

LeetCode Solve the Equation
Solve a given equation and return the value of x in the form of string "x=#value". The equation contains only '+', '-' operation, the variable xand its coefficient.
If there is no solution for the equation, return "No solution".
If there are infinite solutions for the equation, return "Infinite solutions".
If there is exactly one solution for the equation, we ensure that the value of x is an integer.
Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"


Example 2:

Input: "x=x"
Output: "Infinite solutions"


Example 3:

Input: "2x=x"
Output: "x=0"


Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"


Example 5:

Input: "x=x+2"
Output: "No solution"

class Solution {
private:
void convert(string& s, int& a, int& b) {
int aa = 0, bb = 0;
s += "+";
int start = 0, end = 0;
for (end = 0; end < s.size(); ++end) {
if (end != 0 && (s[end] == '+' || s[end] == '-')) { // -x=-1
string tmp = s.substr(start, end - start);
if (tmp.find('x') != string::npos) {
if (tmp == "x" || tmp == "+x")bb += 1;
else if (tmp == "-x")bb -= 1;
else bb += stoi(tmp.substr(0, tmp.size() - 1));
}
else {
aa += stoi(tmp);
}
start = end;
}
}
a = aa;
b = bb;
}
public:
string solveEquation(string equation) {
size_t pos = equation.find('=');
string left = equation.substr(0, pos), right = equation.substr(pos + 1);
int la = 0, lb = 0, ra = 0, rb = 0;
convert(left, la, lb);
convert(right, ra, rb);
int b = lb - rb, a = ra - la;
if (b == 0) {
if (a == 0)return "Infinite solutions";
else return "No solution";
}
else {
return "x=" + to_string(a / b);
}
}
};


# LeetCode Continuous Subarray Sum

LeetCode Continuous Subarray Sum
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.


Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.


Note:

1. The length of the array won't exceed 10,000.
2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

• [23,25,29,35,42]
• [5,1,5,5,0]

class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int, int> reminders;
reminders[0] = -1;
int accusum = 0;
for (int i = 0; i < nums.size(); ++i) {
accusum += nums[i];
if (k != 0)accusum %= k; // 注意k为0时，不能取模
if (reminders.find(accusum) != reminders.end()) {
if (i - reminders[accusum] >= 2)return true;
} else reminders[accusum] = i; // 注意必须是在else分支
}
return false;
}
};


# LeetCode Sum of Square Numbers

LeetCode Sum of Square Numbers
Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.
Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5


Example 2:

Input: 3
Output: False

class Solution {
public:
bool judgeSquareSum(int c) {
long long i = 0, j = sqrt(c) + 1;
while (i <= j) {
long long cur = i*i + j*j;
if (cur == c)return true;
else if (cur < c)++i;
else --j;
}
return false;
}
};


# LeetCode Minimum Factorization

LeetCode Minimum Factorization
Given a positive integer a, find the smallest positive integer b whose multiplication of each digit equals to a.
If there is no answer or the answer is not fit in 32-bit signed integer, then return 0.
Example 1
Input:

48

Output:

68

Example 2
Input:

15

Output:

35

class Solution {
public:
int smallestFactorization(int a) {
if (a < 10)return a;
vector<int> factors;
for (int i = 9; i >= 2; --i) {
while (a%i == 0) {
factors.push_back(i);
a /= i;
}
}
if (a != 1)return 0; // caution
long long ans = 0;
for (int i = factors.size() - 1; i >= 0; --i) {
ans = ans * 10 + factors[i];
}
return ans > INT_MAX ? 0 : ans;
}
};


# LeetCode Valid Triangle Number

LeetCode Valid Triangle Number
Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:

Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3


Note:

1. The length of the given array won't exceed 1000.
2. The integers in the given array are in the range of [0, 1000].

class Solution {
private:
void dfs(int &ans, vector<int>& nums, vector<int>& cand, int idx) {
if (cand.size() == 3) {
int &a = cand[0], &b = cand[1], &c = cand[2];
if (a + b > c&&a + c > b&&b + c > a) {
++ans;
//cout << a << "\t" << b << "\t" << c << endl;
}
return;
}
for (int i = idx; i < nums.size(); ++i) {
if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
cand.push_back(nums[i]);
dfs(ans, nums, cand, i + 1);
cand.pop_back();
}
}
public:
int triangleNumber(vector<int>& nums) {
int ans = 0;
vector<int> cand;
sort(nums.begin(), nums.end());
dfs(ans, nums, cand, 0);
return ans;
}
};


class Solution {
private:
void dfs(int& ans, vector<int>& count, vector<int>& nums, vector<int>& cand, int idx) {
if (cand.size() == 3) {
int &a = cand[0], &b = cand[1], &c = cand[2];
if (a + b > c&&a + c > b&&b + c > a) {
ans += count[a] * count[b] * count; // 三边各异
//cout << a << "\t" << b << "\t" << c << endl;
}
return;
}
for (int i = idx; i < nums.size(); ++i) {
if (cand.size() == 2 && cand[0] + cand[1] <= nums[i])return;
cand.push_back(nums[i]);
dfs(ans, count, nums, cand, i + 1);
cand.pop_back();
}
}
public:
int triangleNumber(vector<int>& nums) {
vector<int> mii(1001, 0);
for (const auto& i : nums)++mii[i]; // hash
vector<int> distinct;
for (int i = 1; i < 1001; ++i) {
if (mii[i] > 0)distinct.push_back(i);
}
int ans = 0;
vector<int> cand;
dfs(ans, mii, distinct, cand, 0); // 三边互不相同
int n = distinct.size();
for (int i = 0; i < n; ++i) {
if (mii[distinct[i]] >= 3) { // 三边相同
int &d = mii[distinct[i]];
ans += (d*(d - 1)*(d - 2)) / 6;
}
for (int j = i + 1; j < n; ++j) {
if (mii[distinct[i]] >= 2) { // 两条边一样
int &a = distinct[i], &b = distinct[i], &c = distinct[j];
if (a + b > c&&a + c > b&&b + c > a) {
ans += (mii[a] * (mii[a] - 1) / 2)*mii;
}
}
if (mii[distinct[j]] >= 2) { // 两条边一样
int &a = distinct[i], &b = distinct[j], &c = distinct[j];
if (a + b > c&&a + c > b&&b + c > a) {
ans += (mii[b] * (mii[b] - 1) / 2)*mii[a];
}
}
}
}
return ans;
}
};


# LeetCode Rotate Function

LeetCode Rotate Function
Given an array of integers A and let n to be its length.
Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a "rotation function" F on A as follow:
F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].
Calculate the maximum value of F(0), F(1), ..., F(n-1).
Note:
n is guaranteed to be less than 105.
Example:

A = [4, 3, 2, 6]
F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

class Solution {
public:
int maxRotateFunction(vector<int>& A) {
if (A.empty())return 0;
int ans = INT_MIN, n = A.size();
for (int k = 0; k < n; ++k) {
int cur = 0;
for (int i = 0; i < n; ++i) {
cur += ((k + i) % n)*A[i];
}
ans = max(ans, cur);
}
return ans;
}
};


class Solution {
public:
int maxRotateFunction(vector<int>& A) {
if (A.empty())return 0;
int n = A.size(), sum = 0, f0 = 0;
for (int i = 0; i < n; ++i) {
sum += A[i];
f0 += i*A[i];
}
int ans = f0, pre = f0;
for (int i = 1; i < n; ++i) {
int cur = pre + sum - n * A[n - i];
ans = max(ans, cur);
pre = cur;
}
return ans;
}
};