LeetCode(力扣)算法初入（一）----糖果分发，区间重叠，双指针求值匹配

找到的别人整理过的LeetCode相关的实例，实际运行通过之后最个记录。

#include <numeric> //  accumulate  vector求和函数

#include <algorithm>//sort  排序函数

#include<iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;
/************************************************************************/
/*
一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一
个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果;
所有孩子至少要有一个糖果。求解最少需要多少个糖果。
*/
/*
把所有孩子的糖果数初始化为 1；
先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的
糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数
不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。通过这两次遍历，
分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一
侧的大小关系。
*/
/************************************************************************/
//贪心算法分糖果
int candy(vector<int> &_vector, vector<int> &_num){
	int n_size = _vector.size();
	if (n_size < 2)
	{
		return n_size;
	}

	vector<int> num(n_size,1);//给每个人都预先分一颗糖果
	for (int i = 1; i< n_size-1 ; i++)
	{
		if (_vector[i] > _vector[i-1])
		{
			num[i] = num[i-1]+1;
		}
	}

	for (int i = n_size -1 ;i > 0;--i)
	{
		if (_vector[i] < _vector[i-1])
		{
			num[i-1] = max(num[i-1],num[i] +1) ;
		}
	}

	vector<int>::iterator it = num.begin();
	for (;it!=num.end(); it++)
	{
		_num.push_back(*it);
	}
	return accumulate(num.begin(), num.end(),0);
}
/************************************************************************/
/*
给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
*/
/*
先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选
择的区间不重叠的区间。
*/
/************************************************************************/
//区间问题
int eraseOverlapIntervals(vector<vector<int>>& intervals){
	if (intervals.empty()){
		return 0;
	}
	int n = intervals.size();
	sort(intervals.begin(), intervals.end(),[](vector<int> a, vector<int> b){
		return a[1] < b[1];
	});
	int total = 0, prev = intervals[0][1];
	cout<<"要删除的区间："<<endl;
	for (int i = 1;i < n; i++)
	{
		if(intervals[i][0] < prev){
			++total;
			cout<<"intervals["<<intervals[i][0]<<","<<intervals[i][1]<<"]"<<"  ";
		}else
		{
			prev = intervals[i][1];
		}
	}
	cout<<endl;
	return total;
}

//在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。
/************************************************************************/
/*
因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最
小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。
如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。如果两个指针指向元
素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元
素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。
可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最
优解的两个数的位置分别是 l 和 r。我们假设在左指针在 l 左边的时候，右指针已经移动到了 r；
此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达 l。同理，如果我们假设
在右指针在 r 右边的时候，左指针已经移动到了 l；此时两个指针指向值的和大于给定值，因此
右指针会一直左移直到到达 r。所以双指针在任何时候都不可能处于 „l;r” 之间，又因为不满足条
件时指针必须移动一个，所以最终一定会收敛在 l 和 r。
*/
/************************************************************************/
vector<int> twoSum(vector<int>& numbers, int target){
	sort(numbers.begin(), numbers.end(), [](int a,int b){
		return a <b;
	});

	int l = 0, r = numbers.size()-1, sum;
	while (l < r)
	{
		sum = numbers[l] + numbers[r];
		if (sum == target)
		{
			break;
		}
		if (sum < target)
		{
			++l;
		}else
			--r;
	}
	vector<int> tmp;
	tmp.push_back(l+1);
	tmp.push_back(r+1);
	return tmp;
}


int main(){
	vector<int> childValue;
	childValue.push_back(2);
	childValue.push_back(1);
	childValue.push_back(3);
	childValue.push_back(6);
	childValue.push_back(7);
	childValue.push_back(4);

	vector<int> _num;
	int n_total = candy(childValue, _num);

	cout<<"需要的最少糖果数量："<<n_total<<endl;
	vector<int>::iterator it_child = childValue.begin();
	cout<<"身上的分数：";
	for (;it_child != childValue.end();it_child++)
	{
		cout<<*it_child<<" ";
	}
	cout<<endl;

	cout<<"糖果数量  ：";
	vector<int>::iterator it = _num.begin();
	for (;it != _num.end();it++)
	{
		cout<<*it<<" ";
	}
	cout<<endl;
	cout<<endl;
	cout<<"区间数组："<<endl;
	vector<vector<int>> base_vector;
	vector<int> tmp_1;
	tmp_1.push_back(1);
	tmp_1.push_back(3);
	base_vector.push_back(tmp_1);
	cout<<"base_vector[1,3] ";
	vector<int> tmp_2;
	tmp_2.push_back(2);
	tmp_2.push_back(4);
	base_vector.push_back(tmp_2);
	cout<<"base_vector[2,4] ";
	vector<int> tmp_3;
	tmp_3.push_back(4);
	tmp_3.push_back(6);
	base_vector.push_back(tmp_3);
	cout<<"base_vector[4,6] ";
	vector<int> tmp_4;
	tmp_4.push_back(5);
	tmp_4.push_back(9);
	base_vector.push_back(tmp_4);
	cout<<"base_vector[5,9]";
	cout<<endl;
	eraseOverlapIntervals(base_vector);

	int a[5] = {1,3,2,8,4};
	vector<int> numbers(a,a+5);
	vector<int> tmp = twoSum(numbers,9);

	cout<<endl;
	cout<<"排序后的数组："<<endl;
	cout<<"number[";
	for (vector<int>::iterator it_number = numbers.begin(); it_number!= numbers.end();it_number++)
	{
		if (it_number == numbers.end()-1)
		{
			cout<<*it_number;
		}else
		{
			cout<<*it_number<<",";
		}
	}
	cout<<"]"<<endl;
	cout<<"获取的两个数值的位置："<<endl;
	vector<int>::iterator it_tmp = tmp.begin();
	cout<<"tmp[";
	for (;it_tmp != tmp.end();it_tmp++)
	{
		if (it_tmp == tmp.end()-1)
		{
			cout<<*it_tmp;
		}else
		{
			cout<<*it_tmp<<",";
		}
	}
	cout<<"]"<<endl;
	system("pause");
	return 0;
}

输出结果：

需要的最少糖果数量：13
身上的分数：2 1 3 6 7 4
糖果数量  ：2 1 2 3 4 1

区间数组：
base_vector[1,3] base_vector[2,4] base_vector[4,6] base_vector[5,9]
要删除的区间：
intervals[2,4]  intervals[5,9]

排序后的数组：
number[1,2,3,4,8]
获取的两个数值的位置：
tmp[1,5]
请按任意键继续. . .