Pony’s Stable

Leetcode battlefield:Start Coding With C++

So, the buggy judging system of python is unbearable, therefore I just turned to C++ and expected a better experience. Also, I need to learn C++ for my future career. So, a good start. This post contains following problems:

  • Reverse words
  • Eval RPN
  • Tree Traversal

Reverse words

Before solving this problem I never tried using std::string, I thought string operation in C++ is as hard as C. However, standard library really ease my pains. In fact, with the help of std, I think coding with C++ is much more easier and happier than coding with Ruby and Python now.

Question:

Given an input string, reverse the string word by word.

Basic logic:

The idea is simple, find each word in the sentence, push then in the stack and pop back after dealing the whole sentence. Be careful to the spaces in the head or tails of the sentence and the repeated spaces.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
public:
    void reverseWords( string &s )
    {
        // get the words in reverse order
        vector<string> words;
        split( s, ' ', words);
        // reconstruct
        s = "";
        if( words.size() == 0 )return;
        for( int i=0; i<words.size();i++)
        {
            s.append(words[i]);
            s.append(" ");
        }
        // delete last space
        s.erase( s.length()-1, -1);

    }

    void split( string &s, char c, vector<string> &v )
    {
        int begin, last;
        // first word
        begin = s.length() -1 ;
        last  = s.find_last_of( c, begin );
        if( s.substr( last+1, begin-last) != "")
        {
            v.push_back(s.substr( last+1, begin-last));
        }
        // find next words
        while( last > 0 and begin != -1 )
        {
            // find a word 
            begin = last - 1;
            last  = s.find_last_of( c, begin );
            // if it's repeated split character, skip it
            while( last == begin )
            {
                begin = last - 1;
                last  = s.find_last_of( c, begin );
            }
            // skip if is last space
            if( s.substr( last+1, begin-last) != "")
            {
                v.push_back(s.substr( last+1, begin-last));
            }
        }
    }
};

evalRPN

Question:

Evaluate the value of an arithmetic expression in Reverse Polish Notation. For example: [“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9

Basic logic:

Also simple idea: Iterater through the list, push numbers to a stack. Everytime we meet operaor, pop top 2 numbers and calculate the result, push the result to the stack. Finally, there will be only one number in the stack, which is the reuslt.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        vector<int> resultStack;
        string symbol;
        int left, right, result;
        bool isOperator;
        for(int i=0; i<tokens.size();i++)
        {
            symbol = tokens[i];
            isOperator =  symbol=="+"||symbol=="-"||symbol=="*"||symbol=="/";
            if( ! isOperator )
                resultStack.push_back(std::stoi(symbol));
            else
            {
                right = resultStack.back();
                resultStack.pop_back();
                left = resultStack.back();
                resultStack.pop_back();
                if(symbol=="+")
                    result = left + right;
                else if(symbol =="-")
                    result = left - right;
                else if(symbol=="*")
                    result = left * right;
                else if(symbol=="/")
                    result = left / right;
                else
                    cout << "ERROR";
                resultStack.push_back(result);
            }
        }
        return resultStack.back();
    }
};

Tree traversal

Basic logic:

Basic algo. There are 3 kind of traversal method: postorder, preorder and inorder.

PostOrder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

using namespace std;

class Solution {
public:
    vector<int> postorderTraversal(TreeNode *root) {
        vector<int> v;
        if( root == NULL){
            return v;
        }
        else{
            if( root->left != NULL ){
                travel( root->left, v );
            }
            if( root->right != NULL){
                travel( root->right, v );
            }
            v.push_back(root->val);
            return v;
        }
    }
    void travel( TreeNode *node, vector<int> &v ){
        if( node->left != NULL ){
            travel( node->left, v );
        }
        if( node->right != NULL){
            travel( node->right, v );
        }
        v.push_back(node->val);
    }
};
PreOrder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

using namespace std;

class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> v;
        if( root == NULL ){
            return v;
        }
        v.push_back(root->val);
        if( root->left ){
            travel( root->left, v );
        }
        if( root->right ){
            travel( root->right, v);
        }
        return v;
    }

    void travel(TreeNode *node, vector<int> &v){
        v.push_back(node->val);
        if( node->left ){
            travel( node->left, v );
        }
        if( node->right ){
            travel( node->right, v);
        }
    }
};