58 笔试

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param m int整型 数值范围大小
 * @param n int整型 取其中多少个数字
 * @return int整型二维数组
 */
function getCombineArr(m, n) {

    let resArr = []
    // inArr是传进来的一个加了新数的数组
    function work(inArr) {
        if (inArr.length === n) {
            // 当传进来的数组的长度等于需要的长度时push这个数组到结果数组里面
            resArr.push(inArr);
            return
        }
        // 长度不到
        if (inArr.length < n) {
            let lastVal = inArr[inArr.length - 1];
            // 从数组末尾的那个数的下一个数开始，直到结束   如果到了结束的数长度还是不够呢？ for循坏不会调用新的work了
            for (let j = lastVal + 1; j <= m; j++) {
                inArr.push(j)
                let newArr = new Array(...inArr)
                inArr.pop();
                console.log(newArr);
                work(newArr)
            }
        }
    }


    for (let i = 1; i <= m - n + 1; i++) {
        console.log(i);
        work([i])
    }
    // work([1])
    console.log(resArr);
}

getCombineArr(3, 2)




// 题目二
// 经典的dp算法

// 转移方程dp[i] = dp[i - 1] + 1

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组 初始数组
 * @return int整型
 */
function lengthOfNums(nums) {
    // write code here
    let maxVal = 1;
    let dp = new Array(nums.length).fill(1)
    console.log(dp);
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[j] + 1, dp[i])
                // 若大于取dp最大值
            }
            console.log("do");
        }
        maxVal = Math.max(dp[i], maxVal)
        console.log(`dp[i]is +${dp[i]} and maxVal is ${maxVal}`);
        // console.log(maxVal);
    }
    // console.log(maxVal);
    return maxVal
}
lengthOfNums([10, 9, 2, 5, 3, 7, 101, 18])
console.log(res);


// 题目3

function findSurveyArr(surveyPosArr, totalDistance) {
    let resArr = [];
    // 还是用类似dp的做法  dp存储在这个区间内小于totalDistance的数组，
    // 这题应该是要求速度空间的算法   或者是递归???
    for (let i = 0; i < surveyPosArr.length; i++) {
        // let s = [].push(surveyPosArr[i]
        console.log([surveyPosArr[i]]);
        work([surveyPosArr[i]], surveyPosArr[i], i)

    }
    function work(arr, sum, lastIndex) {
        if (lastIndex >= surveyPosArr.length) return
        // 下标超出
        let val = surveyPosArr[lastIndex + 1]
        if (sum + val > totalDistance) work(arr, sum, ++lastIndex)
        if (sum + val === totalDistance) resArr.push(arr.concat(val))
        work(arr.concat([val]), sum + val, ++lastIndex)
    }
    console.log(resArr);
}
findSurveyArr([10, 1, 2, 7, 6, 1, 5], 8)

难度不大,但是第一题真的浪费太多时间，第三题差一点点就写出来了真的可惜

#笔试复盘#