Cloud_cal
BAN USERMy solution. It is really lengthy, but works fine.
The basic idea is:
1. We start from the right(end digit position of the number).
2. Each possible length is between 1 ~ number.length.
e.g. 9817 -> 9 + 8 = 17 (when length = (4 / 2 = 2))
3. If length is k, the possible combination is
(1). num1(1~k) + num2(k) = num3(k)
(2). num1(k) + num2(1~k) = num3(k)
(3). num1(1~k-1) + num2(k-1) = num3(k)
(4). num1(k-1) + num2(1~k-1) = num3(k)
here, num1(1~k) means the length of num1 could be from 1 to k.
Test Cases:
123 -> true
125 -> false
1235 -> true
121224 -> true
1910 -> true
37239 -> true
370239 -> false (02 is ill-formated)
2353355 -> true
bool isValidHelper(const string& num_str, int i, int k) {
for (int j = k; j >= k - 1; j--) {
for (int t = 1; t <= j; t++) {
int sub1 = -1, sub2 = -1, sub3 = -1;
if (i - (t + j + k - 1) >= 0) {
if (t > 1 && num_str[i - (t + j + k - 1)] - '0' == 0)
break;
else
sub1 = stoi(num_str.substr(i - (t + j + k - 1), t));
} else
break;
if (i - (j + k - 1) >= 0) {
if (j > 1 && num_str[i - (j + k - 1)] - '0' == 0)
break;
else
sub2 = stoi(num_str.substr(i - (j + k - 1), j));
} else
break;
if (i - (k - 1) >= 0) {
if (k > 1 && num_str[i - (k - 1)] - '0' == 0)
break;
else
sub3 = stoi(num_str.substr(i - (k - 1), k));
} else
break;
if (sub1 + sub2 == sub3) {
if (i - k - j - t < 0) {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return true;
}
else {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return isValidHelper(num_str, i - k, j);
}
}
}
}
for (int t = k; t >= k - 1; t--) {
for (int j = 1; j <= t; j++) {
int sub1 = -1, sub2 = -1, sub3 = -1;
if (i - (t + j + k - 1) >= 0) {
if (t > 1 && num_str[i - (t + j + k - 1)] - '0' == 0)
break;
else
sub1 = stoi(num_str.substr(i - (t + j + k - 1), t));
} else
break;
if (i - (j + k - 1) >= 0) {
if (j > 1 && num_str[i - (j + k - 1)] - '0' == 0)
break;
else
sub2 = stoi(num_str.substr(i - (j + k - 1), j));
} else
break;
if (i - (k - 1) >= 0) {
if (k > 1 && num_str[i - (k - 1)] - '0' == 0)
break;
else
sub3 = stoi(num_str.substr(i - (k - 1), k));
} else
break;
if (sub1 + sub2 == sub3) {
if (i - k - j - t < 0) {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return true;
}
else {
cout << sub1 << "," << sub2 << "," << sub3 << endl;
return isValidHelper(num_str, i - k, j);
}
}
}
}
return false;
}
bool isValid(int num) {
string num_str = to_string(num);
int i = (int)num_str.size() - 1;
int len = (int)num_str.size() / 2;
bool ret = false;
for (int k = len; k > 0; k--) {
ret |= isValidHelper(num_str, i, k);
}
return ret;
}
vector<int> generateValidNum(int start, int end) {
vector<int> ret;
for (int i = start; i <= end; i++) {
if (isValid(i))
ret.emplace_back(i);
}
return ret;
}
Here is my code with O(n) time and O(1) space
TreeNode* flipTree(TreeNode* root) {
flipTreeHelper(root);
TreeNode* prev = nullptr;
while (root) {
TreeNode* temp = root->right;
root->right = prev;
prev = root;
root = root->left;
prev->left = temp;
}
return prev;
}
void flipTreeHelper(TreeNode* root) {
if (!root->left && !root->right) { return; }
flipTreeHelper(root->left);
root->left->right = root->right;
root->right = nullptr;
}
I think we need to check each element in the array twice for both 1 and 3. Here is my code with time complexity O(n):
void sort(int a[], int n)
{
int begin = 0;
int end = n - 1;
int i;
while(a[begin]==1)
{
begin++;
}
while(a[end]==3)
{
end--;
}
for(i=begin;i<=end;i++)
{
if(a[i]==1)
{
swap(a[i], a[begin++]);
if(a[i]==3)
swap(a[i], a[end--]);
}
else if(a[i]==3)
{
swap(a[i], a[end--]);
if(a[i]==1)
swap(a[i], a[begin++]);
}
}
}
#include<iostream>
#include<string>
using namespace std;
bool isMatch(string s1, string s2)
{
if(s1.length()==0 && s2.length()==0)
return true;
string s1_next = s1.substr(0, s1.length()-1);
string s2_next = s2.substr(0, s2.length()-1);
if(s1[s1.length()-1]=='*')
{
string s1_next_next = s1.substr(0, s1.length()-2);
return isMatch(s1_next, s2) || isMatch(s1_next_next, s2);
}
else if(s1[s1.length()-1]=='.' && s2[s2.length()-1]!='\0')
{
return isMatch(s1_next, s2_next);
}
else
{
return s1[s1.length()-1]==s2[s2.length()-1] && isMatch(s1_next, s2_next);
}
}
@wws: i think your original solution is correct. Perhaps i misunderstood your improvement, but if you output "impossible" when you're are trying to merge two different existing vertices, what about { p1 S p2, p2 S p3, p3 N p1 } ? I think in this case, all three vertices have the same x coordinate, but it is "possible".
- Cloud_cal November 06, 2014