CHIEMINCHAN'S BLOG

# 🌵 JavaScript 基础算法

# 001： 列举实现数组扁平化的方法。

即将嵌套任何层数的数组转换成只有一层的数组，

let array = [1,2,[3,[4,5]]]; => [1,2,3,4,5]

# (1) toString

array
    .toString()
    .split(",")
    .map((item) => {
        return +item;
    });

# (2) 递归

const flatten1 = (array) => {
    let result = [];
    array.forEach((item) => {
        if (Array.isArray(item)) {
            result = result.concat(flatten1(item));
        } else {
            result.push(item);
        }
    });
    return result;
};

const flatten2 = (arr) => {
    return arr.reduce((prev, cur) => {
        const item = Array.isArray(cur) ? flatten2(cur) : cur;
        return prev.concat(item);
    }, []);
};

# 002. 数组去重

# (1) 数组 filter

removeRepeatArray: (arr) => {
    arr.filter((item, index, self) => {
        return self.indexOf(item) === index;
    });
};

# (2) Object.keys()

let obj = {};
removeRepeatArray: (arr) => {
    arr.forEach((item) => {
        obj[item] = item;
    });

    return Object.keys(obj);
};

注意： 这种方法在有[1, "1"]元素的数组不适用。

# (3) Set

const result = [...new Set(arr)];

# (4)reduce

const removeRepeatArray = arr.reduce((pre, cur) => {
    if (pre.indexOf(cur) === -1) {
        console.log(pre, cur);
        pre.push(cur);
    }
    return pre;
}, []);

# (5) sort

const removeRepeatArray = () => {
    arr.sort();

    const result = [];

    for (let i = 0; i < arr.length; i++) {
        if(arr[i] !=== result[result.length-1]){
            result.push(arr[i]);
        }
    }

    return result;
};

⚠️ 若要返回重复元素的数组:

//缓存重复出现元素的数组
const cacheExtraChar = [];

array.map((item, index) => {
    array.indexOf(item) !== array.lastIndexOf(item) &&
    cacheExtraChar.indexOf(item) === -1
        ? cacheExtraChar.push(item)
        : -1;
});

# 003： 给一个未排序的整数数组和一个值 sum，如果数组中任意两项相加等于 sum，则返回 true，否则返回 false。

例如：给定数组 [3, 5, 1, 4] 和值 9，我们的方法应该返回 true，因为 4 + 5 = 9。

const findSum = (arr, sum) => {
    const searchVals = new Set();
    arr.forEach((item) => {
        const searchVal = sum - item;
        searchVals.has(item) ? (result = true) : searchVals.add(searchVal);
    });
    return result;
};

# 004： 给定两个数组，写一个方法来计算它们的交集。

例如：给定 nums1 = [1, 2, 2, 1]，nums2 = [2, 2]，返回 [2, 2]。

const intersect = (nums1, nums2) => {
    const map = {};
    const result = [];
    for (let item of nums1) {
        map[item] ? map[item]++ : (map[item] = 1);
    }

    for (let item of nums2) {
        if (map[item] && map[item] > 0) {
            result.push(item);
            map[item]--;
        }
    }

    return result;
};

💡 注意：这道题不是工程题，是道算法题。求的是两个数组的最长公共子序列 (子序列要求顺序，交集不需要）。特殊例子：nums1 = [1,1], nums2 = [1]。

这道题两种思路，空间换时间，或不用额外空间但提升时间复杂度。

空间换时间的思路是用个 Hash 表来存数组 1 的元素以及出现的个数（此处需要遍历 n 次，并存一个 n 级别的空间）。
遍历数组 2，发现数组 2 里有 Hash 表里的值就存到 Result 数组里，并把 Hash 表内该值次数减一（为 0 之后就 Delete）。如果不存在 Hash 表里，就跳过。这样时间复杂度就是 (m+n)。

不用额外空间，就用遍历 n 的时候，判断值在不在 m 里，如果在，把 m 里的该值 push 到 Result 数组里，并将该值从 m 数组里删掉（用 splice）。这样就是不用额外空间，但是提高了时间复杂度。

# 005： 如何把一个字符串的大小写取反（大写变小写，小写变大写）?

例如： ’AbC' 变成 'aBc' 。

const transFormStr = (str) => {
    const strArr = str.split("");
    let result = "";
    for (let n of strArr) {
        n === n.toLowerCase()
            ? (result += n.toUpperCase())
            : (result += n.toLowerCase());
    }
    return result;
};

← 🌵 ES6 →