zyq2652192993

SJTU

### 题目描述

You are given two sorted arrays of distinct integers nums1 and nums2.

A valid path is defined as follows:

• Choose array nums1 or nums2 to traverse (from index-0).
• Traverse the current array from left to right.
• If you are reading any value that is present in nums1 and nums2 you are allowed to change your path to the other array. (Only one repeated value is considered in the valid path).

Score is defined as the sum of uniques values in a valid path.

Return the maximum score you can obtain of all possible valid paths.

Since the answer may be too large, return it modulo 10^9 + 7.

#### 样例

Example 1:

Input: nums1 = [2,4,5,8,10], nums2 = [4,6,8,9]
Output: 30
Explanation: Valid paths:
[2,4,5,8,10], [2,4,5,8,9], [2,4,6,8,9], [2,4,6,8,10],  (starting from nums1)
[4,6,8,9], [4,5,8,10], [4,5,8,9], [4,6,8,10]    (starting from nums2)
The maximum is obtained with the path in green [2,4,6,8,10].


Example 2:

Input: nums1 = [1,3,5,7,9], nums2 = [3,5,100]
Output: 109
Explanation: Maximum sum is obtained with the path [1,3,5,100].


Example 3:

Input: nums1 = [1,2,3,4,5], nums2 = [6,7,8,9,10]
Output: 40
Explanation: There are no common elements between nums1 and nums2.
Maximum sum is obtained with the path [6,7,8,9,10].


Example 4:

Input: nums1 = [1,4,5,8,9,11,19], nums2 = [2,3,4,11,12]
Output: 61


Constraints:

• 1 <= nums1.length <= 10^5
• 1 <= nums2.length <= 10^5
• 1 <= nums1[i], nums2[i] <= 10^7
• nums1 and nums2 are strictly increasing.

• 如果是两个列表，数据范围是$10^3$，大概率就是动态规划，如果是$10^5$，那么大概率就是双指针
• 如果是多个有序列表，一般数据范围是$10^5$，基本上就是优先级队列

nums1 [1] (4) [5 8 9] (11) [19]
nums2 [2 3] (4) (11) [12]


class Solution {
public:
int maxSum(vector<int>& nums1, vector<int>& nums2) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int m = nums1.size(), n = nums2.size();
const int MODE = 1e9 + 7;
queue<int> q1, q2;
q1.push(0), q2.push(0);

vector<long long> prefixSum1(m + 1, 0), prefixSum2(n + 1, 0);
for (int i = 1; i <= m; ++i) prefixSum1[i] = prefixSum1[i - 1] + nums1[i - 1];
for (int i = 1; i <= n; ++i) prefixSum2[i] = prefixSum2[i - 1] + nums2[i - 1];

int pos = 0;
for (int i = 0; i < m; ++i) {
while (pos < n && nums2[pos] < nums1[i]) ++pos;
if (pos >= n) break;
if (nums1[i] == nums2[pos]) q1.push(i + 1), q2.push(pos + 1);
}
if (q1.size() == 1) return max(prefixSum1[m] % MODE, prefixSum2[n] % MODE);

long long res = 0;
while (q1.size() > 1) {
int tmp1 = q1.front(); q1.pop();
int tmp2 = q2.front(); q2.pop();

res = max(res + gap(tmp1, q1.front() - 1, prefixSum1) + nums1[q1.front() - 1],
res + gap(tmp2, q2.front() - 1, prefixSum2) + nums2[q2.front() - 1]);
}
res = max(res + gap(q1.front(), m, prefixSum1), res + gap(q2.front(), n, prefixSum2));

return res % MODE;
}

inline long long gap(int start, int end, vector<long long> & prefixSum)
{
return prefixSum[end] - prefixSum[start];
}
};


class Solution {
public:
int maxSum(vector<int>& nums1, vector<int>& nums2) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int m = nums1.size(), n = nums2.size();
const int MODE = 1e9 + 7;
long long res = 0, sum1 = 0, sum2 = 0;
int pos1 = 0, pos2 = 0;

while (pos1 < m && pos2 < n) {
if (nums1[pos1] < nums2[pos2]) sum1 += nums1[pos1++];
else if (nums1[pos1] > nums2[pos2]) sum2 += nums2[pos2++];
else {
res += max(sum1, sum2) + nums1[pos1++];
++pos2;
sum1 = sum2 = 0;
}
}

if (pos1 < m) {
for (int i = pos1; i < m; ++i) sum1 += nums1[i];
}
if (pos2 < n) {
for (int i = pos2; i < n; ++i) sum2 += nums2[i];
}

res += max(sum1, sum2);

return res % MODE;
}
};


### 题目描述

Given an n x n binary grid, in one step you can choose two adjacent rows of the grid and swap them.

A grid is said to be valid if all the cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid, or -1 if the grid cannot be valid.

The main diagonal of a grid is the diagonal that starts at cell (1, 1) and ends at cell (n, n).

#### 样例

Example 1:

Input: grid = [[0,0,1],[1,1,0],[1,0,0]]
Output: 3


Example 2:

Input: grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
Output: -1
Explanation: All rows are similar, swaps have no effect on the grid.


Example 3:

Input: grid = [[1,0,0],[1,1,0],[1,1,1]]
Output: 0


Constraints:

• n == grid.length
• n == grid[i].length
• 1 <= n <= 200
• grid[i][j] is 0 or 1

class Solution {
public:
int minSwaps(vector<vector<int>>& grid) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n = grid.size();
vector<int> zeroNum(n);

for (int i = 0; i < n; ++i) {
int j = n - 1;
while (j >= 0 && grid[i][j] == 0) {
++zeroNum[i];
--j;
}
}

int res = 0;
for (int i = 0; i < n - 1; ++i) {
if (zeroNum[i] < n - i - 1) {
int j = i + 1;
while (j < n && zeroNum[j] < n - i - 1) ++j;
if (j == n) return -1;
while (j > i) {
std::swap(zeroNum[j], zeroNum[j - 1]);
--j;
++res;
}
}
}

return res;
}
};


### 题目描述

Given an integer array arr of distinct integers and an integer k.

A game will be played between the first two elements of the array (i.e. arr[0] and arr[1]). In each round of the game, we compare arr[0] with arr[1], the larger integer wins and remains at position 0 and the smaller integer moves to the end of the array. The game ends when an integer wins k consecutive rounds.

Return the integer which will win the game.

It is guaranteed that there will be a winner of the game.

#### 样例

Example 1:

Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
Explanation: Let's see the rounds of the game:
Round |       arr       | winner | win_count
1   | [2,1,3,5,4,6,7] | 2      | 1
2   | [2,3,5,4,6,7,1] | 3      | 1
3   | [3,5,4,6,7,1,2] | 5      | 1
4   | [5,4,6,7,1,2,3] | 5      | 2
So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.


Example 2:

Input: arr = [3,2,1], k = 10
Output: 3
Explanation: 3 will win the first 10 rounds consecutively.


Example 3:

Input: arr = [1,9,8,2,3,7,6,4,5], k = 7
Output: 9


Example 4:

Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
Output: 99


Constraints:

• 2 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^6
• arr contains distinct integers.
• 1 <= k <= 10^9

[] [] [] [] ... max_element


class Solution {
public:
int getWinner(vector<int>& arr, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n = arr.size();
if (k >= n - 1) return *max_element(arr.begin(), arr.end());

queue<int> q;
for (int i = 1; i < n; ++i) q.push(arr[i]);

int res = arr[0], tmp = arr[0];
int cnt = 0;

while (true) {
if (tmp > q.front()) {
q.push(q.front()); q.pop();
++cnt;
}
else {
q.push(tmp);
tmp = q.front(); q.pop();
cnt = 1;
res = tmp;
}

if (cnt >= k) break;
}

return res;
}
};


class Solution {
public:
int getWinner(vector<int>& arr, int k) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n = arr.size();
if (k >= n - 1) return *max_element(arr.begin(), arr.end());

int cnt = 0, res = arr[0];
for (int i = 0; i < n - 1; ++i) {
if (arr[i] > arr[i + 1]) {
++cnt;
arr[i + 1] = arr[i];
}
else {
res = arr[i + 1];
cnt = 1;
}

if (cnt >= k) break;
}

return res;
}
};


### 题目描述

Design a logger system that receive stream of messages along with its timestamps, each message should be printed if and only if it is not printed in the last 10 seconds.

Given a message and a timestamp (in seconds granularity), return true if the message should be printed in the given timestamp, otherwise returns false.

It is possible that several messages arrive roughly at the same time.

#### 样例

Logger logger = new Logger();

// logging string "foo" at timestamp 1
logger.shouldPrintMessage(1, "foo"); returns true;

// logging string "bar" at timestamp 2
logger.shouldPrintMessage(2,"bar"); returns true;

// logging string "foo" at timestamp 3
logger.shouldPrintMessage(3,"foo"); returns false;

// logging string "bar" at timestamp 8
logger.shouldPrintMessage(8,"bar"); returns false;

// logging string "foo" at timestamp 10
logger.shouldPrintMessage(10,"foo"); returns false;

// logging string "foo" at timestamp 11
logger.shouldPrintMessage(11,"foo"); returns true;


### 算法

##### (字符串哈希 + 哈希表)

• 之前这条Message没有出现过
• 或者两次Message的时间戳的差大于等于10

#### C++ 代码

class Logger {
typedef unsigned long long ull;
static constexpr ull base = 13331;

unordered_map<ull, int> um;

public:
/** Initialize your data structure here. */
Logger() {}

ull getHash(const string & str)
{
int n = str.size();
ull res = 0;
for (int i = 0; i < n; ++i) {
res = res * base + (int)str[i];
}

return res;
}

/** Returns true if the message should be printed in the given timestamp, otherwise returns false.
If this method returns false, the message will not be printed.
The timestamp is in seconds granularity. */
bool shouldPrintMessage(int timestamp, string message) {
ull key = getHash(message);
if (um.find(key) == um.end()) {
um[key] = timestamp;
return true;
}

if (timestamp - um[key] >= 10) {
um[key] = timestamp;
return true;
}

return false;
}
};

/**
* Your Logger object will be instantiated and called as such:
* Logger* obj = new Logger();
* bool param_1 = obj->shouldPrintMessage(timestamp,message);
*/


### 题目描述

Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

#### 样例

Example 1:

11000
11000
00011
00011


Given the above grid map, return 1.

Example 2:

11011
10000
00001
11011


Given the above grid map, return 3.

Notice that:

11
1


and

 1
11


are considered different island shapes, because we do not consider reflection / rotation.
Note: The length of each dimension in the given grid does not exceed 50.

### 算法

#### C++ 代码

class Solution {
typedef unsigned long long ull;
static constexpr ull base = 13331;
unordered_set<ull> us;

struct Node
{
int x, y;
Node(int x, int y) : x(x), y(y) {}

bool operator<(const Node & obj) const
{ return (x < obj.x) || (x == obj.x && y < obj.y); }
};

int direction[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

public:
int numDistinctIslands(vector<vector<int>>& grid) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

vector<Node> seq;
int m = grid.size(), n = grid[0].size();

for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j]) {
seq.push_back(Node(i, j));
int minX = i, minY = j;
DFS(grid, seq, i, j, minX, minY);
Hash(seq, minX, minY);
seq.clear();
}
}
}

return us.size();
}

void DFS(vector<vector<int>>& grid, vector<Node> & seq, int row, int col, int & minX, int & minY)
{
int m = grid.size(), n = grid[0].size();
grid[row][col] = 0;

for (int i = 0; i < 4; ++i) {
int nextRow = row + direction[i][0];
int nextCol = col + direction[i][1];
if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && grid[nextRow][nextCol]) {
seq.push_back(Node(nextRow, nextCol));
minX = min(minX, nextRow), minY = min(minY, nextCol);
DFS(grid, seq, nextRow, nextCol, minX, minY);
}
}
}

void Hash(vector<Node> & seq, const int & minX, const int & minY)
{
sort(seq.begin(), seq.end());
for (auto & e : seq) { e.x -= minX, e.y -= minY; }

ull res = 0;
const ull square = base * base, triple = square * base;

for (auto & e : seq) {
res = res * triple + e.x * square + (ull)(',') * base + e.y;
}

us.emplace(res);
}
};


### 题目描述

A delivery company wants to build a new service centre in a new city. The company knows the positions of all the customers in this city on a 2D-Map and wants to build the new centre in a position such that the sum of the euclidean distances to all customers is minimum.

Given an array positions where positions[i] = [xi, yi] is the position of the ith customer on the map, return the minimum sum of the euclidean distances to all customers.

In other words, you need to choose the position of the service centre [xcentre, ycentre] such that the following formula is minimized:

Answers within 10^-5 of the actual value will be accepted.

#### 样例

Example 1:

Input: positions = [[0,1],[1,0],[1,2],[2,1]]
Output: 4.00000
Explanation: As shown, you can see that choosing [xcentre, ycentre] = [1, 1] will make the distance to each customer = 1, the sum of all distances is 4 which is the minimum possible we can achieve.


Example 2:

Input: positions = [[1,1],[3,3]]
Output: 2.82843
Explanation: The minimum possible sum of distances = sqrt(2) + sqrt(2) = 2.82843


Example 3:

Input: positions = [[1,1]]
Output: 0.00000


Example 4:

Input: positions = [[1,1],[0,0],[2,0]]
Output: 2.73205
Explanation: At the first glance, you may think that locating the centre at [1, 0] will achieve the minimum sum, but locating it at [1, 0] will make the sum of distances = 3.
Try to locate the centre at [1.0, 0.5773502711] you will see that the sum of distances is 2.73205.
Be careful with the precision!


Example 5:

Input: positions = [[0,1],[3,2],[4,5],[7,6],[8,9],[11,1],[2,12]]
Output: 32.94036
Explanation: You can use [4.3460852395, 4.9813795505] as the position of the centre.


Constraints:

• 1 <= positions.length <= 50
• positions[i].length == 2
• 0 <= positions[i][0], positions[i][1] <= 100\

### 算法

##### (Weiszfeld算法)

Weber问题：求平面上的供给点到需求点的最小欧几里得距离和。

Weiszfeld算法：通过以下迭代式进行迭代更新，自定义求解精度。其中x, y代表上一轮的供给点的横纵坐标，x', y'代表新一轮的供给点横纵坐标。

#### C++ 代码

class Solution {
public:
double getMinDistSum(vector<vector<int>>& positions) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n = positions.size();
double eps = 1e-8;
double x, y;
double sum_x = 0, sum_y = 0;
for (int i = 0; i < n; ++i) {
sum_x += positions[i][0];
sum_y += positions[i][1];
}
x = sum_x / n, y = sum_y / n;
double pre_x = x, pre_y = y;

while (true) {
double sum1 = 0, sum2 = 0, sum3 = 0;
for (int i = 0; i < n; ++i) {
double tmp = dis(x, y, positions[i][0], positions[i][1]);
if (tmp < eps) continue;
sum1 += (double)positions[i][0] / tmp;
sum2 += (double)positions[i][1] / tmp;
sum3 += (double)1 / tmp;
}
if (sum3 < eps) break;

pre_x = x, pre_y = y;
x = sum1 / sum3, y = sum2 / sum3;
if (abs(x - pre_x) < eps && abs(y - pre_y) < eps) break;
}

double res = 0;
for (auto & e : positions) res += dis(x, y, e[0], e[1]);

return res;
}

inline double dis(double x1, double y1, double x2, double y2)
{
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
};


class Solution {
public:
double getMinDistSum(vector<vector<int>>& positions) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n = positions.size();
double resX = 0, resY = 0;
for (auto & e : positions) {
resX += e[0], resY += e[1];
}
resX /= n, resY /= n;
double resW = energy(resX, resY, positions);

for (int i = 0; i < 3; ++i) {
SA(resX, resY, resW, positions);
}

return resW;
}

double energy(double x, double y, vector<vector<int>>& positions)
{
double res = 0;
for (auto & e : positions) {
double tmpX = x - e[0];
double tmpY = y - e[1];
res += sqrt(tmpX * tmpX + tmpY * tmpY);
}

return res;
}

void SA(double & resX, double & resY, double & resW, vector<vector<int>>& positions)
{
double T = 3000;
const double EPS = 1e-15;
while (T > EPS) {
double nextX = resX + ((long long)rand() * 2 - RAND_MAX) * T;
double nextY = resY + ((long long)rand() * 2 - RAND_MAX) * T;
double nextW = energy(nextX, nextY, positions);
double delta = nextW - resW;

if (delta < 0) {
resX = nextX, resY = nextY, resW = nextW;
}
else if (exp(- delta / T) * RAND_MAX > rand()) {
resX = nextX, resY = nextY;
}

T *= 0.995;
}
}
};


### 题目描述

You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[i] = [a, b] is an undirected edge connecting the nodes a and b with a probability of success of traversing that edge succProb[i].

Given two nodes start and end, find the path with the maximum probability of success to go from start to end and return its success probability.

If there is no path from start to end, return 0. Your answer will be accepted if it differs from the correct answer by at most 1e-5.

#### 样例

Example 1:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.


Example 2:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
Output: 0.30000


Example 3:

Input: n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
Output: 0.00000
Explanation: There is no path between 0 and 2.


Constraints:

• 2 <= n <= 10^4
• 0 <= start, end < n
• start != end
• 0 <= a, b < n
• a != b
• 0 <= succProb.length == edges.length <= 2*10^4
• 0 <= succProb[i] <= 1
• There is at most one edge between every two nodes.

### 算法

##### (BFS)

start开始，依次去更新与其相连的点，这些点作为源点再去更新其他点，数组d[i]记录从starti的最大概率乘积，很典型的BFS套路。

#### C++ 代码

class Solution {
struct Node
{
int to;
double probability;
Node(int t, double p) : to(t), probability(p) {}
};

public:
double maxProbability(int n, vector<vector<int>>& edges, vector<double>& succProb, int start, int end) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

vector<vector<Node>> grid(n);
for (int i = 0; i < edges.size(); ++i) {
int from = edges[i][0], to = edges[i][1];
grid[from].push_back(Node(to, succProb[i]));
grid[to].push_back(Node(from, succProb[i]));
}

vector<double> d(n, 0); d[start] = 1;
queue<int> q;
q.push(start);

while (!q.empty()) {
int from = q.front(); q.pop();
for (int i = 0; i < grid[from].size(); ++i) {
int to = grid[from][i].to;
double probability = grid[from][i].probability;
if (d[to] < d[from] * probability) {
q.push(to);
d[to] = d[from] * probability;
}
}
}

return d[end];
}
};


### 题目描述

Given a binary string s (a string consisting only of ‘0’ and ‘1’s).

Return the number of substrings with all characters 1’s.

Since the answer may be too large, return it modulo 10^9 + 7.

#### 样例

Example 1:

Input: s = "0110111"
Output: 9
Explanation: There are 9 substring in total with only 1's characters.
"1" -> 5 times.
"11" -> 3 times.
"111" -> 1 time.


Example 2:

Input: s = "101"
Output: 2
Explanation: Substring "1" is shown 2 times in s.


Example 3:

Input: s = "111111"
Output: 21
Explanation: Each substring contains only 1's characters.


Example 4:

Input: s = "000"
Output: 0


Constraints:

• s[i] == '0' or s[i] == '1'
• 1 <= s.length <= 10^5

### 算法

#### C++ 代码

class Solution {
public:
int numSub(string s) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int n = s.size();
long long res = 0;
const int MODE = 1e9 + 7;

int pre = 0;
for (int i = 0; i < n; ++i) {
if (s[i] == '1') {
pre = i;
while (i < n && s[i] == '1') ++i;
long long len = i - pre;
res = (res + (len + 1) * (len) / 2) % MODE;
}
}

return res;
}
};


### 题目描述

Alice and Bob take turns playing a game, with Alice starting first.

Initially, there are n stones in a pile. On each player’s turn, that player makes a move consisting of removing any non-zero square number of stones in the pile.

Also, if a player cannot make a move, he/she loses the game.

Given a positive integer n. Return True if and only if Alice wins the game otherwise return False, assuming both players play optimally.

#### 样例

Example 1:

Input: n = 1
Output: true
Explanation: Alice can remove 1 stone winning the game because Bob doesn't have any moves.


Example 2:

Input: n = 2
Output: false
Explanation: Alice can only remove 1 stone, after that Bob removes the last one winning the game (2 -> 1 -> 0).


Example 3:

Input: n = 4
Output: true
Explanation: n is already a perfect square, Alice can win with one move, removing 4 stones (4 -> 0).


Example 4:

Input: n = 7
Output: false
Explanation: Alice can't win the game if Bob plays optimally.
If Alice starts removing 4 stones, Bob will remove 1 stone then Alice should remove only 1 stone and finally Bob removes the last one (7 -> 3 -> 2 -> 1 -> 0).
If Alice starts removing 1 stone, Bob will remove 4 stones then Alice only can remove 1 stone and finally Bob removes the last one (7 -> 6 -> 2 -> 1 -> 0).


Example 5:

Input: n = 17
Output: false
Explanation: Alice can't win the game if Bob plays optimally.


Constraints:

• 1 <= n <= 10^5

### 算法

##### （动态规划）$O(n(\sqrt{n} + \log{n}))$

d[i]表示石子数量为i时先手能否获胜，i = 1, 2时可以直接得出结果。首先如果这个数本身就是完全平方数，直接取走所有的石子，先手必胜。如果一个数不是完全平方数，并且要求每次必须取完全平方数的数量的石子，所以我们尝试所有小于等于n的完全平方数，假设取走的完全平方数是k，那么余下的就是n - k，只有此时n-k先手必输的情况下，先手取走k是一个必胜的策略。

#### C++ 代码

class Solution {
public:
bool winnerSquareGame(int n) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

if (n == 1) return true;
if (n == 2) return false;

vector<int> d(n + 1, 0);
d[1] = 1; d[2] = 0;

vector<int> seq;
int cnt = 1;
int limit = 1e5;
while (cnt * cnt <= limit) {
seq.push_back(cnt * cnt);
++cnt;
}

for (int i = 3; i <= n; ++i) {
if (isSuqare(i)) {
d[i] = 1;
}
else {
int pos = (upper_bound(seq.begin(), seq.end(), i) - seq.begin()) - 1;
for (int j = 0; j <= pos; ++j) {
if (!d[i - seq[j]]) { d[i] = 1; break; }
}
}
}

return d[n];
}

bool isSuqare(int n)
{
int k = sqrt(n);
return k * k == n;
}
};


### 题目描述

Given an array nums, you are allowed to choose one element of nums and change it by any value in one move.

Return the minimum difference between the largest and smallest value of nums after perfoming at most 3 moves.

#### 样例

Example 1:

Input: nums = [5,3,2,4]
Output: 0
Explanation: Change the array [5,3,2,4] to [2,2,2,2].
The difference between the maximum and minimum is 2-2 = 0.


Example 2:

Input: nums = [1,5,0,10,14]
Output: 1
Explanation: Change the array [1,5,0,10,14] to [1,1,0,1,1].
The difference between the maximum and minimum is 1-0 = 1.


Example 3:

Input: nums = [6,6,0,1,1,4,6]
Output: 2


Example 4:

Input: nums = [1,5,6,14,15]
Output: 1


Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

### 算法1

#### C++ 代码

class Solution {
public:
int minDifference(vector<int>& nums) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int k = 3, n = nums.size(); if (n <= 4) return 0;

sort(nums.begin(), nums.end());
int res = INT_MAX;
int pos = 0, len = n - 1 - k;
for (int cnt = 0; cnt < k + 1; ++cnt) {
res = min(res, nums[pos + len] - nums[pos]);
++pos;
}

return res;
}
};