아 리 와 바이트 점프 전단 알고리즘 면접 문제

let arr = [
    [1, 2, 2],
    [3, 4, 5, 5],
    [6, 7, 8, 9, [11, 12, [12, 13, [14]]]], 10
];

/*  1：   Array.prototype.flat   */
arr = arr.flat(Infinity);

/*  2：            */
arr = arr.toString().split(',').map(item => {
     
    return Number(item);
});

/*  3：JSON.stringify*/
arr = JSON.stringify(arr).replace(/(\[|\])/g, '').split(',').map(item => Number(item));

/*  4：     some        */
while (arr.some(item => Array.isArray(item))) {
     
    arr = [].concat(...arr);
}

/*  5：        */
Array.prototype.myFlat = function myFlat() {
     
    let result = [];
    //=>         ，             
    let fn = (arr) => {
     
        for (let i = 0; i < arr.length; i++) {
     
            let item = arr[i];
            if (Array.isArray(item)) {
     
                fn(item);
                continue;
            }
            result.push(item);
        }
    };
    fn(this);
    return result;
}

/*
 *       N，      N       
 *   ：  15
 *   ：[[1,2,3,4,5],[4,5,6],[7,8]]
 */
function createArr(n,len){
     
    let arr=new Array(len).fill(null),
        temp=[];
    arr[0]=n;
    arr=arr.map((item,index)=>{
        if(item===null){
            item=temp[index-1]+1;
        }
        temp.push(item);
        return item;
    });
    return arr;
}
function fn(count){
    let result=[];
    //=>     
    let middle=Math.ceil(count/2);
    // 1    
    for(let i=1;i<=middle;i++){
        //       
        for(let j=2;;j++){
            //        
            let total=(i+(i+j-1))*(j/2);
            if(total>count){
     
                break;
            }else if(total===count){
     
                result.push(createArr(i,j));
                break;
            }
        }
    }
    return result;
}

/* 
 *          nums        target，                      ，          
 * nums = [1,6,4,8,7];
 * target = 9
 * => nums[0] + nums[3] = 9
 * => [0,3]
 */

/*  1：   （       x，            target - x        ）*/
function func(nums, target) {
     
    for (let i = 0; i < nums.length - 1; i++) {
     
        let item = nums[i],
            diff = target - item;
        for (let j = i + 1; j < nums.length; j++) {
     
            if (nums[j] === diff) {
     
                return [i, j];
            }
        }
    }
}

/*  2：     */
function func(nums, target) {
     
    let temp = {
     };
    for (let i = 0; i < nums.length; i++) {
     
        let item = nums[i],
            diff = target - item;
        if (temp[diff] !== undefined) {
     
            return [temp[diff], i];
        }
        temp[item] = i;
    }
}

function maxSubArray(nums) {
     
    let ans = nums[0],
        sum = 0;
    for (let i = 0; i < nums.length; i++) {
     
        let item = nums[i];
        if (sum > 0) {
     
            sum += item;
        } else {
     
            sum = item;
        }
        ans = Math.max(ans, sum);
    }
    return ans;
}
console.log(maxSubArray([-2, 2, -1, 1, -3]));

// O((n+m)*log(n+m))
function merge(nums1, nums2) {
     
    return nums1.concat(nums2).sort((a,b)=>a-b);
}

// O(m+n)
function merge(nums1, nums2) {
    let len1 = nums1.length - 1;
    let len2 = nums2.length - 1;
    let len = nums1.length + nums2.length - 1;
    while (len1 >= 0 && len2 >= 0) {
        let val1 = nums1[len1],
            val2 = nums2[len2];
        if (val1 > val2) {
            nums1[len] = val1;
            len1--;
        } else {
            nums1[len] = val2;
            len2--;
        }
        len--;
    }
    return nums1;
};
console.log(merge([1, 5, 8, 16, 26], [4, 7, 9, 17]));

/*
 *     fibonacci [ˌfɪbəˈnɑːtʃi]   ，       ：
 *        ：[1,1,2,3,5,8,13,21,…]
 * fibonacci(0) -> 1
 * fibonacci(4) -> 5
 */
function fibonacci(count) {
     
    if (count <= 1) return 1;
    let arr = [1, 1],
        n = count + 1 - 2; //=>      
    while (n > 0) {
     
        let cur = arr[arr.length - 2],
            next = arr[arr.length - 1];
        arr.push(cur + next);
        n--;
    }
    return arr[arr.length - 1];
}