Problem 1: Number FormationProblem Description Xiao R is learning string processing. Xiao X gave Xiao R a string s, which contains only lowercase letters and digits, and contains at least one digit from 1 to 9. Xiao X hopes that Xiao R can use any number of digits from s, in any order, to form a positive integer. Note: Xiao R can choose the same digit from s, but each digit can only be used once. For example, if s is 1a01b, then Xiao R can choose the 1st, 3rd, and 4th characters (which are 1, 0, and 1) to form the positive integers 101 or 110; but cannot form 111 (since s only contains two 1s). Xiao R wants to know what the maximum positive integer that can be formed is. Please help Xiao R find this maximum value. Input FormatRead data from the file number.in:The first line of input contains a string s, representing the string given to Xiao R by Xiao X.Output FormatOutput to the file number.out:Output one line with a positive integer, representing the maximum positive integer that can be formed.Sample Input 1:5Sample Output 1:5Explanation:s contains only one digit 5, so the only positive integer that can be formed is 5.Sample Input 2:290es1q0Sample Output 2:92100Explanation: s contains the digits 2, 9, 0, 1, 0, and the maximum positive integer is 92100.5. Data RangeLet | s | be the length of the string s, all test data satisfies:•1 ≤ |s| ≤ 10⁶;•s contains only lowercase letters and digits, and contains at least one digit from 1 to 9.
Method 1: Sorting Method
1. Traverse the input string and extract all digit characters.2. Use the standard library’s sort function with greater<char> for descending order sorting.3. Output the sorted string.
#include<bits/stdc++.h>using namespace std;int main() { freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); string s; cin >> s; string digits; for (char c : s) { if (isdigit(c)) { digits.push_back(c); } } sort(digits.begin(), digits.end(), greater<char>()); cout << digits << endl; return 0;}Method 2: Ascending Sort then Reverse Method
1. Extract all digit characters.2. First perform ascending sort.3. Reverse the entire string to get descending order.
#include <bits/stdc++.h>using namespace std;string s, ans;int main(){ freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); cin >> s; for (int i = 0; i < s.size(); i++) { if (s[i] >= '0' && s[i] <= '9') ans += s[i]; } sort(ans.begin(), ans.end()); // Ascending sort reverse(ans.begin(), ans.end()); // Reverse the entire string (descending) cout << ans;}Method 3: Character Counting Method
1. Traverse each digit character from ‘9’ to ‘0’.2. Use the count function to count the occurrences of each digit character in the original string.3. Output the corresponding digit characters in descending order.
#include<bits/stdc++.h>using namespace std;int main(){ freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); string s; cin >> s; for(char c = '9'; c >= '0'; c--) { int t = count(s.begin(), s.end(), c); while(t--) cout << c; } return 0;}Method 4: Counting Array Method
1. Use a counting array to count the occurrences of each character.2. Traverse the string only once to complete the counting.3. Output digit characters from ‘9’ to ‘0’.
#include<bits/stdc++.h>using namespace std;char s[1000005];int cnt[128]; // Count occurrences of each ASCII characterint main(){ freopen("number.in", "r", stdin); freopen("number.out", "w", stdout); cin >> s; int n = strlen(s); for(int i = 0; i < n; i++) cnt[s[i]]++; for(char c = '9'; c >= '0'; c--) { for(int i = 1; i <= cnt[c]; i++) cout << c; } return 0;}