Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
- The length of num is less than 10002 and will be ≥ k.
- The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3 Output: "1219" Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1 Output: "200" Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2 Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
A:
就是先处理删除掉0 的情况, 然后再每次找到前k+1个digit里最小的,保留之。
(哎,我一开始还想用快点儿的方法,后来觉得挺麻烦的,就算了, 先用笨方法,然而 结果beat 96.17%. TNND . )
class Solution { public: string removeKdigits(string num, int k) { // deal with trailing 0 firstly int n = num.length(); for(int i =0;i< min(n, k+1); i++){ //need go further to check num[k],i.e.10200 if(num[i]=='0'){ string sub = num.substr(i+1); return removeKdigits(sub, k-i); } } return helper(num, k); } private: string helper(string num, int k){ // need helper, as we would not deal with heading 0s int n = num.length(); if(n == 0 || n == k) return "0"; if(k==0) return num; // in first k+1, find the smallest and keep it, remove everything before it. char smallestVal = num[0]; int smallestIndex = 0; for(int i =1;i<k+1; i++){ //now n >k, if(num[i] < smallestVal){ smallestVal = num[i]; smallestIndex = i; } } string res(1,smallestVal); // use string constructor to convert char to string // keep smallest char, remove everything before it string subNum = num.substr(smallestIndex+1); int toBeDeleted = k - smallestIndex; return res + (subNum.length() == toBeDeleted?"" : helper(subNum, toBeDeleted)); } };
这里最需要注意的,就是:
要先处理 leading 0 的问题。 然后递归时, 就不处理了。 因此需要helper ()
另外,char to string, 很多时候, 不是可以直接 return "" + 'a' ; 的, 结果时个数字。 TNND
#include <iostream>
#include <string> int main(){ char c = 'A'; // using string class fill constructor std::string s(1, c); std::cout << s << '\n'; return 0; }
No comments:
Post a Comment