ravio
BAN USERThis the Java version inspired by uuuouou. Thanks.
public class Test{
public class Node{
int value;
Node left;
Node right;
public Node(int value){
this.value = value;
this.left = null;
this.right = null;
}
}
public int findMinimumLength(Node root, int rest){
if(root == null){
return Integer.MAX_VALUE;
}
rest = root.value;
int minValue = Integer.MAX_VALUE;
//if rest is less than 0, then if we go to left child, we may be faster since all
//the values in the left subtree are less than that in the right subtree.
if(rest < 0){
if(root.left != null){
int value = findMinimumLength(root.left, rest);
minValue = Math.min(minValue, value);
}
if(minValue == Integer.MAX_VALUE && root.right != null){
minValue = Math.min(minValue, findMinimumLength(root.right, rest));
}
}else if(rest > 0){//same thing with right tree.
if(root.right != null){
int value = findMinimumLength(root.right, rest);
minValue = Math.min(minValue, value);
}
if(minValue == Integer.MAX_VALUE && root.left != null){
minValue = Math.min(minValue, findMinimumLength(root.left, rest));
}
}else{//find the sum and this node is the leaf node.
if(root.left == null && root.right == null){
minValue = 0;
}
}
//try to avoid integer overflow
if(minValue == Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}else{
return minValue + 1;
}
}
public static void main(String[] args){
Test test = new Test();
Node root = test.new Node(10);
root.left = test.new Node(2);
root.right = test.new Node(5);
root.left.left = test.new Node(3);
System.out.println(test.findMinimumLength(root, 15));
}
}

ravio
May 30, 2014 If you try it out, you will find out that the swap and sort solution works. You can think about it. For example the easiest case, we have x = 11, 24, 15, a = 2, 1, 3,
Then you swap a[0] with a[1], you get 24, 11, 15 which is exactly what you want. Certainly, this case is not convencing, but you can try other cases. It should work.
Here is another recursive solution to this problem. I tested it using C++
#include<iostream>
#include<string>
using namespace std;
void remove_duplicate(string& input_str, int start_pos, int current_pos){
if(current_pos == input_str.length()  input_str.length() == 1){
if(current_pos  start_pos > 1){
input_str = input_str.substr(0, start_pos) + input_str.substr(current_pos);
}
return;
}
if(input_str[start_pos] == input_str[current_pos]){
remove_duplicate(input_str, start_pos, current_pos + 1);
}else{
//duplication exists
if(current_pos  start_pos > 1){
//remove duplicate
input_str = input_str.substr(0, start_pos) + input_str.substr(current_pos);
remove_duplicate(input_str, max(start_pos  1, 0), start_pos);//max(start_pos  1, 0) means the index cannot be less than 0
}else{
remove_duplicate(input_str, current_pos, current_pos + 1);
}
}
}
int main(){
string input_str = string("AAAAAB");
remove_duplicate(input_str, 0, 1);
if(input_str.length() > 0){
cout<<input_str<<endl;
}else{
cout<<"1"<<endl;
}
return 0;
}

ravio
April 11, 2014 Although you don't have multiinherentence in java, but you can extends from two classes that have the same method. In C++, they are quite different.
class base1 {
void start() { cout << "Inside base1"; }
};
class base2 {
void start() { cout << "Inside base2"; }
};
class derived : base1, base2 { };
int main() {
derived a;
a.start();
}
You can solve it like this
a.base1::start();
a.base2::start();
Or
class derived:public base1,public base2
{
public:
using base1::start;
};

ravio
April 09, 2014 recursive solution using C++
#include<iostream>
#include<string>
using namespace std;
bool hasRemoved = false;
bool recursive_remove(string& str, int pos){
//pos cannot be greater than the length of str.
if(pos >= str.length()){
return hasRemoved;
}
//judge how many identical characters have appeared
int index = pos;
while(index < str.length() && str[index] == str[pos]){
++index;
}
//if duplication exists
if(index  pos > 1){
hasRemoved = true;
str.erase(pos, index  pos);
recursive_remove(str, max(pos  1, 0));//max(pos1, 0) means if it's like AAAB, after erasing AAA, we start from 0, if it is like ADBBC, we start from the first index of B  1.
}else{
recursive_remove(str, pos + 1);
}
return hasRemoved;
}
int main(){
//string str = "ABCCBCBA";
string str = "AA";
if(recursive_remove(str, 0)){
if(str.length() > 0)
cout<<str<<endl;
else
cout<<"1"<<endl;
}
return 0;
}

ravio
April 09, 2014 Assume that all the letters are in lower case. Then we could use the following algorithm. The time complexity is O(26n)
#include<iostream>
#include<string>
using namespace std;
bool check(int* array1, int* array2, int length){
for(int i = 0; i < length; ++i){
if(array1[i] != array2[i]){
return false;
}
}
return true;
}
int isAnagram(char* first, int length1, char* second, int length2){
if(length2 < length1){
return false;
}
int count[26];
int currentCount[26];
memset(count, 0, sizeof(count));
memset(currentCount, 0, sizeof(currentCount));
for(int i = 0; i < length1; ++i){
++count[first[i]  'a'];
}
for(int i = 0; i < length2; ++i){
if(i >= length1  1){
++currentCount[second[i]  'a'];
if(check(count, currentCount, 26)){
return i  length1 + 1;
}
currentCount[second[i  length1 + 1]  'a'];
}else{
++currentCount[second[i]  'a'];
}
}
return 1;
}
int main(){
char* first = "tea";
char* second = "slate";
int startIndex = 1;
if((startIndex = isAnagram(first, strlen(first), second, strlen(second))) >= 0){
cout<<string(second).substr(startIndex, strlen(first))<<endl;
}else
cout<<"none"<<endl;
}

ravio
April 09, 2014 Sorry for the confusion, I misspell the dp , it should be the following. The idea is that we can build the dp array from left to right. But here I made an assumption that all the elements in the array are not negative. Am I right?
For example we have an array
1 2 1 1 1
The index are
0 1 2 3 4
Then dp[0] = 0, dp[0 + array[0]] = dp[1] = 1 initially, then we update it to dp[1] = 1 because we can get to index 1 throught dp[0] + array[0]. Here dp[i] means the minimum steps we need to get to index i.
int minHop(int* array, int length){
int* dp = new int[length];
memset(dp, 1, sizeof(dp));
dp[0] = 0
for(int i = 0; i < length; ++i){
if(dp[i] >= 0){
if(i + array[i] < length){
if(dp[i + array[i]] == 1  dp[i + array[i]] > dp[i] + 1){
dp[i + array[i]] = dp[i] + 1;
}
}
}
int result = dp[length  1];
delete dp;
return result;
}
Actually, this algorithm is not right because we can jump less than array[i] according to the question. But I am assuming that we can only jump exactly array[i]. I am sorry.
 ravio March 28, 2014This is an incremental question. We can solve it easily in O(n)
int minHop(int* array, int length){
int* dp = new int[length];
memset(dp, 1, sizeof(dp));
dp[0] = 0
for(int i = 0; i < length; ++i){
if(dp[i] >= 0){
if(dp[i + dp[i]] == 1  dp[i + dp[i]] > dp[i] + 1){
dp[i + dp[i]] = dp[i] + 1;
}
}
}
int result = dp[length  1];
delete dp;
return result;
}

ravio
March 27, 2014 Here is a working version of C++ which is more concise than using stacks.
#include<string>
#include<iostream>
using namespace std;
int evaluateExpression(string s){
int sum = 0;
int times = 0;
int product = 1;
for(int i = 0; i < s.length(); ++i){
int number = 0;
while(s[i] == ' ')
++i;
while(i < s.length() && s[i] >= '0' && s[i] <= '9'){
number = number * 10 + s[i]  '0';
++i;
}
while(i < s.length() && s[i] == ' '){
++i;
}
if(i == s.length()){
if(times){
return product * number + sum;
}else{
return sum + number;
}
}else{
if(s[i] == '+'){
if(times){
sum += product * number;
}else{
sum += number;
}
times = 0;
product = 1;
}else{
times = 1;
product *= number;
}
}
}
return sum;
}
int main(){
cout<<evaluateExpression("1 * 2 + 3 * 5 + 2 + 1 + 7")<<endl;
}

ravio
March 27, 2014 I would prefer do it using recursion
#include<iostream>
#include<vector>
#include<stack>
#include<map>
using namespace std;
void printString(string s, int i){
if(i == s.length()){
cout<<s<<endl;
return;
}
if(s[i] >= '0' && s[i] <= '9'){
printString(s, i + 1);
}else{
printString(s, i + 1);
if(s[i] >= 'A' && s[i] <= 'Z'){
s[i] = s[i] + 0x20;
printString(s, i + 1);
}else{
s[i] = s[i]  0x20;
printString(s, i + 1);
}
}
}
int main(){
string s = "0ab";
printString(s, 0);
return 0;
}

ravio
March 26, 2014 Open Chat in New Window
I don't understand why the output of 100 will the the value you give, I thought it should be 1 / (2 * 100) = 0.005.
Here is my code
 ravio May 31, 2014