算法

  • 解决问题的计算方法
  • 程序=数据结构+算法

判断括号是否闭合

思路：使用栈解决，遇到 ( 入栈，遇到 ) 出栈，栈空了合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 判断括号是否闭合
 * @param {String} str 
 */
function brackets(str) {
  var arr1 = str.split('')
  var arr2 = []
  for (let i = 0; i < arr1.length; i++) {
    if (arr1[i] === "(") {
      arr2.push("(")
    } else if (arr1[i] === ")") {
      arr2.pop()
    }
  }
  return !arr2.length
}
// 测试用例 true 闭合，false 未闭合
brackets('') // true
brackets('()()()()()') // true
brackets('((((()') // false
brackets('((()(())))') // true
brackets('(())))') // true

转换字符串为json

entry

1
const entry={"a.b.c.d":"dd","e":"ee","ab.ac.da.dc.ee":"end"};

output

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const output={
  a:{
    b:{
      c:{
        d:"dd"
      }
    }
  },
  e:"ee",
  ab:{
    ac:{
      da:{
        dc:{
          ee:"end"
        }
      }
    }
  }
}

思路：迭代对象，key转换为数组，使用队列处理key数组，判断最后一个直接赋值，其它赋值为：{}

1
2
3
4
5
6
7
8
9
10
11
12
// 定义变量，展示最后结果
const output={}
for(let key in entry){
  const ar=key.split('.');
  let p=output;
  while(ar.length){
    const item=ar.shift();
    p[item]=ar.length?{}:entry[key];
    p=p[item];
  }
}
console.log(output);

LeetCode 经典示例

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

1
2
3
4
5
6
7
8
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) return [map.get(diff), i];
    map.set(nums[i], i);
  }
}

2. 反转链表

反转一个单链表。

1
2
3
4
5
6
7
8
9
10
function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  return prev;
}

3. 合并两个有序链表

将两个升序链表合并为一个新的升序链表。

1
2
3
4
5
6
7
8
9
10
11
function mergeTwoLists(l1, l2) {
  if (!l1) return l2;
  if (!l2) return l1;
  if (l1.val < l2.val) {
    l1.next = mergeTwoLists(l1.next, l2);
    return l1;
  } else {
    l2.next = mergeTwoLists(l1, l2.next);
    return l2;
  }
}

4. 最大子序和

给定一个整数数组，找到一个具有最大和的连续子数组。

1
2
3
4
5
6
7
8
function maxSubArray(nums) {
  let max = nums[0], sum = 0;
  for (let num of nums) {
    sum = Math.max(num, sum + num);
    max = Math.max(max, sum);
  }
  return max;
}

5. 移动零

给定一个数组 nums，将所有 0 移动到数组末尾，同时保持非零元素的相对顺序。

1
2
3
4
5
6
7
8
9
function moveZeroes(nums) {
  let j = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      j++;
    }
  }
}

6. 有效的括号

判断字符串中的括号是否有效。

1
2
3
4
5
6
7
8
9
10
11
function isValid(s) {
  const stack = [];
  const map = {')':'(', ']':'[', '}':'{'};
  for (let c of s) {
    if (c === '(' || c === '[' || c === '{') stack.push(c);
    else {
      if (stack.pop() !== map[c]) return false;
    }
  }
  return stack.length === 0;
}

7. 删除排序数组中的重复项

原地删除有序数组中的重复元素。

1
2
3
4
5
6
7
8
function removeDuplicates(nums) {
  if (!nums.length) return 0;
  let i = 0;
  for (let j = 1; j < nums.length; j++) {
    if (nums[j] !== nums[i]) nums[++i] = nums[j];
  }
  return i + 1;
}

8. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

1
2
3
4
function maxDepth(root) {
  if (!root) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

9. 爬楼梯

每次可以爬 1 或 2 阶楼梯，求有多少种方法爬到楼顶。

1
2
3
4
5
6
7
function climbStairs(n) {
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

10. 合并区间

合并所有重叠的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function merge(intervals) {
  if (!intervals.length) return [];
  intervals.sort((a, b) => a[0] - b[0]);
  const res = [intervals[0]];
  for (let i = 1; i < intervals.length; i++) {
    let last = res[res.length - 1];
    if (intervals[i][0] <= last[1]) {
      last[1] = Math.max(last[1], intervals[i][1]);
    } else {
      res.push(intervals[i]);
    }
  }
  return res;
}