移除K位数字
想法一：动态规划
String num代表了输入的数字。
A.思路：
当处理第n位上的数字的时候，用f(n,k)表示删除后所剩的结果
A.如果删除k位，那么可以得到当我删除第n位时候我的结果f(n,k) = f(n-1,k-1) 也就是说我最终的结果和我从0->n-1位删除k-1位的结果一样
B.如果不删除第k位，不删除第n位时候的结果f(n,k) = f(n-1,k)+num.charAt(n) 也就是说我保留第n位，然后从n-1位中删除k位
那么什么时候删什么时候不删除呢？
当f(n-1,k-1)代表的数大于f(n-1,k)+num,.charAt(n)那么就不删除，否则就删除
可以规约成
公式
情况说明：情况1：当删除的位数小于数字的位数。情况2：表示当数字有n位，且删除n位，情况3：表示删除的位数大于数的位数，肯定不可删，那么没有结果。情况4.当有n位，但是删除0位，直接返回该数
B.代码:
private static int findMinValue(String num, int k) {
String[][] f = new String[num.length()+1][k+1];
for(int i=1;i<num.length()+1;i++)f[i][0]=num.substring(0,i); //情况一
for(int i=1;i<num.length()+1;i++){
for(int j=1;j<k+1;j++){
if(i==j)f[i][j]=""; //情况二
else if(i<j)break; //情况三
else{ //情况四
int val1 = getMyValue(f[i-1][j-1]); //假设删除该位
int val2 = getMyValue(f[i-1][j]); //假设不删除该位
val2 = val2*10+Character.digit(num.charAt(i-1),10);
if(val2>=val1){
f[i][j] = f[i-1][j-1];
}else{
f[i][j] = f[i-1][j]+String.valueOf(num.charAt(i-1));
}
}
}
}
return Integer.valueOf(f[num.length()][k]);
}
private static int getMyValue(String s) {
if(s.equals("")){
return 0;
}
return Integer.valueOf(s);
}
以上代码可以运行但是题目中有一个限制
image.png
那么说明getValue的值一定会溢出，int的最大位数是10位，而long是18位远远不能满足条件
那么我们只能去比较String了
public String removeKdigits(String num, int k) {
String[][] f = new String[num.length()+1][k+1];
for(int i=1;i<num.length()+1;i++)f[i][0]=num.substring(0,i);
for(int i=1;i<num.length()+1;i++){
for(int j=1;j<k+1;j++){
if(i==j)f[i][j]="";
else if(i<j)break;
else{
if(isBigger(f[i-1][j]+String.valueOf(num.charAt(i-1)),f[i-1][j-1])){
f[i][j] = f[i-1][j-1];
}else{
f[i][j] = f[i-1][j]+String.valueOf(num.charAt(i-1));
}
}
}
}
String result = cleanMyZero(f[num.length()][k]);
return result.length() ==0 ?"0":result;
}
private boolean isBigger(String s1, String s2) {
//这么做的前提是我们知道s1和s2的长度是一样的
int index = 0;
while(index<s1.length()){
if(s1.charAt(index)>s2.charAt(index)){
return true;
}else if(s1.charAt(index)<s2.charAt(index)){
return false;
}
index++; //相等，检查下一位
}
return true; //如果相等也返回true
}
private String cleanMyZero(String s) {
int index =0;
while(index<s.length()){
if(s.charAt(index) != '0') {
break;
}
else index++;
}
return index == s.length()?"":s.substring(index);
}
这个算法的所有逻辑都是正确的，但是当长度为10001时的测试用例超出时间限制
image.png
image.png
image.png
我们把所有的n>=k的地方都算了，那么我们就是算了(n-k+1+n)k/2步，那么这个时间复杂度为O((2n-k+1)k)≈O(nk),空间复杂度为O(nK)
想法二：贪心法（来自王越的想法）
1.想法：
我要从n位中删除K位，那么我就还剩n-k位.那么要从这n-k位中找出最小的，我们可知第一位一定是从0->k处选取的，然后选取的原则是选最小的那一个，如果最小的那一个有多个，那么我们选最前面的那一个。例如：
image.png
n=6 k=2:也就是删除2位余下4位。
第一位取值范围，因为如果第一位在后面3位中去肯定没有4位了
image.png
然后我们比较一下记录最小值出现的地方，可以看到是1，那么第一位就是index = 0的1
接下来第二位的取值范围为前一位取值的index+1到K+1，也就是因为取了一位了，而我剩下3位需要取，子问题就是变成剩下的数取3位，一直重复这个过程直到剩余所取位数等于0
image.png
可以看到第二位取值为2，并且是最前面的2.
image.png
2.代码
先实现查找数字的功能
private String findMyNum(int start, int end, int hasNum, int allleft, String temp, String num) {
if(hasNum == allleft){ //当我要找的数等于我已经找到的数就直接返回
return temp;
}else{
char standard = num.charAt(start); //查找范围内最小的数
int index = start;
for(int i=start+1;i<=end;i++){
if(num.charAt(i)<standard){
index = i;
standard = num.charAt(i);
}
}
temp+=num.charAt(index); //加上范围内最小的数
return findMyNum(index+1,end+1,hasNum+1,allleft,temp,num); //查找下一个
}
}
但是上面的代码当数字很大的时候栈中栈帧的数字很大，可能会溢出
image.png
所以不使用递归的写法，改写为迭代
image.png
3.完整代码
public String removeKdigits(String num, int k) {
String result = cleanMyZero(findMyNum(0,k,0,num.length()-k,"",num));
result = result.length() == 0 ?"0":result; //当result长度为0时，返回0
return result;
}
private String findMyNum(int start, int end, int hasNum, int allleft, String temp, String num) { //寻找数字的过程
while(hasNum!=allleft){
char standard = num.charAt(start);
int index = start;
for(int i=start+1;i<=end;i++){
if(num.charAt(i)<standard){
index = i;
standard = num.charAt(i);
}
}
temp+=num.charAt(index);
start = index+1;
end = end+1;
hasNum++;
}
return temp;
}
private String cleanMyZero(String s) { //移除前面多出来的0
int index =0;
while(index<s.length()){
if(s.charAt(index) != '0') {
break;
}
else index++;
}
return index == s.length()?"":s.substring(index);
}
网友评论