S*******C
发帖数: 822 | 1 Delete Digits
12%
Accepted
Given string A representative a positive integer which has N digits, remove
any k digits of the number, the remaining digits are arranged according to
the original order to become a new positive integer. Make this new positive
integers as small as possible.
N <= 240 and k <=N,
Example
Given an integer A = 178542, k = 4
return a string "12"
Tags Expand
Greedy
public class Solution {
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
public String DeleteDigits(String A, int k) {
// write your code here
}
}
http://lintcode.com/en/problem/delete-digits/ |
p****6
发帖数: 3 | 2 this is the c++ version, based on greedy method.
string DeleteDigits(string A, int k) {
// wirte your code here
int len = A.size();
if(len==k) return "0";
int idx = 0;
while(k>0){
if(A[idx]>A[idx+1]){
A.erase(A.begin()+idx);
k--;
} else{
while(A[idx] <= A[idx+1])
idx++;
A.erase(A.begin()+idx);
k--;
idx = 0;
}
}
while(A.length()>0 &&A[0] == '0')
A.erase(A.begin());
if(A.length() ==0) return "0";
return A;
} |
S*******C
发帖数: 822 | 3 JAVA版怎么写？
【在 p****6 的大作中提到】
: this is the c++ version, based on greedy method.
: string DeleteDigits(string A, int k) {
: // wirte your code here
: int len = A.size();
: if(len==k) return "0";
: int idx = 0;
: while(k>0){
: if(A[idx]>A[idx+1]){
: A.erase(A.begin()+idx);
: k--;
|
h***k
发帖数: 161 | 4 把二楼的c++版翻译了一下，能过但应该还能优化
public class Solution {
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
public String DeleteDigits(String A, int k) {
// write your code here
int len = A.length();
if (len == k) {
return "";
}
int idx = 0;
int[] num = new int[len];
for (int i = 0; i < len; i++) {
num[i] = A.charAt(i) - '0';
}
while (k > 0) {
// if current number is greater than
// next number: decreasing seq. drop
// first digit.
if (num[idx] > num[idx + 1]) {
num[idx] = -1;
k--;
} else {
while (idx + 1 < num.length && num[idx] <= num[idx + 1]) {
// keep increasing idx if pre
// seq is increasing
idx++;
}
// current idx is a violation
num[idx] = -1;
k--;
idx = 0;
num = refresh(num);
}
}
while (num.length > 0 && num[0] == 0) {
num[0] = -1;
num = refresh(num);
}
StringBuilder sb = new StringBuilder();
for (int i : num) {
sb.append(i + "");
}
return sb.toString();
}
public int[] refresh(int[] num) {
int count = 0;
for (int i : num) {
if (i >= 0) {
count++;
}
}
int[] res = new int[count];
int i = 0;
for (int j = 0; j < num.length; j++) {
if (num[j] >= 0) {
res[i++] = num[j];
}
}
return res;
}
}
【在 S*******C 的大作中提到】
: JAVA版怎么写？
|
s*******h
发帖数: 105 | 5 Java 版，这个题一次过很难那。
public String DeleteDigits(String A, int k) {
// write your code here
if(A.length()<2) return A;
int i=0;
StringBuilder s=new StringBuilder(A);
while(i
if(i>=0&&s.charAt(i)>s.charAt(i+1)){
s.deleteCharAt(i);
k--;
if(k==0) break;
i--;
}
else i++;
}
i=s.length()-1;
while(k>0&&i>-1){
s.deleteCharAt(i);
i--;
k--;
}
while(s.charAt(0)=='0'&&s.length()>1){
s.deleteCharAt(0);
}
return s.toString();
} |
k*******e
发帖数: 24 | 6 class Solution {
public:
string DeleteDigits(string A, int k) {
while (k > 0) {
for (int i = 0; i < A.size(); i++) {
if (i == A.size() - 1 || A[i] > Aij+1]) {
A.erase(i, 1);
break;
}
}
k--;
}
auto it = A.begin();
while (*it == '0')
it = A.erase(it);
return A;
}
}; |
d****n
发帖数: 397 | 7 DP
python solution
class Solution:
"""
@param A: A positive integer which has N digits, A is a string.
@param k: Remove k digits.
@return: A string
"""
def DeleteDigits(self, A, k):
# write you code here
l = len(A)
S = [['' for j in range(k + 1)] for i in range(l + 1)]
T = ''
for j in range(0, k + 1):
S[j][j] = ''
for i in range(1, l + 1):
T += A[i - 1]
S[i][0] = T
for j in range(1, k + 1):
for i in range(j + 1, l + 1):
if self.smaller (S[i - 1][j - 1], S[i - 1][j] + A[i - 1]):
S[i][j] = S[i - 1][j - 1]
else:
S[i][j] = S[i - 1][j] + A[i - 1]
res = S[l][k]
p = 0
# remove prevailing zeros
for i in range(len(res)):
if res[i] != '0':
p = i
break
return res[p : ]
def smaller(self, s1, s2):
if int(s1) < int(s2):
return True
else:
return False
remove
positive
【在 S*******C 的大作中提到】
: Delete Digits
: 12%
: Accepted
: Given string A representative a positive integer which has N digits, remove
: any k digits of the number, the remaining digits are arranged according to
: the original order to become a new positive integer. Make this new positive
: integers as small as possible.
: N <= 240 and k <=N,
: Example
: Given an integer A = 178542, k = 4
|
S*******C
发帖数: 822 | 8 Delete Digits
12%
Accepted
Given string A representative a positive integer which has N digits, remove
any k digits of the number, the remaining digits are arranged according to
the original order to become a new positive integer. Make this new positive
integers as small as possible.
N <= 240 and k <=N,
Example
Given an integer A = 178542, k = 4
return a string "12"
Tags Expand
Greedy
public class Solution {
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
public String DeleteDigits(String A, int k) {
// write your code here
}
}
http://lintcode.com/en/problem/delete-digits/ |
p****6
发帖数: 3 | 9 this is the c++ version, based on greedy method.
string DeleteDigits(string A, int k) {
// wirte your code here
int len = A.size();
if(len==k) return "0";
int idx = 0;
while(k>0){
if(A[idx]>A[idx+1]){
A.erase(A.begin()+idx);
k--;
} else{
while(A[idx] <= A[idx+1])
idx++;
A.erase(A.begin()+idx);
k--;
idx = 0;
}
}
while(A.length()>0 &&A[0] == '0')
A.erase(A.begin());
if(A.length() ==0) return "0";
return A;
} |
S*******C
发帖数: 822 | 10 JAVA版怎么写？
【在 p****6 的大作中提到】
: this is the c++ version, based on greedy method.
: string DeleteDigits(string A, int k) {
: // wirte your code here
: int len = A.size();
: if(len==k) return "0";
: int idx = 0;
: while(k>0){
: if(A[idx]>A[idx+1]){
: A.erase(A.begin()+idx);
: k--;
|
|
|
h***k
发帖数: 161 | 11 把二楼的c++版翻译了一下，能过但应该还能优化
public class Solution {
/**
*@param A: A positive integer which has N digits, A is a string.
*@param k: Remove k digits.
*@return: A string
*/
public String DeleteDigits(String A, int k) {
// write your code here
int len = A.length();
if (len == k) {
return "";
}
int idx = 0;
int[] num = new int[len];
for (int i = 0; i < len; i++) {
num[i] = A.charAt(i) - '0';
}
while (k > 0) {
// if current number is greater than
// next number: decreasing seq. drop
// first digit.
if (num[idx] > num[idx + 1]) {
num[idx] = -1;
k--;
} else {
while (idx + 1 < num.length && num[idx] <= num[idx + 1]) {
// keep increasing idx if pre
// seq is increasing
idx++;
}
// current idx is a violation
num[idx] = -1;
k--;
idx = 0;
num = refresh(num);
}
}
while (num.length > 0 && num[0] == 0) {
num[0] = -1;
num = refresh(num);
}
StringBuilder sb = new StringBuilder();
for (int i : num) {
sb.append(i + "");
}
return sb.toString();
}
public int[] refresh(int[] num) {
int count = 0;
for (int i : num) {
if (i >= 0) {
count++;
}
}
int[] res = new int[count];
int i = 0;
for (int j = 0; j < num.length; j++) {
if (num[j] >= 0) {
res[i++] = num[j];
}
}
return res;
}
}
【在 S*******C 的大作中提到】
: JAVA版怎么写？
|
s*******h
发帖数: 105 | 12 Java 版，这个题一次过很难那。
public String DeleteDigits(String A, int k) {
// write your code here
if(A.length()<2) return A;
int i=0;
StringBuilder s=new StringBuilder(A);
while(i
if(i>=0&&s.charAt(i)>s.charAt(i+1)){
s.deleteCharAt(i);
k--;
if(k==0) break;
i--;
}
else i++;
}
i=s.length()-1;
while(k>0&&i>-1){
s.deleteCharAt(i);
i--;
k--;
}
while(s.charAt(0)=='0'&&s.length()>1){
s.deleteCharAt(0);
}
return s.toString();
} |
k*******e
发帖数: 24 | 13 class Solution {
public:
string DeleteDigits(string A, int k) {
while (k > 0) {
for (int i = 0; i < A.size(); i++) {
if (i == A.size() - 1 || A[i] > Aij+1]) {
A.erase(i, 1);
break;
}
}
k--;
}
auto it = A.begin();
while (*it == '0')
it = A.erase(it);
return A;
}
}; |
d****n
发帖数: 397 | 14 DP
python solution
class Solution:
"""
@param A: A positive integer which has N digits, A is a string.
@param k: Remove k digits.
@return: A string
"""
def DeleteDigits(self, A, k):
# write you code here
l = len(A)
S = [['' for j in range(k + 1)] for i in range(l + 1)]
T = ''
for j in range(0, k + 1):
S[j][j] = ''
for i in range(1, l + 1):
T += A[i - 1]
S[i][0] = T
for j in range(1, k + 1):
for i in range(j + 1, l + 1):
if self.smaller (S[i - 1][j - 1], S[i - 1][j] + A[i - 1]):
S[i][j] = S[i - 1][j - 1]
else:
S[i][j] = S[i - 1][j] + A[i - 1]
res = S[l][k]
p = 0
# remove prevailing zeros
for i in range(len(res)):
if res[i] != '0':
p = i
break
return res[p : ]
def smaller(self, s1, s2):
if int(s1) < int(s2):
return True
else:
return False
remove
positive
【在 S*******C 的大作中提到】
: Delete Digits
: 12%
: Accepted
: Given string A representative a positive integer which has N digits, remove
: any k digits of the number, the remaining digits are arranged according to
: the original order to become a new positive integer. Make this new positive
: integers as small as possible.
: N <= 240 and k <=N,
: Example
: Given an integer A = 178542, k = 4
|
I*******x
发帖数: 69 | 15
赞，这个比较易懂。
1. 从最高位往下走，高位比低位大，删除，
2. 如果各位都相等，一位一位删除。
3. 处理高位的零。
【在 s*******h 的大作中提到】
: Java 版，这个题一次过很难那。
: public String DeleteDigits(String A, int k) {
: // write your code here
: if(A.length()<2) return A;
: int i=0;
: StringBuilder s=new StringBuilder(A);
: while(i: if(i>=0&&s.charAt(i)>s.charAt(i+1)){
: s.deleteCharAt(i);
: k--;
|
z*******o
发帖数: 4773 | |
