算法题

西瓜皮儿 2022/2/10

# 1.移动*

将数组的*号移动到最前面，不能改变数字顺序。

const arr = ['*', '*', '1', '2', '*', '4', '*', '*', '7', '3'];

moveStar(arr);
console.log(arr); // ['*', '*', '*', '*', '*', '1', '2', '4',  '7', '3']
 
        复制成功

1
2
3
4

# 2.千位分隔符

const num = 12335667999;

console.log(split(num)); // 12,335,667,999
 
        复制成功

1
2
3

# 3.比较版本号

力扣165 (opens new window)


/**
 * 比较两个版本号大小：
 *  1：参数1大
 *  0：一样大
 * -1：参数2大
 */

const ver1 = '2.11.21';
const ver2 = '1.2.03';

console.log(compare(ver1, ver2)); // 1
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12

# 4.手写getElementById

<body>
    <div>
        <div>
            <button id='btn1'>按钮</button>
        </div>
    </div>
    <div>
        <button id='btn2'>按钮</button>
    </div>

    <script>
        console.log(getElementById('btn1')); // <button id='btn1'>按钮</button>
    </script>
</body>
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14

实际API是深度优先

function getElementById(id) {
    const find = Array.prototype.find;
    let ans;
    const handler = el => {

        // 深度优先遍历
        find.call(el.children, item => {
            if (!ans && item.id === id) {
                ans = item;
                return true;
            } else {
                handler(item);
            }
        });
    }
    handler(document.body);
    return ans;
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

function getElementById(id) {
    const handler = children => {
        for (let i = 0; i < children.length; i++) {
            if (children[i].id === id) {
                return children[i];
            }
            const ans = handler(children[i].children);
            if (ans) {
                return ans;
            }
        }
    }
    return handler(document.body.children);
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14

function getElementById(id) {
    const find = Array.prototype.find;
    const forEach = Array.prototype.forEach;
    let ans;
    const isEle = (el) => el.id === id;
    const handler = el => {
        const children = el.children;

        // 广度优先遍历
        ans = find.call(children, item => isEle(item)) || ans;
        if (!ans) {
            forEach.call(children, item => handler(item));
        }
    }
    handler(document.body);
    return ans;
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 5.合并对象

const obj1 = {a: 1, b: 2, c: {d: 3}, j: 7};
const obj2 = {a: 4, b: {e: 5}, c: {f: 6}};

console.log(merge(obj1, obj2));
// { a: 4, b: {e: 5}, c: {d: 3, f: 6}, j: 7 }
 
        复制成功

1
2
3
4
5

# 6.数据流清理

node: 节点,string

const node = 'NODE_1';
 
        复制成功

columns: 节点排列，二维数组

const columns = [
    ['NODE_2', 'NODE_3'],
    ['NODE_1', 'NODE_4', 'NODE_1'],
    ['NODE_5', 'NODE_3'],
];
 
        复制成功

1
2
3
4
5

links: 错误的/冗余的连接数据。

const rawLinks = [
    { source: 'NODE_2', target: 'NODE_1', value: 3 },
    { source: 'NODE_2', target: 'NODE_1', value: 23 },
    { source: 'NODE_3', target: 'NODE_1', value: 11 },
    { source: 'NODE_1', target: 'NODE_5', value: 53 },
    { source: 'NODE_1', target: 'NODE_5', value: 6 },
    { source: 'NODE_3', target: 'NODE_3', value: 20 },
]
 
        复制成功

1
2
3
4
5
6
7
8

要求生成正确的连接数据

// 1.左侧列节点和右侧列节点必须有连接
// 2.如果原来没有这个连接，新建并且value设置成0
// 3.如果原来有多个这条路径的连接，加起来
// 4.计算出每个node的出入度
console.log(getRightLinks(rawLinks, columns));
 
        复制成功

1
2
3
4
5

function getRightLinks(rawLinks, columns) {
    // 初始化所有需要的连接，值设置成 { source-target:0 }
    const initNeedLinks = () => { }
    const initLinksObj = initNeedLinks();

    // 如果原生路径的连接，重复的加起来生成一个【hasLinks】对象
    // {source-target:value，source-target:value}
    const mergeRawLinks = () => { }
    const hasLinks = mergeRawLinks();

    // 遍历hasLinks给initLinksObj赋值，替换掉原来的0
    Object.entries(hasLinks).forEach(([key, val]) => { })

    // 将initLinksObj转换成
    // links：[{source, target, value},{...}]
    const links = Object.entries(initLinksObj).map(([key, value]) => { })

    // 根据links生成新的对象，拿到所有node的出入度，
    // {'NODE_1': 10, ...}
    const getSumNodeValue = () => {}
    const nodes = getSumNodeValue();

    return {
        links,
        nodes
    }
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// 测试数据
const columns = [
    ['NODE_2', 'NODE_3'],
    ['NODE_1', 'NODE_4', 'NODE_1'],
    ['NODE_5', 'NODE_3'],
];

const rawLinks = [
    { source: 'NODE_2', target: 'NODE_1', value: 3 },
    { source: 'NODE_2', target: 'NODE_1', value: 23 },
    { source: 'NODE_3', target: 'NODE_1', value: 11 },
    { source: 'NODE_1', target: 'NODE_5', value: 53 },
    { source: 'NODE_1', target: 'NODE_5', value: 6 },
    { source: 'NODE_3', target: 'NODE_3', value: 20 },
]

console.log(getRightLinks(rawLinks, columns));
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

function getRightLinks(rawLinks, columns) {
    // 初始化所有需要的连接，值设置成 { source-target:0 }
    const initNeedLinks = () => {
        const ans = {}
        for (let i = 0; i < columns.length - 1; i++) {
            const sources = columns[i];
            sources.forEach(source => {
                for (let j = 0; j < columns[i + 1].length; j++) {
                    const target = columns[i + 1][j];
                    const key = source + '-' + target;
                    ans[key] = 0;
                }
            })
        }
        return ans;
    }
    const initLinksObj = initNeedLinks();

    // 如果原来路径的连接，加起来生成一个source-target:value的值的对象
    const mergeRawLinks = () => {
        const ans = {};
        for (let i = 0; i < rawLinks.length; i++) {
            const source = rawLinks[i].source;
            const target = rawLinks[i].target;
            const key = source + '-' + target;
            const value = rawLinks[i].value;
            ans[key] = ans.hasOwnProperty(key) ? ans[key] + value : value;
        }
        return ans;
    }
    const hasLinks = mergeRawLinks();

    // 遍历hasLinks给initLinksObj赋值
    Object.entries(hasLinks).forEach(([key, val]) => {
        if (initLinksObj.hasOwnProperty(key)) {
            initLinksObj[key] = val;
        }
    })

    // 将links转换成[{source, target, value},{...}]形式
    const links = Object.entries(initLinksObj).map(([key, value]) => {
        const [source, target] = key.split('-');
        return { source, target, value }
    })

    // 根据links生成新的对象，拿到所有node的出入度
    const getMaxNodeValue = () => {
        return links.reduce((pre, { source, target, value }) => {
            pre[source] = pre.hasOwnProperty(source) ? pre[source] + value : value;
            pre[target] = pre.hasOwnProperty(target) ? pre[target] + value : value;
            return pre;
        }, {});
    }
    const nodes = getMaxNodeValue();

    return {
        links,
        nodes
    }
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

// 测试数据
const columns = [
    ['NODE_2', 'NODE_3'],
    ['NODE_1', 'NODE_4', 'NODE_1'],
    ['NODE_5', 'NODE_3'],
];

const rawLinks = [
    { source: 'NODE_2', target: 'NODE_1', value: 3 },
    { source: 'NODE_2', target: 'NODE_1', value: 23 },
    { source: 'NODE_3', target: 'NODE_1', value: 11 },
    { source: 'NODE_1', target: 'NODE_5', value: 53 },
    { source: 'NODE_1', target: 'NODE_5', value: 6 },
    { source: 'NODE_3', target: 'NODE_3', value: 20 },
]

console.log(getRightLinks(rawLinks, columns));

// {
//     links: [
//       { source: 'NODE_2', target: 'NODE_1', value: 26 },
//       { source: 'NODE_2', target: 'NODE_4', value: 0 },
//       { source: 'NODE_3', target: 'NODE_1', value: 11 },
//       { source: 'NODE_3', target: 'NODE_4', value: 0 },
//       { source: 'NODE_1', target: 'NODE_5', value: 59 },
//       { source: 'NODE_1', target: 'NODE_3', value: 0 },
//       { source: 'NODE_4', target: 'NODE_5', value: 0 },
//       { source: 'NODE_4', target: 'NODE_3', value: 0 }
//     ],
//     nodes: { NODE_2: 26, NODE_1: 96, NODE_4: 0, NODE_3: 11, NODE_5: 59 }
// }
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 7.八进制加法

console.log(add('12343234', '42343234')); // 54706470
 
        复制成功

按竖式思路进行求解

function add(num1, num2) {
    const arr1 = num1.split('').reverse();
    const arr2 = num2.split('').reverse();
    let ans = [];
    let addOne = 0;
    const maxLen = Math.max(num1.length, num2.length);
    for (let i = 0; i < maxLen; i++) {
        const n1 = arr1[i] != undefined ? +arr1[i] : 0;
        const n2 = arr2[i] != undefined ? +arr2[i] : 0;
        let sum;
        if (n1 + n2 + addOne > 7) {
            sum = (n1 + n2 + addOne) % 8;
            addOne = 1;
        } else {
            sum = n1 + n2 + addOne;
            addOne = 0;
        }
        ans.push(sum);
    }
    return ans.reverse().join('');
}
 
        复制成功

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

css相关项目相关