leetcode 402 贪心法非单调栈
class Solution {
public:
string removeKdigits(string num, int k) {
int len = num.length();
if (len <= k) {
num = "0";
return num;
}
int begin = 0;
while (k--) {/*未删完的都有可比较地余地*/
if (begin == num.length() - 1){
num.erase(0,k+1);
break;
}
if (num[begin] > num[begin+1]) num.erase(begin, 1),begin = 0;/*贪心*/
else if (num[begin] == num[begin+1]) {
++begin, ++k;
}
else num.erase(begin+1, 1),begin = 0;
}
bool flag = false;/*指示有无前导零*/
for (int i = 0; i < num.length(); ++i)
if (num[i] == '0') {
flag = true;
if (i == num.length() - 1)num = "0";
continue;
}
else {
if (flag)num.erase(0, i);
break;
}
return num;
}
};
例子过了34个，改了几次，不知道这个不用单调栈地方法逻辑是否可行，能再改改就ac？
参考：
- 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7745984
- 这篇博客也不错, 你可以看下Leetcode:给出一组候选数C和一个目标数T，找出候选数中起来和等于T的所有组合。C中的数字在组合中可以被无限次使用。(回溯法)
- 除此之外, 这篇博客: 记第一次参加Leetcode周赛2021.12.19中的 5957. 向字符串添加空格 AC 部分也许能够解决你的问题。
- 以下回答由chatgpt基于相关博客总结生成:
问题分析
根据代码，这是一个解决LeetCode 402的问题的解决方案。问题是给定一个数字字符串num和一个整数k，需要从num中移除k个数字，使得剩下的数字组成的字符串最小。
该方案通过使用贪心法和非单调栈的策略来解决问题。具体来说，它通过遍历字符串并删除高位比低位大的数字来尽量保留低位较小的数字。在遍历过程中，如果遇到低位与高位相等的数字，则将处理指针往后移一位，以保留较小的数字。
最后，该方案还有一个步骤是删除前导零。
改进空间
根据提供的信息，已经尝试了34个测试用例，并进行了几次修改，但是无法确定逻辑是否正确。对于这种情况，可以考虑以下几个改进空间：
测试用例覆盖率不足：已经尝试了一些测试用例，但是对于复杂的边界情况是否已经考虑并解决了可能存在的问题并不清楚。可以继续寻找一些特殊的测试用例来测试解决方案，并确保覆盖了各种情况，包括边界情况和极限情况。
代码错误：可以先检查代码是否存在语法错误或逻辑错误。可以通过手动计算一些简单的测试用例，检查代码的输出是否与预期一致。还可以在测试用例上添加一些调试输出，以便更好地理解和调试代码的执行。
优化算法和数据结构：根据已提供的代码，可以考虑优化算法和数据结构，以提高执行效率和减少错误的可能性。可以尝试找到更好的算法或数据结构来解决该问题。
解决方案
测试用例
首先，确保测试用例已经充分覆盖了各种情况。可以包括以下类型的测试用例：
- 基本情况：包含一位数字的情况，k为0的情况等。
- 普通情况：包含多位数字和非零k值的情况。
- 边界情况：包含全部数字需要移除的情况（所有数字相等）、k等于字符串长度的情况等。
- 极限情况：包含超大长度字符串和大值k的情况等。
代码错误检查
将代码分析和手动计算结果进行比较，看是否存在错误。可以手动计算简单的测试用例，以检查代码的输出是否与预期一致。还可以在代码中添加一些调试输出，以便更好地理解和调试代码的执行。
优化算法和数据结构
- 考虑使用具有更好时间复杂度的算法。目前给出的代码的时间复杂度为O(k * n)，可以寻找更优的算法。
- 考虑使用更适合该问题的数据结构，例如栈或队列等。
总结
根据现有的信息，问题使用的解决方案是使用贪心法和非单调栈的策略来解决。如果已经尝试了一些测试用例，并对代码进行了检查和分析，但仍然无法确定逻辑是否正确，可以考虑进一步寻找优化的空间，包括增加测试用例覆盖率，检查代码错误以及优化算法和数据结构。
如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^