---

1.柠檬水找零

1.题目链接

• 柠檬水找零

---

2.算法原理详解

• 分情况讨论：
  • 如果是5元，只接收下
  • 如果是10元，找零5元之后，收下
  • 如果是20元，则出现贪心策略
    • 先优先考虑10 + 5的组合
    • 如果凑不出来，则拼凑5 + 5 + 5的组合

---

3.代码实现

bool lemonadeChange(vector<int>& bills) 
{int five = 0, ten = 0;for(auto& x : bills){if(x == 5){five++;}else if(x == 10){if(five == 0) {return false;}else{five--;ten++;}}else{if(ten && five){ten--;five --;}else if(five >= 3){five -= 3;}else{return false;}}}return true;
}

---

2.将数组和减半的最少操作次数

1.题目链接

• 将数组和减半的最少操作次数

---

2.算法原理详解

• 思路：贪心 + 大根堆
• 贪心：每次挑选当前数组中，最大的那个数，然后减半，直到数组和减少到至少一半为止

---

3.代码实现

int halveArray(vector<int>& nums) 
{double sum = 0.0;priority_queue<double> heap;for(const auto& x : nums){heap.push(x);sum += x;}sum /= 2.0;int count = 0;while(sum > 0){double tmp = heap.top() / 2;heap.pop();sum -= tmp;count++;heap.push(tmp);}return count;
}

---

3.最大数

1.题目链接

• 最大数

---

2.算法原理详解

• 贪心：正确的排序顺序，确定谁在前，谁在后
  • ab > ba：a前，b后
  • ab == ba：无所谓
  • ab < ba：b前，a后
• 优化：把数转化成字符串，然后拼接字符串，比较字典序
• 策略：本题只需要给出排序策略，排序工作可以通过调用sort()完成
• 返回值：排除前导0
  • ret[0] == 0 ? 0 : ret

---

3.代码实现

string largestNumber(vector<int>& nums) 
{// 优化：先转化成字符串，再比较字典序vector<string> strs;for(const auto& x : nums){strs.push_back(to_string(x));}sort(strs.begin(), strs.end(), [](const string& s1, const string& s2){return s1 + s2 > s2 + s1;});string ret;for(const auto& str : strs){ret += str;}return ret[0] == '0' ? "0" : ret;
}

---

4.摆动序列

1.题目链接

• 摆动序列

---

2.算法原理详解

• 贪心：统计出所有的波峰以及波谷的数量
  

• 如何统计出最终的结果？

  • 统计过程中，可能会有下述几种情况
    

  • 解决方案：无视/挖空中间平的地方即可

    right = nums[i - 1] - nums[i];// 如果是平的，跳过该点即可
    if(right == 0) continue;if(left * right <= 0)
    {ret++;
    }left = right;
    

    

---

3.代码实现

int wiggleMaxLength(vector<int>& nums) 
{int n = nums.size();if(n < 2) return n;int ret = 0, left = 0;for(int i = 0; i < n - 1; i++){int right = nums[i + 1] - nums[i];// 跳过平的地方if(right == 0){continue;}// 寻找波峰/波谷if(left * right <= 0){ret++;}left = right;}return ret + 1;
}