贪心：remove K digits移除K个数字
问题描述：
已知一个使用字符串表示的非负整数num，将num中的k个数字移 除，求移除k个数字后，可以获得的最小的可能的新数字。
例如：num = “1432219” , k = 3
在去掉3个数字后得到的很多很多可能里，如1432、4322、2219、1219
、1229…; 去掉数字4、3、2得到的1219最小!
贪心规律：
根据以上举例，移除三个数的过程中
每一次我们移除一个数的时候，想要保证最终存储的数是最小的，那么移除当前数的条件就是下一个数小于当前数。当前数处于高位，下一个数显然处于低位，那么保留较小的，即可保证高位是较小的。类似：遍历到14 和143 时，发现3小于4，则将4移除，存储的数据变为13；
迭代策略：
每一次的移除，保证在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 <iostream>
#include <vector>
#include <stack>
#include <string>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
相关文章：
oracle 分组排序 update,oracle分组排序
oracle 分组排序：这个麻烦：SELECT * FROM (SELECT deptno,ename,sal,ROW_NUMBER() OVER (PARTITION BY deptno ORDER BY sal DESC ) Top3 FROM emp)WHERE Top3 < 3开窗函数也ok：代码简单点：where 11 and status2JOIN( select p…
QLocalServer与QLocalSocket进程通讯
在Qt中，提供了多种IPC方法，作者所用的是QLocalServer和QLocalSocket。看起来好像和Socket搭上点边，实则底层是windows的name pipe。这应该是支持双工通信的。一 QLocalServer#ifndef VXMAINWINDOW_H#define VXMAINWINDOW_H#include <QWidg…
JDBC编程步骤
JDBC编程步骤 JDBC编程大致按如下步骤进行： （1）加载数据库驱动。通常我们使用Class类的forName静态方法来加载驱动。例如如下代码： Class.forName(driverClass) driverClass就是数据库驱动类所对应的字符串 例如加载…
（13）中值滤波和双边滤波
其实中值滤波，就是那九个数值，进行排序，选择中间的数值来代替那九个数的中间位置的值，然后再从左到右，从上到下，这样移动运算 下面是均值滤波和高斯滤波的基础知识 中值滤波基础知识 运用中值滤波&a…
贪心：Jump Game 跳跃游戏
一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个 位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回是true或者false判断是否能够跳跃到…
MFC之按键消息（长按处理）
想要实现长按键的一些控制，查了查可以通过捕获键盘事件，然后处理按键时需要进行的操作。下面简单的实现左右按键界面更新数值加减。 1. 重载PreTranslateMessage(MSG* pMsg)函数，在函数中捕获键盘事件并处理响应： BOOL CEditTestD…
服务器oracle11g卸载,卸载Oracle11g步骤详解
卸载Oracle11g步骤详解用Oracle自带的卸载程序不能从根本上卸载Oracle，从而为下次的安装留下隐患，那么怎么才能完全卸载Oracle呢？那就是直接注册表清除，步骤如下：1、 开始－>设置－>控制面板…
Fedora下配置网卡
第一次在fedora下配置静态网卡，首先去网络管理里面添加并设置网卡的IP，子网掩码和默认网关出口，然后保存即可， 也可以在 /etc/sysconfig/network-scripts/ifcfg-eth0 中直接添加这些信息，对应的为网卡的IP，…
echarts相关设置
1.显示隐藏工具栏 注释toolbox即可 /* toolbox: {show : true,feature : {dataView : {show: true, readOnly: false},magicType : {show: true, type: [line, bar]},restore : {show: true},saveAsImage : {show: true}}},*/ 2.鼠标划过数据显示对应的数据 tooltip : {trig…
贪心：jump 游戏（获取最少跳跃的次数以及跳跃路径）
一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个 位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回最少跳跃的次数以及跳跃过程的路径&…
ADO.NET事务
在发布System.Transaction命名空间之前，可以直接用ADO.NET创建事务，也可以通过组件、特性和COM运行库（位于System.EnterpriseServices命名空间中）进行事务处理。本文如题所示，介绍在这些传统事务处理方式中较为简单的“…
oracle表中怎么去重复,oracle去掉表重复数据
今天在做项目过程中，碰到数据库表存在重复记录，显示的时候需要去掉重复的数据。想了老半天，最终用rank() over (partition by 分组字段 order by 排序字段 顺序)解决了此问题。一、首先介绍下rank() over (partition by 分组字段 order by 排…
JavaIO操作(1)字节流和字符流-1
3.2、字节流和字符流（核心） 使用File类执行的所有操作都是针对于文件本身，但是却没有针对于文件的内容，而要进行文件内容操作就需要通过Java之中提供的两组类完成： 字节操作流（是在JDK 1.0的时候定义的&am…
7min到40s：SpringBoot 启动优化实践
然后重点排查这些阶段的代码。先看下。
SpringBoot系列教程之Bean之指定初始化顺序的若干姿势
之前介绍了@Order注解的常见错误理解，它并不能指定 bean 的加载顺序，那么问题来了，如果我需要指定 bean 的加载顺序，那应该怎么办呢？本文将介绍几种可行的方式来控制 bean 之间的加载顺序。
在Java中使用WebSocket
WebSocket是一种协议，用于在Web应用程序和服务器之间建立实时、双向的通信连接。它通过一个单一的TCP连接提供了持久化连接，这使得Web应用程序可以更加实时地传递数据。WebSocket协议最初由W3C开发，并于2011年成为标准。
3种方案，模拟两个线程抢票
在多线程编程中，资源竞争是一个常见的问题。资源竞争发生在多个线程试图同时访问或修改共享资源时，可能导致数据不一致或其他并发问题。在模拟两个线程抢票的场景中，我们需要考虑如何公平地分配票，并确保每个线程都有机会成功获取票。本篇文章将通过三种方式来模拟两个线程抢票的过程，以展示不同的并发控制策略。使用 Synchronized 来确保一次只有一个线程可以访问票资源。使用 ReentrantLock 来实现线程间的协调。使用 Semaphore 来限制同时访问票的线程数量。
初级七 委托与事件
1.委托是一种类型，定义委托后想要实现他需要实例化，而事件其实就是委托的一个实例，加了event修饰； 委托实例化可以在 2.委托的作用：可以作为函数的参数传递； 无委托无异步； 委托主要是用来解耦 …
r-route 命令 显示/配置ip路由表
文章目录前言语法格式命令使用输出含义使用实例前言 route命令用于显示和配置IP路由表，在不同节点间的网络通信，想要实现同一局域网之间的通信就需要交换机，不同局域网之间的通信就需要路由器。而路由器的存在是为了提供NAT转换，…
suse oracle 12c安装,用半行代码实现在LINUX(SUSE/RH)下安装ORACLE 12C
最近新到单位的朋友总是抱怨在LINUX下安装ORACLE，实在是太麻烦了，而且这些步骤既不知是什么意思，也记不住；索性，我就分析了一下，经过实践，实现了只用半行代码(确切的说，只消4个字母)…
shell--数组的定义/访问/赋值/遍历
1 #!/bin/bash2 # 数组3 4 # 数组的定义5 a(0 1 2 3)6 # 数组元素的访问7 echo "a[0]:${a[0]}"8 # 数组的长度9 echo "length:${#a[*]}" 10 # 所有元素 11 echo "all element:${a[*]}" 12 # 删除某个元素 13 unset a[1] 14 echo "after uns…
四百元值不值——论小米2A与2S
作为一个米2用户，面对这手机市场极快的更新速度，有些跟不上速度。最近出了小米2A与2S，碰巧有人问值不值的问题，于是就小小的进行了一个研究，跟大家讨论一下。首先小米2A与2S在我看来就是2的翻版，现在小米的…
python复习冒泡排序
冒泡排序： 思路： 先找到最大值放到最右边： #encodingutf-8 a[1,9,2,8,3,6,4] print "a before change:",a for i in range(len(a)-1): if a[i] > a[i1]: a[i],a[i1] a[i1],a[i] print "a after change:",a 结果&…
linux 文件查找命令集:find,locate,wheres,which,type
文章目录前言find命令命令格式：常用选项：举例使用locate命令命令格式使用实例whereis命令使用过程:which命令type命令前言 在linux系统中一切皆文件，此时我们想要从海量的文件中快速定位中我们想要的文件来，需要指定的命令来操作…
oracle生成xml方法,oracle存储过程生成xml==转
1.创建如下存储过程，注意将其中location >d:\work之中的目录改为你本机的某个目录.create or replace procedure getXML(newContext_qry varchar2,rowSettag varchar2,rowTag varchar2,filename varchar2) is-- Input query string-- Input rowsetTag , the root…
打算看的书或正在看的书
打算看的书或正在看的书 《Data Structures and Algorithm Analysis in C》 正在看，这本书是在博客园上看到某个去google的大牛推荐的，的确，虽然数据结构，我已经很熟悉了，但是看这本书的时候，有一些细节我是…
Tutorial——使用Maven开发Cloud Driver
2019独角兽企业重金招聘Python工程师标准>>> Before You Start 开发之前，应有以下准备 Apache MavenCloudify调用云API的安全凭证，使用SSH访问你的机器，如果需要访问您的云的存储。 例如，通过以下步骤获得OpenStack的安…
[Machine Learning with Python] Data Visualization by Matplotlib Library
Before you can plot anything, you need to specify which backend Matplotlib should use. The simplest option is to use Jupyter’s magic command %matplotlib inline. This tells Jupyter to set up Matplotlib so it uses Jupyter’s own backend. Scatter Plot housin…
贪心：Burst Balloons 最少次数完成射击气球
已知在一个平面上有一定数量的气球，平面可以看作一个坐标系，在平面的x轴的不同位 置安排弓箭手向y轴方向射箭，弓箭可以向y轴走无穷远;给定气球的宽度 xstart ≤ x ≤ xend，问至少需要多少弓箭手，将全部气球打爆? 例如…
linux服务器加固的命令,Linux 服务器安全加固
一、summary随着互联网的发展，隐私以及安全被大家看的越来越重视，越来越多的重要交易正在通过网络完成，与此同时数据被损坏、截取和修改的风险也在增加。优秀的系统应当拥有完善的安全措施，应当足够坚固、能够抵抗来自Internet的侵…