5.9

19. 删除链表的倒数第 N 个结点

各个排序的时间复杂度

41. 缺失的第一个正数

const firstMissingPositive = nums => {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    // 将nums[i]放到对应的位置
    while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] !== nums[i]) {
      [nums[nums[i] - 1], nums[i]] = [nums[i], nums[nums[i] - 1]];
    }
  }
  // 遍历是否是对应位置
  for (let i = 0; i < len; i++) {
    if (nums[i] !== i + 1) return i + 1;
  }
  return len + 1;
};

1143. 最长公共子序列

var longestCommonSubsequence = function(text1, text2) {
    const m = text1.length, n = text2.length;
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        const c1 = text1[i - 1];
        for (let j = 1; j <= n; j++) {
            const c2 = text2[j - 1];
            if (c1 === c2) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
};

151. 翻转字符串里的单词

var reverseWords = function(s) {
    return s.trim().split(/\s+/).reverse().join(' ');
};

349. 两个数组的交集

const set_intersection = (set1, set2) => {
    if (set1.size > set2.size) {
        return set_intersection(set2, set1);
    }
    const intersection = new Set();
    for (const num of set1) {
        if (set2.has(num)) {
            intersection.add(num);
        }
    }
    return [...intersection];
}
var intersection = function(nums1, nums2) {
    const set1 = new Set(nums1);
    const set2 = new Set(nums2);
    return set_intersection(set1, set2);
};

169. 多数元素

var majorityElement = function(nums) {
    const map = new Map()
    for(let num of nums) {
        if (!map.get(num)) {
            map.set(num, 1)
        } else {
            map.set(num, map.get(num) + 1)
        }
    }
    for(const [key, value] of map) {
        if (value > nums.length / 2) {
            return key
        }
    }
};