4058

# 1.基础

### 字符串处理

#### C++ 代码

class Solution {
public:
vector<int> sequentialDigits(int low, int high) {
string lower = to_string(low);
string higher = to_string(high);
int n = lower.size();
int m = higher.size();

vector<int> ans;
for(int i = n; i <= m; i++) // 枚举区间长度
{
for(int j = 1; j <= 9 - i + 1; j++) // 枚举可以选择的第一个数字
{
string temp = "";
int index = j;
for(int k = 1; k <= i; k++) // 补全当前数字开头的当前长度的数字
{
temp += to_string(index ++);
}

int now = atoi(temp.c_str());
if(now > high) return ans;

if(now >= low && now <= high)
ans.push_back(now);
}
}

return ans;
}
};


### 贪心 + dp

#### C++ 代码

class Solution {
public:

static bool cmp(pair<int, int> a, pair<int, int> b)
{
if(a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}

int bestTeamScore(vector<int>& scores, vector<int>& ages) {
int n = scores.size();

vector<pair<int, int>> temp;
for(int i = 0; i < scores.size(); i++)
temp.push_back({ages[i], scores[i]});

sort(temp.begin(), temp.end(), cmp);

vector<int> f(n, 0);
f[0] = temp[0].second;
for(int i = 1; i < n; i++)
{
f[i] = temp[i].second;
for(int j = 0; j < i; j++)
{
if(temp[i].first > temp[j].first && temp[i].second < temp[j].second)
{
continue;
}
else
f[i] = max(f[i], f[j] + temp[i].second);
}
}

int maxv = 0;
for(auto item : f)
{
maxv = max(maxv, item);
}

return maxv;
}
};


### 贪心 $O(13n)$

#### C++ 代码

class Solution {
public:
string breakPalindrome(string p) {
if(p.size() <= 1) return "";
int pos = p.size() / 2 - 1;
for(int i = 0; i < 26; i++)
{
char now = 'a' + i;
for(int j = 0; j <= pos; j++)
if(p[j] != now)
{
string temp1 = p, temp2 = p;
temp1[j] = now;
temp2[p.size() - 1 - j] = now;
return min(temp1, temp2);
}
}

return "";
}
};


### 题目描述

In some cultures, children are named after ancestors and there is a number following which represents how many ancestors have shared that name. They are often shown as Roman Numerals

in Roman numerals, a value ts not repeated more than three times At that point. a smaller value precedes a larger value to indicate subtraction. For example the letter I represents the number 1, and Represents s Reason through the formation of I to 1o below, and see how it is appied in the following lines

#### 样例

For example, f you are given the names [Steven XL, Steven XVI, David IX, Mary XV, Mary XIII, Mary XX]
the result of the sort is (David IX, Mary XIII, Mary XV, Mary XX, Steven XVI, Steven XL)
The resul with Roman numerals is the expected return  value.
Written with the numbers in decimal, they are [David 9. Mary 13. Mary I5, Mary 20, Steven 16 Steven 40]


### 算法1

#### C++ 代码

unordered_map<char, int> words;

string deal(string str)
{
int pos = str.find(' ');
string a1 = str.substr(0, pos);
string a2 = str.substr(pos + 1);

int ans = 0;

for (int i = 0; i < a2.size(); i++)
{
if (i != a2.size() - 1 && words[a2[i + 1]] > words[a2[i]])
{
ans += words[a2[i + 1]] - words[a2[i]];
i++;
}
else
ans += words[a2[i]];
}

return a1 + " " + to_string(ans);
}

vector<string> ancestralNames(vector<string> &names)
{
words['I'] = 1; words['V'] = 5;
words['X'] = 10; words['L'] = 50;
words['C'] = 100; words['D'] = 500;
words['M'] = 1000;

for(int i = 0; i < names.size(); i++)
{
names[i] = deal(names[i]);
}
sort(names.begin(), names.end());
return names;
}


### 题目描述

Alex is given n piles of boxes of equal or unequal heights. In one step. Alex can remove any number of boxes from the pile which has the maximum height and try to make it equal to the one which is just lower than the maximum height of the stack. Determine the minimum number of steps required to make all of the piles equal in height

#### 样例

n = 3;
boxinpiles = [5, 2, 1]

In the first step, remove 3 boxes from boxinpiles[0], and the new array is boxinpiles = [2,2,1]
Now reduce the two taller piles by 1 box each to match the height of the shortest plle This takes
2 steps because each step is performed on only one pile. The final number of steps requlred is 3



### 排序

#### C++ 代码

int pilesOfBox(int n, vector<int> &piles)
{
sort(piles.begin(), piles.end(), greater<int>());
int ans = 0;
for(int i = 0; i + 1 < piles.size(); i++)
{
int gap =  piles[i] - piles[i + 1];
ans += gap * (i + 1);
}
return ans;
}


### 题目描述

A prisoner is planning to escape from prison! The prison s gate consists of horizontal and vertical bars that are spaced one unit apart so the area of each hole between the bars is 1 x 1. The prisoner manages to remove certain bars to make some bigger holes. Determine the area of the largest hole in the gate after the bars are removed

#### 样例

n = 6
m = 6
h = [4];
v = [2];

In the images below. the left image depicts the initial
prison gate with n 6 horizontal and m=6 vertical bars.
The area of the biggest hole in the bars is 1 x 1. The
right image depicts that same gate after the prisoner
removes horizontal bar 4 and vertical bar 2, at which
point the area of the biggest hole in the bars becomes
2 x2=4



### 贪心

#### C++ 代码

int prisonBreak(int n, int m, vector<int> &h, vector<int> &v)
{
unordered_set<int> h_(h.begin(), h.end());
unordered_set<int> v_(v.begin(), v.end());

int maxh = 0, maxv = 0;
int pre = -1;
for(int i = 1; i <= n; i++)
{
if(h_.find(i) != h_.end()) continue;
else
{
if(pre != -1)
maxh = max(maxh, i - pre);
pre = i;
}
}

if(pre == -1) return -1;

pre = -1;

for(int i = 1; i <= m; i++)
{
if(v_.find(i) != v_.end()) continue;
else
{
if(pre != -1)
maxv = max(maxv, i - pre);
pre = i;
}
}

if(pre == -1) return -1;

return maxh * maxv;
}