# 选择排序

``````void swap(int* arr, int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}

void selectSort(int* arr, int n)
{
//降序
for (int i = 0; i < n; i++)
{
int maxIndex = i;
for (int j = i+1; j < n; j++)
{
if (arr[j] >= arr[maxIndex])
maxIndex = j;
}
swap(arr, i, maxIndex);
}
}
``````

# 平衡字符串

``````class Solution {
public:
int balancedStringSplit(string s) {
if(s.size() == 1)
return 0;
int cnt = 0;
int balance = 0;
for(int i = 0; i < s.size(); i++)
{
if(s[i] == 'R')
--balance;
else
++balance;
if(balance == 0)
cnt++;
}
if(cnt == 0)
return 1;

return cnt;
}
};
``````

# 买股票的最佳时机

``````class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for(int i = 0; i < prices.size() - 1; i++)
{
if(prices[i] <= prices[i+1])
profit += prices[i+1] - prices[i];
}

return profit;
}
};
``````

# 跳跃游戏

``````class Solution {
public:
bool canJump(vector<int>& nums) {
int maxLen = nums[0];
for(int i = 0; i < nums.size(); i++)
{
if(i <= maxLen)
{
maxLen = max(i + nums[i],maxLen);
if(maxLen >= nums.size() - 1)
return true;
}
}

return false;
}
};
``````

# 钱币找零

``````//按面值降序
struct cmp {
bool operator()(vector<int>& a1, vector<int>& a2) {
return a1[0] > a2[0];
}
};

int solve(vector<vector<int>>& moneyCount, int money)
{
int num = 0;
sort(moneyCount.begin(), moneyCount.end(), cmp());
//首先选择最大面值的纸币
for (int i = 0; i < moneyCount.size() - 1; i++)
{
//选择需要的当前面值和该面值有的数量中的较小值
int c = min(money / moneyCount[i][0], moneyCount[i][1]);
money -= c * moneyCount[i][0];
num += c;
}
if (money > 0)
num = -1;
return num;
}
``````

# 多机调度问题

``````struct cmp{
bool operator()(const int& x, const int& y){
return x > y;
}
};

int findMax(vector<int>& machines)
{
int ret = 0;
for (int i = 0; i < machines.size(); i++)
{
if (machines[i] > machines[ret])
ret = i;
}

return machines[ret];
}

int greedStrategy(vector<int>& works, vector<int>& machines)
{
//降序
sort(works.begin(), works.end(), cmp());
int n = works.size();
int m = machines.size();
for (int i = 0; i < n; i++)
{
int finish = 0;
int machineTime = machines[finish];
for (int j = 1; j < m; j++)
{
if (machines[j] < machines[finish])
{
finish = j;
}
}
machines[finish] += works[i];
}

return findMax(machines);
}
``````

# 活动选择

1.每次都选择开始时间最早的活动，不能得到最优解。
2.每次都选择持续时间最短的活动，不能得到最优解。

3.每次选取结束时间最早的活动（结束时间最早意味着开始时间也早），可以得到最优解。按这种方法选择，可以为未安排的活动留下尽可能多的时间。如下图的活动集合S，其中各项活动按照结束时间单调递增排序。

``````struct cmp{
bool operator()(vector<int>& s1, vector<int>& s2){
return s1[1] < s2[1];
}
};

int getMaxNum(vector<vector<int>>& events)
{
sort(events.begin(), events.end(), cmp());
int num = 1;
int i = 0;
for (int j = 1; j < events.size();j++)
{
if (events[j][0] >= events[i][1])
{
++num;
i = j;
}
}

return num;
}
``````

# 无重叠区间

``````struct cmp{
bool operator()(vector<int>& s1, vector<int>& s2){
return s1[1] < s2[1];
}
};

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp());
int num = 1;
int i = 0;
for(int j = 1; j < intervals.size(); j++)
{
if(intervals[j][0] >= intervals[i][1])
{
i = j;
num++;
}
}

return intervals.size() - num;
}
};
``````

``````struct cmp{
bool operator()(vector<int>& s1, vector<int>& s2){
return s1[1] < s2[1];
}
};

class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.empty())
return 0;
sort(intervals.begin(), intervals.end(), cmp());
int prev = 0;
int num = 0;
for(int i = 1; i < intervals.size(); i++)
{
//情况1 不冲突
if(intervals[i][0] >= intervals[prev][1])
{
prev = i;
}
else
{
if(intervals[i][1] < intervals[prev][1])
{
//情况2
prev = i;
}
num++;
}
}

return num;
}
};
``````

THE END