題目
本人比較菜浴捆，八道題只a了五道比較簡單的办成，在這里簡單整理一下思路。
題目就只附上鏈接胜宇，不完全復制過來了。
題目分別是：
 周賽.png
|
 雙周賽.png
|
|---|
題目分析
5384.擁有最多糖果的孩子
這題目描述起來看著挺難的恢着，實際很簡單桐愉。遍歷一遍數(shù)組找到數(shù)組最大值。然后再次遍歷數(shù)組掰派，計算每個元素與最大值的差值从诲，如果這個差值大于額外的糖果數(shù)量，那么返回false靡羡，反之系洛，則返回true。
比較簡單亿眠，完整解答見最后碎罚。
5385.改變一個整數(shù)能得到的最大差值
這道題思路也比較簡單，就是實現(xiàn)起來略微復雜纳像。
首先要將這個數(shù)組的每一位數(shù)字都取出來荆烈，比較直觀的想法是對這個數(shù)字除10取余可以得到個位數(shù)字，然后再對這個除10取商竟趾，循環(huán)上述過程憔购，直到當前數(shù)組小于等于0。
由于這樣的過程是從個位數(shù)開始存取岔帽，為了方便后續(xù)操作玫鸟，我使用了棧來保存每一位數(shù)字。
stack<int> s;
while (num > 0){
s.push(num % 10);
num /= 10;
}
然后需要將改變這個數(shù)字犀勒，需要分別改造成最大值和最小值屎飘。
改造最大值的方法：從棧的頂部開始遍歷妥曲，如果第一個元素不等于9，那么將其記錄并改為9钦购；如果第一個元素等于9檐盟，那么彈出，直到遇到不為9的第一個數(shù)字押桃，記錄其并改為9葵萎。之后不斷彈出頂端元素，將與記錄值相等的元素都改為9唱凯。
改造最大值的過程如下：
int max_num = 0;
int flag = 0;
int len = s.size();
for (int i = 0; i < len; i++){
if (flag == 0){
if (s.top() != 9){
int temp = s.top();
flag = 1;
}
}else {
if (s.top() == temp) s.top() = 9;
}
max_num += pow(10, s.size() - 1) * s.top();
s.pop();
}
改造最小值的方法比最大值復雜一點羡忘，由于不能將首位改為0，所以如果首位不為1的情況磕昼，應該將首位的數(shù)字全部改成1卷雕；如果首位不為1，應該將接下來的第一個非0元素改為0掰烟。
改造最小值的過程如下：
int min_num = 0;
while (s.top() == 1 || s.top() == 0){
min_num += pow(10, s.size() - 1) * s.top();
s.pop();
flag = 0;
}
int len = s.size();
int temp = s2.top();
for (int i = 0; i < s.size(); i++){
if (flag == 0){
if (s.top() == temp) s.top() = 0;
}else {
if (s.top() == temp) s.top() = 1;
}
min_num += pow(10, s.size() - 1) * s.top();
s.pop();
}
最后返回最大值與最小值的差值即可爽蝴。
5386.檢查一個字符串是否可以打破另一個字符串
這道題我最初想復雜了，我最初沒有思路纫骑，只好暴力求解：利用回溯算法求出s1和s2的全排列蝎亚，然后將依次將兩個字符串的全排列對比是否可以打破，只要找到一個可以打破的先馆，就返回true发框。
上述思路可以計算出結果，但是最后幾組數(shù)據(jù)會超時煤墙。最后幾分鐘時梅惯，我突然想到，可以給s1和s2分別按字典序排序仿野，然后直接計算排序后的s1和s2能否打破或被打破即可铣减。
在這里簡單梳理一下分辨兩個字符串能否打破或被打破的過程：用兩個計數(shù)器分別記錄s1[i] > s2[i]和s1[i] < s2[i]的個數(shù)，如果s1[i] == s2[i]脚作，兩個計數(shù)器都自增1葫哗。
bool isBreak(string s1, string s2){
if (s1.length() == 0) return false;
int in = 0;
int out = 0;
int len = s1.length();
for (int i = 0; i < len; i++){
if (s1[i] == s2[i]){
in++;
out++;
}
else if (s1[i] > s2[i]) in++;
else out++;
}
return out == len || in == len;
}
題目完整的解答見最后。
5400.旅行終點站
這道題目也是看起來復雜實際簡單的球涛。
我是暴力解開的劣针，遍歷每個路線，取終點亿扁，然后檢驗這個終點是否是別的路線的捺典，若不是任何其他路線的起點，則返回這個終點即可从祝。
int count = 0;
int len = paths.size();
for (auto t1 : paths){
for (auto t2 : paths){
if (t1[1] == t2[0]) count++;
else break;
}
if (len == count) return t1[1];
else continue;
}
完整解答見最后襟己。
5401.是否所有1都至少相隔k個元素
這道題也比較簡單引谜。使用一個數(shù)組記錄給定數(shù)組中值為1的索引，然后遍歷這個索引數(shù)組稀蟋，如果相鄰元素差值小于k煌张，則返回false。
for (int i = 0; i < nums.size(); i++){
if (nums[i] == 1) temp.push_back(i);
}
if (temp.size() == 0) return true;
for (int i = 0; i < temp.size() - 1; i++){
if (temp[i + 1] - temp[i] - 1 < k) return false;
}
return true;
完整的解答見最后退客。
題目解答
5384.擁有最多糖果的孩子
class Solution {
public:
vector<bool> res;
vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {
if (candies.size() == 0) return res;
int max = candies[0];
for (auto temp : candies){
if (temp > max) max = temp;
}
// 思路 找到最大值，再遍歷一遍數(shù)組链嘀，如果差值小于等于extracandies萌狂，則返回true；
for (auto temp : candies){
if (max - temp <= extraCandies) res.push_back(true);
else res.push_back(false);
}
return res;
}
};
5385.改變一個整數(shù)能得到的最大差值
class Solution {
public:
stack<int> s1, s2;
int maxDiff(int num) {
if (num < 10) return 8;
while (num > 0){
s1.push(num % 10);
num /= 10;
}
s2 = s1;
int len = s1.size();
int num1 = 0;
int num2 = 0;
int flag = 0;
int temp;
for (int i = 0; i < len; i++){
if (flag == 0){
if (s1.top() != 9) {
temp = s1.top();
s1.top() = 9;
flag = 1;
}
}else {
if (s1.top() == temp){
s1.top() = 9;
}
}
num1 += s1.top() * pow(10, s1.size() - 1);
s1.pop();
}
while (s2.top() == 1 || s2.top() == 0){
num2 += pow(10, s2.size() - 1) * s2.top();
s2.pop();
flag = 0;
}
len = s2.size();
temp = s2.top();
for (int i = 0; i < len; i++){
if (flag == 0){
if (s2.top() == temp){
s2.top() = 0;
}
}else {
if (s2.top() == temp){
s2.top() = 1;
}
}
num2 += pow(10, s2.size() - 1) * s2.top();
s2.pop();
}
return num1 - num2;
}
};
5386.檢查一個字符串是否可以打破另一個字符串
bool isBreak(string s1, string s2){
if (s1.length() == 0) return false;
int in = 0;
int out = 0;
int len = s1.length();
for (int i = 0; i < len; i++){
if (s1[i] == s2[i]){
in++;
out++;
}
else if (s1[i] > s2[i]) in++;
else out++;
}
return out == len || in == len;
}
bool checkIfCanBreak(string s1, string s2) {
sort(s1.begin(), s1.end());
sort(s2.begin(), s2.end());
return isBreak(s1, s2);
}
5400.旅行終點站
class Solution {
public:
string res;
string destCity(vector<vector<string>>& paths) {
if (paths.size() == 1) return paths[0][1];
int count = 0;
int len = paths.size();
for (auto t1 : paths){
for (auto t2 : paths){
if (t1[1] == t2[0]) break;
else count++;
}
if (count == len){
res = t1[1];
break;
}else {
count = 0;
}
}
return res;
}
};
5401.是否所有1都至少相隔k個元素
class Solution {
public:
vector<int> temp;
bool kLengthApart(vector<int>& nums, int k) {
if (nums.size() == 1) return true;
for (int i = 0; i < nums.size(); i++){
if (nums[i] == 1) temp.push_back(i);
}
if (temp.size() == 0) return true;
for (int i = 0; i < temp.size() - 1; i++){
if (temp[i + 1] - temp[i] - 1 < k) return false;
}
return true;
}
};
