DManchala16@students.claremontmckenna.edu
BAN USERBFS using C++.
class Position {
public:
int _x;
int _y;
Position(int x, int y) :
_x(x),
_y(y) {
}
bool operator== (const Position& rhs) {
return _x == rhs._x && _y == rhs._y;
}
};
vector<Position> neighbors(const Position& curr, const vector<vector<int>>& puzzle) {
vector<Position> neighbors = {
Position(curr._x - 1, curr._y),
Position(curr._x + 1, curr._y),
Position(curr._x, curr._y - 1),
Position(curr._x, curr._y + 1)
};
for (auto it = neighbors.begin(); it != neighbors.end();) {
const Position& p = *it;
if (p._x == -1 || p._x == puzzle[0].size() || p._y == -1 || p._y == puzzle.size()) {
it = neighbors.erase(it);
}
else {
++it;
}
}
return neighbors;
}
bool pathExists(vector<vector<int>> &puzzle,
const Position& start,
const Position& end) {
queue<Position> Q;
Q.push(start);
puzzle[start._y][start._x] = 1;
while (Q.size() > 0) {
Position curr = Q.front();
Q.pop();
if (curr == end) {
return true;
}
for (Position& neighbor : neighbors(curr, puzzle)) {
if (puzzle[neighbor._y][neighbor._x] == 0) {
puzzle[neighbor._y][neighbor._x] = 1;
Q.push(neighbor);
}
}
}
return false;
}
can, what about this O(n^2) solution?
string smallestUniqueCharSubsequence(const string& s) {
string solution;
solution += s[0];
for (int i = 1; i < s.size(); ++i) {
int j;
for (j = solution.size() - 1; j >= 0; --j) {
if (s[i] == solution[j]) {
if(static_cast<int>(solution[j + 1]) < static_cast<int>(solution[j])) {
solution.erase(solution.begin() + j);
solution += s[i];
}
break;
}
}
if (j == -1) {
solution += s[i];
}
}
return solution;
}
Never mind, can is right, just tested.
- DManchala16@students.claremontmckenna.edu September 10, 2015Never mind, understood, the next lowest index is the lowest index of any char in the input string already used in the solution. Good job!
- DManchala16@students.claremontmckenna.edu September 10, 2015Does anyone have an O(n) solution? This is an O(n^2) solution:
string smallestUniqueCharSubsequence(const string& s) {
string solution;
solution += s[0];
for (int i = 1; i < s.size(); ++i) {
int j;
for (j = solution.size() - 1; j >= 0; --j) {
if (s[i] == solution[j]) {
if(static_cast<int>(solution[j + 1]) < static_cast<int>(solution[j])) {
solution.erase(solution.begin() + j);
solution += s[i];
}
break;
}
}
if (j == -1) {
solution += s[i];
}
}
return solution;
}
My algorithm is identical to Alexander's, except in C++.
vector<int> commonElements(const vector<int>& v1, const vector<int>& v2) {
vector<int> common;
int i = 0;
int j = 0;
while (i < v1.size() && j < v2.size()) {
if (v1[i] == v2[j]) {
common.push_back(v1[i]);
++i;
++j;
}
if (v1[i] < v2[j]) {
++i;
}
if (v1[i] > v2[j]) {
++j;
}
}
return common;
}
Passes all of the cases from the comments tested against.
int prev(int curr) {
return (curr + 3) % 4;
}
int opp(int curr) {
return (curr + 2) % 4;
}
bool crossesPath(const vector<double>& steps) {
if (steps.size() < 4) {
return false;
}
vector<double> bounds = {steps[0], steps[1], 0, 0};
bool decreased = false;
for (int i = 2, j = 2; i < steps.size(); ++i, j = i % 4) {
if (steps[i] < bounds[opp(j)] || (steps[i] == bounds[opp(j)] && !decreased)) {
if (!decreased && steps[i] >= bounds[opp(j)] - bounds[j]) {
bounds[prev(j)] -= bounds[opp(prev(j))];
}
if (!decreased) {
decreased = true;
}
}
else if (decreased) {
return true;
}
bounds[j] = steps[i];
}
return false;
}
string longestCommonSubsequence(const string& s1, const string& s2) {
// Compute table of partial lengths of longest common SS's
vector<vector<int>> partials(s2.size(), vector<int>(s1.size(), 0));
partials[0][0] = (s1[0] == s2[0]);
for (int i = 1; i < s1.size(); ++i) {
partials[0][i] = max<int>(partials[0][i - 1], s1[i] == s2[0]);
}
for (int i = 1; i < s2.size(); ++i) {
partials[i][0] = max<int>(partials[i - 1][0], s2[i] == s1[0]);
}
for (int i = 1; i < s2.size(); ++i) {
for (int j = 1; j < s1.size(); ++j) {
partials[i][j] = max<int>(max<int>(partials[i - 1][j],
partials[i][j - 1]),
partials[i - 1][j - 1] + (s1[j] == s2[i]));
}
}
// Produce string of longest common SS
int i = s2.size() - 1;
int j = s1.size() - 1;
string longest;
while (i >= 0 && j >= 0 && partials[i][j] > 0) {
if (i > 0 && partials[i - 1][j] == partials[i][j]) {
--i;
}
else if (j > 0 && partials[i][j - 1] == partials[i][j]) {
--j;
}
else {
longest += s2[i];
--i;
--j;
}
}
reverse(longest.begin(), longest.end());
return longest;
}
string shortestStringContainingSubsequences(const string& s1, const string& s2) {
string longest = longestCommonSubsequence(s1, s2);
string res;
auto i = s1.begin();
auto j = s2.begin();
auto k = longest.begin();
while (res.size() < s1.size() + s2.size() - longest.size()) {
if (*j == *k) {
// Append all chars in s1 not in s2 to result
while (*i != *j) {
res += *i;
++i;
}
++i;
++k;
}
// Either append common char or char in s2 not in s1
res += *j;
++j;
}
return res;
}
#include <vector>
#include <exception>
using namespace std;
void incrementIntegerArray(vector<int>& A) {
// Checking for invalid input - skip to second for loop for algorithm
if (A[0] < 0 || A[0] > 9) { // Not a valid array of digits
throw exception();
}
int i;
for (i = 1; i < A.size(); ++i) {
if (A[i] < 0 || A[i] > 9) { // Not a valid array of digits
throw exception();
}
if (A[i] != 9) {
break;
}
}
if (i == A.size() && A[0] == 9) { // A is all 9's
throw exception();
}
if (i < A.size() && A[0] == 0) { // A + 1 will have a leading 0
throw exception();
}
// Algorithm
int carry = 1;
for (i = static_cast<int>(A.size() - 1); i > 0; --i) {
int sum = A[i] + carry;
A[i] = sum % 10;
carry = sum / 10;
}
A[0] += carry;
}
- DManchala16@students.claremontmckenna.edu September 21, 2015