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));
}
}
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;
}
Although you don't have multi-inherentence 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;
};
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(pos-1, 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;
}
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;
}
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;
}
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;
}
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;
}
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