//
//  Solution.cpp
//  LPCPlusPlusProject
//
//  Created by 鹏 刘 on 2018/3/21.
//  Copyright © 2018年 鹏 刘. All rights reserved.
//

#include "Solution.hpp"

//迭代求链表逆序
void Solution:: reverseList(ListNode *head) {
    ListNode *pre = NULL;
    ListNode *current = head;
    ListNode *next = NULL;
    while (current != NULL) {
        next = current -> next;
        current -> next = pre;
        pre = current;
        current = next;
    }

    head = pre;
}

//递归求链表逆序
void Solution:: recursiveReverseList(ListNode *head) {
    if (head -> next == NULL) {
        return;
    }

    ListNode *next = head -> next;
    recursiveReverseList(next);

    head -> next -> next = head;
    head -> next = NULL;
}

//递归求阶乘
int Solution:: recursiveFactorial(int n) {
    if (n == 0||n == 1) {
        return 1;
    } else {
        return n*recursiveFactorial(n-1);
    }
}

//非递归求阶乘
int Solution:: noRecursiveFactorial(int n) {
    int result = 1;
    for (int i = 1; i <= n; i ++) {
        result = result*i;
    }

    return result;
}

//上下左右递增二维数组求某数是否存在
bool Solution:: Find(int target, vector<vector<int> > array) {
    long int Row = array.size();
    long int Col = array[0].size();

    for (long int i = 0, j = Col - 1; i < Row && j >= 0;) {
        if (array[i][j] > target) {
            j--;
        } else if (array[i][j] == target) {
            return true;
        } else {
            i++;
        }
    }

    return false;
}

//请实现一个函数，将一个字符串中的空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
void Solution:: replaceSpace(char *str) {
    long int lenth = strlen(str);
    int count = 0;
    for (long int i = 0; i < lenth; i++) {
        if (str[i] == ' ') {
            count++;
        }
    }

    for (long int i = lenth - 1; i >= 0; i--) {
        if (str[i] != ' ') {
            str[i+2*count] = str[i];
        } else {
            count--;
            str[i+2*count] = '%';
            str[i+2*count+1] = '2';
            str[i+2*count+2] = '0';
        }
    }

    printf("现在的str is %s\n",str);
}

//快速排序
void Solution:: fastSort(int *arr,int left,int right) {
    int i = left; int j = right;

    if (left > right) {
        return;
    }

    int key = arr[left];

    while (i != j) {
        while (arr[j] >= key && j > i) {
            j--;
        }

        while (arr[i] <= key && j > i) {
            i++;
        }

        //找到左边大于基准数的跟右边小于基准数的交换位置
        if (j > i) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
//        printf("快排后");
//        for (int i = 0; i < 7; i++) {
//            printf("%i,",arr[i]);
//        }
//        printf("\n");
    }
    //交换基准数
    arr[left] = arr[i];
    arr[i] = key;

//    printf("快排后");
//    for (int i = 0; i < 7; i++) {
//        printf("%i,",arr[i]);
//    }
//    printf("\n");

    fastSort(arr, left, i-1);
    fastSort(arr, i+1, right);
}

//非递归斐波那契数列求第n位数值
int Solution:: fibonacci(int n) {
    int result = 0;
    int a = 1;
    int b = 1;

    if (n == 0||n == 1) {
        result = a;
        return result;
    }

    for (int i = 2; i <= n; i++) {
        result = a + b;
        a = b;
        b = result;
    }

    return result;
}

//递归斐波那契数列求第n位数值
int Solution:: recursiveFibonacci(int n) {
    if (n == 0||n == 1) {
        return 1;
    }

    return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
}

//递归求解杨辉三角
int Solution:: recursiveTriangle(int i,int j) {
    if (j == 0 || i == j) {
        return 1;
    }

    return recursiveTriangle(i - 1, j - 1) + recursiveTriangle(i - 1, j);
}

/*
              9
           /     \
          4       8
        /       /   \
       3       6     7
     /   \      \
    2     1      5
 */
/**
 * 前序遍历【根左右】根在最前
 * 中序遍历【左根右】根在中间
 * 后续遍历【左右根】根在最后
*/
void Solution:: initTree() {
    TreeNode H = TreeNode(1);
    TreeNode G = TreeNode(2);
    TreeNode D = TreeNode(3);
    D.left = &G;
    D.right = &H;
    TreeNode B = TreeNode(4);
    B.left = &D;
    TreeNode I = TreeNode(5);
    TreeNode E = TreeNode(6);
    E.right = &I;
    TreeNode F = TreeNode(7);
    TreeNode C = TreeNode(8);
    C.left = &E;
    C.right = &F;
    TreeNode A = TreeNode(9);
    A.left = &B;
    A.right = &C;

    this->PrintPreOrder(&A);

    printf("二叉树前序遍历（递归）：");
    this->PrintPreOrderReverse(&A);
    printf("\n");

    this->PrintInOrder(&A);

    printf("二叉树中序遍历（递归）：");
    this->PrintInOrderReverse(&A);
    printf("\n");

//    this->PrintPostOrder(&A);

    printf("二叉树后序遍历（递归）：");
    this->PrintPostOrderReverse(&A);
    printf("\n");

    this->PrintFromTopToBottom(&A);

    this->PrintFromBottomToTop(&A);
}

void Solution:: PrintPreOrder(TreeNode *root) {
    printf("二叉树前序遍历（非递归）：");

    stack<TreeNode*> s;
    TreeNode *t = root;
    s.push(t);
    while (!s.empty()) {
        t = s.top();
        if (t) {
            printf("%i ",t -> val);
            s.pop();
            if (t -> right) {
                s.push(t -> right);
            }

            if (t -> left) {
                s.push(t -> left);
            }
        }
    }

    printf("\n");
}

void Solution:: PrintPreOrderReverse(TreeNode *root) {

    if (root) {
        printf("%i ",root -> val);
        PrintPreOrderReverse(root -> left);
        PrintPreOrderReverse(root -> right);
    }
}

void Solution:: PrintInOrder(TreeNode *root) {//
    printf("二叉树中序遍历（非递归）：");

    stack<TreeNode*> s;
    TreeNode *t = root;
    while (t != NULL || !s.empty()) {

        while(t != NULL) {
            s.push(t);
            t = t->left;
        }

        if(!s.empty()) {
            t = s.top();
            printf("%i ",t -> val);
            s.pop();
            t = t->right;
        }
    }

    printf("\n");
}

void Solution:: PrintInOrderReverse(TreeNode *root) {
    if (root) {
        PrintInOrderReverse(root -> left);
        printf("%i ",root -> val);
        PrintInOrderReverse(root -> right);
    }
}

void Solution:: PrintPostOrder(TreeNode *root) {
    printf("二叉树后序遍历（非递归）：");

    stack<TreeNode*> s;
    TreeNode *t = root;
    TreeNode *r = NULL;

    while (t != NULL || !s.empty()) {

        while(t != NULL) {
            s.push(t);
            t = t->left;
        }

        if (!s.empty()) {
            t = s.top();
            if (t -> right&&t -> right != r) {
                t = t -> right;
            } else {
                t = s.top();
                printf("%i ",t -> val);
                r = t;
                s.pop();
            }
        }
    }

    printf("\n");
}

void Solution:: PrintPostOrderReverse(TreeNode *root) {
    if (root) {
        PrintPostOrderReverse(root -> left);
        PrintPostOrderReverse(root -> right);
        printf("%i ",root -> val);
    }
}


vector <int> Solution:: PrintFromTopToBottom(TreeNode *root) {
    printf("二叉树从上到下 从左往右（非递归）：");

    queue <TreeNode*> q;
    q.push(root);
    vector <int> r;
    while(!q.empty()){
        root = q.front(); q.pop();
        if(!root) continue;
        r.push_back(root -> val);
        printf("%i ",root -> val);
        q.push(root -> left);
        q.push(root -> right);
    }
    printf("\n");

    return r;
}

vector <int> Solution:: PrintFromBottomToTop(TreeNode *root) {
    printf("二叉树从下到上 从右往左（非递归）：");

    queue <TreeNode*> q;
    q.push(root);
    stack <TreeNode*> s;
    vector <int> r;
    while(!q.empty()){
        root = q.front(); q.pop();
        if(!root) continue;
        s.push(root);
        q.push(root -> left);
        q.push(root -> right);
    }

    while (!s.empty()) {
        TreeNode *node = s.top();
        r.push_back(node -> val);
        printf("%i ",node -> val);
        s.pop();
    }
    printf("\n");

    return r;
}

void Solution:: PringDiamond() {
    printf("/\\\n\\/\n");
}