zect
BAN USERThis is a simple dynamic programming algorithm. I added comments to make it readable. The output for "aaaa" is 3,3, which different from the results given by the example, which is 0,0. But it actually does not matter because reverse (0,0) and (3,3) all results in the same string.
void maxSwap(string s) {
if(s.length() == 0)
return;
//dynamic programming algorithm
//This matrix records if the substring of s[j]....s[i] should be reversed or not
vector<vector<bool>> goodSwap(s.length(), vector<bool>(s.length(), false));
string minStr = s;//records the smallest string we can achieve
int start = 0;
int end = s.length() - 1;
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j <= i; j++) {
bool good;
if(i - j < 2)
good = true;//if i == j or i = j + 1, always good to reverse
else {
if(s[j] == 'b' && s[i] == 'a')//always good to reverse
good = true;
else if (s[j] == 'a' && s[i] == 'b')//always bad to reverse
good = false;
else// if (s[i] == s[j]), depends on the reversability of s[j + 1]....s[i - 1]
good = goodSwap[i - 1][j + 1];
}
if(good = true){//if it is good to reverse
goodSwap[i][j] = true;
string newStr = s;
reverse(newStr.begin() + j, newStr.begin() + i + 1);//reverse the string
if(newStr <= minStr){//if the reversed string is smaller
start = j;
end = i;
minStr = newStr;//records the smallest string we can achieve
}
}
}
}
cout << start << end << endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
maxSwap("abab");
maxSwap("abba");
maxSwap("bbaa");
maxSwap("aaaa");
maxSwap("babaabba");
return 0;
}
This is a DFS algorithm which gives correct results. Not sure how to improve this by smart algorithms.
#include <iostream>
#include <vector>
using namespace std;
void getMax(vector<int>& input, int k, int& maxNum, vector<int>& output){
if (k == 0) {
int sum = 0;
for (auto v : input) {
sum *= 10;
sum += v;
}//calculate the number after several swaps
if (sum > maxNum) {
maxNum = sum;
output = input;
}//update the results
return;
}
for (int i = 0; i < input.size() - 1; i ++) {
for (int j = i + 1; j < input.size(); j ++) {
swap(input[i], input[j]);//try to swap input[i] with input[j]
getMax(input, k - 1, maxNum, output);//takecare of the other k - 1 swaps
swap(input[i], input[j]);//swap back
}
}
return;
}
void swap2max(vector<int> input, int k) {
if (input.size() < 2) {
cout << "invalid input" << endl;
}
int maxNum = INT_MIN;
vector<int> maxVec;
getMax(input, k, maxNum, maxVec);//DFS function to call
//print out the results here
cout << "{ ";
for (int i = 0; i < maxVec.size(); i ++) {
cout << maxVec[i] << " ";
}
cout << " }" << endl;
return;
}
int main(int argc, const char * argv[])
{
vector<int> input1 = {1,3,2};
swap2max(input1, 1);
vector<int> input2 = {1,3,2};
swap2max(input2, 2);
vector<int> input3 = {7,8,9,9};
swap2max(input3, 2);
vector<int> input4 = {8,7,9,9};
swap2max(input4, 2);
return 0;
}
Use a min_heap to store the second number, the first number is added into results if it is larger than the top element of the min_heap.
- zect October 11, 2014