跳到主要内容

编程

第一题​

由于总和sum为一个或几个正整数之和，所以如果存在符合条件的正整数 X，那么这个正整数 X 的范围必定小于或等于sum

  • 当正整数为一位数，那么 sum === X
  • 当正整数为一位数以上，那么 X < sum

可以通过二分查找法在区间 [0, sum] 中查找 X，查找的过程中，移动左右边界 [left, right]

function count(sum) {
    let left = 0,
        right = sum;

    while (left <= right) {
        let middle = left + Math.floor((right - left) / 2);
        // console.log("middle:", middle, "right: ", right, "left: ", left);
        let midSum = getSumByX(middle); // 通过查找到的正整数，计算出和
        if (midSum === sum) {
            // 找到符合条件的正整数
            return middle;
        } else if (midSum > sum) {
            right = middle - 1; //因为找到的数大于目标总和 所以需要寻找的正整数在中间值的左边，移动右边届
        } else {
            left = middle + 1; //相反，移动左边届
        }
    }

    return -1; // 所有区间查找完（left > right）都没有找到，返回 -1
}

// 通过查找到的正整数，计算出插黑板拼数字之和
function getSumByX(x) {
    let sum = x,
        len = x.toString().length; // len 为位数
    for (let i = 1; i < len; i++) {
        sum += Math.floor(x / Math.pow(10, i));
    }
    return sum;
}

console.log("输入sum=738，符合条件的正整数为:", count(738)); // 666
// console.log("输入sum=1098，符合条件的正整数为: ", count(1098));
// console.log("get X by 754: ", count(754));
// console.log("get X by 700: ", count(700));
// console.log("get X by 10: ", count(10));
// console.log("get X by 7: ", count(7));
// console.log("get X by 0: ", count(0));

调试

时间复杂度：O（logn）​

因为二分查找法中查找的区间大小变化：n, n/2, n/4, ... , n/2^k

当 n/2^k = 1 时，k 就是查找的次数。此时 k = log2n，时间复杂度为 O(logn)

空间复杂度：O(1)​

开辟若干个变量

第二题​

由于可以将例如AAB BBA ABB BAA通过任意次切割翻转，

所以可以将 A 和 B 中个数最小的元素全部间隔开来，由此得知，

解决步骤：

  1. 计算出A 和 B的个数 ANum, BNum
  2. 计算出最长连续黑白相间长度 当 A 和 B 个数相等，则为 A 和 B 的个数总和：2 Min(ANum, BNum) 当 A 和 B 个数不相等，则为 最小个数的两倍加一：2 Min(ANum, BNum) + 1
function countMaxLength(zebraMarking) {
    let ANum = 0,
        BNum = 0;
    // 迭代计算 A 和 B 的个数
    for (let i = 0; i < zebraMarking.length; i++) {
        if (zebraMarking[i] === "A") {
            ANum++;
        } else if (zebraMarking[i] === "B") {
            BNum++;
        }
    }

    let res = 2 * Math.min(ANum, BNum);
    return ANum === BNum ? res : res + 1;
}

console.log("ABABAAABAB 的最长连续黑白相间长度为: ", countMaxLength("ABABAAABAB")); // 9
console.log("最长连续黑白相间长度为: ", countMaxLength("")); // 0
console.log("A 的最长连续黑白相间长度为: ", countMaxLength("A")); // 1

调试

时间复杂度：O（n） n 为斑马线的总长度​

空间复杂度：O(1)​

开辟若干个变量

第三题​

由于第一次调整分配的结果为：7、8、6、5

此后的分配结果每四次循环一遍：

球队：：A、B、C、D

第一次：7、8、6、5

第二次：8、5、7、6

第三次：5、6、8、7

第四次：6、7、5、8

第五次：7、8、6、5

...

由此可得，战斗力最高（战斗力为8）的球队在循环交替：arr = ["B", "A", "C", "D"]

调整次数 n 与战斗力最高的球队下标关系为：index = (time - 1) % 4;,

战斗力最高球队為 arr[index]

function getBest() {
    let arr = ["B", "A", "C", "D"];
    let time = 5 * 12; // 计算5年里有几个月
    let index = (time - 1) % 4;
    return arr[index];
}

let best = getBest();
console.log("经过五年的战⽃⼒优化调整后，战⽃⼒最⾼的⼩队：", best);// "D"

调试

taskorder​

某银行网点某时间段内共开放 n 个服务窗口，有 m 个用户排队办理不同的业务，每个用户的业务办理时间或许不同。这些用户需要办理的业务可以用 tasks 表示。

实现函数 function runTasks(n, tasks)，根据服务窗口数 n 和任务 tasks，输出所有用户办理完各自业务的顺序。

举例说明，针对如下任务，

若 n=1，输出顺序是 c b a，因为只有一个窗口，只能依次执行；

若 n=2，输出顺序是 b a c，任务 b c 同时执行，b 执行完后 a 执行；

若 n>=3，输出顺序是 a b c，同时执行，时间越短完成越早。

const tasks = [
    {
        name: 'c',
        taskTime: 60,
    },
    {
        name: 'b',
        taskTime: 30,
    },
    {
        name: 'a',
        taskTime: 10,
    },
];

磁盘容量排序​

磁盘的容量单位有M、G、T，其关系为 1T = 1000G、1G = 1000M， 如样例所示先输入磁盘的个数，再依次输入磁盘的容量大小，然后按照从小到大的顺序对磁盘容量进行排序并输出。 要求排序保持稳定，磁盘容量可能出现多个子串，相同单位也可能出现多次 如：3M2T3M22G

示例一:

输入

3
20M
1T
300G

输出

20M
300G
1T

说明：

示例二：

输入

3
1G
3M2T3M
1024M

输出

1G
1024M
3M2T3M

说明：1G == 1024M，但是由于题目要求稳定排序，所以 1G 在 1024M 前；

// let inputArr = ['20M', '1T', '300G'];
let inputArr = ["1G", "3M2T321M", "1024M"];

function sortDisk(arr: Array) {
    /* 原来做法：将计算出来的值通过key(原值)：value(计算出来的值)放到一个对象数组中
    let sortArr = [];
    arr.map((item) => {
        let sum = exchangeToM(item);
        console.log("sum: ", sum);
        let obj = {};
        obj[item] = sum;
        sortArr.push(obj);
    });

    console.log(sortArr);
    let sortRes = sortArr.sort((a, b) => {
        console.log("object.values:", Object.values(a)[0]);
        console.log("object.values:", Object.values(b)[0]);
        return Object.values(a)[0] - Object.values(b)[0];
    });
    console.log("sortRes:", sortRes);*/
    
    // 优化：其实不用重新组织一个对象数组，直接通过排序传入比较函数，比较函数内直接计算结果
    arr.sort((a, b) => {
        return exchangeToM(a) - exchangeToM(b);
    });
    console.log(arr);
}

function exchangeToM(str: string) {
    let splitRes = str.match(/[0-9]+M|[0-9]+G|[0-9]+T/g); // 未处理非法情况
    console.log(splitRes);
    let sum = 0;
    splitRes.map((item) => {
        if (item.substr(-1) === "M") {
            sum += parseInt(item.slice(0, -1));
        } else if (item.substr(-1) === "G") {
            sum += parseInt(item.slice(0, -1)) * 1024;
        } else if (item.substr(-1) === "T") {
            sum += parseInt(item.slice(0, -1)) * 1024 * 1024;
        }
    });

    return sum;
}

sortDisk(inputArr);

let me try

字母出现次数排序，输出字符串​

输入一串字母，区分大小写，计算每个字母出现的个数，并以个数从小到大（“a:8;b:9;A:11”） 的顺序排序，当个数相同，按照自然顺序排序，如“a:8;b8”

示例一：

输入

bbddaa

输出

a:2;b:2;d:2;

示例二：

输入

cccZZb

输出

c:3;Z:2;b:1;
// 输入一串字母，区分大小写，计算每个字母出现的个数，并以个数从小到大（“a:8;b:9;A:11”） 的顺序排序，当个数相同，按照自然顺序排序，如“A:11;a:8;b8”

let str = "aaassbbccA";
// 按自然顺序排序：['b', 'a'].sort()// ['a', 'b'], Array.prototype.sort是原地排序
// 按自然顺序排序的比较函数怎么写？ 'a' > 'b' -> false 'b' > 'a' -> true
// 自然顺序，ASCII 表中，大写字母在前
function getObjArr(str) {
    let strArr = [...str];
    let obj = {};
    strArr.map((item) => {
        if (obj[item]) {
            obj[item]++;
        } else {
            obj[item] = 1;
        }
    });
    let objArr = [];
    Object.keys(obj).map((item) => {
        let objTemp = {};
        objTemp[item] = obj[item];
        objArr.push(objTemp);
    });
    return objArr;
    // return [{ a: 9 }, { s: 2 }, { c: 2 }, { A: 2 }];
}

let resSort = getObjArr(str).sort((a, b) => {
    if (Object.values(a)[0] === Object.values(b)[0]) {// 如果是相等的，则按照字母的自然顺序排序
        if (Object.keys(a)[0] > Object.keys(b)[0]) {
            // 'a' > 'b' -> false 'b' > 'a' -> true
            return 1;
        } else {
            return -1;
        }
    } else {
        return Object.values(a)[0] - Object.values(b)[0];
    }
});

let newArr = resSort.map(
    (item) => Object.keys(item)[0] + ":" + Object.values(item)[0]
);

console.log("resSort:", resSort);
console.log("newArr:", newArr.join(";"));

知识点总结

  • 数组排序 Array.prototype.sort(？compareFun)
    • 比较函数
      • return 1 顺序
      • return -1 逆序
  • 比较字母的自然顺序
    • 'a' > 'b' === true

let me try

转骰子 旋转的操作有六个操作： 左 右 前 后 顺时针 逆时针​

一个立方体骰子平放在桌面上，有一面正对着读者，称为前面。 我们将六个面分别称为左、右、前、后、上、下，每个面对应的数字分别为1、2、3、4、5、6。 我们定义以下操作：向前滚动称为F，向后滚动称为B，向左滚动称为L，向右滚动称为R， 上下面不变顺时针旋转称为C，上下面不变逆时针旋转称为U。在原始状态情况下，输入对应的操作码， 输出最终的骰子状态（按照每个面的顺序左右前后上下）。

题目来源

车牌号排序​

每次停车场数据有，车牌号，日期，停车时长（分钟），需要统计当月的车牌并排序。

排序规则：1. 按时长排序 2. 时长相同，按次数排序 3. 次数还相同，按照车牌的字典顺序排序

function sort(_arr, month) {
    // 合并同车牌号
    // 根据时长排序，从大到小
    // 时间相同，根据次数排序，从大到小
    // 时间和次数都相同，根据车牌字典排序
    let map = new Map(); // code, 总时间 次数 车牌
    _arr.map((item) => {
        if (item.month !== month) return; // 删除不是本月的数据
        if (map.has(item.code)) {
            let pre = map.get(item.code);
            pre.time = parseInt(item.time) + parseInt(pre.time);
            pre.count = pre.count + 1;
        } else {
            map.set(item.code, {
                code: item.code,
                time: parseInt(item.time),
                count: 1
            });
        }
    });

    let resArr = [...map.values()];
    // console.log("resArr: ", resArr);
    console.log("ssort:  ", resArr.sort(compareFun));

    let temp = resArr.map((item) => item.code);
    console.log("temp: ", temp);
}

function compareFun(a, b) {
    if (a.time === b.time) {
        if (a.count === b.count) {
            return b.code > a.code ? -1 : 1; // 比较字符 按照字典顺序
        }

        return b.count - a.count; // 从大到小
    }

    return b.time - a.time; // 从大到小
}

let arr = [
    { code: "A12", month: "12", time: "1" },
    { code: "A22", month: "11", time: "4" },
    { code: "A22", month: "12", time: "3" },
    { code: "A22", month: "12", time: "1" },
    { code: "B12", month: "12", time: "5" },
    { code: "T12", month: "12", time: "4" }
];
sort(arr, "12");

let me try

按积分抽奖​

我们做了一个活动，根据用户的积分来抽奖，用户的积分都保存在一个数组里面

arr = [20, 34, 160, 2…]，数组下标就是用户的 ID，则这里：

ID 为 0 的用户的积分是 arr[0] 等于 20 分。

ID 为 1 的用户的积分是 arr[1] 等于 34 分。

请你设计一个抽奖算法，随机抽出一位中奖用户，要求积分越高中奖概率越高。

返回值是中奖用户的 ID

PS: 1<= arr.length <= 50000 且 1<= arr[i] <= 50000

代码写出算法，

并分析其时间复杂度，

为其编写尽量多 unit test。

function randomPick(arr) {
    // 求前缀和
    let preSum = new Array(arr.length).fill(0);
    preSum[0] = arr[0];
    for (let i = 1; i < arr.length; i++) {
        preSum[i] = preSum[i - 1] + arr[i];
    }

    let total = preSum[preSum.length - 1]; // 总权重
    // 从0开始到最大值，求随机值
    let randomVal = getRandomIntInclusive(0, total);
    console.log( "preSum: ", preSum, "randomVal(随机数):", randomVal, "total（总权重）: ", total);

    // 通过随机值查找所在权重的区间
    return binarySearch(randomVal, preSum);
}

// 获取两个数之间的随机整数
function getRandomIntInclusive(min, max) {
    min = Math.ceil(min);
    max = Math.floor(max);
    // Math.random : 随机数在范围从0到小于1, 伪随机数在范围从0到小于1，也就是说，从0（包括0）往上，但是不包括1（排除1）
    return Math.floor(Math.random() * (max - min + 1)) + min; // 含最大值，含最小值
}

// 通过二分查找方法 查找随机值所在区间，返回前缀和数组的index就是积分数组的index
function binarySearch(_target, _preSum) {
    let left = 0,
        right = _preSum.length - 1;
    while (left < right) {
        let middle = Math.floor((right - left) / 2) + left;
        // 当值再区间 [a, b]之间时候，取b的下标，所以移动left，直到找到最小下标，返回left，符合 preSum[i] <= target的

        if (_preSum[middle] === _target) {
            return middle;
        } else if (_preSum[middle] < _target) {
            left = middle + 1;
        } else {
            right = middle; // 不减一：防止寻找的值在区间 [middle - 1, middle] 里。跟二分查找精准值不同
        }
    }
    return left;
}

function genTestCase() {
    let res = new Array(50000).fill(1)
    for (let i = 0; i < 500000; i++) {
        res[i] = i
    }
    return res
}

const testCase = [
    [2, 2, 2],
    [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 ],
    [1, 100, 100],
    [...genTestCase()],
];

console.log(testCase)
testCase.forEach((item) => {
    let resIndex = randomPick(item);
    console.warn( "用户积分： ", item, "中奖的用户 id 为：", resIndex, "积分为：", item[resIndex]);
});

/*
// 二分查找测试用例
console.log(
    "[1, 3, 5, 10, 20]\n2 binarySearch:",
    binarySearch(2, [1, 3, 5, 10, 20]) // 1
);
console.log("0 binarySearch:", binarySearch(0, [1, 3, 5, 10, 20])); // 0
console.log("1 binarySearch:", binarySearch(1, [1, 3, 5, 10, 20])); // 0
console.log("4 binarySearch:", binarySearch(4, [1, 3, 5, 10, 20])); // 2
console.log("5 binarySearch:", binarySearch(5, [1, 3, 5, 10, 20])); // 2
console.log("20 binarySearch:", binarySearch(20, [1, 3, 5, 10, 20])); // 4
*/

console.log("-----------------------------");

时间复杂度：迭代数组建立权重数组和二分查找，O(n) + O(logn)，n 是积分数组的长度。​

空间复杂度：开辟长度为n的数组空间 O(n)。n 是积分数组的长度。​

在线代码

使⽤正则表达式把字符串 str 中的占位符替换成 obj 的对应属性值，要求只能调⽤⼀次 replace ⽅法。​

var str = 'My name is ${name}. I like ${hobby}.';
var obj = { name: 'Tom', hobby: 'coding' };
// 结果应为 'My name is Tom. I like coding.'

var newStr = str.replace(/\$\{(.+?)\}/g,(match, p1) => {
    console.log('match 匹配的子串： ', str,' p1 第一个括号匹配的字符串： ', p1)
    return obj[p1]
})
console.log('newStr = ',newStr)

str.replace(regexp|substr, newSubStr|function)

str.replace