leetcode-0524-0529-所刷题目

[22]. 括号生成

/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
// solution: 回溯 + 剪枝
var generateParenthesis = function (n) {var res = [];
  var initialPath = '';
  dfs(res, n, n, initialPath);
  return res;

  function dfs(res, left, right, path) {if (left === 0 && right === 0) {res.push(path);
      return;
    }

    if (left > 0) {dfs(res, left - 1, right, path + '(');
    }

    if (left < right) {dfs(res, left, right - 1, path + ')');
    }
  }
};

[01]. 两数之和

/*
 * @lc app=leetcode.cn id=1 lang=javascript
 *
 * [1] 两数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

// solution 1:
var twoSum = function (nums, target) {for (var i = 1; i < nums.length; i++) {var idx = nums.indexOf(target - nums[i]);
    if (idx > -1 && idx !== i) {return [i, idx];
    }
  }
  return [];};

//  solution 2:
var twoSum = function (nums, target) {var dic = {};
  for (var i = 0; i < nums.length; i++) {var complement = target - nums[i];
    if (complement in dic) {return [dic[complement], i];
    }
    dic[nums[i]] = i;
  }
};
// @lc code=end

[40]. 最小的 k 个数

/**
 * 40. 最小的 k 个数
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var getLeastNumbers = function (arr, k) {var result = [];
  var nums = arr.sort((a, b) => a - b);
  for (var i = 0; i < k; i++) {result.push(nums[i]);
  }

  return result;
};

[49] 字母异位词分组

/*
 * @lc app=leetcode.cn id=49 lang=javascript
 *
 * [49] 字母异位词分组
 */

// @lc code=start
/**
 * @param {string[]} strs
 * @return {string[][]}
 */

// 思路: 以排序后的 str 作为 key, values 为排序后为 key 的 str 集合.
var groupAnagrams = function (strs) {const map = new Map();

  for (var i = 0; i < strs.length; i++) {const sortedStr = strs[i].split('').sort().join();
    if (map.has(sortedStr)) {let temp = map.get(sortedStr);
      temp.push(strs[i]);
      map.set(sortedStr, temp);
    } else {map.set(sortedStr, [strs[i]]);
    }
  }

  return [...map.values()];
};
// @lc code=end

[94] 二叉树的中序遍历

/*
 * @lc app=leetcode.cn id=94 lang=javascript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function (root) {var stack = [];

  function helper(node) {if (!node) return;

    node.left && helper(node.left);
    stack.push(node.val);
    node.right && helper(node.right);
  }

  helper(root);

  return stack;
};
// @lc code=end

[242] 有效的字母异位词

/*
 * @lc app=leetcode.cn id=242 lang=javascript
 *
 * [242] 有效的字母异位词
 */

// @lc code=start
/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
// 方法 1:
var isAnagram = function (s, t) {return s.split('').sort().join('') == t.split('').sort().join('');
};

// 方法 2: Set
var isAnagram = function(s, t) {if(s.length !== t.length) return false;
  
  var ary = new Array(26).fill(0);

  for(var i = 0; i < s.length; i++) {ary[s[i].charCodeAt(0) - 97]++;
      ary[t[i].charCodeAt(0) - 97]--;
  }
  for(var i = 0; i < ary.length; i++) {if(ary[i] !== 0) return false;
  }
  return true
};
// @lc code=end

[347] 前 K 个高频元素

/*
 * @lc app=leetcode.cn id=347 lang=javascript
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */

// 解法: 优先队列，大顶堆
var topKFrequent = function (nums, k) {var map = new Map();
  var list = [];
  var result = [];

  for (var i = 0; i < nums.length; i++) {if (map.has(nums[i])) {let count = map.get(nums[i]);
      map.set(nums[i], count + 1);
    } else {map.set(nums[i], 1);
    }
  }

  for (let [key, value] of map.entries()) {list.push({ value, key});
  }

  // 降序排列
  list.sort((a, b) => b.value - a.value);

  for (let i = 0; i < k; i++) {result.push(parseInt(list[i].key, 10));
  }

  return result;
};
// @lc code=end

[429] N 叉树的层序遍历

/*
 * @lc app=leetcode.cn id=429 lang=javascript
 *
 * [429] N 叉树的层序遍历
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  var initialLevel = 0;
  var stack = [];

  if (!root) return [];
  helper(root, initialLevel);
  return stack;

  function helper(node, level) {if (stack.length === level) {stack.push([]);
    }
    stack[level].push(node.val);
    for (var i = 0; i < node.children.length; i++) {helper(node.children[i], level + 1);
    }
  }
};
// @lc code=end

[589] N 叉树的前序遍历

/*
 * @lc app=leetcode.cn id=589 lang=javascript
 *
 * [589] N 叉树的前序遍历
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var preorder = function (root) {var stack = [];
  if (!root) return [];
  helper(root, stack);
  return stack;

  function helper(node, stack) {if (!node) return;
    stack.push(node.val);
    for (var i = 0; i < node.children.length; i++) {helper(node.children[i], stack);
    }
  }
};
// @lc code=end

[590] N 叉树的后序遍历

/*
 * @lc app=leetcode.cn id=590 lang=javascript
 *
 * [590] N 叉树的后序遍历
 */

// @lc code=start
/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node} root
 * @return {number[]}
 */
var postorder = function (root) {var stack = [];
  if (!root) return [];
  helper(root, stack);
  return stack;

  function helper(node, stack) {if (!node) return;
    for (var i = 0; i < node.children.length; i++) {helper(node.children[i], stack);
    }
    stack.push(node.val);
  }
};
// @lc code=end