算法与数据结构：数组与字符串

Quickeryi commented 7 years ago

写在前面

虽然貌似前端接触算法的机会很少或者有些人根本就没有在实际的开发中使用过算法相关的东西（其实是个人能力问题或者业务复杂度或者性能要求不高）。但是不可否认的是，当程序性能遇到瓶颈，而无法在硬件上解决问题时，算法就犹如一把利剑，一路披荆斩棘。我这里要记录的只是一些大家熟知的算法概念以及面试遇到的问题～

字符串相关

[x] 回文判断
- 何为回文：一个顺着读和反过来读都一样的字符串，例如：aba
- 解法一：同时从字符串头尾开始向中间扫描字串，如果所有字符都一样，那么这个字串就是一个回文 1）时间复杂度：O(n) 2）空间复杂度：O(1)
- 解法二：从中间开始、然后向两边扩展查看字符是否相等 1）时间复杂度：O(n) 2）空间复杂度：O(1)
```
// 解法一
/** 
```
- @param str 字符串
- @param n 字符串长度 */ var IsPalindrome = (str, n) => { "use strict"; if (!str) return false; let front = 0, back = n-1; while (front < back) { if (str[front] != str[back]) { return false; } front++; back--; } return true; }

// 解法二 /**

@param str 字符串
@param n 字符串长度 */ let IsPalindrome = (str, n) => { "use strict"; if (!str) return false; let mid = Math.floor(n/2), front = mid -1, back; n%2 == 0 ? back = mid : back = mid + 1; while (front > -1) { if (str[front] != str[back]) { return false; } front--; back++; } return true; }
```
- [x] 统计一个字符串出现最多的字母
- 问题描述：给出一段英文连续的英文字符窜，找出重复出现次数最多的字母，例如：输入`abaaaac`，输出`a`
- 解法：线性遍历
   1）时间复杂度：`O(m+n)`
   2）空间复杂度：`O(1)`
```javascript
let findMaxDuplicateChar = (str) => {
"use strict";
if (!str || str.length == 1) return str;
let map = {},
    char,
    max = 1;
for (let i=0, len=str.length; i<len; i++) {
    if (!map[str[i]]) {
        map[str[i]] = 1;
    } else {
        map[str[i]]++;
    }
}

for (let key in map) {
    if (map[key] > max) {
        char = key;
        max = map[key];
    }
}

return char;
}
```
数组相关
- [x] 旋转数组
- 问题描述：给定一个数组，要求把数组前面的若干个元素移动到数组的尾部，如把字符串[a, b, c, d, e, f]前面的2个元素a和b移动到数组的尾部，使得原数组变成[c, d, e, f, a, b]
- 解法一：把需要移动的元素一个一个地移动到数组的尾部 1）时间复杂度：O(m*n) 2）空间复杂度：O(1)
- 解法二：三步反转法，将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题 1）时间复杂度：O(n) 2）空间复杂度：O(1)
```
// 解法一
/** 
```
@param arr 数组
@param n 数组长度 */ let LeftShiftOne = (arr, n) => { let first = arr[0]; for (let i = 1; i < n; i++) { arr[i-1] = arr[i]; } arr[n-1] = first; }

/**

@param arr 数组
@param n 数组长度
@param m 移动的元素个数 */ let LeftRotateArray = (arr, n, m) => { while(m--) { LeftShiftOne(arr, n); } }

// 解法二 /**

反转数组
@param arr 数组
@param from 起始位置
@param to 结束位置 */ let reverse = (arr, from ,to) => { while (from < to) { let first = arr[from]; arr[from++] = arr[to]; arr[to--] = first; } }

/**

@param arr 数组
@param n 数组长度

@param m 移动的元素个数 */ let LeftRotateArray = (arr, n, m) => { m%=n; reverse(arr, 0, m-1); //反转[0..m - 1]，套用到上面举的例子中，就是X->X^T，即 abc->cba reverse(arr, m, n-1); // 反转[m..n - 1]，例如Y->Y^T，即 def->fed reverse(arr, 0, n-1); // 反转[0..n - 1]，即如整个反转，(X^TY^T)^T=YX，即 cbafed->defabc }


- [x] 数组去重
- 问题描述：去除数组重复元素
- 方法一：遍历法
   1）时间复杂度：`O(n)`
   2）空间复杂度：`O(1)`
- 方法二：ES6实现
```javascript
// 方法一
let unique = (arr) => {
"use strict";
if (!Array.isArray(arr) || arr.length < 2) return arr;
let data = [],
  hasMap = {};
for (let i=0, len=arr.length; i<len; i++) {
let key = `${typeof arr[i]}${JSON.stringify(arr[i])}`;
if (!hasMap[key]) {
    hasMap[key] = !!1;
    data.push(arr[i]);
}
}
return data;
}

// 方法二 let unique = (arr) => { "use strict"; if (!Array.isArray(arr) || arr.length < 2) return arr; return Array.from(new Set(arr)); }

Quickeryi commented 7 years ago

参考一参考二

wind-stone commented 6 years ago

数组去重的方法一，不合适对象的去重。

let key = ${typeof arr[i]}${arr[i]}; 里 arr[i] 如果是对象，会调用其 toString 方法，得到的是 "[object Object]"，所以如果你的输入是 [{a: 1}, {a: 2}]，去重返回的结果是 [{a: 1}]

Quickeryi / note

算法与数据结构：数组与字符串 #15

写在前面

字符串相关

数组相关