/*
* @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 + ')');
}
}
};
/*
* @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 个数
* @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;
};
/*
* @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
/*
* @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
/*
* @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
/*
* @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
/*
* @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
/*
* @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
/*
* @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