发表于： 2020-01-11 21:32:47
1 1275
今日完成
- 题目
- 给出一个整数，从该整数中去掉k个数字，要求剩下的数字形成的新整数尽可能小，如何选取被去掉的数字
- 其中整数的长度大于或等于k，给出的整数的大小可以超过long类型的数字范围
- 举例
- 给出一个整数1 593 212，删去3个数字，新整数最小的情况是1212
- 设给出一个整数30 200，删去1个数字，新整数最小的情况是200
- 假设给出一个整数10，删去2个数字（注意，这里要求删去的不是1个数字，而是2个），新整数的最小情况是0
- 给出一个整数1 593 212，删去3个数字，新整数最小的情况是1212
- 以栈的方式实现：整数541 270 936，k=3
- 1 当遍历到数字5时，数字5入栈
- 2 当遍历到数字4时，发现栈顶5>4，栈顶5出栈，数字4入栈
- 当遍历到数字1时，发现栈顶4>1，栈顶4出栈，数字1入栈
- 继续遍历数字2、数字7，并依次入栈
- 遍历数字0，发现栈顶7>0，栈顶7出栈，数字0入栈
- 此时k的次数已经用完，无须再比较，让剩下的数字一起入栈
- 1 当遍历到数字5时，数字5入栈
- 代码
- 代码
- 1.创建一个栈，用于接收所有的数字
- 2.得到结果的Stack
- 3.找到栈中第1个非零数字的位置，以此构建新的整数字符串
- 测试
- 1.创建一个栈，用于接收所有的数字
- 结果
- 代码
- 时间复杂度：只对所有数字遍历了一次，遍历的时间复杂度是O(n)，把栈转化为字符串的时间复杂度也是O(n)——>最终的时间复杂度是O(n)
- 空间复杂度：利用栈来回溯遍历过的数字及删除数字，是O(n)
明日计划
争取demo
返回列表
评论