[LEETCODE] Sort Colors

[LEETCODE] Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

思路:

定义一个red指针在最左，一个blue指针在最右。

一个变量从0开始向blue指针扫描：

遇到red(0)  就跟red 指针对换，red 指向下一个，扫描变量指向下一个；

遇到blue(2)就跟blue指针对换，blue指向前一个，扫描变量不动，因为需要判断被换了的值。

代码:

An one-pass algorithm using only constant space

    void sortColors(int A[], int n) {

        int red  =0  ;

        int blue =n-1;

        int i=0;

        while(i<blue+1){

            if(A[i] == 0){

                std::swap(A[red], A[i]);

                red++;

                i++;

                continue;

            }

            if(A[i] == 2){

                std::swap(A[blue],A[i]);

                blue--;

                continue;

            }

            i++;

        }

    }

[LEETCODE] Binary Tree Postorder Traversal

[LEETCODE] Binary Tree Postorder Traversal 

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1

    \

     2

    /

   3

return [3,2,1].

思路：

Postorder: 左右中。

注意点：

1. Recursive method iterate 条件先判断root 是否存在.

2. 对于Non-recursive method. 用两个vector，vector1存树上的node，vector2存值;
    1) 开始的判断root是否为NULL 不要忘了，且在vector1中存入root;
    2) 循环结束条件为vector1为空; 循环内容是，存node值到vector2，存node的左右（先左后右）node到vector1
    3) vector2存的顺序是反的，所以最后用一个reverse()函数

[LEETCODE]Evaluate Reverse Polish Notation

[LEETCODE] Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9

  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

思路：

不是运算符的时候入栈，遇到运算符的时候出栈两个数字，计算新的值然后再入栈。

注意点：

1. string to integer 的处理， 使用函数 stoi();

2. 最后的结果是栈的最上面一个数。

3. 注意先出栈的是算式右边的数字，后出栈的是左边的，搞错了的话运算除法分母为0就错了

[LEETCODE] Length of Last Word

[LEETCODE]  Length of Last Word

Given a string s consists of upper/lower-case alphabets and empty space characters ' ', return the length of last word in the string. If the last word does not exist, return 0.

A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = "Hello World",
return 5.

思路:

最后一个单词的2种情况：

1， *hello; 2， *hello* ; *代表空格，可以为一个也可以为多个;
从前向后扫描，遇到空格就计算当前单词的长度，然后移动指针到下一个不是空格的地方继续计算，如果是情况1，指针移动到最后的‘\0’ 时，长度还未计算，所以循环结束之后再计算一次长度。

[LEETCODE] Integer to Roman

[LEETCODE] Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

思路:
Following is how integer is represented as Roman. 

当数字为1 和 5 的10 或10次方倍数时，罗马数字改变，小于1-3时为1的重复，4为在5左边添加1， 6-8 为在5的右边添加1，9为在新1的左边加旧1.

注意:

1. char name[number] = {" ", " ", " "} char数组的赋值
2. string result的用法：
    1) result.append(个数，char); 个数一定要有，最小为1；
    2) result.push_back(char/string); 一次只push一个进去.