# 1. 前言
最近回顾了一下以前做过的leetCode题目，主要是字符串和数组相关为主，本文整理一下常见的题目，解题思路。本人是算法萌新，互相学习，大神勿喷。
# 2.字符串类
题目：计算出字符串abcdefeb中出现次数最少（多）的字符的次数。
这个题目还是比较简单的：循环一遍字符串，建一个空对象用来保存字符的数量即可。
function f(str){
let obj = {};
for(let i=0;i<str.length;i++){
if (obj[str[i]]) {
obj[str[i]] ++;
} else {
obj[str[i]] = 0;
}
}
let countArr = [];
Object.keys(obj).for((item)=>{
countArr.push(obj[item]);
});
return Math.min(...countArr);
}
题目：去掉字符串abcdefeb中出现次数最少（多）的字符。
这个题目只是上一个题目的变形而已，计算出出现次数最少（多）的次数后，再遍历对象，获取对应的字符使用replace替换掉即可。具体代码省略。
题目：对字符串中的所有单词进行倒排后输出，输出的单词之间只有一个空格。构成单词的字符只有大小写字母，非字母字符视作空格。如：
i %am a b&oy等价于i am a b oy，则倒排后的输出应为：oy b a am i
我解这个题的思路是新建一个空数组用来接受句子中的单词，然后循环一遍字符串，如果是字符则连结组成单词，如果遇到非字符则将之前的单词存到数组中。具体代码如下：
function f(str){
const acode = 'a'.charCodeAt();
const zcode = 'z'.charCodeAt();
const Acode = 'A'.charCodeAt();
const Zcode = 'Z'.charCodeAt();
function isLetter(word){
const value = word.charCodeAt();
if (value>=acode&&value<=zcode || value>=Acode&&value<=Zcode){
return true;
} else {
return false;
}
}
let arr = [], res= '';
for(let i=0;i<str.length;i++){
if (isLetter(str[i])){
res += str[i];
} else {
if (res){
arr.push(res);
}
res = '';
}
if (i===(str.length-1) && res){
arr.push(res);
}
}
return arr.reverse().join(' ');
}
题目：计算两个字符串的最大公共子序列的长度。（子序列是由原字符串中的字符按照原顺序组成的字符串。如"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。）题目举例："abcde"和"ace"的最长公共子序列是 "ace"，它的长度为3，因此输出3。
这个题目稍微困难一点，按照一般的思路无法解决，要应用动态规划的方法来做。所谓的动态规划，就是将当前的问题分解为若干个可以解决的更小的问题。然后将分解后的问题再分解成更小的问题。在已知某些初始条件的情况下，最终将所需的问题求解。
对于当前这个问题，我们假设一个二维数组dp[i][j]是当第一个字符串str1的i位置，第二个字符串str2的j位置时，此时的最大公共子序列的长度。那么有两种情况：
- str1[i]等于str2[j]，则dp[i][j]等于dp[i-1][j-1]加1。
- str1[i]不等于str2[j]，则dp[i][j]等于dp[i][j-1]或者dp[i-1][j]中较大的那一个。
写成代码表示为：
function f(str1, str2){
let dp = [],
m = str1.length,
n = str2.length;
for(let i=0;i<=m;i++){
// 创建一个二维数组
dp.push((new Array(n+1)).fill(0));
}
for(let i=1;i<=m;i++){
for(let j=1;j<=n;j++){
if (str1[m]===str2[n]){
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
}
}
}
return dp[m][n];
}
# 3.数组类
题目：给一个指定的数组进行排序或者去重的操作。
这类型的题目算是数组中最基本的操作了。数组排序可以使用冒泡排序，快排，插入排序等，当然也可以用sort()函数直接实现。去重可以使用es6 Set去重，还有些其他的手段此处不再详细介绍。
// 冒泡排序
function f(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // 相邻元素两两对比
let temp = arr[j+1]; // 元素交换
arr[j+1] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
//去重
function f(arr) {
// 删除数组应当是从后往前遍历，从前往后会跳过某些项
for (let i = (arr.length-1); i >= 0; i--) {
if (i !== arr.indexOf(arr[i])) {
arr.splice(i, 1);
}
}
return arr;
}
题目：求一个数组重复次数最多/少的子项的次数。例：求[3, 6, 9, 5, 4, 6, 3]中出现次数最多的项的次数。
这中题目也算是比较简单的题目了，如果数组子项是数值型的可以用一个空数组来存储子项出现的次数，如果是字符型的则可以用空对象。
// 求出现次数最多的次数
function f(arr) {
let arrLen = Math.max(...arr);
let countArr = (new Array(arrLen + 1)).fill(0);
for (let i = 0; i < arr.length; i++) {
countArr[arr[i]]++;
}
return Math.max(...countArr);
}
如果给的数组是[a, b, c, d, a, f]，则解法：
function f(arr) {
let countObj = {};
for (let i = 0; i < arr.length; i++) {
if (!countObj[arr[i]]) {
countObj[arr[i]] = 1;
} else {
countObj[arr[i]]++;
}
}
let resultArr = Object.keys(countObj).map((item) => countObj[item]);
return Math.max(...resultArr);
}
题目：给定一个长度为N的数组，找出一个最长的单调递增子序列的长度，子序列不一定连续，但初始顺序不能乱。例：[4,5,7,1,3,9]的最长递增子序列是[4,5,7,9]，则输入长度4。
这个题目可以分别求出以每个子项数字为起点的最长递增子序列，然后再最长度进行判断。
function f(arr){
let finalArr = [];
for (let i = 0; i < arr.length; i++) {
let riseArr = [];
riseArr.push(arr[i]);
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] >= riseArr[riseArr.length - 1]) {
riseArr.push(arr[j]);
}
}
finalArr.push(riseArr);
}
let resultArr = finalArr.map((item) => item.length);
return Math.max(resultArr);
}
这题还可以用动态规划的方法解答。我们建立一个一维数组dp[i]用来表示当此时位于数组的i位置时最长递增子序列的长度。那么我们可以得出以下结论：
- 在目标数组arr上，当j<i时，如果arr[j]小于arr[i]，那么arr[j]和arr[i]是满足递增序列的，此时的dp[i]应等于dp[j]加1。
写成代码表示为：
function f(arr){
let dp = [];
for(let i=0;i<arr.length;i++){
dp[i] = 1; // 初始化dp，每个子项至少有本身一个递增序列
for(let j=0;j<i;j++){
// dp[i]动态赋值
if (arr[j]<arr[i] && dp[j] >= dp[i]) {
dp[i] = dp[j] + 1;
}
}
}
return Math.max(...dp);
}
题目：给出一个N个学生身高的有序数组，计算最少出列多少位同学，使得剩下的同学排成合唱队形。合唱队队形指的是身高从低到高再到低。例：[186, 186, 150, 200, 160, 130, 197, 200]，最少出列四个同学186，186，200，130使得剩下的同学呈合唱队排列[]。
这个题目的解法是由上面一题变形而来的。我们想要出列最少的同学，即让呈合唱队的同学越多越好。只要我们对数组序列的每一项求其左边递增序列的最大值和右边递减序列的最大值即可。
function f(arr) {
let arrLen = arr.length;
let dp1=[],dp2=[],dp3=[];
for(let i=0;i<arrLen;i++){
dp1[i] = 1 // 至少有自身1个作为递增序列
for(let j=0;j<i;j++){
if (arr[j]<arr[i] && dp1[j]>=dp1[i]){
dp1[i] = dp1[j] + 1;
}
}
}
arr.reverse(); // 将数组倒过来，以递增计算递减序列
for(let i=0;i<arrLen;i++){
dp2[i] = 1 // 至少有自身1个作为递增序列
for(let j=0;j<i;j++){
if (arr[j]<arr[i] && dp2[j]>=dp2[i]){
dp2[i] = dp2[j] + 1;
}
}
}
dp2.reverse(); // 反过来作为递减序列
for(let i=0;i<arrLen;i++){
dp3[i] = dp1[i] + dp2[i] - 1;
}
return (arrLen - Math.max(...dp3)); // 计算最少出列的数量
}
作者简介： 宫晨光，人和未来 (opens new window)大数据前端工程师。