Объяснение алгоритма:
Стратегия жадного алгоритма состоит в том, чтобы гарантировать, что каждая операция является локально оптимальной, так что конечный результат является глобально оптимальным.
Например: A и B любят есть яблоки, A может съесть 5 яблок, B может съесть 3 яблока, и всегда есть неограниченное количество яблок, затем найдите максимальное количество яблок, которые двое могут съесть в сумме, это очевидно. , 5+3, что является результатом локального оптимума. Это жадная стратегия.
Проблема назначения:
455. Распространение файлов cookie
легкая сложность
Допустим, вы замечательный родитель и хотите подарить своим детям немного печенья. Однако каждому ребенку можно дать не более одного файла cookie.
на каждого ребенкаi, имеют значение аппетитаg[i], это печенье самого маленького размера, которое удовлетворит детский аппетит; и каждое печеньеj, все имеют размерs[j]. еслиs[j] >= g[i], мы можем разместить этот файл cookiejназначается детямi, ребенок будет доволен. Ваша цель — удовлетворить как можно больше детей и вывести это максимальное значение.
Пример 1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
Пример 2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
Код переменного тока:
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int g1 =0 ,s1 =0;
while(g1<g.size()&&s1<s.size()){
if(g[g1]<=s[s1]) g1++;
s1++;
}
return g1;
}
};
Идеи:
Во-первых, мы знаем количество детей и пищу, в которой они нуждаются, а также размер каждой еды, и каждый ребенок может съесть только одну еду. Затем, чтобы сделать больше детей сытыми, мы не должны начинать кормить детей, которые едят больше, тогда мы должны начать кормить детей, которые едят меньше всего. И мы всегда начинаем кормить с ребенка, который ест меньше всего, поэтому мы, конечно, не можем кормить ребенка, который вначале ест меньше пищи старшего возраста, поэтому мы должны сравнивать самый маленький кусок пищи с ребенком с наименьшим голодом, чтобы максимально использовать Ребенок сыт.
Сложность Сложность
Воспитатель хочет раздать детям конфеты, есть
N
Дети встают в прямую линию, и учитель заранее оценивает каждого ребенка в зависимости от его успеваемости.
Вам нужно будет помочь учителю раздать конфеты этим детям, выполнив следующие требования:
- Выделите каждому ребенку хотя бы по 1 конфете.
- Ребенок с более высоким баллом должен получить больше конфет, чем ребенок рядом с ним.
Так сколько хотя бы конфет нужно приготовить учителю?
Пример 1:
输入：[1,0,2]
输出：5
解释：你可以分别给这三个孩子分发 2、1、2 颗糖果。
Пример 2:
输入：[1,2,2]
输出：4
解释：你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
Код переменного тока:
class Solution {
public:
int candy(vector<int>& ratings) {
int size=ratings.size();
if(size<2){
return size;
}
vector<int> num(size,1);
for(int i=1;i<size;i++){
if(ratings[i]>ratings[i-1]){
num[i]=num[i-1]+1;
}
}
for(int i=size-1;i>0;i--){
if(ratings[i]<ratings[i-1]){
num[i-1]=max(num[i]+1,num[i-1]);
}
}
return accumulate(num.begin(), num.end(), 0); // std::accumulate 可以很方便 地求和
}
};
Идеи:
Известно, что каждому ребенку дается хотя бы одна конфета, поэтому дайте каждому ребенку по конфете, а затем обход слева направо, после обхода справа налево, обратите внимание, что когда второй обход не начат, из-за первый обход, каждый Количество конфет для каждого ребенка может быть совершенно разным, поэтому вместо простого использования num[i]=num[i-1]+1; big результат равен +1.
Вопросы двустороннего алгоритма PDD
Вам дан массив, в котором разница между каждым значением в массиве и его соседними элементами равна m, теперь вам дано целевое значение k, найдите индексы всех элементов в массиве, равные k, вернитесь, используя набор.
Чем меньше элементов нужно пройти, тем лучше, неупорядоченный
List fun(List list,int m,int k)
Например, [1,2,3,2,1,0,-1,0,1] m=1 k=3 возвращает [2], k должно быть значением в массиве
Справочный код, который я написал:
class Solution {
public:
int getK(vector<int>& list,int m,int k) {
int index=0;
int len=list.size();
while(index<len){
int cur=list[index];
int step=Math.abs(cur-k)/m;
if(step==0){
return ++index;
}
else{
index+=step;
};
}
}
Идея: Во-первых, это проблема алгоритма большой фабрики, я чувствую, что расследование почти жадное, и я не знаю, что это такое, во всяком случае, мышление очень ясное.
Разница между соседними элементами в этом неупорядоченном массиве равна m, тогда мы начинаем с первого элемента и продолжаем поиск до тех пор, пока текущий элемент минус целевой элемент не равен 0. Этот код использует m для пропуска шагов. , index+=step; это значительно сокращает количество обходов и отвечает требованиям интервьюера.
435. Непересекающиеся интервалы
средняя сложность
Учитывая набор интервалов, найдите минимальное количество интервалов, которые нужно удалить, чтобы оставшиеся интервалы не перекрывали друг друга.
Уведомление:
- Можно считать, что конечная точка интервала всегда больше его начальной точки.
- Границы интервалов [1,2] и [2,3] «касаются» друг друга, но не перекрывают друг друга.
Пример 1:
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
Пример 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
Пример 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
Код переменного тока:
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[1] < v[1];
});
int count=0,cur=intervals[0][1],size=intervals.size();
for(int i=1;i<size;++i){
if(intervals[i][0]<cur){
++count;
}
else{
cur=intervals[i][1];
}
}
return count;
}
};
Идеи:
Многие воротилы в этом вопросе используют динамическое программирование, но можно использовать и жадность. Известно, что задача требует на выходе удалить хотя бы несколько массивов, поэтому жадную стратегию для этой задачи мы находим отсюда: сортируем второй элемент каждого массива, а затем по очереди сравниваем первые элементы соседних массивов.
легкая сложность
Допустим, есть очень длинная клумба, одна часть участка засажена цветами, а другая нет. Однако цветы нельзя сажать на соседних участках, они будут конкурировать за воду, и оба погибнут.
дает вам массив целых чиселflowerbedПредставляет собой клумбу, состоящую из нескольких0и1состоит из0Указывает, что цветы не посажены,1Указывает, что цветы посажены. другой номерn, можно сажать, не нарушая правил посадкиnцветок? может вернутьсяtrue, если нет, вернутьfalse.
Пример 1:
输入：flowerbed = [1,0,0,0,1], n = 1
输出：true
Пример 2:
输入：flowerbed = [1,0,0,0,1], n = 2
输出：false
Код переменного тока:
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
for(int i=0; i<flowerbed.size(); i++) {
if(flowerbed[i] == 0 && (i == 0 || flowerbed[i-1] == 0) && (i == flowerbed.size()-1 || flowerbed[i+1] == 0)) {
n--;
if(n <= 0) return true;
flowerbed[i] = 1;
}
}
return n <= 0;
}
};
Идеи:
Жадная стратегия этой задачи очень проста, то есть если вы можете сажать цветы, вы можете сажать цветы, и условий для посадки цветов всего несколько: само-ноль и ноль справа и крайний слева ноль слева и ноль слева и справа ноль сам по себе И слева и справа ноль, чтобы можно было вставить больше всего цветов.
452. Взорвите воздушные шары с минимальным количеством стрел.
Средняя сложность 456
В двумерном пространстве много сферических шаров. Для каждого воздушного шара вводятся начальные и конечные координаты диаметра воздушного шара в горизонтальном направлении. Поскольку он горизонтальный, ордината не имеет значения, поэтому достаточно знать начальную и конечную абсциссы. Начальная координата всегда меньше конечной координаты.
Лук и стрела могут быть выпущены совершенно перпендикулярно из разных точек вдоль оси X. Стреляйте стрелой в координату x, если есть воздушный шар, диаметр которого начинается и заканчивается в координатахx``start,x``end, и удовлетворитьxstart ≤ x ≤ x``end, воздушный шар взорвется. Количество луков, из которых можно стрелять, не ограничено. Как только лук и стрелы выпущены, они могут двигаться вперед бесконечно. Мы хотим найти минимальное количество луков, необходимое для взрыва всех воздушных шаров.
дает вам массивpoints,вpoints [i] = [xstart,xend], который возвращает минимальное количество стрел, которое необходимо запустить, чтобы взорвать все воздушные шары.
Пример 1:
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
Пример 2:
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
Пример 3:
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
Пример 4:
输入：points = [[1,2]]
输出：1
Пример 5:
输入：points = [[2,3],[2,3]]
输出：1
Код переменного тока:
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& intervals) {
if (intervals.empty()) {
return 0;
}
sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
return u[0] < v[0];
});
int count=1,size=intervals.size();
for(int i=1;i<size;++i){
if(intervals[i][0]<=intervals[i-1][1]){
intervals[i][1]=min(intervals[i-1][1],intervals[i][1]);
}
else{
++count;
}
}
return count;
}
};
Идеи:
Стратегия этого вопроса состоит в том, чтобы отсортировать начальное положение каждого воздушного шара, а затем решить, подходят ли начальное и конечное положения соседних воздушных шаров.Как только два воздушных шара можно взорвать вместе, конечные положения двух воздушных шаров должны занять минимальное значение. Затем оцените, можно ли взорвать следующий воздушный шар.
средняя сложность
нитьSСостоит из строчных букв. Мы хотим разделить эту строку на как можно больше сегментов, чтобы одна и та же буква встречалась не более чем в одном сегменте. Возвращает список, представляющий длину каждого фрагмента строки.
Пример:
输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
Код переменного тока:
class Solution {
public:
vector<int> partitionLabels(string s) {
int map[26]={0},cur=0,pre=0;
vector<int> arr;
for(int i=0;i<s.size();i++){
map[s[i]-'a']=i;
}
for(int i=0;i<s.size();i++){
cur=max(cur,map[s[i]-'a']);
if(i==cur){
arr.push_back(cur-pre+1);
pre=cur+1;
}
}
return arr;
}
};
Идеи:
Столкнувшись с проблемой такого рода, мы наиболее чувствительны к последнему вхождению каждой буквы, потому что, если вы не знаете эту позицию, как найти наименьший массив, поэтому давайте плыть по течению и искать последнее вхождение каждой буквы, затем начните с первой буквы, чтобы сформировать закрытый массив, и используйте pre и cur для вычисления длины.
122. Лучшее время для покупки и продажи акций II
Средняя сложность 1355
задан массивprices,вprices[i]является заданным запасомiдневная цена.
Разработайте алгоритм для расчета максимальной прибыли, которую вы можете получить. Вы можете совершить столько сделок, сколько сможете (покупая и продавая акции несколько раз).
**Примечание.** Вы не можете участвовать в нескольких сделках одновременно (вы должны продать предыдущие акции перед повторной покупкой).
Пример 1:
输入: prices = [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
Пример 2:
输入: prices = [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
Пример 3:
输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
Код переменного тока:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int count=0;
for(int i=0;i<prices.size()-1;i++){
if(prices[i]<prices[i+1]){
count+=prices[i+1]-prices[i];
}
}
return count;
}
};
Идеи:
Такого рода вопрос не прост для получения результата, но если я смотрю на него с жадной точки зрения, то для получения максимальной прибыли я могу даже покупать или продавать каждый день, а не действовать при падении цены , чтобы добиться максимизации прибыли.
406. Реконструкция когорт по росту.
средняя сложность
Предположим, что есть группа людей, стоящих в очереди не по порядку, массивpeopleУказывает атрибуты некоторых людей в очереди (не обязательно по порядку). каждыйpeople[i] = [hi, ki]означает первыйiРост человека составляетhi,Фронтв самый разимеютkiвысота больше или равнаhiлюди.
Восстановите и верните входной массивpeopleуказанную очередь. Возвращаемая очередь должна быть отформатирована как массивqueue,вqueue[j] = [hj, kj]стоит первым в очередиjличные качества (queue[0]человек в начале очереди).
Пример 1:
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
解释：
编号为 0 的人身高为 5 ，没有身高更高或者相同的人排在他前面。
编号为 1 的人身高为 7 ，没有身高更高或者相同的人排在他前面。
编号为 2 的人身高为 5 ，有 2 个身高更高或者相同的人排在他前面，即编号为 0 和 1 的人。
编号为 3 的人身高为 6 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
编号为 4 的人身高为 4 ，有 4 个身高更高或者相同的人排在他前面，即编号为 0、1、2、3 的人。
编号为 5 的人身高为 7 ，有 1 个身高更高或者相同的人排在他前面，即编号为 1 的人。
因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
Пример 2:
输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
Код переменного тока:
class Solution {
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
vector<vector<int>> arr;
sort(people.begin(), people.end(), [](const auto& u, const auto& v) {
if (u[0] == v[0]) return u[1] < v[1];
return u[0] > v[0];
});
for(int i=0;i<people.size();i++){
if(arr.size()<=people[i][1]) arr.push_back(people[i]);
else{
arr.insert(arr.begin() +people[i][1], people[i]);
}
}
return arr;
}
};
Идеи:
Жадная идея этого вопроса на самом деле заключается в том, чтобы сначала отсортировать высоту в порядке убывания, а если высота одинакова, второй параметр сортируется в порядке возрастания. В этом случае мы можем иметь четкое суждение о людях, которые выше, чем этот человек перед нами.Сначала мы ставим более высоких людей первыми и используем второй параметр в качестве их индекса, а затем позволяем последним использовать второй параметр в качестве их индекса.Параметры вставляются вперед, почему это возможно сделать? Потому что, когда люди позади вас войдут в этот двумерный массив, вы обнаружите, что каждый сидящий человек выше вас, поэтому ваш второй параметр можно использовать в качестве индекса, позволяющего вам напрямую врезаться в очередь.
665. Неубывающие последовательности.
Средняя сложность 608
дает вам длинуnмассив целых чисел, пожалуйста, оцените всамыйИзменять1Можно ли превратить массив в неубывающую последовательность с количеством элементов.
Определим неубывающую последовательность следующим образом: для любогоi (0 <= i <= n-2), всегда удовлетворятьnums[i] <= nums[i + 1].
Пример 1:
输入: nums = [4,2,3]
输出: true
解释: 你可以通过把第一个4变成1来使得它成为一个非递减数列。
Пример 2:
输入: nums = [4,2,1]
输出: false
解释: 你不能在只改变一个元素的情况下将其变为非递减数列。
Код переменного тока:
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
if (nums.size() <= 1) {
return true;
}
int cnt = 0;
for (int i = 1; i < nums.size() && cnt < 2; i++) {
if (nums[i-1] <= nums[i]) {
continue;
}
cnt++;
if (i-2>=0 && nums[i-2] > nums[i]) {
nums[i] = nums[i-1];
}else {
nums[i-1] = nums[i];
}
}
return cnt <= 1;
}
};
Идеи:
Этот вопрос сложнее, и здесь много соображений.Основная идея такова: если известно, что элемент меньше своего предыдущего элемента, если его предыдущий элемент не существует, то сделать предыдущий элемент равным этому элементу, а если предыдущий элемент не существует Если элемент существует, и этот элемент больше, чем этот элемент, то сделать этот элемент равным предыдущему элементу, если предыдущий элемент меньше этого элемента, сделать предыдущий элемент равным этому элементу, и проблема может быть решена идеально.
Жадный алгоритм кажется простым, но на самом деле нет фиксированной рутины, добавьте картинку и вернитесь, чтобы прочитать ее снова после очистки вопроса: