lintcode delete digits怎么做？ - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - lintcode delete digits怎么做？

相关主题
● 贡献G家电面面经
● 求解lintcode Majority Number III
● lintcode 上的 Count of Smaller Number before itself
● 一道面试题(integer to binary string)
● share int2roman and roman2int java version
● 星期一福利：某公司店面题
● 发个evernote的code challenge
● FB 面筋
● 问道google面试题
● 问个考古的题

相关话题的讨论汇总
话题: idx话题: string话题: int话题: num话题: return

进入JobHunting版参与讨论

(共1页)

S*******C
发帖数: 822

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

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

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

把二楼的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

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

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

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

p****6
发帖数: 3

S*******C
发帖数: 822

JAVA版怎么写？

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

相关主题
● 一道面试题(integer to binary string)
● share int2roman and roman2int java version
● 星期一福利：某公司店面题
● 发个evernote的code challenge
进入JobHunting版参与讨论

h***k
发帖数: 161

: JAVA版怎么写？

s*******h
发帖数: 105

k*******e
发帖数: 24

d****n
发帖数: 397

I*******x
发帖数: 69

赞，这个比较易懂。
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

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

(共1页)

进入JobHunting版参与讨论

相关主题
● 问个考古的题
● 好不容易写了个bug free, 可是被说会秒据, 帮看看
● 请教一道算法题
● linkedin,rocketfuel, google面经若干
● 求解lintcode Wood Cut 问题
● 请教leetcode上的count and say
● lintcode Majority Number II 怎么做？
● lintcode subarray sum 怎么做？
● 收到G家拒信，发面经
● 问个java hashcode的题

相关话题的讨论汇总
话题: idx话题: string话题: int话题: num话题: return

boards