整理几道常见的 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 const MinStack = function ( this .a = []; this .b = []; }; MinStack.prototype.push = function (x ) this .a.push(x); if (!this .b.length || x <= this .b[this .b.length - 1 ]) { this .b.push(x); } }; MinStack.prototype.pop = function ( const x = this .a.pop(); if (x === this .b[this .b.length - 1 ]) { this .b.pop(); } }; MinStack.prototype.top = function ( return this .a[this .a.length - 1 ]; }; 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('' )} ` ; }
