2023-8-26

8-26

数组

题号剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

这道题目的考点在于大数的表示，在不考虑大数的情况下

直接使用循环就可以了

function printNumbers(n: number): number[] {
    let r = []
    for(let i = 1;i<Math.pow(10,n);i++){
        r.push(i)
    }
        return r

};

解法二

这才是这道题真正的考点，大数。因此考虑使用字符串来表示

/**
 * 获取最大位数为 n 的所有数字数组
 * @param n 最大位数
 * @returns 所有最大位数为 n 的数字数组
 */
function printNumbers(n: number): number[] {
    // 定义数字字符集合
    const loop: string[] = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9'];
    // 存储结果的数组
    const res: number[] = [];
    // 当前结果数组的索引
    let index: number = 0;

    /**
     * 深度优先搜索递归函数
     * @param i 当前要填的位
     * @param path 一个符合的结果
     * @param isPre 是否有前导零
     */
    function dfs(i: number, path: string, isPre: boolean): void {
        // 如果已经填满 n 位，将结果存入 res 数组
        if (i === n) {
            if (path.length > 0) {
                res[index] = parseInt(path);
                index++;
            }
            return;
        }
        // 依次遍历数字字符集合
        for (const c of loop) {
            // 如果有前导零，跳过 '0'
            if (isPre && c === '0') {
                dfs(i + 1, path, true);
            } else {
                dfs(i + 1, path + c, false);
            }
        }
    }

    // 从第 0 位开始深度优先搜索
    dfs(0, "", true);
    return res;
}

const n = 3; // 你可以根据需要修改 n 的值
console.log(printNumbers(n)); // 输出所有最大位数为 n 的数字数组

题号 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

题目 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

解法思路是双指针，一个从头来一个从尾巴来，头只找奇数尾巴只找偶数，找到之后交换

function exchange(nums: number[]): number[] {
    let i = 0,
        j = nums.length-1,
        tmp
    while(i<j){
        while(i<j&&(nums[i]%2)===1){i++}
        while(i<j&&(nums[j]%2)===0){j--}
       tmp = nums[i]
       nums[i] = nums[j]
       nums[j] = tmp
    }
    return nums
};