常见算法

Copy 
1const isValid = function (s) {
2  if (s.length % 2 === 1) {
3    return false;
4  }
5  const regObj = {
6    "{": "}",
7    "(": ")",
8    "[": "]",
9  };
10  let stack = [];
11  for (let i = 0; i < s.length; i++) {
12    if (s[i] === "{" || s[i] === "(" || s[i] === "[") {
13      stack.push(s[i]);
14    } else {
15      const cur = stack.pop();
16      if (s[i] !== regObj[cur]) {
17        return false;
18      }
19    }
20  }
21
22  if (stack.length) {
23    return false;
24  }
25
26  return true;
27};

Copy 
1const longestCommonPrefix = function (strs) {
2  const str = strs[0];
3  let index = 0;
4  while (index < str.length) {
5    const strCur = str.slice(0, index + 1);
6    for (let i = 0; i < strs.length; i++) {
7      if (!strs[i] || !strs[i].startsWith(strCur)) {
8        return str.slice(0, index);
9      }
10    }
11    index++;
12  }
13  return str;
14};

Copy 
1const lengthOfLongestSubstring = function (s) {
2  if (s.length === 0) {
3    return 0;
4  }
5
6  let left = 0;
7  let right = 1;
8  let max = 0;
9  while (right <= s.length) {
10    let lr = s.slice(left, right);
11    const index = lr.indexOf(s[right]);
12
13    if (index > -1) {
14      left = index + left + 1;
15    } else {
16      lr = s.slice(left, right + 1);
17      max = Math.max(max, lr.length);
18    }
19    right++;
20  }
21  return max;
22};

Copy 
1function getTenNum(testArray, n) {
2  const cloneArr = [...testArray];
3  let result = [];
4  for (let i = 0; i < n; ++i) {
5    const random = Math.floor(Math.random() * cloneArr.length);
6    const cur = cloneArr[random];
7    result.push(cur);
8    cloneArr.splice(random, 1);
9  }
10  return result;
11}
12const testArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
13const resArr = getTenNum(testArray, 14);

Copy 
1/**
2 * @param {number[]} nums
3 * @return {number[][]}
4 */
5const permute = nums => {
6    if (!nums) return [];
7    const res = [];
8    // path是组合的数组
9    const backtrack = path => {
10        if (path.length === nums.length) {
11            // 长度满足条件，推入res数组
12            res.push(path);
13            return;
14        }
15        nums.forEach(n => {
16            // path中已经有n，放弃此轮
17            if (path.includes(n)) return;
18            // 将n加入path继续找
19            backtrack([...path, n]);
20        });
21    };
22    // 从空数组开始
23    backtrack([]);
24    return res;
25};

Copy 
1const hasCycle = function(head) {
2  if(head === null || head.next === null) {
3    return false;
4  }
5  let slow = head;
6  let fast = head.next;
7  while (slow) {
8    if(slow === fast) {
9      return true
10    }
11    slow = slow?.next || null;
12    fast = fast?.next?.next || null;
13  }
14  return false;
15};

Copy 
1// 有许多[start, end]的闭区间, 请设计一个算法, 算出这些区间中, 最多有几个互不相交的区间。
2// 比如intvs = [[1,3], [2,4], [3,6]]
3// 这些区间最多有两个区间互不相交, 即 [1,3], [3,6], intervalSchedule函数此时应该返回2
4
5function intervalSchedule(intvs) {
6    if (intvs.length === 0) {
7        return 0;
8    }
9
10    const sortArray = intvs.sort((a, b) => a[1] - b[1]);
11
12    let count = 1; // 最少有一个区间不相交
13    let xEnd = sortArray[0][1];
14
15    for (let item of intvs) {
16        const start = item[0];
17        // 这里是> 或者 >=取决于, [1,3][3,6], 3算不算相交
18        if (start >= xEnd) {
19            count++;
20            xEnd = item[1];
21        }
22    }
23    return count;
24}
25
26console.log(intervalSchedule([
27    [1, 3],
28    [2, 4],
29    [3, 6]
30]))