cvs 10% off 的BEAUTY胖子， - 未名空间MITBBS历史存档

cvs 10% off 的BEAUTY胖子，# PennySaver - 省钱一族

S*C2011-07-25 07:07

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/

a*32011-07-25 07:07

2 楼

下午申请加入后就去店里买了OLAY，回来才发现，收到个10% OFF的BEAUTY 胖子，请教
下，这种胖子可以和其它的OFF 胖子叠用吗？比如那个 5 OFF SKIN CARE的？
这个也是只有3天的有效期，都不知道买什么好，已经完成OLAY的本周任务了。

p*62011-07-25 07:07

3 楼

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;
}

g*n2011-07-25 07:07

4 楼

我当初加入时收到的这个胖子也过期浪费了。
你仔细看下能用在sale的东西上吗？如果能倒还不错

S*C2011-07-25 07:07

5 楼

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--;

p*h2011-07-25 07:07

6 楼

not good on sales. only on full price items, pretty much useless

h*k2011-07-25 07:07

7 楼

把二楼的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版怎么写？

r*r2011-07-25 07:07

8 楼

re

【在 p*****h 的大作中提到】

: not good on sales. only on full price items, pretty much useless

s*h2011-07-25 07:07

9 楼

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(iif(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();
}

a*32011-07-25 07:07

10 楼

谢谢各位，原来跟那些25% OFF一样的，不能用在ON SALE的东西上，就没啥意思。可惜
我居然打印出来了，浪费墨水了。

k*e2011-07-25 07:07

11 楼

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*n2011-07-25 07:07

12 楼

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*C2011-07-25 07:07

13 楼

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*62011-07-25 07:07

14 楼

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*C2011-07-25 07:07

15 楼

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*k2011-07-25 07:07

16 楼

把二楼的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*h2011-07-25 07:07

17 楼

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(iif(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*e2011-07-25 07:07

18 楼

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*n2011-07-25 07:07

19 楼

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*x2011-07-25 07:07

20 楼

赞，这个比较易懂。
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*o2011-07-25 07:07

21 楼

删掉首位0‘s 就不是delete k位了。