首页 > 贪心：remove K digits移除K个数字

贪心：remove K digits移除K个数字

问题描述：

已知一个使用字符串表示的非负整数num，将num中的k个数字移 除，求移除k个数字后，可以获得的最小的可能的新数字。

例如：num = “1432219” , k = 3

在去掉3个数字后得到的很多很多可能里，如1432、4322、2219、1219

、1229…; 去掉数字4、3、2得到的1219最小!

  1. 贪心规律：

    根据以上举例，移除三个数的过程中

    每一次我们移除一个数的时候，想要保证最终存储的数是最小的，那么移除当前数的条件就是下一个数小于当前数。当前数处于高位，下一个数显然处于低位，那么保留较小的，即可保证高位是较小的。

    类似：遍历到14 和143 时，发现3小于4，则将4移除，存储的数据变为13；

  2. 迭代策略：

    每一次的移除，保证在k的范围内，保留的数是比上一位小的即可

实现过程可以使用栈来存储最终的结果，出栈的条件即为以上所说的迭代策略。

实现如下(文末有完整测试代码):

string remove_k_num(string &str,int k){ /*使用vector，同样支持类似于栈的操作*/vector<int> S;string result="";if (str == "" || k == 0) { return str;}int number;for (int i = 0;i < str.length(); ++i) { number = str[i] - '0';//将字符转为数字/*迭代策略：保证k满足的情况下，存储数据的栈不为空，则每次迭代，将栈顶较大的移除*/while(0 != S.size() && S[S.size() -1] > number && k >0 ) { S.pop_back();k--;}/*处理0的情况，即0处在中间位置时才可以入栈，因为0不能做为数字的开头，不属于有效位*/if(number != 0 || S.size() != 0) { S.push_back(number);}}/*处理持续递增的情况，类似12345，没有出栈的，则即可从栈顶直接弹出*/while(S.size() != 0 && k >0) { S.pop_back();k--;}/*将栈中的整型数据转为字符串最终返回*/for (int i =0;i < S.size(); ++i) { result.append(1,S[i] + '0');}if (result == "") { result = "0";}return result;
}

测试代码如下:

#include 
#include 
#include 
#include using namespace std;string remove_k_num(string &str,int k){ vector<int> S;string result="";if (str == "" || k == 0) { return str;}int number;for (int i = 0;i < str.length(); ++i) { number = str[i] - '0';while(0 != S.size() && S[S.size() -1] > number && k >0 ) { S.pop_back();k--;}if(number != 0 || S.size() != 0) { S.push_back(number);}}while(S.size() != 0 && k >0) { S.pop_back();k--;}for (int i =0;i < S.size(); ++i) { result.append(1,S[i] + '0');}if (result == "") { result = "0";}return result;
}int main() { string s;int k;cout << "input the string and k " << endl;cin >> s;cin >> k;cout << "the min number is " << remove_k_num(s,k) << endl;return 0;
}

输出如下:

input the string and k 
432895689 4
the min number is 25689input the string and k 
100010 2
the min number is 0

更多相关：

  • 为什么必须是final的呢？

    一个谜团 如果你用过类似guava这种“伪函数式编程”风格的library的话，那下面这种风格的代码对你来说应该不陌生： 1 2 3 4 5 6 7 8 9 public void tryUsingGuava() { final int expectedLength = 4; Iterables.filter(...

  • Condition_number

    http://en.wikipedia.org/wiki/Condition_number...

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

  • des vue 双倍长 解密_3DES双倍长加密 - osc_ojx9hm4t的个人空间 - OSCHINA - 中文开源技术交流社区...

    importjava.security.SecureRandom;importjavax.crypto.Cipher;importjavax.crypto.SecretKey;importjavax.crypto.SecretKeyFactory;importjavax.crypto.spec.DESKeySpec;//结果与DES算...

  • 剑指offer：面试题05. 替换空格

    题目：替换空格 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 输入：s = "We are happy." 输出："We%20are%20happy." 限制： 0 <= s 的长度 <= 10000 解题： 时间复杂度：O(n) 空间复杂度：O(n) class Solution { public:s...

  • c++ to_string用法

    在C++11标准库中，string.h已经添加了to_string方法，方便从其他类型（如整形）快速转换成字面值。 例如： for (size_t i = 0; i < texArrSize; i++)RTX_Shader.SetInt(string("TexArr[") + to_string(i) + "]", 7 + i);...

  • Ubuntu 14.04 64位字体美化(使用文泉驿微黑)

    Ubuntu 14.04安装并升级之后，变成楷体字体非常难看，我昨天搞了一晚上，终于理了个头绪，这里整理一下。 经过网上调研，大家的一致看法是，使用开源字体库文泉驿的微黑字体效果比较理想，甚至效果不输windows平台的雅黑字体。下面我打算微黑来美化Ubuntu 14.04. 1.安装文泉驿微黑字体库 sudo aptitude...

  • 关于std::string 在 并发场景下 __grow_by_and_replace free was not allocated 的异常问题

    使用string时发现了一些坑。 我们知道stl 容器并不是线程安全的，所以在使用它们的过程中往往需要一些同步机制来保证并发场景下的同步更新。 应该踩的坑还是一个不拉的踩了进去，所以还是记录一下吧。 string作为一个容器，随着我们的append 或者 针对string的+ 操作都会让string内部的数据域动态增加，而动态增加的...

©2024 11GX.COM