# hihoCoder 1550-顺序三元组

hihoCoder 1550-顺序三元组

### 输出

6
1 3 2 1 2 3

3

#include<algorithm>
#include<vector>
#include<iostream>
#include<map>
using namespace std;
typedef long long ll;
int main() {
//freopen("input.txt", "r", stdin);
int n = 0;
scanf("%d", &n);
vector<int> nums(n, 0);
map<int, int> left, right;
for (int i = 0; i < n; ++i) {
scanf("%d", &nums[i]);
++right[nums[i]];
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
--right[nums[i]];
if (nums[i] == 2) {
ans += left[1] * right[3];
}
++left[nums[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 2 Keys Keyboard

LeetCode 2 Keys Keyboard
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1. Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).
2. Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
Example 1:

Input: 3
Output: 3
Explanation:
Intitally, we have one character 'A'.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get 'AA'.
In step 3, we use Paste operation to get 'AAA'.


Note:

1. The n will be in the range [1, 1000].

class Solution {
private:
struct Node {
int presented_cnt_; // 现在有多少个字符
int copied_cnt_; // 剪切板中有多少个字符
int step_; // 走过多少步了
Node(int p, int c, int s) :presented_cnt_(p), copied_cnt_(c), step_(s) {};
};
public:
int minSteps(int n) {
queue<Node> q;
Node node(1, 0, 0);
q.push(node);
while (!q.empty()) {
Node cur = q.front();
q.pop();
if (cur.presented_cnt_ == n)
return cur.step_;
if (cur.presented_cnt_ > n)continue;
Node copy_node(cur.presented_cnt_, cur.presented_cnt_, cur.step_ + 1); // 全选
q.push(copy_node);
if (cur.copied_cnt_ != 0) { // 粘贴
Node paste_node(cur.presented_cnt_ + cur.copied_cnt_, cur.copied_cnt_, cur.step_ + 1);
q.push(paste_node);
}
}
}
};


class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[1] = 0;
for (int i = 2; i <= n; ++i) {
dp[i] = i;
for (int j = i - 1; j >= 1; --j) {
if (i%j == 0) {
dp[i] = min(dp[i], dp[j] + i / j);
}
}
}
return dp[n];
}
};


class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[1] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 2 * i, k = 2; j <= n; j += i, ++k) {
dp[j] = min(dp[j], dp[i] + k);
}
}
return dp[n];
}
};


# LeetCode Palindromic Substrings

LeetCode Palindromic Substrings
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".


Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".


Note:

1. The input string length won't exceed 1000.

class Solution {
public:
int countSubstrings(string s) {
int ans = 0, n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
++ans;
}
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n; ++i) {
int j = i + len - 1;
if (j >= n)break;
if (s[i] == s[j] && (len == 2 || dp[i + 1][j - 1] == 1)) {
dp[i][j] = 1;
++ans;
}
}
}
return ans;
}
};


# LeetCode Maximum Length of Pair Chain

LeetCode Maximum Length of Pair Chain
You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
Example 1:

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]


Note:

1. The number of given pairs will be in the range [1, 1000].

bool cmp(const vector<int>& p1, const vector<int>& p2) {
return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]);
}
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), cmp);
int n = pairs.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = 0;
dp[0][1] = 1;
int ans = 1;
for (int i = 1; i < n; ++i) {
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = 1;
int j = i - 1;
while (j >= 0 && pairs[i][0] <= pairs[j][1]) {
--j;
}
if (j >= 0) {
dp[i][1] = max(dp[i][1], dp[j][1] + 1);
}
ans = max(ans, dp[i][0]);
ans = max(ans, dp[i][1]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[0] < p2[0] || (p1[0] == p2[0] && p1[1] < p2[1]); });
int n = pairs.size(), ans = 1;
vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = i - 1; j >= 0; --j) {
if (pairs[i][0] > pairs[j][1]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
ans = max(ans, dp[i]);
}
return ans;
}
};


class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), [](const vector<int>& p1, const vector<int>& p2) {return p1[1] < p2[1]; });
int ans = 0;
for (int i = 0, j = 0; j < pairs.size(); ++j) {
if (j == 0 || pairs[j][0] > pairs[i][1]) {
++ans;
i = j;
}
}
return ans;
}
};


# LeetCode Maximum Average Subarray I

LeetCode Maximum Average Subarray I
Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75


Note:

1. 1 <= k <= n <= 30,000.
2. Elements of the given array will be in the range [-10,000, 10,000].

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


# LeetCode Shopping Offers

LeetCode Shopping Offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and$5 respectively.
In special offer 1, you can pay $5 for 3A and 0B In special offer 2, you can pay$10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and$4 for 2A.


Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and$3 for B, $4 for C. You may pay$4 for 1A and 1B, and $9 for 2A ,2B and 1C. You need to buy 1A ,2B and 1C, so you may pay$4 for 1A and 1B (special offer #1), and $3 for 1B,$4 for 1C.
You cannot add more items, though only \$9 for 2A ,2B and 1C.


Note:

1. There are at most 6 kinds of items, 100 special offers.
2. For each item, you need to buy at most 6 of them.
3. You are not allowed to buy more items than you want, even if that would lower the overall price.

class Solution {
private:
int dot(vector<int>& price, vector<int>& needs) {
int ans = 0;
for (int i = 0; i < needs.size(); ++i) {
ans += price[i] * needs[i];
}
return ans;
}
int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
if (idx == special.size())return dot(price, needs); // 原价购买
int i = 0, n = special[idx].size();
vector<int> small_needs = needs;
for (i = 0; i < n - 1; ++i) {
if (special[idx][i] > needs[i])break;
small_needs[i] -= special[idx][i];
}
if (i == n - 1)return min(shopping(price, special, small_needs, idx) + special[idx][n - 1], shopping(price, special, needs, idx + 1));
else return shopping(price, special, needs, idx + 1);
}
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return shopping(price, special, needs, 0);
}
};


# LeetCode Decode Ways II

LeetCode Decode Ways II
A message containing letters from A-Z is being encoded to numbers using the following mapping way:

'A' -> 1
'B' -> 2
...
'Z' -> 26


Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:

Input: "*"
Output: 9
Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".


Example 2:

Input: "1*"
Output: 9 + 9 = 18


Note:

1. The length of the input string will fit in range [1, 105].
2. The input string will only contain the character '*' and digits '0' - '9'.

const int MOD = 1000000007;
typedef long long ll;
class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++)
{
if (s[i] >= '1' && s[i] <= '9')
dp[i] += dp[i - 1] % MOD; // 独自解析
if ((s[i - 1] == '1' && s[i] >= '0' && s[i] <= '9') || (s[i - 1] == '2' && s[i] >= '0' && s[i] <= '6'))
dp[i] += dp[i - 2] % MOD;
if (s[i - 1] == '*'&&s[i] >= '0'&&s[i] <= '9') {
if (s[i] >= '0'&&s[i] <= '6')dp[i] += dp[i - 2] * 2 % MOD;
if (s[i] > '6')dp[i] += dp[i - 2] % MOD;
}
if (s[i] == '*') {
dp[i] += dp[i - 1] * 9 % MOD; // 独自解析
if (s[i - 1] != '*') {
if (s[i - 1] == '1')dp[i] += dp[i - 2] * 9 % MOD;
else if (s[i - 1] == '2')dp[i] += dp[i - 2] * 6 % MOD;
}
else {
dp[i] += dp[i - 2] * 15 % MOD;
}
}
dp[i] %= MOD;
}
return dp[n - 1];
}
};


class Solution {
public:
int numDecodings(string s) {
if (s == "" || s[0] == '0')return 0;
s = "^" + s;
int n = s.size();
vector<ll> dp(n, 0);
dp[0] = 1;
if (s[1] == '*')dp[1] = 9;
else dp[1] = 1;
for (int i = 2; i < n; i++) {
char cur = s[i], pre = s[i - 1];
ll &curCnt = dp[i], preCnt = dp[i - 1], prePreCnt = dp[i - 2];
if (cur == '0') {
if (pre == '1'|| pre == '2')curCnt += prePreCnt % MOD;
else if (pre == '*')curCnt += prePreCnt * 2 % MOD;
else return 0;
}
else if (cur == '*') {
curCnt += preCnt * 9 % MOD;
if (pre == '1')curCnt += prePreCnt * 9 % MOD;
else if (pre == '2')curCnt += prePreCnt * 6 % MOD;
else if (pre == '*')curCnt += prePreCnt * 15 % MOD;
}
else { // ['1','9']
curCnt += preCnt % MOD;
if(pre=='1')curCnt += prePreCnt % MOD;
else if (pre == '2' && cur <= '6')curCnt += prePreCnt % MOD;
else if (pre == '*') {
if (cur <= '6')curCnt += prePreCnt * 2 % MOD;
else curCnt += prePreCnt % MOD;
}
}
curCnt %= MOD;
}
return dp[n - 1];
}
};


# 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 Range Sum Query 2D - Immutable

LeetCode Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.
Example:

Given matrix = [
[3, 0, 1, 4, 2],
[5, 6, 3, 2, 1],
[1, 2, 0, 1, 5],
[4, 1, 0, 1, 7],
[1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12


Note:

1. You may assume that the matrix does not change.
2. There are many calls to sumRegion function.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

dp[i][j]=dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+matrix[i][j]

cursum=dp[j][v]-dp[j][u-1]-dp[i-1][v]+dp[i-1][u-1]

      |               |
-----(i,u)----------(i,v)----
|               |
|               |
-----(j,u)----------(j,v)----
|               |

class NumMatrix {
private:
vector<vector<int>> dp;
public:
NumMatrix(vector<vector<int>> matrix) {
if (matrix.empty() || matrix[0].empty())return;
int m = matrix.size(), n = matrix[0].size();
for (int i = 0; i < m + 1; ++i)dp.push_back(vector<int>(n + 1, 0)); // 为了方便，多增加了一行和一列
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
if (dp.empty())return 0;
++row1; // 因为dp多一行和一列，所以这里提前加上
++col1;
++row2;
++col2;
return dp[row2][col2] - dp[row2][col1 - 1] - dp[row1 - 1][col2] + dp[row1 - 1][col1 - 1];
}
};