# 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 Wiggle Sort II

LeetCode Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Can you do it in O(n) time and/or in-place with O(1) extra space?

class Solution {
private:
//自己实现的快排程序
void my_quick_sort(vector<int>& nums, int s, int t) {
int i = s, j = t, pivot = s;
if (i >= j)return;
while (i <= j) {
while (i <= j&&nums[i] <= nums[pivot])++i;
if (i > j)break;
while (i <= j&&nums[j] >= nums[pivot])--j;
if (i > j)break;
swap(nums[i++], nums[j--]);
}
swap(nums[pivot], nums[j]);
my_quick_sort(nums, s, j - 1);
my_quick_sort(nums, j + 1, t);
}
public:
void wiggleSort(vector<int>& nums) {
int n = nums.size();
my_quick_sort(nums, 0, n - 1);
int i = (n & 1) == 0 ? n / 2 - 1 : n / 2, j = n - 1;
vector<int> ans(n, 0);
for (int k = 0; k < n; ++k) {
ans[k] = (k & 1) == 0 ? nums[i--] : nums[j--];
}
nums = ans;
}
};


class Solution {
public:
void wiggleSort(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size(), i = (n + 1) / 2, j = n;
vector<int> ans(n, 0);
for (int k = 0; k < n; ++k) {
ans[k] = (k & 1) == 0 ? nums[--i] : nums[--j];
}
nums = ans;
}
};


# LeetCode K-diff Pairs in an Array

LeetCode K-diff Pairs in an Array
Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.


Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).


Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).


Note:

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won't exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

class Solution {
public:
int findPairs(vector<int>& nums, int k) {
if (k < 0)return 0;
int repeated = 0;
map<int, int> count;
for (const auto& num : nums) {
++count[num];
if (count[num] == 2)++repeated;
}
if (k == 0)return repeated;
vector<int> sorted;
for (const auto& it : count) {
sorted.push_back(it.first);
}
int ans = 0;
for (const auto& num : sorted) {
if (count.find(num + k) != count.end())++ans;
}
return ans;
}
};


# LeetCode Maximum Product of Three Numbers

LeetCode Maximum Product of Three Numbers
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:

Input: [1,2,3]
Output: 6


Example 2:

Input: [1,2,3,4]
Output: 24


Note:

1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
2. Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
int ans1 = nums[n - 1] * nums[n - 2] * nums[n - 3], ans2 = 0;
if (nums[0] > 0)return ans1;
if (nums[0] < 0 && nums[1] < 0)ans2 = nums[0] * nums[1] * nums[n - 1];
return max(ans1, ans2);
}
};


# LeetCode Maximum Distance in Arrays

LeetCode Maximum Distance in Arrays
Given m arrays, and each array is sorted in ascending order. Now you can pick up two integers from two different arrays (each array picks one) and calculate the distance. We define the distance between two integers a and b to be their absolute difference |a-b|. Your task is to find the maximum distance.
Example 1:

Input:
[[1,2,3],
[4,5],
[1,2,3]]
Output: 4
Explanation:
One way to reach the maximum distance 4 is to pick 1 in the first or third array and pick 5 in the second array.


Note:

1. Each given array will have at least 1 number. There will be at least two non-empty arrays.
2. The total number of the integers in all the m arrays will be in the range of [2, 10000].
3. The integers in the m arrays will be in the range of [-10000, 10000].

class Solution {
struct P {
int idx;
int value;
P(int i, int v) :idx(i), value(v) {};
bool operator<(const P& p) {
return this->value < p.value;
}
};
public:
int maxDistance(vector<vector<int>>& arrays) {
vector<P> vp;
for (int i = 0; i < arrays.size(); ++i) {
vp.push_back({ i,arrays[i][0] });
vp.push_back({ i,arrays[i][arrays[i].size() - 1] });
}
sort(vp.begin(), vp.end());
int ans = 0, n = vp.size();
if (vp[0].idx != vp[n - 1].idx)return abs(vp[n - 1].value - vp[0].value);
return max(abs(vp[n - 1].value - vp[1].value), abs(vp[n - 2].value - vp[0].value));
}
};


class Solution {
public:
int maxDistance(vector<vector<int>>& arrays) {
int ans = INT_MIN;
int curMin = arrays[0][0], curMax = arrays[0][arrays[0].size() - 1];
for(int i = 1; i < arrays.size(); ++i) {
ans = max(ans, abs(arrays[i][0] - curMax));
ans = max(ans, abs(arrays[i][arrays[i].size() - 1] - curMin));
curMin = min(curMin, arrays[i][0]);
curMax = max(curMax, arrays[i][arrays[i].size() - 1]);
}
return ans;
}
};


# LeetCode Shortest Unsorted Continuous Subarray

LeetCode Shortest Unsorted Continuous Subarray
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:

Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.


Note:

1. Then length of the input array is in range [1, 10,000].
2. The input array may contain duplicates, so ascending order here means <=.

class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
vector<int> nums_copy = nums;
sort(nums_copy.begin(), nums_copy.end());
int i = 0, j = nums.size() - 1;
while (i <= j&&nums[i] == nums_copy[i])++i;
while (j >= i&&nums[j] == nums_copy[j])--j;
return j - i + 1;
}
};


1. 从左往右，如果该数已经在最终排序的位置了，那么该数必须小于等于该数右边的最小值
2. 从右往左，如果该数已经在最终排序的位置了，那么该数必须大于等于该数左边的最大值

/**
*            /------------\
* nums:  [2, 6, 4, 8, 10, 9, 15]
* minsf:  2  4  4  8   9  9  15
*         <--------------------
* maxsf:  2  6  6  8  10 10  15
*         -------------------->
*/
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
vector<int> min_so_far(n, 0), max_so_far(n, 0);
for (int i = 0, maxsf = INT_MIN; i < n; ++i)max_so_far[i] = maxsf = max(maxsf, nums[i]);
for (int i = n - 1, minsf = INT_MAX; i >= 0; --i)min_so_far[i] = minsf = min(minsf, nums[i]);
int i = 0, j = n - 1;
while (i <= j&&nums[i] <= min_so_far[i])++i;
while (j >= i&&nums[j] >= max_so_far[j])--j;
return j - i + 1;
}
};


Given an m * n matrix M initialized with all 0's and several update operations.
Operations are represented by a 2D array, and each operation is represented by an array with two positive integers a and b, which means M[i][j] should be added by one for all 0 <= i < a and 0 <= j < b.
You need to count and return the number of maximum integers in the matrix after performing all the operations.
Example 1:

Input:
m = 3, n = 3
operations = [[2,2],[3,3]]
Output: 4
Explanation:
Initially, M =
[[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]
After performing [2,2], M =
[[1, 1, 0],
[1, 1, 0],
[0, 0, 0]]
After performing [3,3], M =
[[2, 2, 1],
[2, 2, 1],
[1, 1, 1]]
So the maximum integer in M is 2, and there are four of it in M. So return 4.


Note:

1. The range of m and n is [1,40000].
2. The range of a is [1,m], and the range of b is [1,n].
3. The range of operations size won't exceed 10,000.

class Solution {
public:
int maxCount(int m, int n, vector<vector<int>>& ops) {
int minRow = m, minCol = n;
for (const auto &op : ops) {
minRow = min(minRow, op[0]);
minCol = min(minCol, op[1]);
}
return minRow*minCol;
}
};


# LeetCode Subarray Sum Equals K

LeetCode Subarray Sum Equals K
Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.
Example 1:

Input:nums = [1,1,1], k = 2
Output: 2


Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

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


class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
if (n == 0)return 0;
int ans = 0, sum = 0;
unordered_map<int, int> cnt;
for (int i = 0; i < n; ++i) {
++cnt[sum];
sum += nums[i];
ans += cnt[sum - k];
}
return ans;
}
};


# LeetCode Reshape the Matrix

LeetCode Reshape the Matrix
In MATLAB, there is a very useful function called 'reshape', which can reshape a matrix into a new one with different size but keep its original data.
You're given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the 'reshape' operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example 1:

Input:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
Output:
[[1,2,3,4]]
Explanation:
The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.


Example 2:

Input:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
Output:
[[1,2],
[3,4]]
Explanation:
There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.


Note:

1. The height and width of the given matrix is in range [1, 100].
2. The given r and c are all positive.

class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
int n = nums.size(), m = nums[0].size();
if (n*m != r*c)return nums;
vector<vector<int>> ans(r, vector<int>(c, 0));
for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
int cnt = i*c + j;
ans[i][j] = nums[cnt / m][cnt % m];
}
}
return ans;
}
};


# 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;
}
};