/**
 * @param {number[]} nums
 * @return {number}
 */
const findRepeatNumber = function(nums) {
    const obj = {};

    for(let i = 0; i < nums.length; i++) {
        if(typeof obj[nums[i]] === 'number') {
            return nums[i];
        } else {
            obj[nums[i]] = nums[i];
        }
    }
};

var findNumberIn2DArray = function(matrix, target) {
    if(!matrix || !matrix.length || !matrix[0].length) {
        return false;
    }

    const height = matrix.length;
    const width = matrix[0].length;

    let i = 0;
    let j = width - 1;

    while(i <= (height -1) && j >= 0) {
        if(matrix[i][j] === target) {
            return true;
        } else if(matrix[i][j] > target) {
            j--;
        } else if(matrix[i][j] < target) {
            i++;
        }
    }

    return false;
};

// 正则
var replaceSpace = function(s) {
    return s.replace(/\s/g, '%20');
};

// 遍历
var replaceSpace = function(s) {
    let res = '';

    for(let i = 0; i < s.length; i ++){
        if(s[i] === ' '){
            res = res + '%20';
        } else {
            res = res + s[i];
        }
    }

    return res;
};

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var reversePrint = function(head) {
    if(!head) return [];

  	// 找最后一个节点，同时添加prev属性
    head.prev = null;
    let currentNode = head;
    let lastNode;
    while(currentNode) {
        if(currentNode.next) {
            currentNode.next.prev = currentNode;
        }

        if(!currentNode.next) {
           lastNode =  currentNode;
        }

        currentNode = currentNode.next;
    }

  	// 最后顺着prev属性输出值
    const res = [];
    while(lastNode) {
        res.push(lastNode.val);

        lastNode = lastNode.prev;
    }

    return res;
};

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if(!preorder || !preorder.length) {
        return null;
    }

    let map = {};
    for(let i = 0; i < inorder.length; i++) {
        map[inorder[i]] = i;
    }

    function doBuild(preorder, preorderStart, preorderEnd, inorder, inorderStart, inorderEnd) {
        if(preorderStart > preorderEnd) {
            return null;
        }

        let rootVal = preorder[preorderStart];
        let root = new TreeNode(rootVal);

        let inIndex = map[rootVal];
        let leftNum = inIndex - inorderStart;
        let rightNum = inorderEnd - inIndex;

        let leftPreorderStart = preorderStart + 1;
        let leftPreorderEnd = preorderStart + leftNum;
        let rightPreorderStart = leftPreorderEnd + 1;
        let rightPreOrderEnd = preorderEnd;

        let leftInorderStart = inorderStart;
        let leftInorderEnd = inIndex - 1;
        let rightInorderStart = inIndex + 1;
        let rightInorderEnd = inorderEnd;

        if(preorderStart === preorderEnd) {
            return root;
        } else {
            let leftRoot = doBuild(preorder, leftPreorderStart, leftPreorderEnd, inorder, leftInorderStart, leftPreorderEnd);
            let rightRoot = doBuild(preorder, rightPreorderStart, rightPreOrderEnd, inorder, rightInorderStart, rightInorderEnd);
            root.left = leftRoot;
            root.right = rightRoot;
            return root;
        }
    }

    let arrLength = preorder.length;

    return doBuild(preorder, 0, arrLength - 1, inorder, 0, arrLength - 1);
};

/**
 * @param {number} num
 * @return {number}
 */
var translateNum = function(num) {
    let res = [1, 1];
    let numStr = `${num}`;
    let length = numStr.length;
    for(let i = 2; i <= numStr.length; i++) {
        let last2Num = parseInt(numStr[i - 2] + numStr[i-1]);

        if(last2Num >= 10 && last2Num <= 25) {
            res[i] = res[i - 1] + res[i - 2];
        } else {
            res[i] = res[i - 1];
        }
    }

    return res[length];
};

var CQueue = function() {
    this.arr1 = [];
    this.arr2 = [];
};

/** 
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function(value) {
    this.arr1.unshift(value);
};

/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function() {
    let length1 = this.arr1.length;
    let length2 = this.arr2.length;

    if(length2) {
        return this.arr2.shift();
    } else if(length1) {
        for(let i = 0; i < length1; i++) {
            this.arr2.unshift(this.arr1.shift())
        }

        return this.arr2.shift();
    } else {
        return -1;
    }
};

/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let res = [0, 1];

    for(let i = 2; i <= n; i++) {
        res[i] = (res[i - 1] + res[i - 2]) % 1000000007;
    }

    return res[n];
};

// 几乎跟斐波拉契数列一样，只是F(0)不一样
/**
 * @param {number} n
 * @return {number}
 */
var numWays = function(n) {
    let res = [1, 1];

    for(let i = 2; i <= n; i++) {
        res[i] = (res[i - 1] + res[i - 2]) % 1000000007;
    }

    return res[n];
};

// 线性查找
/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
    let minNum = numbers[0];
    const length = numbers.length;

    for(let i = 0; i < length; i++) {
        if(numbers[i] < minNum) {
            minNum = numbers[i];
        }
    }

    return minNum;
};

// 二分查找, 时间复杂度为O(lgn)；
/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function(numbers) {
    const length = numbers.length;
    let i = 0;
    let j = length - 1;

    while(i !== j) {
        let m = Math.floor((i + j) / 2);
        if(numbers[m] > numbers[j]) {
            i = m + 1;
        } else if(numbers[m] < numbers[j]) {
            j = m;
        } else {
            j--;
        }
    }

    return numbers[i];
};

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
    function dfs(i, j, k) {
        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] !== word[k]) return false;
        if(k === (word.length - 1)) return true;
        let temp = board[i][j];
        board[i][j] = '/';
        const res = dfs(i, j+1, k+1) || dfs(i, j-1, k+1) || dfs(i+1, j, k+1) || dfs(i-1, j, k+1)
        board[i][j] = temp;

        return res;
    }

    let k = 0;
    for(let i = 0; i < board.length; i++){
        for(let j = 0; j < board[0].length; j++){
            if(dfs(i, j, k)) return true;
        }
    }
    return false;
};

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function(m, n, k) {
    function getSum(i) {
        let sum = 0;
        let tmp = i;
        while(tmp > 0) {
            sum = sum + tmp % 10;
            tmp = parseInt(tmp / 10);
        }

        return sum;
    }

    let count = 0;

    const arr = [];
    for(let p = 0; p < m; p++){
        arr.push([]);
    }

    function dfs(i, j, k) {
        if(i < 0 || i > m -1 
            || j < 0 || j > n - 1 
            || (getSum(i) + getSum(j)) > k
            || arr[i][j]) return;

        count++;
        arr[i][j] = true;
        dfs(i + 1, j, k);
        dfs(i, j + 1, k);
    }

    dfs(0, 0, k);

    return count;
};

var cuttingRope = function(n) {
     if(n === 2) return 1;

     let res = 0;

     for(let i = 1; i <= n; i++) {
         res = Math.max(res, i * (n - i), i * cuttingRope(n - i));
     }

     return res;
 };

var cuttingRope = function(n) {
    const DP = [0, 0, 1];

    for(let i = 3; i <= n; i++) {
        DP[i] = 0;

        for(let j = 1; j <= i; j++) {
            DP[i] = Math.max(DP[i], j * (i - j), j * DP[i - j]);
        }
    }

    return DP[n];
}

var cuttingRope = function(n) {
    const DP = [0n, 0n ,1n];
    for(let j = 3; j <= n; j++) {
        DP[j] = 0;
        for(let i = 1; i <= j; i++){
            if(i * (j - i) > DP[j]) {
                DP[j] = BigInt(i * (j - i))
            }

            if(BigInt(i) * BigInt(DP[j - i]) > DP[j]) {
                DP[j] = BigInt(i) * BigInt(DP[j - i])
            }
        }
    }

    return DP[n] % 1000000007n;
};