算法

算法(49)-medium 题目汇总

整理几道常见的 medium 题目。

[toc]

数组(前缀和)

连续的子数组和

题目

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为 2 ，且

子数组元素总和为 k 的倍数。

如果存在，返回 1 ；否则，返回 0 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。

题解

可以用暴力遍历两遍的思路，也可以用前缀和的思路。但是这里要求子数组的长度至少为 2，所以要用 map 记录前缀和的位置。如果两个前缀和的差是 k 的倍数，那么这两个位置之间的子数组的和就是 k 的倍数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function checkSubarraySum(nums, k) {
    const len = nums.length;
    if (len < 2) {
        return false;
    }

    const map = new Map();
    map.set(0, -1);
    let remain = 0;
    for (let i = 0; i < len; i++) {
        remain = (remain + nums[i]) % k;
        if (map.has(remain)) {
            if (i - map.get(remain) > 1) {
                return true;
            }
        } else {
            map.set(remain, i);
        }
    }
    return false;
}

链表

分段反转链表

题目

给定一个常数 K 和一个单链表 L，请你在单链表上每 K 个元素做一次反转，并输出反转完成后的链表。

如果链表最后一部分不足 K 个元素，则最后一部分不翻转。

例如，假设 L 为 1→2→3→4→5→6

如果 K=3，则你应该输出 3→2→1→6→5→4

如果 K=4，则你应该输出 4→3→2→1→5→6

用例

输入样例:
在这里给出一组输入。例如：

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

题解

这题第一个问题就是读取用例生成一条链表。拆解成两部分依次读取。

第二个问题就是直接用链表，分段反转会很难处理。所以可以用栈和队列的思路。本质就是每 k 个转置下顺序。

代码

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
function reverseList(nodes, start, n, k) {
    let current = nodes[start];
    const stack = [];
    const queue = [];
    let remain = n;
    while (current && remain >= k) {
        let i = 0;
        while (i < k) {
            stack.push(current);
            current = nodes[current.next];
            i++;
        }
        while (stack.length) {
            queue.push(stack.pop());
        }
        remain -= k;
    }
    while (current) {
        queue.push(current);
        current = nodes[current.next];
    }
    return queue;
}

process.stdin.on('end', function() {
    const lines = buf.split('\n');
    const [start, N, K] = lines[0].split(' ');
    const n = parseInt(N);
    const k = parseInt(K);
    const nodes = {};
    for(let i = 1; i <= n; i++) {
        const [address, value, next] = lines[i].split(' ');
        nodes[address] = { address, value, next };
    }
    const queue = reverseList(nodes, start, n, k);
    const res = queue.reduce((prev, cur, index) => {
        const { address, value } = cur || {};
        return `${prev}${index !== 0 ? ` ${address}\n` : ''}${address} ${value}`;
    }, '');
    console.log(`${res} -1`);
});

字符串

字符串编辑距离

题目

给定一个源串和目标串，能够 对源串进行如下操作：

在给定位置上插入一个字符

替换任意字符

删除任意字符

写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串

题解

经典动态规划题目，不了解思路难度堪比hard。主要记忆三个状态转移方程，以及一个字符相等的特殊情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function minDistance(word1, word2) {
    const x = word1.length;
    const y = word2.length;
    const dp = Array.from({ length: x + 1 }).map((_, i) => Array(y + 1)
        .fill(0)
        .map((__, j) => (!i || !j ? (!i && j) || (!j && i) : 0)));
    for (let i = 1; i <= x; i++) {
        for (let j = 1; j <= y; j++) {
            dp[i][j] = word1[i - 1] === word2[j - 1]
                ? dp[i - 1][j - 1]
                : Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1;
        }
    }
    return dp[x][y];
}

哈希表

交换和

题目

给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。
若有多个答案，返回所有满足条件的答案。若无满足条件的数值，不输出。

题解

交换的数的差是两个数组和的差的一半，利用这一点，建立两个 Set，遍历其中一个去另一个中找匹配。最后再对结果排序。

代码

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
function findSwapValues(arr1, arr2) {
    const res = [];
    const sum1 = arr1.reduce((a, b) => a + b, 0);
    const sum2 = arr2.reduce((a, b) => a + b, 0);
    const diff = sum1 - sum2;
    if (diff % 2 !== 0) {
        return res;
    }
    const set1 = new Set(arr1);
    const set2 = new Set(arr2);
    for (const num of set1) {
        let num1 = num;
        let num2 = num - diff / 2;
        if (set2.has(num2)) {
            if (num2 < num1) {
                [num1, num2] = [num2, num1];
            }
            res.push([num1, num2]);
        }
    }
    res.sort((a, b) => {
        if (a[0] < b[0]) {
            return -1;
        } if (a[0] === b[0]) {
            return a[1] - b[1] ? -1 : 1;
        }
        return 1;
    });
    return res;
}

栈与队列

删除无效的括号

题目

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

括号只考虑 “(“ 和 “)” ，有效的括号是指一系列左括号 “(“ 和 “)” 组成；但是如果有一些额外的括号，使得括号不能正确配对，就需要删除。

删除规则：从前往后，且尽可能少的删除多余括号。

题解

本质就是用栈来匹配左右括号，但是这题要求删除最少的括号，而不是展示要去除的括号，所以需要记录下多余的括号的位置，最后再一起删除。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const removeInvalidParentheses = function (arr) {
    const stack = [];
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === '(') {
            stack.push(i);
        }
        if (arr[i] === ')') {
            if (stack.length > 0 && arr[stack[stack.length - 1]] === '(') {
                stack.pop();
            } else {
                stack.push(i);
            }
        }
    }
    if (stack.length > 0) {
        return arr.filter((_, i) => !stack.includes(i)).join('');
    }
    return arr.join('');
};

位运算

或运算的最小翻转次数

题目

给你三个正整数 a、b 和 c。

你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。

「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。

题解

难点反倒是把数字转化为二进制，js 里没有原生支持，得手动计算，保存成字符串或者数组。

然后就分类讨论 c，如果 c 的某一位是 1，那么 a 和 b 的这一位必须有一个是 1，否则就要翻转。如果 c 的某一位是 0，那么 a 和 b 的这一位必须都是 0，否则就要翻转，如果 a 和 b 都是 1，那么就要翻转 2 次。

代码

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
const toBinary = (num) => {
    let n = num;
    const res = [];
    while (n) {
        res.push(n % 2);
        n = Math.floor(n / 2);
    }
    return res;
};

const minFlips = function (...numbers) {
    let count = 0;
    const [a, b, c] = [...numbers].map((v) => toBinary(v));
    const maxLen = Math.max(a.length, b.length, c.length);
    for (let i = 0; i < maxLen; i++) {
        if (c[i]) {
            if (!a[i] && !b[i]) {
                count++;
            }
        } else {
            if (a[i]) {
                count++;
            }
            if (b[i]) {
                count++;
            }
        }
    }
    return count;
};

暴力法

给定数字组成最大时间

题目

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。

24 小时格式为HH:MM ，其中 HH 在 00 到 23 之间，MM 在 00 到 59 之间。最小的 24 小时制时间是 00:00 ，而最大的是 23:59。

以长度为 5 的字符串，按 HH:MM 格式返回答案。如果不能确定有效时间，则返回空字符串。

题解

这道题应该算是 easy。就是三重遍历暴力求解。小细节就是时间字符串补 0。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function largestTimeFromDigits(arr) {
    let res = -1;
    for (let i = 0; i < 4; i++) {
        for (let j = 0; j < 4; j++) {
            for (let k = 0; k < 4; k++) {
                if (j !== i && k !== i && k !== j) {
                    const l = 6 - i - j - k;
                    const hours = 10 * arr[i] + arr[j];
                    const mins = 10 * arr[k] + arr[l];
                    if (hours < 24 && mins < 60) {
                        res = Math.max(res, hours * 60 + mins);
                    }
                }
            }
        }
    }
    return res === -1
        ? ''
        : `${Math.floor(res / 60)
            .toString()
            .padStart(2, '0')}:${(res % 60).toString().padStart(2, '0')}`;
}