// 算法

// 斐波那契数列
// 1. 递归
function f(n) {
    if (n === 1) {
        return 1;
    }
    if (n === 0) {
        return 0;
    }
    return f(n-1) + f (n - 2);
}

// 2. 线性规划
function g(n) {
    let p = 0, q = 0, r =1;
    for (let i = 2; i <= n; i++) {
        p = q;
        q = r;
        r = p + q;
    }

    return r;
}

// const a = f(4);
// const b = g(4);
// console.log(a, b);

// 合并有序链表
// [1,2,3] [1,2,4]
// 思路为定义2个指针寻找大值，后移
function mergeArray(a, b) {
    let c = [];
    let aStart = 0;
    let bStart = 0;
    let left = [];
    while(aStart < a.length || bStart < b.length) {
        if (a[aStart] < b[bStart]) {
            c.push(a[aStart]);
            aStart ++;
        } else {
            c.push(b[bStart]);
            bStart ++;
        }
    }

    if (aStart < a.length) {
        left = a.slice(aStart);
    }
    if (bStart < b.length) {
        left = b.slice(aStart);
    }

    c = c.concat(left);

    return c;
}

// const r = mergeArray([1, 2, 3], [1, 2, 4]);
// console.log(r);

// 反转链表
// 1 -> 2 -> 3 -> null => 3 -> 2 -> 1 -> null
function traverse(head) {
    let curr = head;
    let prev = null;
    while(curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
}

// var c = { value: 3, next: null };
// var b = { value: 2, next: c };
// var a = { value: 1, next: b };
//
// traverse(a);

// console.log(a, b, c);

// 链表有环
// 利用一个map字典存储每个节点的访问情况
function judgeCircle(head) {
    const map = new Map();
    let curry = head;
    let flag = false;
    while(curry) {
        if (!map.get(curry)) {
            map.set(curry, true);
        } else {
            flag = true;
            return flag;
        }
        curry = curry.next;
    }

    return flag;
}

// var c = { value: 3, next: null };
// var b = { value: 2, next: c };
// var a = { value: 1, next: b };
//
// c.next = b;
//
// judgeCircle(a)
//
// console.log(judgeCircle(a), a, b, c);

// 判断字符串有效性
// 双栈匹配

// 快速排序
function quickSort(arr) {
    let len = arr.length,
        index,
        pivot,
        left = [],
        right = [];

    if (len <= 1){
        return arr;
    }

    index = Math.floor(len / 2);

    pivot = arr.splice(index, 1);
    len -= 1;

    for (let i = 0; i < len; i++) {
        if (arr[i] < pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }

    return quickSort(left).concat(pivot, quickSort(right));
}

// let a = [2, 1, 6, 4, 2, 3];
// let b = quickSort(a);
// console.log(b);

// 二分查找
function find(target, key) {
    let left = 0, right = target.length - 1, mid;
    while(left <= right) {
        mid = Math.floor((left + right) / 2);
        if (target[mid] === key) {
            return mid;
        } else if (target[mid] > key) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return -1;
}

// console.log(find(b, 6));