1.3.2 String类型常见算法-Javascript重点难点实例精讲（一）

当前位置:　首页>> 技术小册>> Javascript重点难点实例精讲（一）

在本小节中我们将会一起学习String类型中常见的算法，学习完本小节后，相信大家不仅能对String类型常见算法有更加详细的了解，在算法设计方面也会有一定的提高。
1. 字符串逆序输出
字符串的逆序输出就是将一个字符串以相反的顺序进行输出。
真实场景如下所示。
给定一个字符串'abcdefg'，执行一定的算法后，输出的结果为'gfedcba'。
针对这个场景，以下总结出了5种不同的处理函数。
算法1
算法1的主要思想是借助数组的reverse()函数。
首先将字符串转换为字符数组，然后通过调用数组原生的reverse()函数进行逆序，得到逆序数组后再通过调用join()函数得到逆序字符串。
通过上述的思路，我们得到下面的代码。

```
// 算法1：借助数组的reverse()函数
function reverseString1(str) {
   return str.split('').reverse().join('');
}

```
然后通过以下的代码进行测试。

```
var str = 'abcdefg';
console.log(reverseString1(str));

```
输出的结果为“gfedcba”，符合预期。
算法2
算法2的主要思想是利用字符串本身的charAt()函数。
从尾部开始遍历字符串，然后利用charAt()函数获取字符并逐个拼接，得到最终的结果。charAt()函数接收一个索引数字，返回该索引位置对应的字符。

通过上述的思路，我们得到下面的代码。

```
// 算法2：利用charAt()函数
function reverseString2(str) {
   var result = '';
   for(var i = str.length 
``` 1; i >= 0; i
```
```){
       result += str.charAt(i);
   }
   return result;
}

```
然后通过以下的代码进行测试。

```
var str = 'abcdefg';
console.log(reverseString2(str));

```
输出的结果为“gfedcba”，符合预期。
算法3
算法3的主要思想是通过递归实现逆序输出，与算法2的处理类似。
递归从字符串最后一个位置索引开始，通过charAt()函数获取一个字符，并拼接到结果字符串中，递归结束的条件是位置索引小于0。
通过上述的思路，我们得到下面的代码。

```
// 算法3：递归实现
function reverseString3(strIn,pos,strOut){
   if(pos<0)
      return strOut;
   strOut += strIn.charAt(pos

);
   return reverseString3(strIn,pos,strOut);
}

```

然后通过以下的代码进行测试。

```
var str = 'abcdefg';
var result = '';
console.log(reverseString3(str, str.length 
``` 1, result));

```
输出的结果为“gfedcba”，符合预期。
算法4
算法4的主要思想是通过call()函数来改变slice()函数的执行主体。
调用call()函数后，可以让字符串具有数组的特性，在调用未传入参数的slice()函数后，得到的是一个与自身相等的数组，从而可以直接调用reverse()函数，最后再通过调用join()函数，得到逆序字符串。
通过上述思路，我们得到下面的代码。

```
// 算法4: 利用call()函数
function reverseString4(str) {
   // 改变slice()函数的执行主体，得到一个数组
   var arr = Array.prototype.slice.call(str);
   // 调用reverse()函数逆序数组
   return arr.reverse().join('');
}

```
然后通过以下的代码进行测试。

```
var str = 'abcdefg';
console.log(reverseString4(str));

```

输出的结果为“gfedcba”，符合预期。
算法5
算法5的主要思想是借助栈的先进后出原则。
由于JavaScript并未提供栈的实现，我们首先需要实现一个栈的数据结构，然后在栈中添加插入和弹出的函数，利用插入和弹出方法的函数字符串逆序。
首先，我们来看下基本数据结构——栈的实现。通过一个数组进行数据存储，通过一个top变量记录栈顶的位置，随着数据的插入和弹出，栈顶位置动态变化。
栈的操作包括两种，分别是出栈和入栈。出栈时，返回栈顶元素，即数组中索引值最大的元素，然后top变量减1；入栈时，往栈顶追加元素，然后top变量加1。

```
// 栈
function Stack() {
   this.data = []; // 保存栈内元素
   this.top = 0;   // 记录栈顶位置
}
// 原型链增加出栈、入栈方法
Stack.prototype = {
   // 入栈:先在栈顶添加元素，然后元素个数加1
   push: function push(element) {
       this.data[this.top++] = element;
   },
   // 出栈：先返回栈顶元素，然后元素个数减1
   pop: function pop() {
       return this.data[

this.top];
   },
   // 返回栈内的元素个数，即长度
   length: function () {
       return this.top;

```

2.统计字符串中出现次数最多的字符及出现的次数

真实场景如下所示。
假如存在一个字符串'helloJavascripthellohtmlhellocss'，其中出现次数最多的字符是l，出现的次数是7次。
针对这个场景，以下总结出了5种不同的处理算法。
算法1
算法1的主要思想是通过key
```
value形式的对象来存储字符串以及字符串出现的次数，然后逐个判断出现次数最大值，同时获取对应的字符，具体实现如下。
· 首先通过key
```
value形式的对象来存储数据，key表示不重复出现的字符，value表示该字符出现的次数。
· 然后遍历字符串的每个字符，判断是否出现在key中。如果在，直接将对应的value值加1；如果不在，则直接新增一组key
```
value，value值为1。
· 得到key
```
value对象后，遍历该对象，逐个比较value值的大小，找出其中最大的值并记录key
```
value，即获得最终想要的结果。
通过以上的分析，可以得到如下的代码。

```

// 算法1
```
function getMaxCount(str) {
   var json = {};
   // 遍历str的每一个字符得到key
```
value形式的对象
```
   for (var i = 0; i < str.length; i++) {
       // 判断json中是否有当前str的值
       if (!json[str.charAt(i)]) {
           // 如果不存在，就将当前值添加到json中去
           json[str.charAt(i)] = 1;
       } else {
           // 如果存在，则让value值加1
           json[str.charAt(i)]++;
       }
   }
   // 存储出现次数最多的值和出现次数
   var maxCountChar = '';
   var maxCount = 0;
   // 遍历json对象，找出出现次数最大的值
  for (var key in json) {
      // 如果当前项大于下一项
      if (json[key] > maxCount) {
          // 就让当前值更改为出现最多次数的值
          maxCount = json[key];
          maxCountChar = key;
      }
   }
   //最终返回出现最多的值以及出现次数
   return '出现最多的值是' + maxCountChar + '，出现次数为' + maxCount;
}
var str = 'helloJavaScripthellohtmlhellocss';
getMaxCount(str); // '出现最多的值是l，出现次数为7'

```

通过上面的测试，结果符合预期。

3.去除字符串中重复的字符
真实场景如下所示。
假如存在一个字符串'helloJavaScripthellohtmlhellocss'，其中存在大量的重复字符，例如h、e、l等，去除重复的字符，只保留一个，得到的结果应该是'heloJavscriptm'。
针对这个场景，以下总结出了3种不同的处理算法。
算法1
算法1的主要思想是使用key

value类型的对象存储，key表示唯一的字符，处理完后将所有的key拼接在一起即可得到去重后的结果。
· 首先通过key

value形式的对象来存储数据，key表示不重复出现的字符，value为boolean类型的值，为true则表示字符出现过。
· 然后遍历字符串，判断当前处理的字符是否在对象中，如果在，则不处理；如果不在，则将该字符添加到结果数组中。
· 处理完字符串后，得到一个数组，转换为字符串后即可获得最终需要的结果。
通过以上的描述，可以得到如下的代码。

// 算法1
```
function removeDuplicateChar1(str) {
   // 结果数组
   var result = [];
   // key
```
value形式的对象
```
   var json = {};
   for (var i = 0; i < str.length; i++) {
       // 当前处理的字符
       var char = str[i];
       // 判断是否在对象中
       if(!json[char]) {
           // value值设置为false
           json[char] = true;
           // 添加至结果数组中
           result.push(char);
       }
   }
   return result.join('');
}

var str = 'helloJavaScripthellohtmlhellocss';
removeDuplicateChar1(str);  // 'heloJavscriptm'

```

通过上面的测试，结果符合预期。