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.
class Solution {
public:
//使用栈
string removeKdigits(string num, int k)
{
if (k >= num.size())
return "";
string res = "";
int count = k;
for (char c : num)
{
while (count > && res.size() > && res.back() > c)
{
res.pop_back();
count--;
}
res.push_back(c);
}
res = res.substr(,num.length()-k);
while (res.empty()== false && res[] == '')
res.erase(res.begin());
return res.length()<= ? "" : res;
}
//深搜
vector<int> all;
string removeKdigits(string num, int k)
{
if (k >= num.length())
return "";
vector<int> bit(num.length(), );
vector<int> flag(num.length(), );
for (int i = ; i < bit.size(); i++)
bit[i] = (int)(num[i] - '');
getAll(,k, flag, bit);
int minRes = numeric_limits<int>::max();
for (int one : all)
minRes = min(minRes, one);
return to_string(minRes);
}
void dfs(int begin,int k,vector<int>& flag,vector<int>& bit)
{
if (k == )
{
int a = ;
for (int i = ; i < bit.size(); i++)
{
if (flag[i] == )
a = a * + bit[i];
}
all.push_back(a);
}
else if (begin >= flag.size())
return;
else
{
dfs(begin + , k, flag, bit);
flag[begin] = ;
dfs(begin + , k - , flag, bit);
flag[begin] = ;
}
}
};
738.leetcode: Monotone Increasing Digits
Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.
(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)
Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299
class Solution
{
public:
int monotoneIncreasingDigits(int n)
{
string num = to_string(n);
int begin = num.length();
for (int i = num.length() - ; i >= ; i--)
{
if (num[i] >= num[i - ])
continue;
else
{
num[i - ]--;
begin = i;
}
}
for (int i = begin; i < num.length(); i++)
num[i] = '';
return stoi(num);
}
};
321. Create Maximum Number:
Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + nfrom digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits.
Note: You should try to optimize your time and space complexity.
Example 1:
Input:
nums1 =[3, 4, 6, 5]
nums2 =[9, 1, 2, 5, 8, 3]
k =5
Output:[9, 8, 6, 5, 3]
Example 2:
Input:
nums1 =[6, 7]
nums2 =[6, 0, 4]
k =5
Output:[6, 7, 6, 0, 4]
Example 3:
Input:
nums1 =[3, 9]
nums2 =[8, 9]
k =3
Output:[9, 8, 9]
class Solution
{
public:
vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k){
int m = nums1.size(), n = nums2.size();
vector<int> res;
// i的取值范围要小心
for (int i = max(, k - n); i <= min(k, m); ++i) {
res = max(res, mergeVector(maxVector(nums1, i), maxVector(nums2, k - i)));
}
return res;
}
// 栈的思想，求取k个数的最大值
vector<int> maxVector(vector<int> nums, int k) {
// 丢的方式比捡的方式实现
int drop = nums.size() - k;
vector<int> res;
for (int num : nums) {
while (drop && res.size() && res.back() < num) {
res.pop_back();
--drop;
}
res.push_back(num);
}
res.resize(k);
return res;
}
// 和有序数组外排有区别，求最大的归并值
vector<int> mergeVector(vector<int> nums1, vector<int> nums2) {
vector<int> res;
while (nums1.size() + nums2.size()) {
vector<int> &tmp = nums1 > nums2 ? nums1 : nums2;
res.push_back(tmp[]);
tmp.erase(tmp.begin());
}
return res;
}
};