算法

算法(48)-easy 题目汇总

整理几道常见的 easy 题目。

[toc]

字符串

同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

题解

本质是映射的实现。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var isIsomorphic = function(s, t) {
    const mapS = {};
    const mapT = {};
    const lenS = s.length;
    const lenT = t.length;
    if (lenS !== lenT) {
        return false;
    }
    for (let i = 0; i < lenS; i++) {
        const x = s[i];
        const y = t[i];
        if ((mapS[x] && mapS[x] !== y) || (mapT[y] && mapT[y] !== x)) {
            return false;
        }
        mapS[x] = y;
        mapT[y] = x;
    }
    return true;
};

最长的美好字符子串

题目

当一个字符串 s 包含的每一种字母的大写和小写形式 同时 出现在 s 中，就称这个字符串 s 是 美好 字符串。比方说，”abABB” 是美好字符串，因为 ‘A’ 和 ‘a’ 同时出现了，且 ‘B’ 和 ‘b’ 也同时出现了。然而，”abA” 不是美好字符串因为 ‘b’ 出现了，而 ‘B’ 没有出现。

给你一个字符串 s ，请你返回 s 最长的 美好子字符串 。如果有多个答案，请你返回 最早 出现的一个。如果不存在美好子字符串，请你返回一个空字符串。

题解

本质就是维护大小写两个数组，数组记录每个字符是否出现过，如果两个数组每一位都相同，就是美好字符串。因为字符只有 26 个，所以可以用一个数字的二进制位来替代数组表示是否出现过。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function longestNiceSubstring(s) {
    const len = s.length;
    let index = -1;
    let count = 0;
    for (let i = 0; i < len; i++) {
        let lower = 0;
        let upper = 0;
        for (let j = i; j < len; j++) {
            const current = s.charAt(j);
            if (current >= 'a' && current <= 'z') {
                lower |= 1 << (current.charCodeAt(0) - 'a'.charCodeAt(0));
            } else {
                upper |= 1 << (current.charCodeAt(0) - 'A'.charCodeAt(0));
            }
            if (lower === upper && j - i + 1 > count) {
                index = i;
                count = j - i + 1;
            }
        }
    }
    return index === -1 ? '' : s.substring(index, index + count);
}

栈与队列

最小栈

题目

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

题解

使用两个栈，一个栈用来存储数据，一个栈用来存储最小值。每次 push 的时候，如果当前值小于等于最小值栈的栈顶值，就将当前值也 push 到最小值栈。pop 的时候也要注意，如果当前值等于最小值栈的栈顶值，就将最小值栈的栈顶值也 pop 出去。

代码

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
/**
 * initialize your data structure here.
 */
const MinStack = function () {
    this.a = [];
    this.b = [];
};

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
    this.a.push(x);
    if (!this.b.length || x <= this.b[this.b.length - 1]) {
        this.b.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
    const x = this.a.pop();
    if (x === this.b[this.b.length - 1]) {
        this.b.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
    return this.a[this.a.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
    return this.b[this.b.length - 1];
};

二叉树

判断二叉树是不是搜索树

给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

题解

这题难点反倒在读取，给的是一个数组，用层序遍历的方式，用队列保存结果。然后每次层序遍历，取下两个节点分别就是左右节点，和父节点比较大小即可。

代码

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
function check(arr) {
    const len = arr.length;
    if (len > 0) {
        const queue = [arr[0]];
        let i = 1;
        while (queue.length > 0 && i < len) {
            const node = queue.shift();
            const left = arr[i];
            const right = arr[i + 1];
            if (left !== null) {
                queue.push(left);
                if (left > node) {
                    return false;
                }
            }
            if (right !== null) {
                queue.push(right);
                if (right < node) {
                    return false;
                }
            }
            i += 2;
        }
    }
    return true;
}

贪心

最小硬币个数

题目

假设现在有一堆硬币，其中有足够个1元硬币、足够个2元硬币和足够个5元硬币。现在需要用这些硬币凑出总价值为n元的钱，求最少需要多少枚硬币？

题解

贪心算法，优先使用面值大的硬币。

代码

1
2
3
4
5
6
7
8
9
function minCoins(n) {
    let count = 0;
    count += Math.floor(n / 5);
    n %= 5;
    count += Math.floor(n / 2);
    n %= 2;
    count += n;
    return count;
}

暴力法

数字拆分求和

题目

对于给定的正整数k，将其表示为一个正整数序列之和，且该序列中相邻元素的差值为等差分布（等差分布从1开始）。注意，请打印出所有可能的序列（打印多个序列时，按照首个数字从小到大依次打印）。

题解

差值是等差分布，可以得知每次加的数都比原来的数多一个等差数列之和。所以可以从两个数开始遍历，把加的数移到外部计算，每次根据公式算出第一个数，如果是整数就满足条件。之后在根据第一个数计算出剩下的数生成结果。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function find(k) {
    let rest = 0;
    const res = [];
    for(let i = 2; i < k; i++) {
        rest = rest + i * (i - 1) / 2;
        const first = (k - rest) / i;
        if (first <= 0) {
            break;
        }
        if (first % 1 === 0) {
            let str = [first];
            let temp = 0;
            for (let j = 1; j < i; j++) {
                temp += j;
                str.push(first + temp);
            }
            res.push(str.join(','));
        }
    }
    return res.reverse().join('\n');
}

买票需要的时间

题目

有 n 个人前来排队买票，其中第 0 人站在队伍 最前方 ，第 (n - 1) 人站在队伍 最后方 。

给你一个下标从 0 开始的整数数组 tickets ，数组长度为 n ，其中第 i 人想要购买的票数为 tickets[i] 。

每个人买票都需要用掉 恰好 1 秒 。一个人 一次只能买一张票 ，如果需要购买更多票，他必须走到 队尾 重新排队（瞬间 发生，不计时间）。如果一个人没有剩下需要买的票，那他将会 离开 队伍。

返回位于位置 k（下标从 0 开始）的人完成买票需要的时间（以秒为单位）。

题解

实际就是每个人减掉目标的票数，单独区分下标排在目标前和排在目标后的情况。

代码

1
2
3
4
5
6
7
8
9
function needTime(tickets, num) {
    let result = 0;
    const target = tickets[num];
    for (let i = 0; i < tickets.length; i++) {
        const current = tickets[i];
        result += Math.min(current, i <= num ? target : target - 1);
    }
    return result;
}

无法吃午餐的学生数量

题目

学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。
餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮：

如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。

否则，这名学生会 放弃这个三明治 并回到队列的尾部。

这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。

题解

考虑停止的条件，也就是出现一个三明治所有剩余的学生都不喜欢，所以其实学生的顺序不重要，三明治给任意一个需要的学生都可以。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
function getNum(students, sandwiches) {
    let result = students.length;
    while (sandwiches.length) {
        const s = sandwiches.shift();
        const index = students.indexOf(s);
        if (index === -1) {
            break;
        }
        result--;
        students.splice(index, 1);
    }
    return result;
}

求最后一块石头的重量

题目

有一堆石头，每块石头的重量都是正整数。

每一回合，从中选出两块 最重的 石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。

题解

直接模拟题目的过程：从后往前遍历，每次取最后两个元素碰撞更新，作为前一个元素的新值。每次遍历都重新排序一下。最后遍历到第一个元素就是结果。

代码

1
2
3
4
5
6
7
function lastStoneWeight(stones) {
    for (let i = stones.length - 1; i >= 1; i--) {
        stones.sort((a, b) => a - b);
        stones[i - 1] = stones[i] - stones[i - 1];
    }
    return stones[0];
}

最小数

题目

给定一组非0整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最小的整数。

注意：

输入整数数组中，可能存在负数，但最多只会有一个负数

输出结果可能非常小，所以你需要返回一个字符串而不是整数。

题解

本质就是拼接完两个数字再作比较。单独考虑有负数的情况，有负数就变成了移除负数元素后求最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
function min(arr) {
    const negativeIndex = arr.findIndex((num) => num < 0);
    const negativeValue = arr[negativeIndex] || '';
    if (negativeValue) {
        arr.splice(negativeIndex, 1);
    }
    if (negativeIndex === -1) {
        arr.sort((a, b) => `${a}${b}` - (`${b}${a}`));
    } else {
        arr.sort((a, b) => `${b}${a}` - (`${a}${b}`));
    }
    return `${negativeValue}${arr.join('')}`;
}